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<natrune  n)))
      (terpri) (loop  for n from 0 below 32 do (format t "~3d" n))
      )

  a  b  c  d  e  f  g  h  i  j  k  l  m  n  o  p  q  r  s  t  u  v  w  x  y  z     '  .  ?  !  ,
  0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31

[3] (setq codes (append '(rune<natrune  fivebit<natnum) +codes+ ))
(RUNE<NATRUNE FIVEBIT<NATNUM GUN<NATNUM BLIP<NATNUM GUNBLIP<NATNUM ELIAS<NATNUM)

[4] (compare-codes 7 :codes codes)

    RUNE<NATRUNE(7) = h
 FIVEBIT<NATNUM(7) = 00111
     GUN<NATNUM(7) = 00000001
    BLIP<NATNUM(7) = 000
 GUNBLIP<NATNUM(7) = 0001000
   ELIAS<NATNUM(7) = 00100000

[5] (compare-codes 27 :codes codes)

    RUNE<NATRUNE(27) = '
 FIVEBIT<NATNUM(27) = 11011
     GUN<NATNUM(27) = 0000000000000000000000000001
    BLIP<NATNUM(27) = 1100
 GUNBLIP<NATNUM(27) = 000011100
   ELIAS<NATNUM(27) = 001011100

[6] (compare-codes 32 :codes codes)

*** - JK: Natnum 32 is not in our RUNE code-set.


================================================================
[12] (setq codes '(BINARY<NATNUM GUN<NATNUM BLIP<NATNUM GUNBLIP<NATNUM ELIAS<NATNUM))

 ^ JK: We discarded RUNE<NATRUNE and FIVEBIT<NATNUM, since those only 
       encode natnums in {0,1,...,31}.


[13] (compare-codes 32 :codes codes)

  BINARY<NATNUM(32) = 100000
     GUN<NATNUM(32) = 000000000000000000000000000000001
    BLIP<NATNUM(32) = 00001
 GUNBLIP<NATNUM(32) = 00000100001
   ELIAS<NATNUM(32) = 0011000001

[14] (compare-codes 53 :codes codes)

  BINARY<NATNUM(53) = 110101
     GUN<NATNUM(53) = 000000000000000000000000000000000000000000000000000001
    BLIP<NATNUM(53) = 10110
 GUNBLIP<NATNUM(53) = 00000110110
   ELIAS<NATNUM(53) = 0011010110

================================================================
[15] (setq codes '(BINARY<NATNUM BLIP<NATNUM GUNBLIP<NATNUM ELIAS<NATNUM))

 ^ JK: Now we've discarded GUN<NATNUM since, when I get to large
       numbers, below, the print-out would be huge.

[16] (compare-codes 53 :codes codes)

  BINARY<NATNUM(53) = 110101
    BLIP<NATNUM(53) = 10110
 GUNBLIP<NATNUM(53) = 00000110110
   ELIAS<NATNUM(53) = 0011010110

[17] (compare-codes 530 :codes codes)

  BINARY<NATNUM(530) = 1000010010
    BLIP<NATNUM(530) = 000010011
 GUNBLIP<NATNUM(530) = 0000000001000010011
   ELIAS<NATNUM(530) = 0001010000010011

[18] (compare-codes 930 :codes codes)

  BINARY<NATNUM(930) = 1110100010
    BLIP<NATNUM(930) = 110100011
 GUNBLIP<NATNUM(930) = 0000000001110100011
   ELIAS<NATNUM(930) = 0001010110100011

[19] (compare-codes 9300 :codes codes)

  BINARY<NATNUM(9300) = 10010001010100
    BLIP<NATNUM(9300) = 0010001010101
 GUNBLIP<NATNUM(9300) = 000000000000010010001010101
   ELIAS<NATNUM(9300) = 00011100010001010101

[20] (setq codes '(FIVEBIT<NATNUM BLIP<NATNUM ELIAS<NATNUM))

[21] (compare-codes 9300 :codes codes)

  BINARY<NATNUM(9300) = 10010001010100
    BLIP<NATNUM(9300) = 0010001010101
   ELIAS<NATNUM(9300) = 00011100010001010101

[22] (setq  big (+ 37 (* 1001 1017)))           
;; Equals 1018054


[25] (compare-codes big :codes codes)

  BINARY<NATNUM(1018054) = 11111000100011000110
    BLIP<NATNUM(1018054) = 1111000100011000111
 GUNBLIP<NATNUM(1018054) = 000000000000000000011111000100011000111
   ELIAS<NATNUM(1018054) = 0000101001111000100011000111

[26] (compare-codes (+ 36 (* big big)) :codes codes)

  BINARY<NATNUM(1036433946952) = 1111000101010000010001101111100101001000
    BLIP<NATNUM(1036433946952) = 111000101010000010001101111100101001001
 GUNBLIP<NATNUM(1036433946952) = 0000000000000000000000000000000000000001111000101010000010001101111100101001001
   ELIAS<NATNUM(1036433946952) = 00000101000111000101010000010001101111100101001001

[62] (loop for n from 0 below 28
       do (format t "~%~3D: ~12S  ~12S" n (gunblip<natnum n :lstp t)(elias<natnum n :lstp t))
       )

  n: GunBlip            Elias=GunBlipBlip                n: GunBlip       Elias=GunBlipBlip
  0: ("1" "")           ("1" "" "")                      0: "1"           "1"
  1: ("01" "0")         ("01" "0" "0")                   1: "010"         "0100"
  2: ("01" "1")         ("01" "0" "1")                   2: "011"         "0101"
  3: ("001" "00")       ("01" "1" "00")                  3: "00100"       "01100"
  4: ("001" "01")       ("01" "1" "01")                  4: "00101"       "01101"
  5: ("001" "10")       ("01" "1" "10")                  5: "00110"       "01110"
  6: ("001" "11")       ("01" "1" "11")                  6: "00111"       "01111"
  7: ("0001" "000")     ("001" "00" "000")               7: "0001000"     "00100000"
  8: ("0001" "001")     ("001" "00" "001")               8: "0001001"     "00100001"
  9: ("0001" "010")     ("001" "00" "010")               9: "0001010"     "00100010"
 10: ("0001" "011")     ("001" "00" "011")              10: "0001011"     "00100011"
 11: ("0001" "100")     ("001" "00" "100")              11: "0001100"     "00100100"
 12: ("0001" "101")     ("001" "00" "101")              12: "0001101"     "00100101"
 13: ("0001" "110")     ("001" "00" "110")              13: "0001110"     "00100110"
 14: ("0001" "111")     ("001" "00" "111")              14: "0001111"     "00100111"
 15: ("00001" "0000")   ("001" "01" "0000")             15: "000010000"   "001010000"
 16: ("00001" "0001")   ("001" "01" "0001")             16: "000010001"   "001010001"
 17: ("00001" "0010")   ("001" "01" "0010")             17: "000010010"   "001010010"
 18: ("00001" "0011")   ("001" "01" "0011")             18: "000010011"   "001010011"
 19: ("00001" "0100")   ("001" "01" "0100")             19: "000010100"   "001010100"
 20: ("00001" "0101")   ("001" "01" "0101")             20: "000010101"   "001010101"
 21: ("00001" "0110")   ("001" "01" "0110")             21: "000010110"   "001010110"
 22: ("00001" "0111")   ("001" "01" "0111")             22: "000010111"   "001010111"
 23: ("00001" "1000")   ("001" "01" "1000")             23: "000011000"   "001011000"
 24: ("00001" "1001")   ("001" "01" "1001")             24: "000011001"   "001011001"
 25: ("00001" "1010")   ("001" "01" "1010")             25: "000011010"   "001011010"
 26: ("00001" "1011")   ("001" "01" "1011")             26: "000011011"   "001011011"
 27: ("00001" "1100")   ("001" "01" "1100")             27: "000011100"   "001011100"


[56] (progn (setq n (+ (expt 2 15) 37) bits (elias<natnum n)) (format nil "~10D: len(n)=~4D of ~A" n (length bits) bits))
"     32805: len(n)=  24 of 000010000000000000100110"

[57] (progn (setq n (+ (expt 2 35) 37) bits (elias<natnum n)) (format nil "~10D: len(n)=~4D of ~A" n (length bits) bits))
"34359738405: len(n)=  46 of 0000010010000000000000000000000000000000100110"

[58] (progn (setq n (+ (expt 2 55) 37) bits (elias<natnum n)) (format nil "~10D: len(n)=~4D of ~A" n (length bits) bits))
"36028797018964005: len(n)=  66 of 000001110000000000000000000000000000000000000000000000000000100110"

[59]  (progn (setq n (+ (expt 2 155) 37) bits (elias<natnum n)) (format nil "~10D: len(n)=~4D of ~A" n (length bits) bits))
"45671926166590716193865151022383844364247892005: len(n)= 170 of 00000001001110000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000100110"

================================================================
Below, I'll sometimes use "a" as a synonym for the bit "1" [but 
not the number 1], and use "b" as a synonym for the bit "0" [but 
not for the number 0].
  
[Actually, for pedegogical purposes, I allow in the source-string: Any digit, or any
 letter.  The mapping to bits that I use is:

           CHARACTER            :-> 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"

================================================================