dww@stl.stc.co.uk (David Wright) (08/04/90)
In the referenced article karn@thumper.bellcore.com writes:
#PKZIP also makes use of a new compression scheme Katz calls
#"implosion", and it seems to do much better than his LZW in PKARC.
#
#Does anybody know how "implosion" works, and whether it might be an
#alternative to LZW? It would be pretty satisfying to tell Unisys to
#take a hike because we've found a more efficient algorithm that's
#public domain...
If you get hold of PZK110.EXE, the PKZIP distribution, you'll find a
file in it called APPNOTE.TXT. Here's a small extract:
The Imploding algorithm is actually a combination of two distinct algorithms.
The first algorithm compresses repeated byte sequences using a sliding
dictionary. The second algorithm is used to compress the encoding of the
sliding dictionary ouput, using multiple Shannon-Fano trees.
The note then goes on to define how the data is coded. It should be easy
reading to anyone already familiar with the general method (not me!).
It also give these references:
Storer, James A. "Data Compression, Methods and Theory",
Computer Science Press, 1988
Held, Gilbert "Data Compression, Techniques and Applications,
Hardware and Software Considerations"
John Wiley & Sons, 1987
So it appears that impoding does not use LZW, and does not depend on the
Sperry/Unisys patent. PKZIP is a copyright work, and only released as
MS-DOS executable code. But presumably someone could write something for
UNIX using the same compression algorithm. Note that unlike PKZIP itself,
its compressed file format has been put into the public domain.
Personally I still use ZOO, (and will continue to do so unless I get informed
formally that I can't), because unlike PKZIP, ZOO is available on UNIX (and
VMS) as well as MS-DOS, and also I find it easier to use. But PKZIP does
seem to get about 10% better compression.
What I don't understand is how Unisys can have a 1989 patent on a method
published in 1984 - perhaps it took 5 years to be granted? In the UK you
cannot patent something after it has been published (I understand that in
some countries such as the USA you can do so within a year of publication).
Does anyone know when the 1989 patent was applied for? If after the 1984
publication then it cannot be effective in the UK, and I believe the same
would apply if after 1985 in the USA. It would also be interesting to see
whether such a patent, which no doubt covers an implementation in a modem,
would stand up in court in the case where only the underlying algorithm is
used, and that implemented purely as a piece of software (aot software used
as part of a mechanism) -- but I wouldn't like to be the one paying the
legal fees to find out :->
Regards, "None shall be enslaved by poverty, ignorance or conformity"
David Wright STL, London Road, Harlow, Essex CM17 9NA, UK
dww@stl.stc.co.uk <or> ...uunet!mcsun!ukc!stl!dww <or> PSI%234237100122::DWW
<or> /g=David/s=Wright/org=STC Technology Ltd/prmd=STC plc/admd=Gold 400/co=GB