NB: What I'm calling the "Elias code", shown below, is ALMOST the "Elias delta code" (not to be confused with the "Elias gamma code" nor the "Elias omega code") as shown in Wikipedia: http://en.wikipedia.org/wiki/Elias_delta_coding --BUT it is shifted by 1. So I call it "Gun-blip-blip". The "Gun" is in reference to gunslingers supposedly cutting a notch in the barrel of their gun, for each man they shot. By the way, some textbooks incorrectly call this a radix numeral-system which is "unary". Actually, it is not a radix system. Below, are some codes we'll be using. We'll use our Gun-blip-blip (Elias code) as a component of (a simplified version of) the Lempel-Ziv compression algorithm. ================================================================ i i i i i i i ooooo o ooooooo ooooo ooooo I I I I I I I 8 8 8 8 8 o 8 8 I \ `+' / I 8 8 8 8 8 8 \ `-+-' / 8 8 8 ooooo 8oooo `-__|__-' 8 8 8 8 8 | 8 o 8 8 o 8 8 ------+------ ooooo 8oooooo ooo8ooo ooooo 8 ... Copyright (c) Sam Steingold, Bruno Haible 2001-2006 [1]> ;; Loading file /home/math0/squash/Top/Lisp/NT/cipher.lsp ... [2] (progn (format t "~% ") (loop for n from 0 below 32 do (format t "~3a" (rune BIT 0 2 ... 8 B D F ... Z |-> 0 1 3 ... 9 A C E Y |-> 1 ] ================ For the following, the starting dictionary is: IDX | WORD ---------- 0 | [null-word] 1 | a [The one-bit-word "1"] 2 | b [The one-bit-word "0"] [194] (enziv "abaababaaaabbbb" :emitidx t :lstp t) ("<1>b" "<1>a" "<2>a" "<5>a" "<4>b" "<2>b" "<0><2>") [195] (enziv "abaababaaaabbbb" :emitidx t) "<1>b<1>a<2>a<5>a<4>b<2>b<0><2>" [196] (enziv "abaababaaaabbbb" :emitidx nil :lstp t) ("0100b" "0100a" "0101a" "01110a" "01101b" "0101b" "10101") [197] (enziv "abaababaaaabbbb" :emitidx nil) "0100b0100a0101a01110a01101b0101b10101" [198] (enziv "abaababaaaabbbb" :emitidx nil :lstp t :emitletter t) ("01000" "01001" "01011" "011101" "011010" "01010" "10101") [199] (enziv "abaababaaaabbbb" :emitletter t) "0100001001010110111010110100101010101" [200] (enziv "101101011110000" ) "0100001001010110111010110100101010101" ================================================================