if 0 { [MS] While rereading ''' Data Compression''' [http://www.ics.uci.edu/~dan/pubs/DataCompression.html], I stumbled on Fibonacci universal codes (see Section 3.3 [http://www.ics.uci.edu/~dan/pubs/DC-Sec3.html#Sec_3.3]). [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). These universal codes can be used to encode a sequence of positive integers as a compact bitstream. The encoding is very efficient if smaller numbers are more frequent than larger ones. ---- The coding rests on the observation that all positive numbers can be uniquely described by a sequence d(i) in {0, 1} such that 1. N = Sum(i=0...k, d(i)*F(i) 2. d(i)==1 => d(i+1)=0 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" } upvar 0 fiboEncs(\$n) res if {[info exists res]} { return \$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 { # # NOTE: the final 1 must have been stripped # already. # 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 { # Strip ending 0s (padding) set str [string trimright \$str 0] set str [string map {11 "1 "} \$str] set res [list] foreach s \$str { lappend res [fiboDecodeNum \$s] } return \$res } if 0 { To illustrate the efficiency compared to the [Elias coding] for small numbers, consider: % foreach i {1 2 4 8 16 32 64 128 256 512 1024 2048 4096} { puts " \$i: [string length [Elias'gamma \$i]] \ [string length [Elias'delta \$i]] \ [string length [fiboEncodeNum \$i]]" } 1: 1 1 2 2: 3 4 3 4: 5 5 4 8: 7 8 6 16: 9 9 7 32: 11 10 8 64: 13 11 10 128: 15 14 11 256: 17 15 13 512: 19 16 14 1024: 21 17 16 2048: 23 18 17 4096: 25 19 18 ... but note that Elias'gamma can beat Fibonacci also for lists of small numbers, if they have a large frequency of ones and threes: 1: 1 1 2 2: 3 4 3 3: 3 4 4 } ---- [Category Mathematics]