if 0 { MS While rereading Data Compression [L1 ], I stumbled on Fibonacci universal codes (see Section 3.3 [L2 ]).
Elias coding provides a different universal code for integers. The Elias codes are asymptotically better, but Fibonacci is better for "small" numbers (up to 514228, when compared to Elias-delta).
The coding rests on the observation that all positive numbers can be uniquely described by a sequence d(i) in {0, 1} such that
where F(i) is the i-th Fibonacci number. Note that (2) means that no two adjacent coefficients d(i) can be 1. By storing the coefficients in bits up to the last non-zero, and adding a final 1 we obtain an encoding such that two consecutive 1 indicate the end of a number and the start of the next.
The initial encodings are:
1 = F(1) 11 2 = F(2) 011 3 = F(3) 0011 4 = F(1)+F(3) 1011 5 = F(4) 00011 6 = F(1)+F(4) 10011 7 = F(2)+F(4) 01011 8 = F(5) 000011
...
16 = F(3)+F(7) 00100011
The algorithm to compute the Fibonacci encoding of a number is easiest to describe by the code below (proc fiboEncodeNum).
The code below implements procs to encode a list of positive integers as a bitstream, and to decode a bitstream as a list of positive numbers. Usage is
% fiboEncodeList {1 2 3 9 8 7}
11011001110001100001101011
% fiboDecodeStr 11011001110001100001101011
1 2 3 9 8 7}
#
# A memoizing generator for the Fibonacci numbers.
#
variable fiboList [list 1 1]
proc fibo n {
variable fiboList
set len [llength $fiboList]
if {$len > $n} {
return [lindex $fiboList $n]
}
set res [expr {[fibo [expr {$n-2}]] + [fibo [expr {$n-1}]]}]
lappend fiboList $res
return $res
}
#
# Computing the Fibonacci encoding of a number - see
# http://www.ics.uci.edu/~dan/pubs/DC-Sec3.html#Sec_3
# (memoizing)
#
variable fiboEncs
proc fiboEncodeNum n {
if {$n < 1} {
error "fiboEncode works on positive numbers"
}
variable fiboEncs
if {[info exists fiboEncs($n)]} {
return $fiboEncs($n)
}
upvar 0 fiboEncs($n) res
set res 1
# Find the first fibonacci number $f > $n
set f 1
for {set k 1} {$f <= $n} {} {
set f [fibo [incr k]]
}
while {[incr k -1]} {
set f [fibo $k]
if {$f <= $n} {
set res 1$res
incr n -$f
} else {
set res 0$res
}
}
return $res
}
proc fiboDecodeNum str {
set coeffs [split $str {}]
if {[lindex $coeffs end] != 1} {
error "Number badly encoded"
}
set n 0
set k 0
foreach c $coeffs {
incr k
if {$c} {
incr n [fibo $k]
}
}
set n
}
proc fiboEncodeList lst {
set res {}
foreach num $lst {
append res [fiboEncodeNum $num]
}
return $res
}
proc fiboDecodeString str {
set str [string map {11 "1 "} $str]
# Strip ending 0s (padding)
if {[string match 0* [lindex $str end]]} {
set str [lrange $str 0 end-1]
}
set res [list]
foreach s $str {
lappend res [fiboDecodeNum $s]
}
return $res
}