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
