home *** CD-ROM | disk | FTP | other *** search
/ QBasic & Borland Pascal & C / Delphi5.iso / C / Samples / COMPRESS.ARJ / LZW / LZW.DOC < prev    next >
Encoding:
Text File  |  1985-08-20  |  3.5 KB  |  128 lines
  1.  
  2.  
  3.  
  4.         V 2.0 lzwcom.exe and lzwunc.exe                             
  5.  
  6.  
  7.  
  8.                                 Description
  9.  
  10.  
  11.  
  12.  
  13.         This  is  a  new  version of my file compressor/uncompressor
  14.         based on the  lempel-zev  data  compression  algorithm.   An
  15.         earlier version is on the Computer Language BBS.
  16.         
  17.         lempel-zev data compression builds a table of strings on the
  18.         fly during compression, where each string has the property
  19.  
  20.                 If  <string><char>  is in the table then 
  21.                         <string>  is also in the table.
  22.  
  23.         The compressed file consists, therefore, of the indexes into
  24.         the  string  table,  rather  than  the  strings  themselves,
  25.         resulting in very good compression rates.
  26.         
  27.         Decompression builds the same table from the input data that
  28.         the compressor built during compression.  There is  no  data
  29.         table  transmitted  first,  as  with  Huffman encoding.  The
  30.         algorithm is (I hope) fairly clear in the source code.
  31.         
  32.         Compression rates vary according to data, but are  generally
  33.         better  than Huffman encoding.  For example, COMPRESS.LBR is
  34.         31K, but the same library after all files are compressed  is
  35.         only 21K.
  36.         
  37.         Note  well,  however,  that  the algorithm stops adapting to
  38.         input data once the table is filled.  If the nature  of  the
  39.         data  changes  after  the table is filled, compression rates
  40.         will suffer.  When  I  compressed  the  whole  COMPRESS.LBR,
  41.         rather  than  each file within it, it came out to 26K.  This
  42.         is because it 'adapted' to the data at the head of  the  LBR
  43.         file  which  was   C source code, and then tried to compress
  44.         the EXE files, that contain entirely different data.
  45.         
  46.  
  47.  
  48.  
  49.  
  50.  
  51.  
  52.  
  53.  
  54.  
  55.  
  56.  
  57.  
  58.  
  59.  
  60.  
  61.  
  62.  
  63.                                     -1-                             
  64.  
  65.  
  66.  
  67.         V 2.0 lzwcom.exe and lzwunc.exe                             
  68.  
  69.  
  70.  
  71.                             Implementation Notes
  72.  
  73.  
  74.  
  75.  
  76.         For this  version,  I  started  embedding  crc-16's  in  the
  77.         compressed   files  every  1K,  and  checking  them  when  I
  78.         uncompress.  2 characters per 1K  overhead  seemed  a  small
  79.         price  to pay for data integrity, and it didn't seem to slow
  80.         things down any.
  81.         
  82.         These programs were compiled w/MANX Aztec C86 - they  should
  83.         be  portable across their entire compiler family.  They will
  84.         also compile under Xenix 286 without change -  and  probably
  85.         any other unix system.  If you go to Unix, you might want to
  86.         play  some  games  with  file permissions, etc., so they get
  87.         preserved across compression/uncompression.
  88.         
  89.         Beware of compiling with Lattice - I use regular  FILEs  and
  90.         getc  and  putc  for  I/O, and Lattice has some non-portable
  91.         open modes that must be dealt with.  If you use "rb" instead
  92.         of "r" for the input file and "wb" instead of "w".
  93.         
  94.         any questions or comments to
  95.         Kent Williams
  96.         NORAND Inc.
  97.         550 2nd St. S.E.
  98.         Cedar Rapids, IA 52401
  99.         (319) 369-3131 (work) (319) 338-6053 (home)
  100.         
  101.  
  102.  
  103.  
  104.  
  105.  
  106.  
  107.  
  108.  
  109.  
  110.  
  111.  
  112.  
  113.  
  114.  
  115.  
  116.  
  117.  
  118.  
  119.  
  120.  
  121.  
  122.  
  123.  
  124.  
  125.  
  126.                                     -2-                             
  127.  
  128.