roy@esp.ics.uci.edu (John Roy) (08/02/90)
Before I go diving into the library, does anybody know of a good/simple data compression algorithm for a stream of random bits. I know this is a tough one, but I would like to the 2 or 3 to 1 compression without loosing any information. The stream will be mostly zeros (like 75%) so there is some hope. thanks, jmar -- John M.A. Roy 714/856-5039 TRINTECH USA 714/757-7757 ICS Dept., Univ. Calif., Irvine CA 92714 18500 Von Karman, #410 Internet: roy@ics.uci.edu Irvine, CA 92715
dave@westmark.UU.NET (Dave Levenson) (08/02/90)
In article <26B70D8E.23784@ics.uci.edu>, roy@esp.ics.uci.edu (John Roy) writes: > Before I go diving into the library, does anybody know of a > good/simple data compression algorithm for a stream of random bits. I > know this is a tough one, but I would like to the 2 or 3 to 1 > compression without loosing any information. The stream will be > mostly zeros (like 75%) so there is some hope. I suggest that you have a look at the UNIX(tm) utility called compress. It performs LZW encoding, and if you're at a UNIX site which runs netnews, you probably already have it. (It's used to send compressed news between sites.) -- Dave Levenson Voice: 908 647 0900 Fax: 908 647 6857 Westmark, Inc. UUCP: {uunet | rutgers | att}!westmark!dave Warren, NJ, USA AT&T Mail: !westmark!dave [The Man in the Mooney]
steve@wattres.UUCP (Steve Watt) (08/06/90)
In article <573@westmark.UU.NET> dave@westmark.UU.NET (Dave Levenson) writes: >In article <26B70D8E.23784@ics.uci.edu>, roy@esp.ics.uci.edu (John Roy) writes: >> Before I go diving into the library, does anybody know of a >> good/simple data compression algorithm for a stream of random bits. I >I suggest that you have a look at the UNIX(tm) utility called compress. >It performs LZW encoding, and if you're at a UNIX site which runs Watch out if you plan on using this for ANY commercial application... There is a patent (number 4 558 302) held on the LZW algorithm by Unisys, and they are starting to realize what they have their hands on... There was a (brief) thread about this in comp.emacs. The article header is: From: rms@AI.MIT.EDU Newsgroups: comp.emacs Subject: compress patent Message-ID: <9008011947.AA22165@sugar-bombs.ai.mit.edu> Date: 1 Aug 90 19:47:31 GMT Lines: 101 [ <--- Too long for me to waste bandwidth. ] [ article body deleted, find it in your spool directory... ] -- Steve Watt ...!claris!wattres!steve wattres!steve@claris.com also works If you torture your data long enough, it'll eventually confess.
dave@westmark.UU.NET (Dave Levenson) (08/07/90)
In article <592@wattres.UUCP>, steve@wattres.UUCP (Steve Watt) writes: > In article <573@westmark.UU.NET> dave@westmark.UU.NET (Dave Levenson) writes: ... > >I suggest that you have a look at the UNIX(tm) utility called compress. > >It performs LZW encoding, and if you're at a UNIX site which runs > > Watch out if you plan on using this for ANY commercial application... There > is a patent (number 4 558 302) held on the LZW algorithm by Unisys, and they > are starting to realize what they have their hands on... I didn't realize that patent-infringement was related to commercial vs non-commercial use. If netnews software contains someone's pattented software and is being copied and distributed without the patent-owner's permission, it would appear that there is already widespread infringement of this pattent. A copy of compress.c comes with every distribution of the netnews software. This software package is freely copied and distributed wherever UNIX goes, and the copy that came with the netnews we run here bears no copyright nor pattent notice. Perhaps all nodes who run netnews should immediately discontinue the use of compressed news transfers until this matter is resolved? -- Dave Levenson Voice: 908 647 0900 Fax: 908 647 6857 Westmark, Inc. UUCP: {uunet | rutgers | att}!westmark!dave Warren, NJ, USA AT&T Mail: !westmark!dave [The Man in the Mooney]
johnl@esegue.segue.boston.ma.us (John R. Levine) (08/07/90)
In article <593@westmark.UU.NET> dave@westmark.UU.NET (Dave Levenson) writes: >Perhaps all nodes who run netnews should immediately discontinue the >use of compressed news transfers until this matter is resolved? Only if you want to triple your phone bill. A few points: -- AT&T distributes compress with recent versions of unix, and they have patent cross-licenses with Unisys. This means that in all likelihood anyone who uses compress on a unix system has the legal right to use the patent, independent of whether it applies to compress or not. -- Since the patent has never been litigated, there is considerable doubt whether the patent is valid, and if so, whether it applies to software-only patents. (The legal basis for software-only patents is quite fuzzy.) -- Discontinuing your use of compress the moment you hear about the patent is, in the eyes of a court, a virtual admission that you think you're infringing it, and only makes your situation worse in the unlikely event that someone took you to court. Personally, I don't think that I am infringing anything and see no reason to change what I'm doing. -- Pragmatically speaking, there is no way that anyone can identify every site that uses compress, arc, or any of the other programs that use LZW compression. There's too many, and there's no audit trail. -- John R. Levine, Segue Software, POB 349, Cambridge MA 02238, +1 617 864 9650 johnl@esegue.segue.boston.ma.us, {ima|lotus|spdcc}!esegue!johnl Marlon Brando and Doris Day were born on the same day.
vjs@rhyolite.wpd.sgi.com (Vernon Schryver) (08/08/90)
In article <592@wattres.UUCP>, steve@wattres.UUCP (Steve Watt) writes: > Watch out if you plan on using this for ANY commercial application... There > is a patent (number 4 558 302) held on the LZW algorithm by Unisys, and they > are starting to realize what they have their hands on... This has been discussed in gnu.misc recently. The enclosed two excerpts from an article there may be relevant, and for all I know, accurate. vjs@sgi.com > From: jaw@riacs.edu (James A. Woods) > Newsgroups: gnu.misc.discuss > Subject: Sperry patent #4,558,302 does *not* affect 'compress' > Keywords: data compression, algorithm, patent > Message-ID: <1990Jul31.220935.1424@riacs.edu> > Date: 31 Jul 90 22:09:35 GMT > Organization: RIACS, NASA Ames Research Center > Lines: 69 ... > As a co-author of 'compress' who has had contact with an attorney for > Unisys (nee Sperry), I would like to relay a very basic admission from Unisys > that noncommercial use of 'compress' is perfectly legal. 'Compress' is also > commercially distributed by AT&T as part of Unix System 5 release 4, > with no further restrictions placed upon the use of the binary, as far > as I am aware.