🚀 go-pugleaf

     This is long, please bomb out of it when ever it gets boring.

     Could someone enlighten me as to what is HASHING?
 
     It arises as an algorithm to search a table of numbers for
the existence of a particular entry.
 
     For example if you have a N by 2 table of random entries of the form
 
     259 4
     34  34
     245 123
     259 4


  what is the absolutely fastest way to determine if any other random
pair of numbers is already in the table and its position.

     The problem arises in LZW compression where in you build
a table of strings of characters. 
 
      For example
 
      DC
      DCB
      DCBE
      DCBEA  ETC.
 
      This example is highly simplified.  The nature of these
LZW tables is that each string that is in the table
consists of a PRIOR string that is also in the table plus one
more character.   The ordering however can be very random and complex.
 
     Thus such an LZW table can be expressed as a two column table
where each entry consists of the index of the prior string and the
one more character.
 
INDEX  STRING
   1    A
   2    B
   3    C
   4    D
   5    E 
   .    .  
 259    DC           4  3
 260    DCB    --> 259  2
 261    DCBA       260  1
 262    DCBAE      261  5  

     Thus if one has an arbitrary string such as DCB, and one has ALREADY
found it in the table at position 260, one then gets the next character in the
material to be coded, say F, and now one needs to know if DCBF is
already in the table.  If it is, one goes on to the next character.
If not, one adds the new string DCBF to the table.
 
     DCBF is clearly 260 6, so the problem becomes searching through
the two column table for the entry 260 6.
 
     LZW tables can be relatively long, usually up to 4096 entries.
The right hand column needs only be a byte wide, but the left
hand column, being an index into previous entries in the table
needs to span 4096 or at least two bytes.
 
     Thus the tables do not take up a terrible amount of space, but
the searching through them can take forever, especially 
if you proceed with a straight forward linear search from the
beginning to the end of the table.
 
     Obviously you only check the right column if you have found
a match in the left column.

     But remember this has to be done over and over again for each
character in the input stream to be compressed.
 
     For a simple 1200 by 800 fractal, the algorithm can take upwards
of 8 minutes on a 486/33 pc, which is ridiculous.

     One solution to this does away with the table searching
completely.
 
     This is done by recognizing that each ordered pair of numbers
such as (261,23) is a multiple base number, the right column
is in base 256 and the left hand column is in base 4096.
 
     Thus (261,23) can be expressed as a unique number of the form
 
     261*256 + 23 = 66839.
 
     The total span of ordered pairs from (0,0) to (4095,255) thus
spans 0 to 4095*256 + 255 or 1048575.
 
     Thus rather than adding a new ordered pair (A,B) to the end
of a simple 2 column table, one places it directly into position
A*256 + B in the longer array.  Actually what one stores there
is the INDEX of the position that the ordered pair would have occupied
in a normal table.
 
     The longer array should intially be set to to -1's.

     Thus when you wish to know if any ordered pair is in the table,
you merely compute A*256 + B and see if anything is in the longer array.
If it is, then that entry is already 'in the table' at the 
implied index position specified by the number found in the longer array.
 
     The brilliance of this is that LZW compression becomes very fast,
the 8 minute example mentioned above reduces down to 38 seconds,
as there is no table searching whatsoever.

     The catch is that it takes over 2 Meg of memory to store the
longer array, space that most people can ill afford.

     The original two columned table only takes 12,288 bytes, 2 bytes
for the left column and 1 for the right column, times 4096.

     I would appreciate any enlightening on this subject that you
can throw my way.
 
     Homer