lzrw5.txt

一个基于lZW压缩算法的高效实现

IMPORTANT NOTE: The LZRW5 document was posted on 23-Jul-1991.
That document appears at the end of this file.

At the time I thought LZRW5 was a new idea. However, I was wrong as is
shown by the following email which I have included here before the
original document.

======================================================================
Path: spam!ross
From: [e-mail] (Ross Williams)
Newsgroups: comp.compression
Subject: LZRW5 is NOT original.
Summary: LZRW5 is NOT original.
Keywords: lzrw5 data compression algorithm orginality yabba yabbawhap
Message-ID: <[e-mail]>
Date: 28 Jul 91 16:21:46 GMT
Sender: [e-mail]
Followup-To: comp.compression
Distribution: world
Organization: Statistics, Pure & Applied Mathematics, University of Adelaide
Lines: 26

LZRW5 is NOT Original
=====================
Earlier I posted my LZRW5 as an original algorithm. However, I have
recently discovered that it has appeared before. The same idea of
keeping an array of pointers to phrases in an LZW algorithm was used
by Dan Bernstein in his yabbawhap compression package which can be
found in comp.sources.unix vol 24. At least one site where you can get
this is UUNET (in Virginia) in

   uunet.uu.net:comp.sources.unix/volume24/yabbawhap.

Dan developed the yabba program about one year ago and posted it to
alt.comp.compression in March 1991.

Boo hoo,

Ross Williams
[e-mail]

PS: How embarrassing - I actually created alt.comp.compression! Dan
posted yabba after I thought I had destroyed alt.comp.compression and
while I was busy with creating comp.compression! I nearly looked at
yabba recently too, but decided to spend the time getting LZRW4 and
LZRW5 out! I have not yet sighted yabba source code, being busy at
present with non-compression stuff.

======================================================================
Path: spam!sirius.ucs.adelaide.edu.au!yoyo.aarnet.edu.au!munnari.oz.au!samsung!uakari.primate.wisc.edu!sdd.hp.com!wupost!emory!ox.com!yale.edu!cmcl2!kramden.acf.nyu.edu!brnstnd
From: [e-mail] (Dan Bernstein)
Newsgroups: comp.compression
Subject: Re: LZRW5: A Turbocharged LZW-like Decompressor.
Message-ID: <[e-mail]>
Date: 25 Jul 91 19:12:17 GMT
References: <[e-mail]>
Organization: IR
Lines: 22

While I'm sure we all appreciate Ross's extensive contributions to the
field of compression, I have to point out that his ``turbocharging'' is
exactly the method stated in my introduction to Y coding (draft 4b,
3/19/91), in section 2 (``Implementing LZW''):

: --- Decoding
:
: LZW decoding is even easier than encoding: the dictionary does not have
: to support searching. The easiest (and generally fastest) method is to
: keep I in memory as it is reconstructed, and to keep track of which
: substring of I a given dictionary number corresponds to. To add pc to
: the dictionary means to add the pair (pointer to start of pc within I,
: length of pc) at the right spot in an array indexed by dictionary
: numbers. There are methods which take slightly less memory than this,
: but they are slower.

I applied this to LZW last year, and indeed it makes a very fast, simple
decompressor. My ``unwhap'' decompressor for AP, as included in my
yabbawhap package, comp.sources.unix volume 24, also applies the same
technique.

---Dan

======================================================================
Path: spam!sirius.ucs.adelaide.edu.au!yoyo.aarnet.edu.au!munnari.oz.au!samsung!mips!swrinde!zaphod.mps.ohio-state.edu!think.com!hsdndev!cmcl2!kramden.acf.nyu.edu!brnstnd
From: [e-mail] (Dan Bernstein)
Newsgroups: comp.compression
Subject: Re: LZRW5 is NOT original.
Message-ID: <[e-mail]>
Date: 29 Jul 91 02:59:29 GMT
References: <[e-mail]>
Organization: IR
Lines: 42

In article <[e-mail]> [e-mail] (Ross Williams) writes:
> Earlier I posted my LZRW5 as an original algorithm. However, I have
> recently discovered that it has appeared before. The same idea of
> keeping an array of pointers to phrases in an LZW algorithm was used
> by Dan Bernstein in his yabbawhap compression package which can be
> found in comp.sources.unix vol 24.

I used it in unwhap, and it's the main reason unwhap runs as fast as
uncompress---AP does three to five times more dictionary manipulations
than LZW. However, I haven't figured out how to apply it to Y coding.
(I have a very promising lead, though, so don't be surprised if and when
undabba is faster than unyabba... more news soon...)

> Dan developed the yabba program about one year ago and posted it to
> alt.comp.compression in March 1991.

Actually, I posted my introduction to Y coding to alt.comp.compression
on March 6, 1991, a few days before the group was officially removed. I
included a slightly revised draft with yabbawhap, which I posted to
comp.sources.unix, not alt.comp.compression. I discovered Y coding on
December 26, 1990. A year ago (July 28, 1990, according to my mail
records) I discovered AP coding, which I called ``B coding'' in private
discussions until a month later, when Brad Templeton pointed out
Storer's prior discovery of the method. To get back to the topic at
hand, my implementations of AP during August 1990 all used the same
technique as in Ross's recent LZRW5. I don't know if I was the first to
come upon this idea.

While I'm on a historical accuracy kick: Don't trust anything you read
in the May 1991 Computer Language article on data compression. I quote:
``One of the most popular data-compression algorithms is the
sliding-window dictionary (SWD) variation on the Lempel-Ziv-Welch (LZW)
algorithm, developed around 1984-85.'' First of all, LZW was developed
in 1983 (both by Welch and by Miller-Wegman), and published in 1984, so
``developed around 1984-85'' is silly. Second, I haven't gone through
the code in that article in detail, but there is no such thing as ``the
sliding-window dictionary variation on LZW.'' The article appears to
describe one of the LZ77 variants. The article goes on to use ``SWD'' as
the name of the method; this is nonstandard at best (though one can say
the same of almost all of Storer's terminology).

---Dan

======================================================================

--<Start of LZRW5 paper>--

LZRW5: A TURBOCHARGED LZW-LIKE DECOMPRESSOR
===========================================
Author : Ross Williams
Date   : 23-Jul-1991.

This is a public domain document and may be copied freely so long as
it is not modified (but text formatting transformations are permitted
though).

Abstract
--------
A technique is described for constructing an LZW-like algorithm that
yields the same compression as LZW but whose decompressor runs much
faster (93K/s for a 68000 assembler implementation on an 8MHz
Mac-SE20). The implementation of the compression algorithm is open
ended (although a modified version of LZW could be used).
Unfortunately it is possible that the technique may be covered by
third party patents.

Distribution Algorithms
-----------------------
Over the last month or so, one or two people have posted requests for
what I call "distribution algorithms", which are data compression
algorithms where the decompressor's speed and memory consumption is
much more important than the compressor's. Such algorithms are useful
when distributing data, where the data will be compressed once by the
distributor, but decompressed thousands or perhaps millions of times
by users. The distributor can afford to use a hugely powerful computer
to perform the compression, but the decompression must be performed on
each user computer using minimum resources.

While thinking about this, I happened to apply the phrase table idea
of my LZRW2 algorithm to the LZW algorithm to produce an LZW-like
algorithm that provides the same compression performance as LZW, but
yields very much faster decompression, possibly at a cost in memory
consumption and speed of the compressor.

Description of the LZRW5 Idea
------------------------------
The trick is for the compressor and decompressor to maintain a "phrase
table" of roughly the most recent 2^n phrases parsed (where n is the
codeword width). Apart from a large memory output buffer, this is the
ONLY data structure of the decompressor. The compressor is likely to
need other data structures. Each phrase table entry consists of a
pointer to the phrase and the length of the phrase. An index rotates
through this table indicating the next position to overwrite. Pointers
point to the input buffer in the compressor and the output buffer in
the decompressor.

To process each phrase, the decompressor receives a phrase number from
the compressor. It then looks up the pointer and the length of the phrase
and copies the phrase to the output. It then overwrites the next position
in the phrase table with a pointer to the phrase just coded, but puts
in the length+1 in the table.

The compressor does all this too but keeps an additional table that
enables it to select the longest match from the strings in the phrase
table.

Here is a rough outline for the decompressor code. A complete 68000
C and assembly language version appears in Appendix A.

   unsigned cycle;              -- Index of next slot to write.
   unsigned word *p_src;        -- Pointer to input block.
   unsigned byte *p_dst;        -- Pointer to output block.
   char *pointer[65536];        -- Stores pointers to phrases.
   unsigned *length[65536];     -- Stores length of phrases.

   p_src=pointer to start of input  block.
   p_dst=pointer to start of output block.
   cycle=256;
   forall ch in 0..255, pointer[ch]=&<constant byte being value of ch>;
   forall ch in 0..255, length[ch]=1;

   while (p_src!=end of input block) loop
      unsigned phrasenum,len;
      phrasenum=*p_src++;       -- Pick up next code word.
      p=pointer[phrasenum];     -- Get pointer and length of phrase to copy
      len=length[phrasenum];
      pointer[cycle]=p_dst;     -- Add a new phrase one byte longer.
      length[cycle]=len+1;
      cycle++;                  -- Update cycle counter.
      if (cycle==2^n) cycle=256;-- Note:0..255 reserved for alphabet.
      while (len--) *p_dst++=*p++; -- Copy phrase to output.
   end loop

This decompressor code has the full power of LZW while giving roughly
the speed of the fast LZ77 decompressors (e.g. the A1 or LZRW1
algorithms). For 65536 phrases, it will use 320K, plus space for the
output buffer. The algorithm is adaptive so reducing the table size
will probably not impact on compression grossly (you may or may not
want to pack the resultant narrower codewords).

This decompressor avoids the nasty problem LZW has with adding a
phrase and then using it immediately (and having to look up the first
character etc). The problem is solved in a LZ77 kind of a way by using
pointers to the output to do automatic overlapping! This decompressor
is also adaptive because it overwrites old phrases with new ones. Unix
compress has to do its adaption explicitly.

There are any number of compressor implementations that could operate
in conjunction with the decompressor above. The compressor can use
expensive data structures to find the best match. It would also be a
very easy and efficient thing to modify the decompressor to (say) add
TWO strings to the dictionary instead of one (e.g. strings of length 1
and 3 characters longer, or this and the next phrase) (many other
similar variations are possible).

There is no reason why a conventional LZW hash table compressor could
not be modified to drive the output through a phrase table. This would
yield roughly the same compression speed.

The code below is an early draft of the LZRW5 algorithm. The
compressor uses binary trees and is rather pathetic (it runs at about
1k/s) as I have been concentrating on the deecompressor.

The 68000 assembly language version of the decompressor runs at
93K/sec on my Mac-SE20 (43K/sec in C). This (the 93K/sec) is only 2/3
the speed of LZRW1 (which yields worse compression), but a lot faster
than Unix compress. The compressor below runs at about 1K/second.

So far I have been unable to ascertain whether this idea is covered by
any patents. If anyone can help here, I would be most grateful.

Enjoy,

Ross Williams
[e-mail]


Appendix A: Half-Baked Code for LZRW5
-------------------------------------
The following code is public domain and is provided "as is". As most
experimental code, it is poorly designed, structured, coded, and
commented.

WARNING: It is possible that this code may be subject to patent
protection by third parties. As such, it should not be included in
production software or executed for any but experimental purposes
without prior legal advice.

WARNING: This code will not work properly for more than 65536 phrases.