[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]). 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} { 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] 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 }