home *** CD-ROM | disk | FTP | other *** search
/ Oakland CPM Archive / oakcpm.iso / cpm / squsq / crunch.abs < prev    next >
Encoding:
Text File  |  1986-12-05  |  3.8 KB  |  74 lines
  1.                        Technical Abstract
  2.  
  3. CRUNCH 1.x maintained a table representing up to 4096 strings  of
  4. varying lengths using the so called LZW algorithm, which has been
  5. described in the earlier documentation.  These strings were  ent-
  6. ered into a table in a manner where the strings content was  used
  7. to  determine the physical location (hashing), and that  location
  8. was used as the output code.  Hash "collisions" were resolved  by
  9. maintaining another 12 bits of data per entry which was a "link",
  10. or pointer to another entry.
  11.  
  12. In contrast, CRUNCH 2.x uses an "open-addressing, double hashing"
  13. method similar to that employed in the UNIX COMPRESS.  This meth-
  14. od  involves a table of length 5003, where only 4096 entries  are
  15. ever made, insuring the table never gets much more than about 80%
  16. full.  When a hash collision occurs, a secondary hash function is
  17. used to check a series of additional entries until an empty entry
  18. is  encountered.   This method creates a table filled  with  many
  19. criss-crossed "virtual" chains, without the use of a "link" entry
  20. in the table.
  21.  
  22. One reason this is important is that [without using any addition-
  23. al  memory] the 1 1/2 bytes which were previously allocated as  a
  24. link can now become the [output] code number.  This enables us to
  25. assign  code  numbers, which are kept right alongside  the  entry
  26. itself,  independently  of the entry's physical  location.   This
  27. allows  the codes to be assigned in order, permitting the use  of
  28. 9-bit  representations  until there are 512 codes in  the  table,
  29. after which 10 bit representations are output, etc.
  30.  
  31. The  variable bit length method has three ramifications.   It  is
  32. particularly  helpful when encoding very short files,  where  the
  33. table  never even fills up.  It also provides a fixed  additional
  34. savings  (not  insubstantial) even when the table does  fill  up.
  35. Thirdly,  it  reduces the overhead associated with  an  "adaptive
  36. reset"  to the point where it becomes a very viable  alternative.
  37. "Adaptive  reset" simply means throwing out the whole  table  and
  38. starting over.  This can be quite advantageous when used  proper-
  39. ly.  CRUNCH v2.x employs this provision, which was not  incorpor-
  40. ated in the V1.x algorithm.
  41.  
  42. "Code  reassignment" is an advancement I introduced with the  re-
  43. lease  of CRUNCH v2.0 based on original work.  It is not used  in
  44. COMPRESS,  any  MS-DOS ARC program, or [to the best of  my  know-
  45. ledge]  any other data compression utility  currently  available.
  46. There are many ways one might go about this (and at least as many
  47. possible pitfalls).  The algorithm I selected seemed to represent
  48. a good tradeoff between speed, memory used, and improved  perfor-
  49. mance, while maintaining "soundness of algorithm" (ie it works).
  50.  
  51.  
  52. Briefly,  it works as follows: Once the table fills up, the  code
  53. reassignment process begins. (At this same time, the  possibility
  54. of  adaptive reset is also enabled).  Whenever a new  code  would
  55. otherwise be made (if the table weren't full), the entries  along
  56. the  hash  chain  which  would normally  contain  the  entry  are
  57. scanned.  The first, if any, of those entries which was made  but
  58. never  subsequently referenced is bumped in favor of the new  en-
  59. try.   The uncruncher, which would not normally need  to  perform
  60. any  hash  type function, has an auxiliary  physical  to  logical
  61. translation table, where it simulates the hashing going on in the
  62. cruncher.   In this fashion it is able to exactly  reproduce  the
  63. reassignments made my the cruncher, which is essential.
  64.  
  65. ---
  66.  
  67. I  hope to write an article soon on "Recent Advancements in  Data
  68. Compression".  It would cover the recent history generally, along
  69. with a more detailed description of some of the algorithms, and a
  70. series of additional ideas for future enhancement.
  71.  
  72.                                               Steven Greenberg
  73.                                               16 November 1986
  74.