home *** CD-ROM | disk | FTP | other *** search
/ CD Actual 15 / CDACTUAL15.iso / cdactual / program / pascal / LZRW.ZIP / LZRW3-A.TXT < prev    next >
Encoding:
Text File  |  1992-01-19  |  4.9 KB  |  104 lines
  1. NOTES ON THE LZRW3-A ALGORITHM
  2. ==============================
  3. Author : Ross Williams (ross@spam.ua.oz.au).
  4. Date   : 15-Jul-1991.
  5.  
  6. Abstract
  7. --------
  8. This file announces the release of my LZRW3-A algorithm which was
  9. invented on 31-Dec-1990 along with LZRW3. The LZRW3-A algorithm has
  10. the following features:
  11.  
  12.    1 Requires only 16K of memory (for both compression and decompression).
  13.    2 The compressor   runs about two   times faster than Unix compress's.
  14.    3 The decompressor runs about three times faster than Unix compress's.
  15.    4 Yields a few percent better compression than Unix compress for
  16.      most files.
  17.    5 Allows you to dial up extra compression at a speed cost in the
  18.      compressor. The speed of the decompressor is not affected.
  19.    6 Algorithm is deterministic.
  20.    7 Algorithm is free of patent problems. The algorithm has not been
  21.      patented (nor will it be) and is of the LZ77 class which is fairly
  22.      clear of patents.
  23.    8 This implementation in C is in the public domain.
  24.  
  25. (Timing tests for the speed comparison were performed on a Pyramid 9820.)
  26.  
  27. LZRW3-A dominates Unix compress in memory and speed. LZRW3-A dominates
  28. Unix compress in compression for object files and smallish (e.g. 50K)
  29. text files, but yields worse compression for large complex English
  30. text files.
  31.  
  32. The exact figures for the Calgary corpus on C implementations on my
  33. Macintosh-SE are (percentage remaining, compression speed,
  34. decompression speed, memory required during compression and
  35. decompression):
  36.  
  37.            PerRem    ComK/S    DecK/S     ComMem    DecMem
  38. LZRW1-A     55.1 %   17 K/s     69 K/s      16 K       0 K
  39. LZRW2       51.5 %   18 K/s     54 K/s      24 K      16 K
  40. LZRW3       50.0 %   20 K/s     33 K/s      16 K      16 K
  41. LZRW3-A     45.8 %    8 K/s     31 K/s      16 K      16 K
  42.  
  43. I would like to hear from anyone who knows of an algorithm that
  44. performs similarly or better to this one when implemented in C and
  45. compiled and run on the same machine on the same files.
  46.  
  47. Availability
  48. ------------
  49. The only implementation available is in C. It can be found in the
  50. following archive in about mid August 1991.
  51.  
  52.    FTP Archive Access:
  53.    Machine   : sirius.itd.adelaide.edu.au   [IP=129.127.40.3]
  54.    Directory : ~pub/compression
  55.    Files     : lzrw3-a.txt   - This file.
  56.                lzrw3-a.c     - An implementation in C.
  57.  
  58. Motivation for LZRW3-A
  59. ----------------------
  60. LZRW3-A was designed as a direct competitor to Unix compress.
  61.  
  62. LZRW3-A is identical to the LZRW3 algorithm except that it uses a
  63. "deep" hash table (of depth 8 by default). See the explanation in the
  64. comments in the program code for more details.
  65.  
  66. Benchmark
  67. ---------
  68. Here are the results of applying LZRW3-A.C compiled under THINK C 4.0
  69. and running on a Mac-SE (8MHz 68000) to the standard Calgary corpus.
  70.  
  71.      +----------------------------------------------------------------+
  72.      | DATA COMPRESSION TEST                                          |
  73.      | =====================                                          |
  74.      | Time of run     : Mon 15-Jul-1991 05:29PM                      |
  75.      | Timing accuracy : One part in 100                              |
  76.      | Context length  : 262144 bytes (= 256.0000K)                   |
  77.      | Test suite      : Calgary Corpus Suite                         |
  78.      | Files in suite  : 14                                           |
  79.      | Algorithm       : LZRW3-A                                      |
  80.      | Note: All averages are calculated from the un-rounded values.  |
  81.      +----------------------------------------------------------------+
  82.      | File Name   Length  CxB  ComLen  %Remn  Bits  Com K/s  Dec K/s |
  83.      | ----------  ------  ---  ------  -----  ----  -------  ------- |
  84.      | rpus:Bib.D  111261    1   49044   44.1  3.53     8.47    31.19 |
  85.      | us:Book1.D  768771    3  420464   54.7  4.38     7.27    30.07 |
  86.      | us:Book2.D  610856    3  277955   45.5  3.64     8.51    33.40 |
  87.      | rpus:Geo.D  102400    1   84218   82.2  6.58     4.23    15.04 |
  88.      | pus:News.D  377109    2  192880   51.1  4.09     7.08    25.89 |
  89.      | pus:Obj1.D   21504    1   12651   58.8  4.71     5.23    17.44 |
  90.      | pus:Obj2.D  246814    1  108044   43.8  3.50     8.01    28.11 |
  91.      | s:Paper1.D   53161    1   24526   46.1  3.69     8.11    30.24 |
  92.      | s:Paper2.D   82199    1   39483   48.0  3.84     8.11    32.04 |
  93.      | rpus:Pic.D  513216    2  111622   21.7  1.74    10.64    49.31 |
  94.      | us:Progc.D   39611    1   17923   45.2  3.62     8.06    29.01 |
  95.      | us:Progl.D   71646    1   24362   34.0  2.72    10.74    39.51 |
  96.      | us:Progp.D   49379    1   16805   34.0  2.72    10.64    37.58 |
  97.      | us:Trans.D   93695    1   30296   32.3  2.59    11.02    38.06 |
  98.      +----------------------------------------------------------------+
  99.      | Average     224401    1  100733   45.8  3.67     8.29    31.21 |
  100.      +----------------------------------------------------------------+
  101.  
  102. --<End of Release Notes for LZRW3-A>--
  103.  
  104.