You mention the possibility of 1 1 1 appearing in an encode result and that making decode awkward without a loop. My guess is that that can happen if you encode multiple numbers into a single result where two adjacent encodings produce the 1 1 1. Is that right?
Anyhow, could you produce a workaround using `test` as below in your decode verb to construct a sort of run length list to break up the 1 1 1 groups and then use Henry's idea in http://www.jsoftware.com/pipermail/programming/2019-July/053594.html to extract the pieces? test =. I. 1 1 1 E. i =. , {:|."1 (8 # 2) ,:|."1 #: a.i. y On Thu, Jul 18, 2019 at 10:46 AM 'Jon Hough' via Programming < [email protected]> wrote: > Positive integers can be encoded using Fibonacci numbers. > For the sake of easer, assume Fibonacci numbers are 1,2,3,5,... (only one > 1). > We can encode a positive integer uniquely using non-consecutive Fibonacci > numbers. For example > > 4 = 1 + 3 (note: 1 and 3 a re non-consecutive) > 5 = 5 (already a Fib number) > 6 = 1 + 5 > 7 = 2 + 5 > 8 = 8 > > These representation can be encoded using bits. 1's where a Fibonacci > number is in the representation, 0s when not. > 4 = 1 + 3 = 101 > 5 = 0001 > 6 = 1001 > 7 = 0101 > 8 = 00001 > ... > > We can append a 1 on the end of the encoding a a delimiter, so that during > decoding we know easily where to stop. This way integers can be packed > together. > > Here are some J verbs for encoding and decoding positive integers. > > > NB. =================================================================== > genfibs=: 3 : 0 > r=. 1 2 > i1=. 1 > i2=. 2 > c=. 2 > while. y > c=. c+1 do. > t=. i1 + i2 > i1=. i2 > i2=. t > r=. r, x: t > end. > ) > > > Fibs=: genfibs 1400 > > encode=: 3 : 0 > d=. > (>@:,&:>)/ (<@encode1)"0 y > r=. d,'0' #~ (#d) -~ 8 * >. 8 %~ # d > pack r > ) > > encode1=: 3 : 0 > n=. x: y > r=. '' > k=: '' > fl=. x: Fibs{~ I. Fibs <: y > i=. <:#fl > while. n do. > r=. r,'1' > n=. n- i{fl > k=: k,i{fl > i=. i-1 > while. (i >: 0) *. (n<i{fl) do. > r=. r,'0' > i=. i-1 > end. > end. > (|.r),'1' > ) > > > > pack=: 3 : 0 > a.{~ #. _8 ] \"."0 y > ) > > decode=: 3 : 0 > i=. , {:|."1 (8 # 2) ,:|."1 #: a.i. y > n=. '' > while. 1 e. 1 1 E. i do. > idx=. {. I. 1 1 E. i > n=. n, +/ Fibs {~ I. i {~ i. >: idx > i=. (2+idx) }. i > end. > n > ) > > NB. =================================================================== > > The encode verb outputs the Fib-representation as bytes. > encode 4 > � > > #: a.i. encode 4 > 1 0 1 1 0 0 0 0 > > > decode encode 449239438124834384923493383837734733747181x > 449239438124834384923493383837734733747181 > > > decode encode 1 2 3 4 5 6 7 > 1 2 3 4 5 6 7 > > Fibonacci encoding is not really a good compression encoding, but has some > good error handling properties. > I am not happy with the decode verb, as I wanted to write it without a > while loop. Difficult though as there are some > awkaward consecutive bits that might appear in the encoding, e.g. > ...0 1 1 1 0... > Using 1 1 E. with this breaks decoding unless done carefully. Easier just > to use a while loop and eat the input every iteration. > > refs: https://en.wikipedia.org/wiki/Fibonacci_coding > https://en.wikipedia.org/wiki/Zeckendorf%27s_theorem > ---------------------------------------------------------------------- > For information about J forums see http://www.jsoftware.com/forums.htm > -- (B=) <-----my sig Brian Schott ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
