Version 12 of Fibonacci coding

Updated 2004-09-05 23:15:53

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).

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