一个基于lZW压缩算法的高效实现，可以用于数据和图像的高效压缩.zip

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: ross@spam.ua.oz.au (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: <967@spam.ua.oz> Date: 28 Jul 91 16:21:46 GMT Sender: ross@spam.ua.oz 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 ross@spam.ua.oz.au 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: brnstnd@kramden.acf.nyu.edu (Dan Bernstein) Newsgroups: comp.compression Subject: Re: LZRW5: A Turbocharged LZW-like Decompressor. Message-ID: <28577.Jul2519.12.1791@kramden.acf.nyu.edu> Date: 25 Jul 91 19:12:17 GMT References: <961@spam.ua.oz> 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: brnstnd@kramden.acf.nyu.edu (Dan Bernstein) Newsgroups: comp.compression Subject: Re: LZRW5 is NOT original. Message-ID: <18214.Jul2902.59.2991@kramden.acf.nyu.edu> Date: 29 Jul 91 02:59:29 GMT References: <967@spam.ua.oz> Organization: IR Lines: 42 In article <967@spam.ua.oz> ross@spam.ua.oz.au (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. Descriptio