Path: gmdzi!unido!mcsun!uunet!lll-winken!elroy.jpl.nasa.gov!swrinde! zaphod.mps.ohio-state.edu!samsung!munnari.oz.au!yoyo.aarnet.edu.au! sirius.ucs.adelaide.edu.au!spam!ross From: r...@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: r...@spam.ua.oz Followup-To: comp.compression Organization: Statistics, Pure & Applied Mathematics, University of Adelaide Lines: 25 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 r...@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: gmdzi!unido!fauern!ira.uka.de!sol.ctr.columbia.edu! zaphod.mps.ohio-state.edu!think.com!hsdndev!cmcl2!kramden.acf.nyu.edu!brnstnd From: brns...@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 <9...@spam.ua.oz> r...@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
Path: gmdzi!unido!mcsun!uunet!bywater!arnor!arnor!victor From: vic...@watson.ibm.com (Victor Miller) Newsgroups: comp.compression Subject: Re: LZRW5 is NOT original. Message-ID: <VICTOR.91Jul29120413@buckland.watson.ibm.com> Date: 29 Jul 91 10:04:13 GMT References: <967@spam.ua.oz> <18214.Jul2902.59.2991@kramden.acf.nyu.edu> Sender: n...@watson.ibm.com (NNTP News Poster) Reply-To: vic...@watson.ibm.com Organization: IBM, T.J. Watson Research Center Lines: 30 In-Reply-To: brnstnd@kramden.acf.nyu.edu's message of 29 Jul 91 02:59:29 GMT Nntp-Posting-Host: buckland Disclaimer: This posting represents the poster's views, not those of IBM >>>>> On 29 Jul 91 02:59:29 GMT, brns...@kramden.acf.nyu.edu (Dan Bernstein) said: Dan> While I'm on a historical accuracy kick: Don't trust anything you read Dan> in the May 1991 Computer Language article on data compression. I quote: Dan> ``One of the most popular data-compression algorithms is the Dan> sliding-window dictionary (SWD) variation on the Lempel-Ziv-Welch (LZW) Dan> algorithm, developed around 1984-85.'' First of all, LZW was developed Dan> in 1983 (both by Welch and by Miller-Wegman), and published in 1984, so I don't know about Welch, but we (Wegman and I) developed our algorithm on December 15, 1981, we sent our disclosure written up in June of 1982, it was filed in June of 1983. We had internally (inside IBM) available versions of the algorithm (fairly well tuned) in April 1982. It was embedded in an extremely popular terminal emulator (called PCTERM) available first in May of 1982. By 1983 PCTERM probably had in excess of 10,000 users. Dan> ``developed around 1984-85'' is silly. Second, I haven't gone through Dan> the code in that article in detail, but there is no such thing as ``the Dan> sliding-window dictionary variation on LZW.'' The article appears to Dan> describe one of the LZ77 variants. The article goes on to use ``SWD'' as Dan> the name of the method; this is nonstandard at best (though one can say Dan> the same of almost all of Storer's terminology). Dan> ---Dan -- Victor S. Miller Vnet and Bitnet: VICTOR at WATSON Internet: vic...@watson.ibm.com IBM, TJ Watson Research Center
Path: gmdzi!unido!mcsun!uunet!cs.utexas.edu!asuvax!ncar!hsdndev!cmcl2! kramden.acf.nyu.edu!brnstnd From: brns...@kramden.acf.nyu.edu (Dan Bernstein) Newsgroups: comp.compression Subject: Re: LZRW5 is NOT original. Message-ID: <25329.Jul3002.22.0191@kramden.acf.nyu.edu> Date: 30 Jul 91 02:22:01 GMT References: <967@spam.ua.oz> <18214.Jul2902.59.2991@kramden.acf.nyu.edu> <VICTOR.91Jul29120413@buckland.watson.ibm.com> Organization: IR Lines: 12 In article <VICTOR.91Jul29120...@buckland.watson.ibm.com> vic...@watson.ibm.com writes: > I don't know about Welch, but we (Wegman and I) developed our > algorithm on December 15, 1981, we sent our disclosure written up in > June of 1982, it was filed in June of 1983. Mea culpa. This shows that ``developed in 1984-1985'' is even more wrong than I thought. This brings up an important side issue: How come so many compression algorithms are developed in December? Is it the winter air? (That wouldn't explain Ross's December discoveries in Australia.) Is there something magical about the year switch? ---Dan