home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #30 / NN_1992_30.iso / spool / comp / os / msdos / programm / 11361 < prev    next >
Encoding:
Text File  |  1992-12-13  |  4.4 KB  |  132 lines
  1. Newsgroups: comp.os.msdos.programmer
  2. Path: sparky!uunet!caen!batcomputer!theory.TC.Cornell.EDU!homer
  3. From: homer@theory.TC.Cornell.EDU (Homer Smith)
  4. Subject: HASHING AND LZW COMPRESSION
  5. Message-ID: <1992Dec13.182946.5344@tc.cornell.edu>
  6. Sender: news@tc.cornell.edu
  7. Nntp-Posting-Host: theory.tc.cornell.edu
  8. Organization: Cornell Theory Center
  9. Date: Sun, 13 Dec 1992 18:29:46 GMT
  10. Lines: 120
  11.  
  12.  
  13.      This is long, please bomb out of it when ever it gets boring.
  14.  
  15.      Could someone enlighten me as to what is HASHING?
  16.  
  17.      It arises as an algorithm to search a table of numbers for
  18. the existence of a particular entry.
  19.  
  20.      For example if you have a N by 2 table of random entries of the form
  21.  
  22.      259 4
  23.      34  34
  24.      245 123
  25.      259 4
  26.  
  27.  
  28.   what is the absolutely fastest way to determine if any other random
  29. pair of numbers is already in the table and its position.
  30.  
  31.      The problem arises in LZW compression where in you build
  32. a table of strings of characters. 
  33.  
  34.       For example
  35.  
  36.       DC
  37.       DCB
  38.       DCBE
  39.       DCBEA  ETC.
  40.  
  41.       This example is highly simplified.  The nature of these
  42. LZW tables is that each string that is in the table
  43. consists of a PRIOR string that is also in the table plus one
  44. more character.   The ordering however can be very random and complex.
  45.  
  46.      Thus such an LZW table can be expressed as a two column table
  47. where each entry consists of the index of the prior string and the
  48. one more character.
  49.  
  50. INDEX  STRING
  51.    1    A
  52.    2    B
  53.    3    C
  54.    4    D
  55.    5    E 
  56.    .    .  
  57.  259    DC           4  3
  58.  260    DCB    --> 259  2
  59.  261    DCBA       260  1
  60.  262    DCBAE      261  5  
  61.  
  62.      Thus if one has an arbitrary string such as DCB, and one has ALREADY
  63. found it in the table at position 260, one then gets the next character in the
  64. material to be coded, say F, and now one needs to know if DCBF is
  65. already in the table.  If it is, one goes on to the next character.
  66. If not, one adds the new string DCBF to the table.
  67.  
  68.      DCBF is clearly 260 6, so the problem becomes searching through
  69. the two column table for the entry 260 6.
  70.  
  71.      LZW tables can be relatively long, usually up to 4096 entries.
  72. The right hand column needs only be a byte wide, but the left
  73. hand column, being an index into previous entries in the table
  74. needs to span 4096 or at least two bytes.
  75.  
  76.      Thus the tables do not take up a terrible amount of space, but
  77. the searching through them can take forever, especially 
  78. if you proceed with a straight forward linear search from the
  79. beginning to the end of the table.
  80.  
  81.      Obviously you only check the right column if you have found
  82. a match in the left column.
  83.  
  84.      But remember this has to be done over and over again for each
  85. character in the input stream to be compressed.
  86.  
  87.      For a simple 1200 by 800 fractal, the algorithm can take upwards
  88. of 8 minutes on a 486/33 pc, which is ridiculous.
  89.  
  90.      One solution to this does away with the table searching
  91. completely.
  92.  
  93.      This is done by recognizing that each ordered pair of numbers
  94. such as (261,23) is a multiple base number, the right column
  95. is in base 256 and the left hand column is in base 4096.
  96.  
  97.      Thus (261,23) can be expressed as a unique number of the form
  98.  
  99.      261*256 + 23 = 66839.
  100.  
  101.      The total span of ordered pairs from (0,0) to (4095,255) thus
  102. spans 0 to 4095*256 + 255 or 1048575.
  103.  
  104.      Thus rather than adding a new ordered pair (A,B) to the end
  105. of a simple 2 column table, one places it directly into position
  106. A*256 + B in the longer array.  Actually what one stores there
  107. is the INDEX of the position that the ordered pair would have occupied
  108. in a normal table.
  109.  
  110.      The longer array should intially be set to to -1's.
  111.  
  112.      Thus when you wish to know if any ordered pair is in the table,
  113. you merely compute A*256 + B and see if anything is in the longer array.
  114. If it is, then that entry is already 'in the table' at the 
  115. implied index position specified by the number found in the longer array.
  116.  
  117.      The brilliance of this is that LZW compression becomes very fast,
  118. the 8 minute example mentioned above reduces down to 38 seconds,
  119. as there is no table searching whatsoever.
  120.  
  121.      The catch is that it takes over 2 Meg of memory to store the
  122. longer array, space that most people can ill afford.
  123.  
  124.      The original two columned table only takes 12,288 bytes, 2 bytes
  125. for the left column and 1 for the right column, times 4096.
  126.  
  127.      I would appreciate any enlightening on this subject that you
  128. can throw my way.
  129.  
  130.      Homer
  131.  
  132.