home *** CD-ROM | disk | FTP | other *** search
/ Programmer 7500 / MAX_PROGRAMMERS.iso / INFO / COMPRESS / LZ13.ARC / LZ.TXT next >
Encoding:
Text File  |  1988-10-20  |  4.5 KB  |  115 lines
  1. These programs are a file compressor and decompressor based on the 
  2. Limpel-Ziv algorithm.
  3.  
  4. The compression algorithm builds a string translation table that maps 
  5. substrings from the input stream into fixed-length codes.  These codes 
  6. are used by the decompression algorithm to rebuild the compressor's table 
  7. and reconstruct the original data stream.  In it's simplest form, the 
  8. algorithm can be stated as:
  9.     "If <w>k is in the table, then <w> is in the table."
  10.  
  11. The following comments were paraphrased from the VMS LZCOMP program 
  12. sources.  The algorithm is from the article "A Technique for High 
  13. Performance Data Compression" by Terry A. Welch which appeared in IEEE 
  14. Computer Volume 17, Number 6 (June 1984), pp 8-19.
  15.  
  16. Compress:
  17.     1) Initialize table to single character strings.
  18.     2) Read first character.  Set <w> (the prefix string) to that
  19.        character.
  20.     3) Read next character, k.
  21.     4) If at end of file, output code <w> and exit.
  22.     5) If <w>k is in the table, set <w> to <w>k; goto step 3.
  23.     6) Output code <w>.
  24.     7) Put <w>k into table.
  25.     8) Set <w> to k. Goto step 3.
  26.  
  27. <w> is a code which represents a string in the table.  When a new 
  28. character k is read in, the table is searched for <w>k.  If this 
  29. combination is found, <w> is set to the code for that combination and the 
  30. next character is read in.  Otherwise, this combination is added to the 
  31. table, the code <w> is written to the output stream and <w> is set to k.
  32.  
  33. The decompression algorithm builds an identical table by parsing each 
  34. received code into a prefix string and extension character.  The 
  35. extension character is pushed onto the stack and the prefix string 
  36. translated again until it is a single character.  This completes the 
  37. decompression.  The decompressed code is then output by popping the stack 
  38. and a new entry is made in the table.
  39.  
  40. The algorithm breaks when the input stream contains the sequence 
  41. k<w>k<w>k, where k<w> is already in the compressor's table.  This 
  42. sequence is handled in step 3 below.
  43.  
  44. Decompress:
  45.     1) Read first input code, assign to <w>, k, oldcode and
  46.        finchar.  Output k.
  47.     2) Read next code <w>, assign to incode.  If end of file, exit.
  48.     3) If <w> not in table (k<w>k<w>k case),
  49.        a) Push finchar onto stack.
  50.        b) Set <w> and incode to oldcode.
  51.     4) If <w> in table,
  52.        a) Push <w>.char onto stack.
  53.        b) Set <w> to <w>.code.
  54.        c) Goto step 4.
  55.     5) Set oldcode and finchar to <w>, output finchar.
  56.     6) While characters on stack pop stack and output character.
  57.     7) Add <oldcode>k to table.
  58.     8) Set oldcode to incode.
  59.     9) Goto step 2.
  60.  
  61. The algorithm used here has one additional feature.  The output codes are 
  62. variable length.  They start at nine bits.  Once the number of codes 
  63. exceeds the current code size, the number of bits in the code is 
  64. increased.  When the table is completely full, a clear code is 
  65. transmitted for the decompressor and the table is reinitialized.  This 
  66. program uses a maximum code size of 12 bits for a total of 4096 codes.
  67.  
  68. The decompressor realizes that the code size is changing when it's table 
  69. size reaches the maximum for the current code size.  At this point, the 
  70. code size is increased.  Remember that the decompressor's table is 
  71. identical to the compressor's table at any point in the original data 
  72. stream.
  73.  
  74. My sources of reference while implementing these programs were the 
  75. following:
  76.  
  77.     Bernie Eiben, DEC
  78.     Unix (tm) COMPRESS program sources
  79.     VMS LZCOMP/LZDCMP program sources (Martin Minow, DEC)
  80.     ARC file archiver sources (Thom Henderson, System Enhancement 
  81.        Associates)
  82.  
  83. Toad Hall Tweaks:
  84. LZCOMP2:
  85.     - Still prompts for input,output file names.
  86.     - Rewritten as a .COM file (tighter, faster).
  87.     - Output is identical to LZCOMP.ASM
  88. LZCOMP3:
  89.     - Takes input filename from command line (else uses StdIn).
  90.     - Outputs per DOS redirection (e.g., LZCOMP3 BOGUS.TXT >BOGUS.LZW)
  91.     - Won't work with "<BOGUS.TXT" input redirection or as a filter
  92.       (sigh...)
  93.     - Tighter and faster yet.
  94.  
  95. LZDCMP2,
  96. LZDCMP3:
  97.     - Same tweaks as equivalent LZCOMP files.
  98.  
  99. Kudos to the original author:
  100.     Tom Pfau
  101.     Digital Equipment Corporation
  102.     Parsippany, NJ
  103.  
  104. ... nice hack!  Sure beats the horrible C stuff I've only been able
  105. to find to date for any sort of file compression!
  106.  
  107. I'm now contemplating some comments I read in a recent ARC utility
  108. (GSARC) where the author expanded the number of code bits from 9..2
  109. to 3..13 (as I recall); and he doesn't discard the table on overflow.
  110. Does some tricky other stuff (not clear yet).
  111.  
  112. David Kirschbaum
  113. Toad Hall
  114. kirsch@braggvax.ARPA
  115.