## Version 3 of Fibonacci coding

Updated 2004-09-04 14:37:16

MS While rereading Data Compression [L1 ], I stumbled on Fibonacci universal codes (see Section 3.3 [L2 ]).

Usage:

``` % fiboEncodeList {1 2 3 9 8 7}
11011001110001100001101011
% fiboDecodeStr 11011001110001100001101011
1 2 3 9 8 7```

The code:

``` #
# 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)
#
# Slight changes with respect to the reference in order
# to improve performance:
#   - the final 11 is replaced by an final 1, so that
#     split and join are easier to use to encode/decode
#     streams.
#

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 {}

# 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} {
}
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] 1
}
return \$res
}

proc fiboDecodeString str {
set str [string map {11 "1 "} \$str]
set res [list]
foreach s \$str {
lappend res [fiboDecodeNum \$s]
}
return \$res
}```