The encoding follows the following algorithm: "To encode an integer N:
Find the largest Fibonacci number equal to or less than N; subtract this number from N, keeping track of the remainder. If the number subtracted was the ith Fibonacci number F(i), put a 1 in place i−2 in the code word (counting the left most digit as place 0). Repeat the previous steps, substituting the remainder for N, until a remainder of 0 is reached. Place an additional 1 after the rightmost digit in the code word. To decode a code word, remove the final "1", assign the remaining the values 1,2,3,5,8,13... (the Fibonacci numbers) to the bits in the code word, and sum the values of the "1" bits." see: https://en.wikipedia.org/wiki/Fibonacci_coding It might not be the most elegant or terse verb, but I think there is not much complexity in it. You are right that there is no need to use char sequence, could just use integer list, which may or may not be fast. I really did that for debugging purposes, to easily read the representation while encoding. On Friday, July 19, 2019, 1:13:18 AM GMT+9, Raul Miller <[email protected]> wrote: I'm not quite sure I understand your encoding scheme. Specifically, you're encoding into a sequence of characters, but when decoding, you're not using (8#2)#:a.i.y and it looks like you've cooked up some mechanism to compensate for how |."1#: behaves ... In other words, I think that the fibonacci encoding aspect isn't the problem here. So I think I would start with either a careful description of your "encode to character" mechanism (how can I know if you've implemented what you intended without that? I'd rather not try to reverse engineer your thoughts and assumptions if that's not necessary) or I would start with an implementation which isn't so complicated. Thanks, -- Raul 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 ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
