Fibonacci coding

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

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

N = Sum(i=0...k, d(i)*F(i)
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)                0010011   ([OPi] June 5, 2005 - 00100011 was incorrect)

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
 }

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