home *** CD-ROM | disk | FTP | other *** search
/ CD Actual 15 / CDACTUAL15.iso / cdactual / program / pascal / LZRW.ZIP / LZRW3.TXT < prev    next >
Encoding:
Text File  |  1992-01-19  |  6.5 KB  |  131 lines
  1. NOTES ON THE LZRW3 ALGORITHM
  2. ============================
  3. Author : Ross Williams.
  4. Date   : 30-Jun-1991.
  5.  
  6. Abstract
  7. --------
  8. This file announces the release of my LZRW3 algorithm which was
  9. invented on 31-Dec-1990. The LZRW3 algorithm is a descendant of the
  10. LZRW1-A and LZRW2 algorithms. LZRW3 runs a little more slowly than
  11. LZRW1-A and LZRW2, but yields better compression. LZRW3 is a
  12. deterministic algorithm. LZRW3 is not patented and is of the LZ77
  13. class and so is unlikely to be subject to a patent challenge. The
  14. exact figures for the Calgary corpus on C implementations on my
  15. Macintosh-SE are (percentage remaining, compression speed,
  16. decompression speed, memory required during compression and
  17. decompression):
  18.  
  19.            PerRem    ComK/S    DecK/S     ComMem    DecMem
  20. LZRW1-A     55.1 %   17 K/s     69 K/s      16 K       0 K
  21. LZRW2       51.5 %   18 K/s     54 K/s      24 K      16 K
  22. LZRW3       50.0 %   20 K/s     33 K/s      16 K      16 K
  23.  
  24. LZRW3 has been written and released mainly to demonstrate the idea of
  25. transmitting hash table indexes directly and to round off the triple
  26. of algorithms I developed in 1989/1990. LZRW3 may also be useful to
  27. those who are unhappy with LZRW1-A's and LZRW2's compression
  28. performance.
  29.  
  30. Users should know that about 3% to 5% absolute extra compression is
  31. possible in all three algorithms by using a deeper hash table (e.g.
  32. 2x2048 rather than 1x4096). This comes at about a 40% speed decrease
  33. in the compressor (and a small decrease in speed in the LZRW3
  34. decompressor). Extra compression could also be obtained by reducing
  35. the size of the phrase table in LZRW2 and the hash table in LZRW3 thus
  36. reducing the offset field width in the code. I have avoided this
  37. option as it would mean that the compressed items would no longer be
  38. byte-aligned which I have perceived would severely affect speed
  39. (although I am not so sure having heard of some of the high speed IBM
  40. PC compressors with variable-length backend coders).
  41.  
  42. Availability
  43. ------------
  44. The only implementation available is in C. It can be found in the
  45. following archive within a couple of days of 30-Jun-1991:
  46.  
  47.    FTP Archive Access:
  48.    Machine   : sirius.itd.adelaide.edu.au   [IP=129.127.40.3]
  49.    Directory : ~pub/compression
  50.    Files     : lzrw3.txt   - This file.
  51.                lzrw3.c     - An implementation in C.
  52.  
  53. Motivation for LZRW3
  54. --------------------
  55. To best understand LZRW3, you should have an understanding of LZRW1-A
  56. and LZRW2.
  57.  
  58. After designing LZRW2, I noted that a phrase table entry would never
  59. be used unless there was a corresponding hash table entry. I realized
  60. that I could bypass the phrase table altogether and send the hash
  61. table indices directly, at the cost of the decompressor maintaining a
  62. hash table too.
  63.  
  64. The benefit of eliminating the phrase table is that phrases are no
  65. longer automatically forgotten when they become 4097 phrases old. In
  66. LZRW1-A, a phrase is forgotten if a new phrase with the same hash
  67. arrives OR if the phrase grows more than 4096 bytes old. In LZRW2, a
  68. phrase is forgotten if a new phrase with the same hash arrives OR if
  69. it grows 4096 phrases old. In LZRW3, a phrase is forgotten ONLY when a
  70. new phrase with the same hash arrives. In LZRW3, rarely used hash
  71. table entries can laze about until their big day comes around again.
  72. LZRW3 gives compression identical to an imaginary supernatural version
  73. of LZRW1-A in which an infinite range of offsets can be fitted into
  74. LZRW1-A's twelve bit offset field.
  75.  
  76. Updating the hash table in LZRW3 is a little messy. Consider the case
  77. of an LZRW3 decompressor that has just received a copy item. Updating
  78. the hash table is easy in this case as the compressor has just
  79. transmitted the index of the hash table entry to be updated! No
  80. hashing involved! The literal case, however, is much nastier as upon
  81. receipt of a literal item, the decompressor is unable to immediately
  82. update the hash table as it does not have three bytes to hash!
  83.  
  84. There are a few solutions to the problem, one easy solution being
  85. simply to make literals three bytes long! The solution adopted in
  86. LZRW3 is to defer the updating of the hash table for each phrase until
  87. the first three bytes of the phrase become available. Both the
  88. compressor and the decompressor perform this buffering in order to
  89. remain synchronized.
  90.  
  91. For more details, see the code itself.
  92.  
  93. Benchmark
  94. ---------
  95. Here are the results of applying LZRW3.C compiled under THINK C 4.0
  96. and running on a Mac-SE (8MHz 68000) to the standard Calgary corpus.
  97.  
  98.    +----------------------------------------------------------------+
  99.    | DATA COMPRESSION TEST                                          |
  100.    | =====================                                          |
  101.    | Time of run     : Sun 30-Jun-1991 09:31PM                      |
  102.    | Timing accuracy : One part in 100                              |
  103.    | Context length  : 262144 bytes (= 256.0000K)                   |
  104.    | Test suite      : Calgary Corpus Suite                         |
  105.    | Files in suite  : 14                                           |
  106.    | Algorithm       : LZRW3                                        |
  107.    | Note: All averages are calculated from the un-rounded values.  |
  108.    +----------------------------------------------------------------+
  109.    | File Name   Length  CxB  ComLen  %Remn  Bits  Com K/s  Dec K/s |
  110.    | ----------  ------  ---  ------  -----  ----  -------  ------- |
  111.    | rpus:Bib.D  111261    1   55033   49.5  3.96    19.46    32.27 |
  112.    | us:Book1.D  768771    3  467962   60.9  4.87    17.03    31.07 |
  113.    | us:Book2.D  610856    3  317102   51.9  4.15    19.39    34.15 |
  114.    | rpus:Geo.D  102400    1   82424   80.5  6.44    11.65    18.18 |
  115.    | pus:News.D  377109    2  205670   54.5  4.36    17.14    27.47 |
  116.    | pus:Obj1.D   21504    1   13027   60.6  4.85    13.40    18.95 |
  117.    | pus:Obj2.D  246814    1  116286   47.1  3.77    19.31    30.10 |
  118.    | s:Paper1.D   53161    1   27522   51.8  4.14    18.60    31.15 |
  119.    | s:Paper2.D   82199    1   45160   54.9  4.40    18.45    32.84 |
  120.    | rpus:Pic.D  513216    2  122388   23.8  1.91    35.29    51.05 |
  121.    | us:Progc.D   39611    1   19669   49.7  3.97    18.87    30.64 |
  122.    | us:Progl.D   71646    1   28247   39.4  3.15    24.34    40.66 |
  123.    | us:Progp.D   49379    1   19377   39.2  3.14    23.91    39.23 |
  124.    | us:Trans.D   93695    1   33481   35.7  2.86    25.48    40.37 |
  125.    +----------------------------------------------------------------+
  126.    | Average     224401    1  110953   50.0  4.00    20.17    32.72 |
  127.    +----------------------------------------------------------------+
  128.  
  129. --<End of Release Notes for LZRW3>--
  130.  
  131.