Part1 - Part2 - Part3 - MultiPage
comp.compression Frequently Asked Questions (part 1/3)
| There are reader questions on this topic! Help others by sharing your knowledge |
From: jloup@gzip.OmitThis.org (Jean-loup Gailly) Newsgroups: comp.compression, comp.compression.research Subject: comp.compression Frequently Asked Questions (part 1/3) Date: 5 Sep 1999 22:34:48 +0200 Message-ID: <compr1_05sep99@gzip_org> Reply-To: jloup@gzip.OmitThis.org Summary: *** READ THIS BEFORE POSTING *** Keywords: data compression, FAQ Archive-name: compression-faq/part1 Last-modified: Sep 5th, 1999 It is insufficiently considered that men more often require to be reminded than informed. Samuel Johnson This file is part 1 of a set of Frequently Asked Questions (FAQ) for the groups comp.compression and comp.compression.research. If you can't find part 2 or 3, see item 53 below. A copy of this FAQ is available by ftp in ftp://rtfm.mit.edu/pub/usenet/news.answers/compression-faq/ files part1 to part3. This FAQ is also accessible in the World Wide Web at http://www.faqs.org/faqs/compression-faq/part1/preamble.html or http://www.cis.ohio-state.edu/hypertext/faq/usenet/compression-faq/top.html Certain questions get asked time and again, and this is an attempt to reduce the bandwidth taken up by these posts and their associated replies. If you have a question, *please* check this file before you post. It may save a lot of peoples time. If you have not already read the overall Usenet introductory material posted to "news.announce.newusers", please do. It is also available by ftp in ftp://garbo.uwasa.fi/pc/doc-net/ (see item 2 below about .zip). If you don't want to see this FAQ regularly, please add the subject line to your kill file. If you don't know what a kill file is, get by ftp the file ftp://rtfm.mit.edu/pub/usenet/news.answers/ If you have corrections or suggestions for this FAQ, send them to Jean-loup Gailly <jloup at gzip.org>. (Replace " at " with "@". This is a protection against junk mail. Sorry for the inconvenience.) Part 1 is oriented towards practical usage of compression programs. Part 2 is more intended for people who want to know how compression works. Part 3 is a long (but somewhat obsolete) list of image compression hardware. Main changes relative to the previous version: - LZO page moved [item 2] - new url for the File Format Collection [items 2 & 54] - new url for ACE [item 2] - new pkzip version [item 3] - fixed url for arithmetic coder [item 13] - add url for DjVu, an image compression library [item 15] - remove obsolete link [item 15] - new url for DCT algorithms [item 15] - add url for lossless image compression benchmarks [item 16] - added urls for the MP3 audio compression standard, and for benchmarks of lossless audio compression programs [item 26] Contents ======== General questions: [1] What are these newsgroups about? [2] What is this .xxx file type? Where can I find the corresponding compression program? [3] What is the latest pkzip version? [4] What is an archiver? [5] What is the best general purpose compression program? [7] Which books should I read? [8] What about patents on data compression algorithms? [9] Compression of random data (WEB, Gilbert and others) [10] Fake compression programs (OWS, WIC) [11] What is the V.42bis standard? [12] I need source for the winners of the Dr Dobbs compression contest [13] I need source for arithmetic coding Image and audio compression: [15] Where can I get image compression programs? [16] What is the state of the art in lossless image compression? [17] What is the state of fractal compression? [18] I need specs and source for TIFF and CCITT group 4 Fax. [19] What is JPEG? [20] I am looking for source of an H.261/H.263 codec and MPEG [25] Fast DCT (Discrete Cosine Transform) algorithms [26] Are there algorithms and standards for audio compression? Common problems: [30] My archive is corrupted! [31] pkunzip reports a CRC error! [32] VMS zip is not compatible with pkzip! [33] I have a problem with Stacker or DoubleSpace! Questions which do not really belong to comp.compression: [50] What is this 'tar' compression program? [51] I need a CRC algorithm [52] What about those people who continue to ask frequently asked questions? [53] Where are FAQ lists archived? [54] I need specs for graphics formats [55] Where can I find Lenna and other images? [56] I am looking for a message digest algorithm [57] I have lost my password on a .zip file Part 2: (Long) introductions to data compression techniques [70] Introduction to data compression (long) Huffman and Related Compression Techniques Arithmetic Coding Substitutional Compressors The LZ78 family of compressors The LZ77 family of compressors [71] Introduction to MPEG (long) What is MPEG? Does it have anything to do with JPEG? Then what's JBIG and MHEG? What has MPEG accomplished? So how does MPEG I work? What about the audio compression? So how much does it compress? What's phase II? When will all this be finished? How do I join MPEG? How do I get the documents, like the MPEG I draft? [72] What is wavelet theory? [73] What is the theoretical compression limit? [74] Introduction to JBIG [75] Introduction to JPEG [76] What is Vector Quantization? [77] Introduction to Fractal compression [78] The Burrows-Wheeler block sorting algorithm Part 3: (Long) list of image compression hardware [85] Image compression hardware [99] Acknowledgments Search for "Subject: [#]" to get to question number # quickly. Some news readers can also take advantage of the message digest format used here. If you know very little about data compression, read question 70 in part 2 first.
Subject: [1] What are these newsgroups about? comp.compression is the place to discuss about data compression, both lossless (for text or data) and lossy (for images, sound, etc..). comp.compression.research was created later to provide a forum for current research on data compression and data compression algorithms; this group is now moderated. If you are not experienced in data compression, please post in comp.compression only. An archive of this newsgroup since Oct 1993 is available in ftp://spib.rice.edu/spib/news/comp.compression/ Excellent collections of compression based information are provided at http://www.internz.com/compression-pointers.html and http://www.sr3.t.u-tokyo.ac.jp/~arimura/compression_links.html If you only want to find a particular compression program for a particular operating system, please read first this FAQ and the article "How to find sources" which is regularly posted in news.answers. If you can't resist posting such a request, other groups are probably more appropriate (comp.binaries.ibm.pc.wanted, comp.os.msdos.apps, comp.sources.wanted, comp.sys.mac.wanted, comp.archives.msdos.d, comp.dsp, alt.graphics.pixutils). Please post your request in comp.compression only as a last resource. If your question is about graphics only (no compression), please post to comp.graphics.misc, *after* reading the comp.graphics FAQ (see item 54 below). For some unknown reason, many questions about graphics are incorrectly posted to comp.compression. For questions related to audio compression, check also comp.dsp. Please do not post any program in binary form to comp.compression. Very short sources can be posted, but long sources should be be posted to the specialized source groups, such as comp.sources.* or alt.sources. If the program is already available by ftp, just give the name of the ftp site and the full path name of the file. As for any newsgroups, do not post the same message separately to comp.compression and comp.compression.research.
Subject: [2] What is this .xxx file type? Where can I find the corresponding compression program? All the programs mentioned in this section are lossless. For most programs, one US and one European ftp site are given. (ftp.simtel.net and garbo.uwasa.fi) Many other sites (in particular wuarchive.wustl.edu) have the same programs. To keep this list to a reasonable size, many programs are not mentioned here. When several programs can handle the same archive format, only one of them is given. If you don't find a particular archiver here, look also in: ftp://ftp.cs.tu-berlin.de/pub/msdos/mirrors/ftp.elf.stuba.sk/pc/ ftp://garbo.uwasa.fi/pc/arcers/ ftp://ftp.fh-koblenz.de/pub/Packers/ Sources for additional lossless data compressors can be found in ftp://garbo.uwasa.fi/pc/programming/lds_11.zip ftp://ftp.simtel.net/pub/simtelnet/msdos/arcutils/lz-comp2.zip http://wwwvms.utexas.edu/~cbloom/index.html ftp://ftp.imag.fr/pub/archive/compression/codecs/ ftp://garbo.uwasa.fi/pc/turbopas/ (sources in Pascal) ftp://ftp.cs.uiowa.edu/pub/jones/compress/ (Splay tree compression) For Macintosh programs, look on ftp://wuarchive.wustl.edu/systems/mac/info-mac/ or in http://hyperarchive.lcs.mit.edu/HyperArchive.html For VM/CMS, look on ftp://vmd.cso.uiuc.edu/ For Atari, look on ftp://atari.archive.umich.edu For Amiga, look on ftp://ftp.wustl.edu/pub/aminet/util/ A general purpose lossless data compression library is available in ftp://ftp.cdrom.com/pub/infozip/zlib/ or zlib113.zip; see http://infozip.cdrom.com/pub/infozip/zlib/ for more information. Another library favoring speed over compression ratio is available at http://wildsau.idv.uni-linz.ac.at/mfx/lzo.html If you don't know how to use ftp or don't have ftp access, read the article "How to find sources" which is regularly posted in news.answers. If you can't find a program given below, a newer version probably exists in the same directory. Tell me at <jloup at gzip.org> A very short description of the compression algorithm is given for most programs. For the meaning of LZ77, LZ78 and LZW, see question 70 in part 2 of the FAQ. If you are looking for the file format of a specific compression program, look at "The File Format Collection" in http://www.wotsit.org and/or get the sources of the decompressor. For the format of uuencode, do "man 5 uuencode" on a Unix box. ext: produced by or read by .ace: ACE http://members.aol.com/mlemke6413/ace.htm .arc, .ark: arc, pkarc for MSDOS. (LZW algorithm) ftp://ftp.simtel.net/pub/simtelnet/msdos/arcers/pk361.exe ftp://garbo.uwasa.fi/pc/arcers/ arc for Unix ftp://ftp.ddj.com/packages/arc521e.tar.Z ftp://garbo.uwasa.fi/unix/arcers/ Contact: Howard Chu <hyc@highlandsun.com> arc for VMS ftp://wuarchive.wustl.edu/packages/compression/vax-vms/arc.exe for Mac ftp://wuarchive.wustl.edu/systems/mac/info-mac/cmp/ arc for Amiga ftp://ftp.funet.fi/pub/amiga/fish/001-100/ff070/arc.lha .arj: arj for MSDOS (LZ77 with hashing, plus secondary static Huffman encoding on a block basis) Contact: Robert K Jung <robjung@world.std.com> http://www.arjsoft.com ftp://ftp.simtel.net/pub/simtelnet/msdos/arcers/arj250a.exe ftp://garbo.uwasa.fi/pc/arcers/ unarj for Unix. Decompresses only. (There is no arj compressor for Unix. Don't post a request.) ftp://oak.oakland.edu/pub/misc/unix/ ftp://garbo.uwasa.fi/unix/arcers/ unarj for Mac ftp://mac.archive.umich.edu/mac/util/compression/ unarj for Amiga ftp://ftp.funet.fi/pub/amiga/utilities/archivers/ base64 (MIME encoding): This is *not* a compression issue but it keeps coming as a question on comp.compression. So: ftp://ftp.andrew.cmu.edu/pub/mpack/mpack-1.5-src.tar.Z (source) ftp://ftp.andrew.cmu.edu/pub/mpack/mpack15d.zip (MSDOS exe) ftp://wuarchive.wustl.edu/systems/mac/info-mac/cmp/ (Mac) ftp://garbo.uwasa.fi/pc/decode/ .bck: VMS BACKUP. BACKUP is *not* a compression program. Do "help backup". .bz2: bzip2 by Julian Seward (Burrows-Wheeler block sorting, see item 78) http://www.muraroa.demon.co.uk/ .cab: Microsoft Cabinets http://www.ddj.com/ftp/1997/1997.05/cabinet.zip ftp://ftp.mv.com/pub/ddj/1997/1997.05/cabinet.zip .cpt: Compact Pro for Mac and Power PC ftp://wuarchive.wustl.edu/systems/mac/info-mac/cmp/ For Unix: http://hyperarchive.lcs.mit.edu/HyperArchive/Archive/cmp/macutil-20b1-unix.shar ftp://ftp.cwi.nl/pub/dik/macutil2.0b3.shar.Z For DOS: ftp://ftp.scruz.net/users/aladdin/public/ ftp://garbo.uwasa.fi/pc/arcers/ .ddi: files made by DiskDupe (Pro) ftp://ftp.tem.nctu.edu.tw/Msdos/arcutil/unddi11u.zip ftp://ftp.tem.nctu.edu.tw/Msdos/arcutil/x2file15.zip .exe: self-extracting MSDOS executable (creates files on disk when run) Run the file, or try unzip, lha or arj on it. .exe: compressed MSDOS executable (decompresses itself in memory then runs the decompressed code). To get the original uncompressed .exe: ftp://garbo.uwasa.fi/pc/execomp/ To create such files: ftp://ftp.simtel.net/pub/simtelnet/msdos/execomp/lzexe91e.zip ftp://nic.funet.fi/pub/msdos/windows/util/winlite1.zip (for Windows) .gif: gif files are images compressed with the LZW algorithm. See the comp.graphics FAQ list for programs manipulating .gif files. See suffix .Z below for source of LZW. .gz, .z: gzip (or pack, see .z below). gzip uses the same algorithm as zip 2.0x (see below); it can also extract packed and compressed files. Contact: Jean-loup Gailly <support at gzip.org> http://www.gzip.org For Unix, MSDOS, OS/2, VMS, Atari, Amiga, Primos: ftp://prep.ai.mit.edu/pub/gnu/ (.shar or .tar.gz: source) ftp://prep.ai.mit.edu/pub/gnu/ (MSDOS self-extract) ftp://ftp.simtel.net/pub/simtelnet/msdos/compress/gzip124.zip (MSDOS) ftp://garbo.uwasa.fi/unix/arcers/ (source) ftp://ftp.cdrom.com/pub/infozip/MSDOS/ (MSDOS exe) ftp://ftp.cdrom.com/pub/infozip/WIN32/ (WIN95 & NT) ftp://ftp.cdrom.com/pub/infozip/OS2/ (OS/2) ftp://ftp.cdrom.com/pub/infozip/VMS/ (VMS exe) ftp://ftp.cdrom.com/pub/infozip/UNIX/SUN/ (Solaris 2) http://www.gzip.org/gzip123mvs.zip (MVS exe) For Mac: ftp://ivo.cps.unizar.es//Graficos/Public/SPDsoft/MacGzip_FAT_1.1.cpt.hqx http://persephone.cps.unizar.es/general/gente/spd/gzip/ (MacGzip page) .ha: ha 0.99 (improved PPMC - 4th order Markov modeling) Contact: Harri Hirvola <harri.hirvola@vaisala.infonet.com> ftp://garbo.uwasa.fi/pc/arcers/ ftp://ftp.nl.net/gopher/NLnet-connected/aipnl/ ftp://sunsite.unc.edu/pub/Linux/utils/compress/ha0999p-linux.tar.gz .hap: Hamarsoft HAP archiver (Markov modeling + arithmetic coding) Contact: feldmann@xs4all.nl or feldmann@pi.net ftp://garbo.uwasa.fi/pc/arcers/ http://www.xs4all.nl/~feldmann .hpk: hpack (archiver with strong encryption) Contact: Peter Gutmann <pgut1@cs.aukuni.ac.nz> ftp://src.doc.ic.ac.uk/computing/archiving/compress/hpack/ .hqx: Macintosh BinHex format.. (BinHex is *not* a compression program, it is similar to uuencode but handles multiple forks.) for Mac: ftp://mac.archive.umich.edu/mac/util/compression/ for Unix: http://hyperarchive.lcs.mit.edu/HyperArchive/Archive/cmp/mcvert-216.shar for MSDOS: ftp://ftp.simtel.net/pub/simtelnet/msdos/mac/ ftp://garbo.uwasa.fi/pc/unix/ .jam: JAM real-time compressor for MSDOS ftp://garbo.uwasa.fi/pc/arcers/ .lha: .lzh: lha for MSDOS (LZ77 with a trie data structure, plus secondary static Huffman coding on a block basis) ftp://ftp.simtel.net/pub/simtelnet/msdos/arcers/lha255e.exe ftp://garbo.uwasa.fi/pc/arcers/ lharc for Unix. (LZ77 with hash table and binary trees, plus secondary Huffman coding). See lha for Unix below. Warning: lharc can extract .lzh files created by lharc 1.xx but not those created by lha. lharc for VMS. Same warning as for Unix lharc. ftp://wuarchive.wustl.edu/packages/compression/vax-vms/lharc.exe lha for Unix. ftp://oak.oakland.edu/pub/misc/unix/ ftp://garbo.uwasa.fi/unix/arcers/ Contact: lha-admin@oki.co.jp or oki@fs.telcom.oki.ac.jp lha for Mac ftp://wuarchive.wustl.edu/systems/mac/info-mac/cmp/ lha for Amiga ftp://ftp.funet.fi/pub/amiga/utilities/archivers/ lha for OS/2: ftp://hobbes.nmsu.edu/pub/os2/util/archiver/lh2_222.zip MIME: see base64 above .pak: pak for MSDOS (LZW algorithm) ftp://ftp.simtel.net/pub/simtelnet/msdos/arcers/pak251.exe ftp://garbo.uwasa.fi/pc/arcers/ .pit: PackIt (Macintosh) for Mac: http://hyperarchive.lcs.mit.edu/HyperArchive/Archive/cmp/stuffit-lite-35.hqx for Unix: http://hyperarchive.lcs.mit.edu/HyperArchive/Archive/cmp/mcvert-216.shar ftp://garbo.uwasa.fi/mac/arcers/ .pp: PowerPacker (Amiga) ftp://ftp.funet.fi/pub/amiga/fish/501-600/ff561/ .rar: RAR Contact: Eugene Roshal <roshal@creabel.com> or Andrey Spasibozhko <as@hq.icb.chel.su> http://www.creabel.com/softronic/ MSDOS: ftp://ftp.simtel.net/pub/simtelnet/msdos/arcers/ rar*.exe ftp://garbo.uwasa.fi/pc/arcers/ rar*.exe ftp://ftp.kiae.su/msdos/arcers/ rar*.exe ftp://ftp.elf.stuba.sk/pub/pc/pack/ *rar2*.exe Unix: ftp://ftp.kiae.su/pub/unix/arcers/ rar*.exe Mac ftp://wuarchive.wustl.edu/systems/mac/info-mac/cmp/ ftp://ftp.creabel.com/pub/rar/ Amiga (Unrar): ftp://ftp.creabel.com/pub/rar/ .sea: self-extracting archive (Macintosh) Run the file to extract it. The self-extraction code can be removed with: ftp://mac.archive.umich.edu/mac/utilities/compressionapps/ ftp://ftp.scruz.net/users/aladdin/public/ (MS Windows, .sit only) .sdn: used by the Shareware Distribution Network. Try the decompressors for .pak or .arj (see above) .shar: Shell archive. This is not a compression program. Use "sh foo.shar" to extract on Unix. ftp://garbo.uwasa.fi/pc/unix/ (MSDOS) ftp://wuarchive.wustl.edu/systems/mac/info-mac/cmp/ (Mac) .sit: Stuffit for Macintosh for Mac: http://hyperarchive.lcs.mit.edu/HyperArchive/Archive/cmp/stuffit-lite-35.hqx for Amiga: ftp://ftp.funet.fi/pub/amiga/utilities/archivers/ for MSDOS: ftp://ftp.scruz.net/users/aladdin/public/ ftp://garbo.uwasa.fi/pc/arcers/ .?q?: Squeeze for MSDOS (do not confuse with other 'squeeze' below). Static Huffman coding. ftp://ftp.simtel.net/pub/simtelnet/msdos/starter/ (squeeze) ftp://ftp.simtel.net/pub/simtelnet/msdos/starter/ (unsqueeze) .sqz: Squeeze for MSDOS (do not confuse with other 'squeeze' above) LZ77 with hashing. ftp://ftp.simtel.net/pub/simtelnet/msdos/arcers/sqz1083e.exe ftp://garbo.uwasa.fi/pc/arcers/ .tar: tar is *not* a compression program. However, to be kind for you: for MSDOS ftp://ftp.simtel.net/pub/simtelnet/msdos/starter/ ftp://garbo.uwasa.fi/pc/unix/ for Unix tar (you have it already. To extract: tar xvf file.tar) for VMS ftp://wuarchive.wustl.edu/packages/compression/vax-vms/tar.exe for Macintosh ftp://wuarchive.wustl.edu/systems/mac/info-mac/cmp/ for Amiga: ftp://ftp.funet.fi/pub/amiga/fish/401-500/ff445/ .tar.Z, .tar-z, .taz: tar + compress For Unix: zcat file.tar.Z | tar xvf - with GNU tar: tar xvzf file.tar.Z for MSDOS: ftp://garbo.uwasa.fi/pc/unix/ (MSDOS exe) ftp://ftp.kiae.su/msdos/arcers/tar*sr.zip (sources) ftp://ftp.kiae.su/msdos/arcers/tar*_p.zip (MSDOS exe) Other OS: first uncompress (see .Z below) then untar (see .tar above) .tar.gz, .tgz, .tar-gz, .tar.z: tar + gzip For Unix: gzip -cd file.tar.gz | tar xvf - with GNU tar: tar xvzf file.tar.gz for MSDOS: ftp://ftp.simtel.net/pub/simtelnet/msdos/arcers/tar320g.zip ftp://garbo.uwasa.fi/pc/unix/ for MSDOS, Windows 95, NT & OS/2: ftp://garbo.uwasa.fi/pc/unix/ or http://till.home.ml.org/untgz.htm for Windows 95 & Windows NT: ftp://ftp.winzip.com/winzip/ or http://www.winzip.com Other OS: first uncompress (see .gz above) then untar (see .tar above) .td0: (compressed MS-DOS floppy image produced by TeleDisk) ftp://ftp.simtel.net/pub/simtelnet/msdos/diskutil/teled212.zip .uc2: UC2 for MSDOS and OS/2. (LZ77 with secondary static Huffman encoding on a block basis, and dynamic dictionaries shared among files.) Contact: desk@aip.nl ftp://garbo.uwasa.fi/pc/arcers/ (or uc2pro.exe) .z: pack or gzip (see .gz above). pack uses static Huffman coding. To extract, see .gz above. .zip: pkzip 2.04g for MSDOS. (LZ77 with hashing, plus secondary static Huffman coding on a block basis). Contact: support@pkware.com or http://www.pkware.com/ ftp://ftp.simtel.net/pub/simtelnet/msdos/zip/pkz204g.exe ftp://garbo.uwasa.fi/pc/arcers/ ftp://ftp.simtel.net/pub/simtelnet/win95/compress/pk250w32.exe (WIN95) arcutil 2.0 for VM/CMS (unzip only, not yet compatible with pkzip 2.04) ftp://vmd.cso.uiuc.edu/public.477/arcutil.* zip 1.1 for Unix, MSDOS, VMS, OS/2, ... (compatible with pkzip 1.10. For corresponding unzip, see unzip 5.32 below). ftp://ftp.cdrom.com/pub/infozip/src/ zip 2.2 and unzip 5.32 for Unix, MSDOS, VMS, OS/2, Amiga, ... Compatible with pkzip 2.04g (LZ77 with hashing, plus secondary static Huffman coding on a block basis). Contact: zip-bugs@lists.wku.edu See also http://infozip.cdrom.com/pub/infozip/ (On SGI, do not confuse with the editor also named 'zip'.) ftp://ftp.cdrom.com/pub/infozip/src/ (source) ftp://ftp.cdrom.com/pub/infozip/src/ (source) ftp://ftp.cdrom.com/pub/infozip/MSDOS/ (MSDOS exe) ftp://ftp.cdrom.com/pub/infozip/MSDOS/ (MSDOS exe) ftp://ftp.cdrom.com/pub/infozip/WIN32/ (Win95 & NT) ftp://ftp.cdrom.com/pub/infozip/WIN32/ (Win95 & NT) [The Win95 version supports long file names; MSDOS version doesn't] ftp://ftp.cdrom.com/pub/infozip/OS2/ (OS/2 exe 16&32 bit) See also AMIGA, ATARI, MAC, UNIX, RISCOS, VMS... subdirectories. ftp://ftp.icce.rug.nl/infozip/src/ (encryption source) for Macintosh: http://members.sitec.net/maczip/download/ ftp://mac.archive.umich.edu/mac/util/compression/ ftp://mac.archive.umich.edu/mac/util/compression/ ftp://ftp.cdrom.com/pub/infozip/MAC/ ftp://wuarchive.wustl.edu/systems/mac/info-mac/cmp/ WinZip by Nico Mak <support@winzip.com> (uses Info-ZIP compress. code): ftp://ftp.winzip.com/winzip/ or http://www.winzip.com (MS Windows) .zoo: zoo 2.10 for MSDOS (algorithm copied from that of lha, see lha above) ftp://ftp.simtel.net/pub/simtelnet/msdos/arcers/zoo210.exe ftp://garbo.uwasa.fi/pc/arcers/ zoo 2.10 for Unix, VMS ftp://oak.oakland.edu/pub/misc/unix/ ftp://garbo.uwasa.fi/unix/arcers/ zoo for Mac ftp://mac.archive.umich.edu/mac/utilities/compressionapps/ zoo for Amiga ftp://ftp.funet.fi/pub/amiga/utilities/archivers/ .??_: Microsoft compress.exe and expand.exe. compress.exe is available in the Windows SDK (Software Development Kit) and in ftp://ftp.microsoft.com/softlib/mslfiles/ .F: freeze for Unix (LZ77 with hashing, plus secondary dynamic Huffman encoding) ftp://wuarchive.wustl.edu/usenet/comp.sources.misc/volume35/freeze/ ftp://ftp.inria.fr/system/arch-compr/ Contact: Leonid A. Broukhis <leo@zycad.com> .Y: yabba for Unix, VMS, ... (Y coding, a variant of LZ78) ftp://wuarchive.wustl.edu/usenet/comp.sources.unix/volume24/yabbawhap/ ftp://ftp.inria.fr/system/arch-compr/ Contact: Dan Bernstein <djb@silverton.berkeley.edu> .Z: compress for Unix ('the' LZW algorithm) It is likely that your Unix system has 'compress' already. Otherwise: ftp://wuarchive.wustl.edu/packages/compression/ (not in .Z format to avoid chicken and egg problem) compress for MSDOS ftp://ftp.simtel.net/pub/simtelnet/msdos/compress/comp430d.zip ftp://garbo.uwasa.fi/pc/unix/ ftp://garbo.uwasa.fi/pc/source/comp430s.zip compress for Macintosh ftp://wuarchive.wustl.edu/systems/mac/info-mac/cmp/ compress for Amiga ftp://ftp.funet.fi/pub/amiga/utilities/archivers/ compress for VAX/VMS ftp://wuarchive.wustl.edu/packages/compression/vax-vms/lzcomp.exe ftp://wuarchive.wustl.edu/packages/compression/vax-vms/lzdcmp.exe
Subject: [3] What is the latest PKZIP version? The latest official DOS version is 2.04g. The latest command line version for Windows 95 is 2.50. The latest Windows 95 version is 2.70. See http://www.pkware.com for more information. Be warned that there are countless bogus PKZIP 1.20, 2.0, 2.02, 3.00B, 3.05, 4.1 and whatever scams floating around. They usually are hacks of PKZIP 1.93A beta test version. Some of them are trojans and / or carry computer viruses. Note about pkzip 2.06 from a PKware employee: Version 2.06 was released as an INTERNAL use only IBM version. It is identical to 2.04G, but it has IBM names in the help screens and such. That release is meant for IBM only. If pkunzip indicates that you need version 2.8 to extract an archive, your archive has been corrupted by a transfer not made in binary mode (see item 30 below).
Subject: [4] What is an archiver? There is a distinction between archivers and other compression programs: - an archiver takes several input files, compresses them and produces a single archive file. Examples are arc, arj, lha, zip, zoo. - other compression programs create one compressed file for each input file. Examples are freeze, yabba, compress, gzip. Such programs are often combined with tar to create compressed archives (see question 50: "What is this tar compression program?"). For a comparison of zip and gzip, see the gzip README file. (In short: zip is an archiver, gzip is not; only zip is compatible with pkzip.)
Subject: [5] What is the best general purpose compression program? The answer is: it depends. (You did not expect a definitive answer, did you?) It depends whether you favor speed, compression ratio, a standard and widely used archive format, the number of features, etc... Just as for text editors, personal taste plays an important role. compress has 4 options, arj 2.30 has about 130 options; different people like different programs. *Please* do not start or continue flame wars on such matters of taste. Several benchmarks of MSDOS archivers are available: - ftp://ftp.simtel.net/pub/simtelnet/msdos/arcers/actest*.zip and http://www.geocities.com/SiliconValley/Park/4264/act.html by Jeff Gilchrist <jeffg@cips.ca> - ftp://garbo.uwasa.fi/pc/arcers/ by Jonathan Burt <jonathan@jaburt.demon.co.uk> Please do not post your own benchmarks made on your own files that nobody else can access. If you think that you must absolutely post yet another benchmark, make sure that your test files are available by anonymous ftp. Since all other benchmarks are for MSDOS only, here is one mainly for Unix, on a 33Mhz Compaq 386. All programs have been run on Unix SVR4, except pkzip and arj which only run on MSDOS. The programs compared here were chosen because they are the most popular or because they run on Unix and source is available. For ftp information, see above. Three programs (hpack, comp-2 and ha) have been added because they achieve better compression (at the expense of speed) and one program (lzrw3-a) has been added because it favors speed at the expense of compression: - comp-2 is in ftp://ftp.coast.net/pub/Coast/disk2/msdos/ddjmag/ (inner zip file nelson.zip), - hpack is in ftp://garbo.uwasa.fi/unix/arcers/ - ha 0.98 is in ftp://garbo.uwasa.fi/pc/arcers/ - lzrw3-a is in http://wwwvms.utexas.edu/~cbloom/src/lzrw.zip The 14 files used in the comparison are from the standard Calgary Text Compression Corpus, available in ftp://ftp.cpsc.ucalgary.ca/pub/projects/text.compression.corpus/ The whole corpus includes 18 files, but the 4 files paper[3-6] are generally omitted in benchmarks. It contains several kinds of file (ascii, binary, image, etc...) but has a bias towards large files. You may well get different ratings on the typical mix of files that you use daily, so keep in mind that the comparisons given below are only indicative. The programs are ordered by decreasing total compressed size. For a fair comparison between archivers and other programs, this size is only the size of the compressed data, not the archive size. The programs were run on an idle machine, so the elapsed time is significant and can be used to compare Unix and MSDOS programs. [Note: These benchmarks are now *very* old. I have to do them again on more recent hardware with the latest programs. For recent results on MSDOS, check http://www.geocities.com/SiliconValley/Park/4264/act.html ] size lzrw3a compress lharc yabba pkzip freeze version: 4.0 1.02 1.0 1.10 2.3.5 options: -m300000 ------ ----- ------ ------ ------ ------ ------ bib 111261 49040 46528 46502 40456 41354 41515 book1 768771 416131 332056 369479 306813 350560 344793 book2 610856 274371 250759 252540 229851 232589 230861 geo 102400 84214 77777 70955 76695 76172 68626 news 377109 191291 182121 166048 168287 157326 155783 obj1 21504 12647 14048 10748 13859 10546 10453 obj2 246814 108040 128659 90848 114323 90130 85500 paper1 53161 24522 25077 21748 22453 20041 20021 paper2 82199 39479 36161 35275 32733 32867 32693 pic 513216 111000 62215 61394 65377 63805 53291 progc 39611 17919 19143 15399 17064 14164 14143 progl 71646 24358 27148 18760 23512 17255 17064 progp 49379 16801 19209 12792 16617 11877 11686 trans 93695 30292 38240 28092 31300 23135 22861 3,141,622 1,400,105 1,259,141 1,200,580 1,159,340 1,141,821 1,109,290 real 0m35s 0m59s 5m03s 2m40s 5m27s user 0m25s 0m29s 4m29s 1m46s 4m58s sys 0m05s 0m10s 0m07s 0m18s 0m08s MSDOS: 1m39s zoo lha arj pkzip zip hpack comp-2 ha 2.10 1.0(Unix) 2.30 2.04g 1.9 0.75a 0.98 ah 2.13(MSDOS) -jm -ex -6 a2 ------ ------ ------ ------ ------- ------ ------ ------ bib 40742 40740 36090 35126 34950 35619 29840 26927 book1 339076 339074 318382 312490 312619 306876 237380 235733 book2 228444 228442 210521 206513 206306 208486 174085 163535 geo 68576 68574 69209 68706 68418 58976 64590 59356 news 155086 155084 146855 144545 144395 141608 128047 123335 obj1 10312 10310 10333 10306 10295 10572 10819 9799 obj2 84983 84981 82052 81132 81336 80806 85465 80381 paper1 19678 19676 18710 18531 18525 18607 16895 15675 paper2 32098 32096 30034 29568 29674 29825 25453 23956 pic 52223 52221 53578 52409 55051 51778 55461 51639 progc 13943 13941 13408 13341 13238 13475 12896 11795 progl 16916 16914 16408 16122 16175 16586 17354 15298 progp 11509 11507 11308 11200 11182 11647 11668 10498 trans 22580 22578 20046 19462 18879 20506 21023 17927 1,096,166 1,096,138 1,036,934 1,019,451 1,021,043 1,005,367 890,976 845,854 real 4m07s 6m03s 1m49s 1h22m17s 27m05s user 3m47s 4m23s 1m43s 1h20m46s 19m27s sys 0m04s 0m08s 0m02s 0m12s 2m03s MSDOS: 1m49s 2m41s 1m43s 14m43s Notes: - the compressed data for 'zoo ah' is always two bytes longer than for lha. This is simply because both programs are derived from the same source (ar002, written by Haruhiko Okumura, available by ftp in ftp://ftp.simtel.net/pub/simtelnet/msdos/arcers/ar002.zip). - hpack 0.75a gives slightly different results on SunOS. (To be checked with latest version of hpack). - the MSDOS versions are all optimized with assembler code and were run on a RAM disk. So it is not surprising that they often go faster than their Unix equivalent.
Subject: [7] Which books should I read? [BWC 1989] Bell, T.C, Cleary, J.G. and Witten, I.H, "Text Compression", Prentice-Hall 1989. ISBN: 0-13-911991-4. Price: approx. US$60 The reference on text data compression. [Nel 1996] Mark Nelson & Jean-loup Gailly, "The Data Compression Book", 2nd edition. M&T Books, New York, NY 1996. ISBN 1-55851-434-1 541 pages. List price in the US is $39.95 including one PC-compatible disk bearing all the source code printed in the book. A practical introduction to data compression. The book is targeted at a person who is comfortable reading C code but doesn't know anything about data compression. Its stated goal is to get you up to the point where you are competent to program standard compression algorithms. [Will 1990] Williams, R. "Adaptive Data Compression", Kluwer Books, 1990. ISBN: 0-7923-9085-7. Price: US$75. Reviews the field of text data compression and then addresses the problem of compressing rapidly changing data streams. [Stor 1988] Storer, J.A. "Data Compression: Methods and Theory", Computer Science Press, Rockville, MD. ISBN: 0-88175-161-8. A survey of various compression techniques, mainly statistical non-arithmetic compression and LZSS compression. Includes complete Pascal code for a series of LZ78 variants. [Stor 1992] Storer, J.A. "Image and Text Compression", Kluwer Academic Publishers, 1992, ISBN 0-7923-9243-4 [Say 1996] Sayood, Khalid. "Introduction to Data Compression", San Francisco: Morgan Kaufmann Publishers, 1996. ISBN 1-55860-346-8; US&Canada $64.95. More info in http://www.mkp.com/pages/3468/index.html The book covers both lossy and lossless compression techniques and their applications to image, speech, text, audio, and video compression. [HHJ 1997] Darrel Hankerson, Greg A. Harris, and Peter D. Johnson Jr. "Introduction to Information Theory and Data Compression", 1997. ISBN 0-8493-3985-5 http://www.dms.auburn.edu/compression/ [DS 1997] David Salomon, "Data Compression: The Complete Reference" Springer, 1997, ISBN 0-387-98280-9. Price: US$ 39.95. [BK 95] Bhaskaran V. and Konstantinides K., "Image and Video Compression Standards: Algorithms and Architectures", Kluwer Academic Publishers, 1995. ISBN 0-7923-9591-3 [ACG 1991] Advances in Speech Coding, edited by Atal, Cuperman, and Gersho, Kluwer Academic Press, 1991. [GG 1991] Vector Quantization and Signal Compression, by Gersho and Gray, Kluwer Acad. Press, 1991, ISBN 0-7923-9181-0. [CT 1991] Elements of Information Theory, by T.M.Cover and J.A.Thomas John Wiley & Sons, 1991. ISBN 0-471-06259-6. Review papers: [BWC 1989] Bell, T.C, Witten, I.H, and Cleary, J.G. "Modeling for Text Compression", ACM Computing Surveys, Vol.21, No.4 (December 1989), p.557 A good general overview of compression techniques (as well as modeling for text compression); the condensed version of "Text Compression". [Lele 1987] Lelewer, D.A, and Hirschberg, D.S. "Data Compression", ACM Computing Surveys, Vol.19, No.3 (September 1987), p.261. A survey of data compression techniques which concentrates on Huffman compression and makes only passing mention of other techniques. Bibliographies for Image Compression are available at http://www.dip.ee.uct.ac.za/~brendt/bibliographies/
Subject: [8] What about patents on data compression algorithms? [Note: the appropriate group for discussing software patents is comp.patents or misc.legal.computing, not comp.compression.] Only a very small subset of all patents on data compression are mentioned here; there are several hundred patents on lossless data compression alone. All patents mentioned here are US patents, and thus probably not applicable outside the US. The abstracts and claims of all recent US patents can be obtained from http://patent.womplex.ibm.com/ See item 70, "Introduction to data compression" for the meaning of LZ77, LZ78 or LZW. (a) Run length encoding - Tsukiyama has two patents on run length encoding: 4,586,027 and 4,872,009 granted in 1986 and 1989 respectively. The first one covers run length encoding in its most primitive form: a length byte followed by the repeated byte. The second patent covers the 'invention' of limiting the run length to 16 bytes and thus the encoding of the length on 4 bits. Here is the start of claim 1 of patent 4,872,009, just for pleasure: 1. A method of transforming an input data string comprising a plurality of data bytes, said plurality including portions of a plurality of consecutive data bytes identical to one another, wherein said data bytes may be of a plurality of types, each type representing different information, said method comprising the steps of: [...] - O'Brien has patented (4,988,998) run length encoding followed by LZ77. (b) LZ77 - Waterworth patented (4,701,745) the algorithm now known as LZRW1, because Ross Williams reinvented it later and posted it on comp.compression on April 22, 1991. (See item 5 for the ftp site with all LZRW derivatives.) The *same* algorithm has later been patented by Gibson & Graybill (see below). The patent office failed to recognize that the same algorithm was patented twice, even though the wording used in the two patents is very similar. The Waterworth patent is now owned by Stac Inc, which won a lawsuit against Microsoft, concerning the compression feature of MSDOS 6.0. Damages awarded were $120 million. (Microsoft and Stac later settled out of court.) - Fiala and Greene obtained in 1990 a patent (4,906,991) on all implementations of LZ77 using a tree data structure. Claim 1 of the patent is much broader than the algorithms published by Fiala and Greene in Comm.ACM, April 89. The patent covers the algorithm published by Rodeh and Pratt in 1981 (J. of the ACM, vol 28, no 1, pp 16-24). It also covers the algorithms used in lharc, lha and zoo. - Notenboom (from Microsoft) 4,955,066 uses three levels of compression, starting with run length encoding. - The Gibson & Graybill patent 5,049,881 covers the LZRW1 algorithm previously patented by Waterworth and reinvented by Ross Williams. Claims 4 and 12 are very general and could be interpreted as applying to any LZ algorithm using hashing (including all variants of LZ78): 4. A compression method for compressing a stream of input data into a compressed stream of output data based on a minimum number of characters in each input data string to be compressed, said compression method comprising the creation of a hash table, hashing each occurrence of a string of input data and subsequently searching for identical strings of input data and if such an identical string of input data is located whose string size is at least equal to the minimum compression size selected, compressing the second and all subsequent occurrences of such identical string of data, if a string of data is located which does not match to a previously compressed string of data, storing such data as uncompressed data, and for each input strings after each hash is used to find a possible previous match location of the string, the location of the string is stored in the hash table, thereby using the previously processed data to act as a compression dictionary. Claim 12 is identical, with 'method' replaced with 'apparatus'. Since the 'minimal compression size' can be as small as 2, the claim could cover any dictionary technique of the LZ family. However the text of the patent and the other claims make clear that the patent should cover the LZRW1 algorithm only. (In any case the Gibson & Graybill patent is likely to be invalid because of the prior art in the Waterworth patent.) - Phil Katz, author of pkzip, also has a patent on LZ77 (5,051,745) but the claims only apply to sorted hash tables, and when the hash table is substantially smaller than the window size. - IBM patented (5,001,478) the idea of combining a history buffer (the LZ77 technique) and a lexicon (as in LZ78). - Stac Inc patented (5,016,009 and 5,126,739) yet another variation of LZ77 with hashing. The '009 patent was used in the lawsuit against Microsoft (see above). Stac also has a patent on LZ77 with parallel lookup in hardware (5,003,307). - Robert Jung, author of 'arj', has been granted patent 5,140,321 for one variation of LZ77 with hashing. This patent is very close to the LZRW3-A algorithm, also previously discovered by Ross Williams. LZRW3-A was posted on comp.compression on July 15, 1991. The patent was filed two months later on Sept 4, 1991. Microsoft has patented a similar idea (two level table with pseudo-LRU managment of slots inside the level-2 table) in 5,455,577 (filed in 1993). - Chambers 5,155,484 is yet another variation of LZ77 with hashing. The hash function is just the juxtaposition of two input bytes, this is the 'invention' being patented. The hash table is named 'direct lookup table'. (c) LZ78 - One form of the original LZ78 algorithm was patented (4,464,650) by its authors Lempel, Ziv, Cohn and Eastman. This patent is owned by Unisys. - The LZW algorithm used in 'compress' is patented by IBM (4,814,746) and Unisys (4,558,302). It is also used in the V.42bis compression standard (see question 11 on V.42bis below), in Postscript Level 2, in GIF and TIFF. Unisys sells the license to modem manufacturers for a onetime fee (contact: Welch Patent Desk, Unisys Corp., P.O. Box 500, Bluebell, PA 19424 Mailcode C SW 19). CompuServe is licensing the usage of LZW in GIF products for 1.5% of the product price, of which 1% goes to Unisys; usage of LZW in non-GIF products must be licensed directly from Unisys. For more information, see http://www.unisys.com/ or email to lzw_info@unisys.com. The IBM patent application was first filed three weeks before that of Unisys, but the US patent office failed to recognize that they covered the same algorithm. (The IBM patent is more general, but its claim 7 is exactly LZW.) - Klaus Holtz also claims that patent 4,366,551 for his "autosophy" data compression method covers LZ78 and LZW. According to Holtz, most of the largest V.42bis modem manufacturers have paid for patent licenses. - AP coding is patented by Storer (4,876,541). (Get the yabba package for source code, see question 2 above, file type .Y) Storer also claims that his patent covers V.42bis. (d) arithmetic coding - IBM holds many patents on arithmetic coding (4,122,440 4,286,256 4,295,125 4,463,342 4,467,317 4,633,490 4,652,856 4,792,954 4,891,643 4,901,363 4,905,297 4,933,883 4,935,882 5,045,852 5,099,440 5,142,283 5,210,536 5,414,423 5,546,080). It has patented in particular the Q-coder implementation of arithmetic coding. The JBIG standard, and the arithmetic coding option of the JPEG standard requires use of the patented algorithm. No JPEG-compatible method is possible without infringing the patent, because what IBM actually claims rights to is the underlying probability model (the heart of an arithmetic coder). (See item 75 for details.) See also below details on many other patents on arithmetic coding (4,973,961 4,989,000 5,023,611 5,025,258 5,272,478 5,307,062 5,309,381 5,311,177 5,363,099 5,404,140 5,406,282 5,418,532). The list is not exhaustive. (e) predictor - The 'predictor' algorithm was first described in the paper Raita, T. and Teuhola, J. (1987), "Predictive text compression by hashing", ACM Conference on Information Retrieval This algorithm has been patented (5,229,768) by K. Thomas in 1993. It is used in the Internet Draft "PPP Predictor Compression Protocol" (see ftp://venera.isi.edu/internet-drafts/). (f) compression of random data - The US patent office no longer grants patents on perpetual motion machines, but has recently granted a patent on a mathematically impossible process (compression of truly random data): 5,533,051 "Method for Data Compression". See item 9.5 of this FAQ for details. As can be seen from the above list, some of the most popular compression programs (compress, pkzip, zoo, lha, arj) are now covered by patents. (This says nothing about the validity of these patents.) Here are some references on data compression patents. Some of them are taken from the list ftp://prep.ai.mit.edu/pub/lpf/patent-list. 3,914,586 Data compression method and apparatus filed 10/25/73, granted 10/21/75 General Motors Corporation, Detroit MI Duane E. McIntosh, Santa Ynez CA Data compression apparatus is disclosed is operable in either a bit pair coding mode of a word coding mode depending on the degree of redundancy of the data to be encoded. 3,976,844 Data communication system for transmitting data in compressed form filed Apr. 4, 1975, granted Aug. 24, 1976 inventor Bernard K. Betz, assignee Honeywell Information Systems, Inc. [encode differences with previous line] 4,021,782 Data compaction system and apparatus inventor Hoerning filed 04/30/1975, granted 05/03/1977 [A primitive form of LZ77 with implicit offsets (compare with previous record)] 4,054,951 Data expansion apparatus inventor R.D. Jackson, assignee IBM filed Jun. 30, 1976, granted Oct. 18, 1977 [Covers only decompression of data compressed with a variant of LZ77.] 4,087,788 Data compression system filed 1/14/77, granted 5/2/78 NCR Canada LTD - NCR Canada Ltee, Mississauga CA Brian J. Johannesson, Waterloo CA A data compression system is disclosed in which the left hand boundary of a character is developed in the form of a sequence of Freeman direction codes, the codes being stored in digital form within a processor. 4,122,440 Method and means for arithmetic string coding assignee IBM filed 1977/03/04, granted 1978/10/24 [This is the basic idea of arithmetic coding. Note that the patent is expired now.] 4,286,256 Method and means for arithmetic coding using a reduced number of operations. granted Aug 25, 1981 assignee IBM 4,295,125 A method and means for pipeline decoding of the high to low order pairwise combined digits of a decodable set of relatively shifted finite number of strings granted Oct 13, 1981 assignee IBM 4,366,551 Associative Memory Search System filed June 16, 1975, granted Dec. 28, 1982. inventor Klaus Holtz, assignee Omni Dimensional Networks. 4,412,306 System for minimizing space requirements for storage and transmission of digital signals filed May 14, 1981, granted Oct. 25, 1983 inventor Edward W. Moll 4,463,342 A method and means for carry-over control in a high order to low order combining of digits of a decodable set of relatively shifted finite number strings. granted Jul 31, 1984 assignee IBM 4,491,934 Data compression process filed May 12, 1982, granted Jan. 1, 1985 inventor Karl E. Heinz 4,464,650 Apparatus and method for compressing data signals and restoring the compressed data signals inventors Lempel, Ziv, Cohn, Eastman assignee Sperry Corporation (now Unisys) filed 8/10/81, granted 8/7/84 A compressor parses the input data stream into segments where each segment comprises a prefix and the next symbol in the data stream following the prefix. [This is the original LZ78 algorithm.] 4,467,317 High-speed arithmetic compression using using concurrent value updating. granted Aug 21, 1984 assignee IBM 4,494,108 Adaptive source modeling for data file compression within bounded memory filed Jun. 5, 1984, granted Jan. 15, 1985 invntors Glen G. Langdon, Jorma J. Rissanen assignee IBM order 1 Markov modeling 4,558,302 High speed data compression and decompression apparatus and method inventor Welch assignee Sperry Corporation (now Unisys) filed 6/20/83, granted 12/10/85 re-examined: filed 12/14/92, granted 4/1/94. The text of the original 1985 patent can be ftped from ftp://ftp.uni-stuttgart.de/pub/doc/comp-patents/US4558302.Z There is also a European Patent 0,129,439 1/2/89 for DE, FR, GB, IT and patent pending for Japan. 4,560,976 Data compression filed 6/5/84, granted 12/24/85 Codex Corporation, Mansfield MA Steven G. Finn, Framingham, MA A stream of source characters, which occur with varying relative frequencies, is encoded into a compressed stream of codewords, each having one, two or three subwords, by ranking the source characters by their current frequency of appearance, encoding the source characters having ranks no higher than a first number as one subword codewords, source characters having ranks higher than the first number but no higher than a second number as two subword codewords, and the remaining source characters as three subword codewords. 4,586,027 Method and system for data compression and restoration inventor Tsukimaya et al. assignee Hitachi filed 08/07/84, granted 04/29/86 patents run length encoding 4,597,057 System for compressed storate of 8-bit ascii bytes using coded strings of 4-bit nibbles. inventor Snow, assignee System Development corporation. filed 12/31/1981, granted 06/24/1986. Compression using static dictionary of common words, prefixes and suffixes. 4,612,532 Data compression apparatus and method inventor Bacon, assignee Telebyte Corportion filed Jun. 19, 1984, granted Sep. 16, 1986 [Uses followsets as in the pkzip 0.92 'reduce' algorithm, but the followsets are dynamically updated. This is in effect a sort of order-1 Markov modeling.] 4,622,545 Method and apparatus for image compression and Manipulation inventor William D. Atkinson assignee Apple computer Inc. filed 9/30/82 granted 11/11/86 4,633,490 Symmetrical adaptive data compression/decompression system. granted Dec 30, 1985 assignee IBM 4,652,856 A multiplication-free multi-alphabet arithmetic code. granted Feb 4, 1986 assignee IBM 4,667,649 Data receiving apparatus filed 4/18/84, granted 6/30/87 inventors Kunishi et al. assignee Canon Kabushiki Kaisha, Tokyo Japan compression of Fax images. 4,682,150 Data compression method and apparatus inventors Mathes and Protheroe, assignee NCR Corporation, Dayton OH A system and apparatus for compressing redundant and nonredundant binary data generated as part of an operation of a time and attendance terminal in which the data represents the time an employee is present during working hours. 4,701,745 Data compression system inventor Waterworth John R assignee Ferranti PLC GB, patent rights now acquired by Stac Inc. filed 03/03/1986 (03/06/1985 in GB), granted 10/20/1987 Algorithm now known as LZRW1 (see above) I claim: 1. A data compression system comprising an input store for receiving and storing a plurality of bytes of uncompressed data from an outside source, and data processing means for processing successive bytes of data from the input store; the data processing means including circuit means operable to check whether a sequence of successive bytes to be processed identical with a sequence of bytes already processed, and including hash generating means responsive to the application of a predetermined number of bytes in sequence to derive a hash code appropriate to those bytes, a temporary store in which the hash code may represent the address of a storage location, and a pointer counter operable to store in the temporary store at said address a pointer indicative of the position in the input store of one of the predetermined number of bytes; output means operable to apply to a transfer medium each byte of data not forming part of such an identical sequence; and encoding means responsive to the identification of such a sequence to apply to the transfer medium an identification signal which identifies both the location in the input store of the previous occurrence of the sequence of bytes and the number of bytes contained in the sequence. 4,730,348 Adaptive data compression system inventor MacCrisken, assignee Adaptive Computer Technologies filed Sep. 19, 1986, granted Mar. 8, 1988 [order-1 Markov modeling + Huffman coding + LZ77] 4,758,899 Data compression control device inventor Tsukiyama, assignee Hitachi filed 11/20/1985, granted 07/19/1988 Limits compression to ensure that tape drive stays busy. 4,792,954 Concurrent detection of errors in arithmetic data compression coding assignee IBM filed 1986/10/31, granted 1988/12/20 4,809,350 Data compression system filed Jan. 30, 1987, granted Feb. 28, 1989 inventor Yair Shimoni & Ron Niv assignee Elscint Ltd., Haifa, Israel [Image compression via variable length encoding of differences with predicted data.] 4,814,746 Data compression method inventors Victor S. Miller, Mark N. Wegman assignee IBM filed 8/11/86, granted 3/21/89 A previous application was filed on 6/1/83, three weeks before the application by Welch (4,558,302) Communications between a Host Computing System and a number of remote terminals is enhanced by a data compression method which modifies the data compression method of Lempel and Ziv by addition of new character and new string extensions to improve the compression ratio, and deletion of a least recently used routine to limit the encoding tables to a fixed size to significantly improve data transmission efficiency. 4,841,092 continued in 5,003,307 4,853,696 Code converter for data compression/decompression filed 4/13/87, granted 8/1/89 inventor Amar Mukherjee, Maitland FL assignee University of Central Florida, Orlando FL Another hardware Huffman encoder: A code converter has a network of logic circuits connected in reverse binary tree fashion with logic paths between leaf nodes and a common root node. 4,872,009 Method and apparatus for data compression and restoration inventor Tsukimaya et al. assignee Hitachi filed 12/07/87, granted 10/03/89 This patent on run length encoding covers the 'invention' of limiting the run length to 16 bytes and thus the encoding of the length on 4 bits. 4,876,541 Stem [sic] for dynamically compressing and decompressing electronic data filed 10/15/87, granted 10/24/89 inventor James A. Storer assignee Data Compression Corporation A data compression system for encoding and decoding textual data, including an encoder for encoding the data and for a decoder for decoding the encoded data. 4,891,643 Arithmetic coding data compression/de-compression by selectively employed, diverse arithmetic encoders and decoders. file 1986/09/15, granted 1990/01/02 assignee IBM 4,901,363 System for compressing bi-level data assignee IBM [arithmetic coding] 4,905,297 Arithmetic coding encoder and decoder system. granted Feb 27, 1990 assignee IBM 4,906,991 Textual substitution data compression with finite length search window filed 4/29/1988, granted 3/6/1990 inventors Fiala,E.R., and Greene,D.H. assignee Xerox Corporation extended in 5,058,144 4,933,883 Probability adaptation for arithmetic coders. granted Jun 12, 1990 assignee IBM 4,935,882 Probability adaptation for arithmetic coders. granted Jun 19, 1990 assignee IBM 4,941,193 Barnsley, fractal compression. 4,943,869 Compression Method for Dot Image Data filed 1988-05-04, granted 1990-07-24 assignee Fuji Photo Film Co. Lossy and lossless image compression schemes. 4,955,066 Compressing and Decompressing Text Files filed 10/13/89, granted 09/04/90 inventor Notenboom, L.A. assignee Microsoft Now extended as 5,109,433 [Noted in signon screen of Word 5.5 and on the outside of the MS-DOS 5.0 Upgrade.] A method of compressing a text file in digital form is disclosed. A full text file having characters formed into phrases is provided by an author. The characters are digitally represented by bytes. A first pass compression is sequentially followed by a second pass compression of the text which has previously been compressed. A third or fourth level of compression is serially performed on the compressed text. For example, in a first pass, the text is run-length compressed. In a second pass, the compressed text is further compressed with key phrase compression. In a third pass, the compressed text is further compressed with Huffman compression. The compressed text is stored in a text file having a Huffman decode tree, a key phrase table, and a topic index. The data is decompressed in a single pass and provided one line at a time as an output. Sequential compressing of the text minimizes the storage space required for the file. Decompressing of the text is performed in a single pass. As a complete line is decompressed, it is output rapidly, providing full text to the user. 4,973,961 Method and apparatus for carry-over control in arithmetic coding. granted Nov 27, 1990 assignee AT&T 4,988,998 Data compression system for successively applying at least two data compression methods to an input data stream. inventor O'Brien assignee Storage Technology Corporation, Louisville, Colorado filed Sep 5, 1989, granted Jan 29, 1991. Run length encoding followed by LZ77. 4,989,000 Data string compression using arithmetic encoding with simplified probability subinterval estimation filed 1989/06/19, granted 1991/01/29] [shift & add instead of multiply] 5,001,478 Method of Encoding Compressed Data filed 12/28/89, granted 03/19/91 inventor Michael E. Nagy assignee IBM 1. A method of encoding a compressed data stream made up of a sequence of literal references, lexicon references and history references, which comprises the steps of: assigning to each literal reference a literal identifier; assigning to each history reference a history identifier; assigning to each lexicon reference a lexicon identifier; and emitting a data stream with said identifiers assigned to said references. Gordon Irlam <gordoni@cs.adelaide.edu.au> says: The invention can probably be best understood by considering the decompressor. It consists of a history buffer, and a lexicon buffer, both of which are initially empty. The history buffer contains the last n symbols emitted. Whenever a history buffer reference is to be output the string so referenced is subsequently moved to the lexicon buffer for future reference. Thus the history buffer keeps track of strings that may be repeated on a very short term basis, while the lexicon buffer stores items for a longer time. Furthermore a history reference involves specifying both the offset and length within the history buffer, whereas a lexicon reference simply specifies a number denoting the string. Both buffers have a finite size. 5,003,307 Data compression apparatus with shift register search means filed Oct. 6, 1989, granted Mar. 26, 1991 inventors George Glen A, Ivey Glen E, Whiting Douglas L assignee Stac Inc continuation of 4,841,092 5,016,009 Data compression apparatus and method filed 01/13/1989, granted 05/14/1991 inventors George Glen A, Ivey Glen E, Whiting Douglas L assignee Stac Inc LZ77 with offset hash table (extended in 5,126,739) 5,023,611 Entropy encoder/decoder including a context extractor. granted Jun 11, 1991 assignee AT&T 5,025,258 Adaptive probability estimator for entropy encoder/decoder. granted Jun 18, 1991 assignee AT&T 5,045,852 Dynamic model selection during data compression assignee IBM [arithmetic coding] 5,049,881 Apparatus and method for very high data rate-compression incorporating lossless data compression and expansion utilizing a hashing technique inventors Dean K. Gibson, Mark D. Graybill assignee Intersecting Concepts, Inc. filed 6/18/90, granted 9/17/91 [covers lzrw1, almost identical with Waterworth 4,701,745] 5,051,745 String searcher, and compressor using same filed 8/21/90, granted 9/24/91 inventor Phillip W. Katz (author of pkzip) In the string search method and apparatus pointers to the string to be searched are indexed via a hashing function and organized according to the hashing values of the string elements pointed to. The hashing function is also run on the string desired to be found, and the resulting hashing value is used to access the index. If the resulting hashing value is not in the index, it is known that the target string does not appear in the string being searched. Otherwise the index is used to determine the pointers which correspond to the target hashing value, these pointers pointing to likely candidates for matching the target string. The pointers are then used to sequentially compare each of the locations in the string being searched to the target string, to determine whether each location contains a match to the target string. In the method and apparatus for compressing a stream of data symbols, a fixed length search window, comprising a predetermined contiguous portion of the symbol stream, is selected as the string to be searched by the string searcher. If a string to be compressed is found in the symbol stream, a code is output designating the location within the search window of the matching string and the length of the matching string. 5,065,447 (continued in 5,347,600) Method and apparatus for processing digital data filed Jul. 5, 1989, granted Nov. 12, 1991 inventors Michael F. Barnsley and Alan D. Sloan [Patents image compression with the "Fractal Transform"] 5,099,440 Probability adaptation for arithmetic coders 5,109,433 Compressing and decompressing text files inventor Notenboom assignee Microsoft extension of 4,955,066 5,126,739 Data Compression Apparatus and Method filed Nov. 27, 1990, granted June 30, 1992. inventor Whiting et. al assignee Stac Inc LZ77 with offset hash table (extension of 5,016,009) 5,140,321 Data compression/decompression method and apparatus filed 9/4/91, granted 8/18/92 inventor Robert Jung assignee Prime Computer 5,142,283 Arithmetic compression coding using interpolation for ambiguous symbols filed 1990/07/10, granted 1992/08/25 assignee IBM 5,155,484 Fast data compressor with direct lookup table indexing into history buffer filed 9/13/1991, granted 10/13/1992 inventor Chambers, IV, Lloyd L., Menlo Park, California assignee Salient Software, Inc., Palo Alto, California (02) Uses a 64K hash table indexed by the first two characters of the input string. Includes several claims on the LZ77 file format (literal or pair offset,length). 5,179,378 file Jul. 30, 1991, granted Jan. 12, 1993 inventor Ranganathan assignee University of South Florida Method and apparatus for the compression and decompression of data using Lempel-Ziv based techniques. [This covers LZ77 hardware compression with a systolic array of processors working in parallel.] 5,210,536 Data compression/coding method and device for implementing said method assignee IBM [PPM + arithmetic coding] 5,229,768 Adaptive data compression system granted Jul. 20, 1993 inventor Kasman E. Thomas assignee Traveling Software, Inc. A system for data compression and decompression is disclosed. A series of fixed length overlapping segments, called hash strings, are formed from an input data sequence. A retrieved character is the next character in the input data sequence after a particular hash string. A hash function relates a particular hash string to a unique address in a look-up table (LUT). An associated character for the particular hash string is stored in the LUT at the address. When a particular hash string is considered, the content of the LUT address associated with the hash string is checked to determine whether the associated character matches the retrieved character following the hash string. If there is a match, a Boolean TRUE is output; if there is no match, a Boolean FALSE along with the retrieved character is output. Furthermore, if there is no match, then the LUT is updated by replacing the associated character in the LUT with the retrieved character. [...] [This algorithm is used in the Internet draft "PPP Predictor Compression Protocol".] 5,272,478 Method and apparatus for entropy coding assignee Ricoh [arithmetic coding with finite state machine] 5,307,062 Coding system filed 1992/12/15, granted 1994/04/26 assignee Mitsubishi [binary arithmetic coding, see also 5,404,140] 5,309,381 Probability estimation table apparatus filed 1992/04/08, granted 1994/05/03 assignee Ricoh [arithmetic coding] 5,311,177 Code transmitting apparatus with limited carry propagation filed 1992/06/19, granted 1994/05/10 assignee Mitsubishi [arithmetic coding] 5,347,600 (continuation of 5,065,447) Method and apparatus for compression and decompression of digital image filed 10/23/1991, granted 09/13/1994 inventors Barnsley and Sloan 5,363,099 Method and apparatus for entropy coding [arithmetic coding with state machine] 5,384,867 (continued in 5,430,812) filed 10/23/1991, granted 01/24/1995 Fractal transform compression board inventors Barnsley et al. 5,404,140 Coding system filed 1994/01/13, granted 1995/04/04 assignee Mitsubishi [binary arithmetic coding, see also 5,307,062] 5,406,282 Data coding and decoding with improved efficiency assignee Ricoh [PPM & arithmedic coding] 5,414,423 Stabilization of probability estimates by conditioning on prior decisions of a given context assignee IBM arithmetic coding] 5,416,856 Method of encoding a digital image using iterated image transformations to form an eventually contractive map filed 1992/03/30, granted 1995/05/16 inventors Jacobs, Boss and Fisher 5,418,532 Method and system for efficient, multiplication-free arithmetic coding filed 1993/05/13, granted 1995/05/23. inventors Lei & Shaw-Min assignee Bell Communications Research, Inc. (Livingston, NJ). 5,430,812 (continuation of 5,384,867) Fractal transform compression board filed 1994/05/18, granted 1995/07/04 inventors Barnsley et al. 5,455,577 Method and system for data compression filed 1993/03/12, granted 1995/10/03 inventors Slivka & Rashid, assignee Microsoft LZ77 with two-level search data structure 5,533,051 Method for Data Compression filed 1993/03/12, granted 1996/07/02 inventor David C. James, assignee The James Group This is a patent on compression of random data, see item 9.5 below. Japan 2-46275 Coding system granted Feb 26, 1990 [Patents one form of arithmetic coding.]
Subject: [9] Compression of random data (WEB, Gilbert and others) [Note from the FAQ maintainer: this topic has generated and is still generating the greatest volume of news in the history of comp.compression. Read this before posting on this subject. I intended to remove the WEB story from the FAQ, but similar affairs come up regularly on comp.compression. The advertized revolutionary methods have all in common their supposed ability to compress random or already compressed data. I will keep this item in the FAQ to encourage people to take such claims with great precautions.] 9.1 Introduction It is mathematically impossible to create a program compressing without loss *all* files by at least one bit (see below and also item 73 in part 2 of this FAQ). Yet from time to time some people claim to have invented a new algorithm for doing so. Such algorithms are claimed to compress random data and to be applicable recursively, that is, applying the compressor to the compressed output of the previous run, possibly multiple times. Fantastic compression ratios of over 100:1 on random data are claimed to be actually obtained. Such claims inevitably generate a lot of activity on comp.compression, which can last for several months. Large bursts of activity were generated by WEB Technologies and by Jules Gilbert. Premier Research Corporation (with a compressor called MINC) made only a brief appearance but came back later with a Web page at http://www.pacminc.com. The Hyper Space method invented by David C. James is another contender with a patent obtained in July 96. Another large burst occured in Dec 97 and Jan 98: Matthew Burch <apoc@pipeline.com> applied for a patent in Dec 97, but publicly admitted a few days later that his method was flawed; he then posted several dozen messages in a few days about another magic method based on primes, and again ended up admitting that his new method was flawed. (Usually people disappear from comp.compression and appear again 6 months or a year later, rather than admitting their error.) Other people have also claimed incredible compression ratios, but the programs (OWS, WIC) were quickly shown to be fake (not compressing at all). This topic is covered in item 10 of this FAQ. 9.2 The counting argument [This section should probably be called "The counting theorem" because some people think that "argument" implies that it is only an hypothesis, not a proven mathematical fact. The "counting argument" is actually the proof of the theorem.] The WEB compressor (see details in section 9.3 below) was claimed to compress without loss *all* files of greater than 64KB in size to about 1/16th their original length. A very simple counting argument shows that this is impossible, regardless of the compression method. It is even impossible to guarantee lossless compression of all files by at least one bit. (Many other proofs have been posted on comp.compression, please do not post yet another one.) Theorem: No program can compress without loss *all* files of size >= N bits, for any given integer N >= 0. Proof: Assume that the program can compress without loss all files of size >= N bits. Compress with this program all the 2^N files which have exactly N bits. All compressed files have at most N-1 bits, so there are at most (2^N)-1 different compressed files [2^(N-1) files of size N-1, 2^(N-2) of size N-2, and so on, down to 1 file of size 0]. So at least two different input files must compress to the same output file. Hence the compression program cannot be lossless. The proof is called the "counting argument". It uses the so-called pigeon-hole principle: you can't put 16 pigeons into 15 holes without using one of the holes twice. Much stronger results about the number of incompressible files can be obtained, but the proofs are a little more complex. (The MINC page http://www.pacminc.com uses one file of strictly negative size to obtain 2^N instead of (2^N)-1 distinct files of size <= N-1 .) This argument applies of course to WEB's case (take N = 64K*8 bits). Note that no assumption is made about the compression algorithm. The proof applies to *any* algorithm, including those using an external dictionary, or repeated application of another algorithm, or combination of different algorithms, or representation of the data as formulas, etc... All schemes are subject to the counting argument. There is no need to use information theory to provide a proof, just very basic mathematics. [People interested in more elaborate proofs can consult http://wwwvms.utexas.edu/~cbloom/news/nomagic.html ] In short, the counting argument says that if a lossless compression program compresses some files, it must expand others, *regardless* of the compression method, because otherwise there are simply not enough bits to enumerate all possible output files. Despite the extreme simplicity of this theorem and its proof, some people still fail to grasp it and waste a lot of time trying to find a counter-example. This assumes of course that the information available to the decompressor is only the bit sequence of the compressed data. If external information such as a file name, a number of iterations, or a bit length is necessary to decompress the data, the bits necessary to provide the extra information must be included in the bit count of the compressed data. Otherwise, it would be sufficient to consider any input data as a number, use this as the file name, iteration count or bit length, and pretend that the compressed size is zero. For an example of storing information in the file name, see the program lmfjyh in the 1993 International Obfuscated C Code Contest, available on all comp.sources.misc archives (Volume 39, Issue 104). A common flaw in the algorithms claimed to compress all files is to assume that arbitrary bit strings can be sent to the decompressor without actually transmitting their bit length. If the decompressor needs such bit lengths to decode the data (when the bit strings do not form a prefix code), the number of bits needed to encode those lengths must be taken into account in the total size of the compressed data. Another common (but still incorrect) argument is to assume that for any file, some still to be discovered algorithm might find a seed for a pseudo-random number generator which would actually generate the whole sequence of bytes contained in the file. However this idea still fails to take into account the counting argument. For example, if the seed is limited to 64 bits, this algorithm can generate at most 2^64 different files, and thus is unable to compress *all* files longer than 8 bytes. For more details about this "magic function theory", see http://www.dogma.net/markn/FAQ.html#Q19 Yet another popular idea is to split the input bit stream into a sequence of large numbers, and factorize those numbers. Unfortunately, the number of bits required to encode the factors and their exponents is on average not smaller than the number of bits of the original bit stream, so this scheme too cannot compress all data. Another idea also related to primes is to encode each number as an index into a table of primes and an offset relative to the indexed prime; this idea doesn't work either because the number of bits required to encode the index, the offset and the separation between index and offset is on average not smaller than the number of bits of the original bit stream. Steve Tate <srt@cs.unt.edu> suggests a good challenge for programs that are claimed to compress any data by a significant amount: Here's a wager for you: First, send me the DEcompression algorithm. Then I will send you a file of whatever size you want, but at least 100k. If you can send me back a compressed version that is even 20% shorter (80k if the input is 100k) I'll send you $100. Of course, the file must be able to be decompressed with the program you previously sent me, and must match exactly my original file. Now what are you going to provide when... er... if you can't demonstrate your compression in such a way? So far no one has accepted this challenge (for good reasons). Mike Goldman <whig@by.net> makes another offer: I will attach a prize of $5,000 to anyone who successfully meets this challenge. First, the contestant will tell me HOW LONG of a data file to generate. Second, I will generate the data file, and send it to the contestant. Last, the contestant will send me a decompressor and a compressed file, which will together total in size less than the original data file, and which will be able to restore the compressed file to the original state. With this offer, you can tune your algorithm to my data. You tell me the parameters of size in advance. All I get to do is arrange the bits within my file according to the dictates of my whim. As a processing fee, I will require an advance deposit of $100 from any contestant. This deposit is 100% refundable if you meet the challenge. 9.3 The WEB 16:1 compressor 9.3.1 What the press says April 20, 1992 Byte Week Vol 4. No. 25: "In an announcement that has generated high interest - and more than a bit of skepticism - WEB Technologies (Smyrna, GA) says it has developed a utility that will compress files of greater than 64KB in size to about 1/16th their original length. Furthermore, WEB says its DataFiles/16 program can shrink files it has already compressed." [...] "A week after our preliminary test, WEB showed us the program successfully compressing a file without losing any data. But we have not been able to test this latest beta release ourselves." [...] "WEB, in fact, says that virtually any amount of data can be squeezed to under 1024 bytes by using DataFiles/16 to compress its own output multiple times." June 1992 Byte, Vol 17 No 6: [...] According to Earl Bradley, WEB Technologies' vice president of sales and marketing, the compression algorithm used by DataFiles/16 is not subject to the laws of information theory. [...] ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ 9.3.2 First details, by John Wallace <buckeye@spf.trw.com> I called WEB at (404)514-8000 and they sent me some product literature as well as chatting for a few minutes with me on the phone. Their product is called DataFiles/16, and their claims for it are roughly those heard on the net. According to their flier: "DataFiles/16 will compress all types of binary files to approximately one-sixteenth of their original size ... regardless of the type of file (word processing document, spreadsheet file, image file, executable file, etc.), NO DATA WILL BE LOST by DataFiles/16." (Their capitalizations; 16:1 compression only promised for files >64K bytes in length.) "Performed on a 386/25 machine, the program can complete a compression/decompression cycle on one megabyte of data in less than thirty seconds" "The compressed output file created by DataFiles/16 can be used as the input file to subsequent executions of the program. This feature of the utility is known as recursive or iterative compression, and will enable you to compress your data files to a tiny fraction of the original size. In fact, virtually any amount of computer data can be compressed to under 1024 bytes using DataFiles/16 to compress its own output files muliple times. Then, by repeating in reverse the steps taken to perform the recusive compression, all original data can be decompressed to its original form without the loss of a single bit." Their flier also claims: "Constant levels of compression across ALL TYPES of FILES" "Convenient, single floppy DATA TRANSPORTATION" From my telephone conversation, I was assured that this is an actual compression program. Decompression is done by using only the data in the compressed file; there are no hidden or extra files. 9.3.3 More information, by Rafael Ramirez <rafael.ramirez@channel1.com>: Today (Tuesday, 28th) I got a call from Earl Bradley of Web who now says that they have put off releasing a software version of the algorithm because they are close to signing a major contract with a big company to put the algorithm in silicon. He said he could not name the company due to non-disclosure agreements, but that they had run extensive independent tests of their own and verified that the algorithm works. [...] He said the algorithm is so simple that he doesn't want anybody getting their hands on it and copying it even though he said they have filed a patent on it. [...] Mr. Bradley said the silicon version would hold up much better to patent enforcement and be harder to copy. He claimed that the algorithm takes up about 4K of code, uses only integer math, and the current software implementation only uses a 65K buffer. He said the silicon version would likely use a parallel version and work in real-time. [...] 9.3.4 No software version Appeared on BIX, reposted by Bruce Hoult <Bruce.Hoult@actrix.gen.nz>: tojerry/chaos #673, from abailey, 562 chars, Tue Jun 16 20:40:34 1992 Comment(s). ---------- TITLE: WEB Technology I promised everyone a report when I finally got the poop on WEB's 16:1 data compression. After talking back and forth for a year and being put off for the past month by un-returned phone calls, I finally got hold of Marc Spindler who is their sales manager. _No_ software product is forth coming, period! He began talking about hardware they are designing for delivery at the end of the year. [...] 9.3.5 Product cancelled Posted by John Toebes <toebes@bnr.ca> on Aug 10th, 1992: [Long story omitted, confirming the reports made above about the original WEB claims.] 10JUL92 - Called to Check Status. Was told that testing had uncovered a new problem where 'four numbers in a matrix were the same value' and that the programmers were off attempting to code a preprocessor to eliminate this rare case. I indicated that he had told me this story before. He told me that the programmers were still working on the problem. 31JUL92 - Final Call to Check Status. Called Earl in the morning and was told that he still had not heard from the programmers. [...] Stated that if they could not resolve the problem then there would probably not be a product. 03AUG92 - Final Call. Earl claims that the programmers are unable to resolve the problem. I asked if this meant that there would not be a product as a result and he said yes. 9.3.6 Byte's final report Extract from the Nov. 95 issue of Byte, page 42: Not suprisingly, the beta version of DataFiles/16 that reporter Russ Schnapp tested didn't work. DataFiles/16 compressed files, but when decompressed, those files bore no resemblance to their originals. WEB said it would send us a version of the program that worked, but we never received it. When we attempted to follow up on the story about three months later, the company's phone had been disconnected. Attempts to reach company officers were also unsuccessful. [...] 9.4 Jules Gilbert As opposed to WEB Technologies, Jules Gilbert <jules@aasp.net> does not claim to compress *all* files, but only "random or random-appearing" files. Here are some quotes from a few of Mr Gilbert's articles, which can be helpful to get a better idea of his claims. No comments or conclusions are given; if you need more information contact Mr. Gilbert directly. From: coffee@spock.ici.net (Jules Gilbert) Newsgroups: comp.compression Subject: Re: No Magic Compressors, No Factoring Compressors, Jules Gilbert is a liar Date: 14 May 1996 03:13:31 -0400 Message-ID: <4n9bqr$89k@spock.ici.net> [...] I will, in front of several Boston area computer scientists ('monitors'), people I choose but generally known to be fair and competent, under conditions which are sufficient to prevent disclosure of the method and fully protect the algorithm and other aspects of the underlying method from untoward discovery, use two computers, (which I am permitted to examine but not alter) with both machine's running Linux, and with the file-systems and Linux OS freshly restored from commercial CD-ROM's do the following: On one machine (the 'src-CPU') will be loaded a copy of the CALGARY-CORPUS. (Or other agreed on '.ZIP' or '.ARJ' file.) I will compress the CALGARY-CORPUS for transfer from the src-CPU onto 3.5" disks and transfer it (by sneaker-net) to the other machine for decompression and produce a perfect copy of the CORPUS file on the 'dst-CPU'. The CORPUS archive contents will not be 'cracked', ie', the original CORPUS can be encrypted and the password kept from me. All I care about is that the input file is highly random-aprearing. I claim that I can perform this process several times, and each iteration will reduce the overall file by at least 50%, ie., a ratio of 2:1. An 'iteration' will constitute copying, using compression, from the src-CPU to the dst-CPU, and then reversing the direction to achieve another iteration. For example, for say a 4M input file, it is reasonable to expect an approximately 1M output file, after two complete iterations. [...] ONLY RANDOM OR RANDOM-APPEARING DATA INPUT CAN BE COMPRESSED BY MY METHOD. [...] If one iteration (of the compression 'sandwich') consists of two parts, say an LZ phase followed by a JG phase, the LZ method will compression by perhaps a ration of 2:1 (at the first iteration), perhaps much better if the input is text, and the JG phase will do 3-4:1, but slowly!! During subsequent iterations, the LZ phase will do perhaps 1.25:1 and the JG phase will continue to do about 3-4:1. Experimentally, I have achieved compression results of nearly 150:1, overall, ^^^^^^^^^^^^^^ ^^^^^ for a 60M file. (I started with a '.arj' archive of a large DOS partition.) [...] ---------------------------------------------------------------------------- From: coffee@spock.ici.net (Jules Gilbert) Newsgroups: comp.compression Subject: Re: Explanation: that uh, alg thing... Date: 15 May 1996 16:38:18 -0400 Message-ID: <4ndfbq$cf3@spock.ici.net> [...] One more thing, I am preparing a short technical note to deal with the reason most programmers' and computer scientists' think it's impossible to (further) compress random input. (Many people think that because you can't get more than 2^N messages from a N-bit compressed msg, that it means that you can't compress random input. (Lot's of folks have told me that.) The short story is: I agree that you can not get more than 2^N messages from N bits. No question about it. BUT THAT STATMENT HAS NOTHING TO DO WHATSOEVER WITH THE INTERPRETATION OF WHAT THOSE BITS 'MEAN'. [...] ---------------------------------------------------------------------------- From: coffee@spock.ici.net (Jules Gilbert) Newsgroups: comp.compression Subject: Seeing is believing! Date: 9 Jun 1996 03:20:52 -0400 Message-ID: <4pdu0k$otg@spock.ici.net> [...] If your firm needs industrial-strength compression, contact 'coffee@ici.net' and ask us for an on-site demonstration of our MR2 compressors. Each can compress large files of 'random-appearing' information, whether RSA-encrypted blocks, or files already compressed using LZ-techniques. Our demonstration will give you the opportunity to observe compression of 'random-appearing' files of at least 100MB by at least 3:1 per iteration. Usually, several iterations are possible. (These are minimum figures easily exceeded.) [...] ---------------------------------------------------------------------------- From: coffee@spock.ici.net (Jules Gilbert) Newsgroups: comp.compression Subject: Re: My remarks on Jules Gilbert Date: 24 Jul 1996 18:05:44 -0400 Message-ID: <4t66no$9qq@spock.ici.net> [...] My claims can not possibly be true IF I'M PLAYING BY THE 'RULES' THAT YOU ASSUME APPLY TO ME. (Sorry to shout). Clearly, anyone sending a signal (in the Shannon context), is constrained by limits which make it impossible to compress RAD ('random-appearing data') input. [...] 1) I can't compress bits any better than the next guy. Maybe not as well, in fact. 2) I have designed an engine that accepts RAD input and emits far too little data to reconstitute the original data, based on conventional assumptions. Okay! I know this. 3) But, I none-the-less reconstitute the original data. [...] ---------------------------------------------------------------------------- From: coffee@soran.ici.net (Jules Gilbert) Newsgroups: comp.compression Subject: Re: Jules Gilbert's New Compresssion Technology Date: 12 Aug 1996 08:11:10 -0400 Message-ID: <4un70u$a2r@soran.ici.net> I have multiple methods for compressing RAD. Watch carefully: MR1 does 3:1, on large buffers and is repeatable until the volume of input data falls below 128k or so. (This figure is under user control, but compreesion quality will suffer as the buffer size is decreased). Recent changes make this method about as fast as any conventional compressor. MR2 does at least 6:1, with a minimum buffer size of perhaps 32k. It is also repeatable. MR2 does not actually compress, though. Instead, it translates an input buffer into an output buffer of roughly equivalent size. This output buffer contains mostly constants, and other things, such as simple sequences: 28,29,31,32,33,35,40,41,42,43,44,45. (An actual sequence of bytes). Obviously, this kind of information is readily compressed, and that is why I claim that MR2 can achieve a minimum of 6:1. Again, like MR1, this process can be re-applied over it's own output. When, I've said, "No, it's impossible to compress by 100:1" I was trying to get this audience to see this as realistic. But I can compress RAD files 100:1 if allowed to re-process the output through the same process. I first actually achieved a 100:1 compression level in March of this year using tools ^^^^^^^^^^^^^^^^^^^^^^^^^ designed for experimenting in RAD issues. But now I have C programs which have been written to be easy to understand and are intended to be part of my technology transfer process for clients. [...] So, can someone compress by 100:1 or even 1000:1? Yes! But ONLY if the input file is sufficiently large. A 1000:1 compression ratio would require a very large input file, and, at least for PC users, archive files of this size are almost never produced. ---------------------------------------------------------------------------- From: coffee@soran.ici.net (Jules Gilbert) Newsgroups: comp.compression Subject: Re: Gilbert's RAD compression product Date: 18 Aug 1996 08:40:28 -0400 Message-ID: <4v72vs$quc@soran.ici.net> [...] (In my original remarks), I am quoted above as claiming that a 3,152,896 byte 'tar 'file (conventionally compressed to 1,029,790 bytes) can be compressed to 50*1024 bytes. It's an accurate quote. Now how can that be possible? If a gzip compressed version of the Corpus requires roughly a 1MB, what do I do with the 950k bytes I don't store in the compressed intermediate file? Well, that's certainly a puzzler! For now, all I will say is that it does not go into the compressed intermediate file. And because it doesn't, Shannons' channel capacity axioms apply only to the 50k component. ---------------------------------------------------------------------------- From: coffee@soran.ici.net (Jules Gilbert) Newsgroups: comp.compression Subject: Some answers about MR1 Date: 22 Aug 1996 23:45:54 -0400 Message-ID: <4vj9hi$pkb@soran.ici.net> [...] However, arrangements are being made to do another demo in September at MIT. One of the files compressed and decompressed will be the Corpus, after it's already been compressed using ARJ, a good quality conventional compressor. (It should be about a 1MB at that point). My program has made the corpus as small as 6k, although that requires SEVERAL separate physical passes. ^^^^^^^^^^^^^^ Because we will only have a few minutes to spend on this single file, I'll likely stop at 250k or so. Under Linux, the total size of the compressor and decompressor load modules is about 50k bytes. And under DOS, using the Intel C compiler (a great product, but sadly, not sold anymore), the same files total about 300k bytes. MR1 contains code that is highly dependent on the particularities of a host computer's floating point processor, or more correctly, architectural differ- ences existing between the source machine and the target machine would likely cause failure to de-compress. [...] 9.5 Patents on compression of random data or recursive compression 9.5.1 David C. James On July 2, 1996, David C. James was granted patent 5,533,051 "Method for data compression" for a method claimed to be effective even on random data. From: u137@aol.com (Peter J. Cranstone) Newsgroups: comp.compression Subject: Re: Jules Gilbert's Compression Technology Date: Sun Aug 18 12:48:11 EDT 1996 Wh have just been issued a patent (US. #5,533,051) and have several more pending on a new method for data compression. It will compess all types of data, including "random", and data containing a uniform distribution of "0's" and "1's". [...] The first line of the patent abstract is: Methods for compressing data including methods for compressing highly randomized data are disclosed. Page 3, line 34 of the patent states: A second aspect of the present invention which further enhances its ability to achieve high compression percentages, is its ability to be applied to data recursively. Specifically, the methods of the present invention are able to make multiple passes over a file, each time further compressing the file. Thus, a series of recursions are repeated until the desired compression level is achieved. Page 27, line 18 of the patent states that the claimed method can compress without loss *all* files by at least one bit: the direct bit encode method of the present invention is effective for reducing an input string by one bit regardless of the bit pattern of the input string. The counting argument shows that this is mathematically impossible (see section 9.2) above. If the method were indeed able to shrink any file by at least one bit, applying it recursively would shrink gigabytes down to a few bits. The patent contains evasive arguments to justify the impossible claims: Page 12, line 22: Of course, this does not take into account any overhead registers or other "house-keeping" type information which must be tracked. However such overhead tends to be negligible when processing the large quantities of data typically encountered in data compression applications. Page 27, line 17: Thus, one skilled in the art can see that by keeping the appropriate counters, the direct bit encode method of the present invention is effective for reducing an input string by one bit regardless of the bit pattern of the input string. Although a certain amount of "loss" is necessary in keeping and maintaining various counters and registers, for files which are sufficiently large, this overhead is insignificant compared to the savings obtained by the direct bit encode method. The flaw in these arguments is that the the "house-keeping" type information is *not* negligible. If it is properly taken it into account, it cancels any gains made elsewhere when attempting to compress random data. The patent contains even more evasive arguments: Page 22, line 31: It is commonly stated that perfectly entropic data streams cannot be compressed. This misbelief is in part based on the sobering fact that for a large set of entropic data, calculating the number of possible bit pattern combinations is unfathomable. For example, if 100 ones and 100 zeros are randomly distributed in a block 200 bits long, there are 200C100 = 9.055 10^58 combinations possible. The numbers are clearly unmanageable and hence the inception that perfectly entropic data streams cannot be compressed. The key to the present compression method under discussion is that it makes no attempt to deal with such large amounts of data and simply operates on smaller portions. The actual claims of the patent are harmless since they only describe methods which cannot work (they actually expand random data instead of compressing it). For example, claims 6 and 7 are: 6. A method of compressing a stream of binary data, comprising the steps of: A) parsing n-bits from said stream of binary data; B) determining the value of said parsed n-bits; C) based on the results of step B, coding said values of said n-bits in at least one of a first, second, and third target string, wherein coding said value includes generating a plurality of code strings and correlating said value with one of said code strings and dividing said correlated code string variable length codes and dividing at least some of said into at least first and second segments, and assigning at least one of said correlated code string segments to at least one of said first, second, and third target strings, wherein at least one of said plurality of codes is not greater than n-1 bits long. 7. The method of compressing a stream of binary data of claim 6, wherein n=2. Making abstraction of the legalese, claim 7 says in short that you can compress an arbitrary sequence of two bits down to one bit. 9.5.2 Michael L. Cole Patent 5,488,364 "Recursive data compression", granted Jan. 30, 1996, also claims that recursive compression of random data is possible. See http://www.teaser.fr/~jlgailly/05488364.html for the text and a short analysis of this patent. 9.5.3 John F. Remillard Patent 5,486,826 "Method and apparatus for iterative compression of digital data" uses methods very similar to those of the "magic function theory" (see section 9.2 above). The patent is available at http://patent.womplex.ibm.com/details?patent_number=5486826 See also from the same person patent 5,594,435 "Permutation-based data compression" http://patent.womplex.ibm.com/details?patent_number=5594435 The assignee for this patent is Philosophers' Stone LLC. (The Philosopher's Stone is the key to all the riches in the universe; an LLC is a Limited Liability Corporation.)
Subject: [10] Fake compression programs (OWS, WIC) Some programs claimed to achieve incredible compression ratios are completely fake: they do not compress at all but just stored the uncompressed data in hidden files on the hard disk or keep it in unused clusters. Needless to say, such programs are dangerous and should never be used because there is a significant risk of losing all the data. The OWS program just remembers which clusters contained the data on the hard disk. The data can be recovered only if those clusters are not used again for another file. The WIC program searches for the first directory in drive C: and creates a hidden file called WINFILE.DLL containing a copy of all the original files. If you copy the compressed file to another computer (which doesn't have the file WINFILE.DLL), WIC reports a CRC error.
Subject: [11] What is the V.42bis standard? A description of the V.42bis standard is given in "The V.42bis standard for data-compressing modems," by Clark Thomborson <cthombor@theory.lcs.mit.edu>, IEEE Micro, Oct 1992, pp. 41-53. If you are looking for freeware source of V.42bis, please read the note below by Peter Gutman explaining why there is no such source code. Short introduction, by Alejo Hausner <hausner@qucis.queensu.ca>: The V.42bis Compression Standard was proposed by the International Consultative Committee on Telephony and Telegraphy (CCITT, now ITU-T) as an addition to the v.42 error-correction protocol for modems. Its purpose is to increase data throughput, and uses a variant of the Lempel-Ziv-Welch (LZW) compression method. It is meant to be implemented in the modem hardware, but can also be built into the software that interfaces to an ordinary non-compressing modem. V.42bis can send data compressed or not, depending on the data. There are some types of data that cannot be compressed. For example, if a file was compressed first, and then sent through a V.42bis modem, the modem would not likely reduce the number of bits sent. Indeed it is likely that the amount of data would increase somewhat. To avoid this problem, the algorithm constantly monitors the compressibility of the data, and if it finds fewer bits would be necessary to send it uncompressed, it switches to transparent mode. The sender informs the receiver of this transition through a reserved code word. Henceforth the data is passed as plain bytes. While transmitting in transparent mode, the sender maintains the LZW trees of strings, and expects the receiver to do likewise. If it finds an advantage in returning to compressed mode, it will do so, first informing the receiver by a special escape code. Thus the method allows the hardware to adapt to the compressibility of the data. The choice of escape code is clever. Initially, it is a zero byte. Any occurrence of the escape code is replaced, as is customary, by two escape codes. In order to prevent a string of escape codes from temporarily cutting throughput in half, the escape code is redefined by adding 51 mod 256 each time it is used. A note from Peter Gutman <pgut01@cs.auckland.ac.nz> about V.42bis implementations: V.42bis is covered by patents, and the licensing terms are rather complex because you need to license it from multiple organisations. At one point British Telecom were charging something like 30,000 pounds for a license (this was a few years ago, things may have changed since then). Because of this, noone has ever implemented a freely-available version of V.42bis as you'd find in a modem. There is a Unix implementation (called "compact") of a V.42bis-like algorithm which comes with a great many disclaimers that it can only be used for research purposes. [Note from FAQ maintainer: "compact" is available in ftp://ftp.sunet.se/pub/usenet/ftp.uu.net/comp.sources.misc/volume15/compact_sv/part01.gz The 'shrink' method of zip 1.1 (see item 2 above) is also similar to V.42bis] If you've ever wondered why noone other than modem manufacturers ever use V.42bis for anything, this is it. Some CCITT (ITU-T) standards documents are available by ftp in ftp://ftp.fdn.org/pub/Library/Ccitt-standards/ccitt/ A mail server for CCITT (ITU-T) documents is available at teledoc@itu.arcom.ch or itudoc@itu.ch. A Gopher server is also available at gopher://info.itu.ch The V42bis standard is also in ftp://ftp.std.com/obi/Standards/Telcom/CCITT/ For ISO documents, try http://www.iso.ch/ See also item 20 below for other sites with standards documents.
Subject: [12] I need source for the winners of the Dr Dobbs compression contest The source of the top 6 programs of the Feb 91 Dr Dobbs data compression contest are available by ftp on ftp://ftp.simtel.net/pub/simtelnet/msdos/compress/ddjcompr.zip ftp://garbo.uwasa.fi/pc/source/ddjcompr.zip The sources are in MSDOS end-of-line format, one directory per program. Unix or VMS users, use "unzip -a ddjcompr" to get correct end-of-lines (add -d to recreate the directory structure if you are using an obsolete version of unzip such as 4.1). Three of the 6 programs are not portable and only run on MSDOS. compact and urban work on Unix, sixpack only requires minor modifications.
Subject: [13] I need source for arithmetic coding (See question 70 for an introduction to arithmetic coding.) The source for the arithmetic coder described in Chap.5 of Bell, Cleary, and Witten's book "Text Compression" (see question 7 above) (or, equivalently, in: Witten, Neal, and Cleary's article "Arithmetic Coding for data Compression" from Communications of the Association for Computing Machinery, 30 (6), pp.520-540, June, 1987) is in ftp://ftp.cpsc.ucalgary.ca/pub/projects/ar.cod/ It only comes with a simple order-0 model but it's set up so that adding your own more sophisticated one is straightforward. Look also in ftp://munnari.mu.oz.au/pub/arith_coder C language source code for adaptive arithmetic coding based on the Witten-Neal-Cleary source code is in http://www.cipr.rpi.edu/wheeler/ac/ This version uses structures for the coder, decoder and data model instead of global variables. This object oriented approach allows you to simultaneously use several arithmetic coders, each streaming bits to a different file and to have several adaptive models for each coder, each with a different number of symbols and frequncy table. Written by Fred Wheeler <wheeler@cipr.rpi.edu> A low precision arithmetic coding implementation avoiding hardware division is available on the same site in ftp://ftp.cpsc.ucalgary.ca/pub/projects/arithmetic.coding/low.precision.version file low.precision.version.shar Kris Popat <popat@image.mit.edu> has worked on "Scalar Quantization with Arithmetic Coding." It describes an arithmetic coding technique which is quite general and computationally inexpensive. The documentation and example C code are available in ftp://ftp.media.mit.edu/pub/k-arith-code/ The program 'urban' in ddjcompr.zip (see item 12 above) is a high order arithmetic coder working at the bit level. It is written by Urban Koistinen <md85-epi@nada.kth.se>. The DMC program is available in ftp://plg.uwaterloo.ca/pub/dmc/ It implements the algorithm described in "Data Compression using Dynamic Markov Modelling", by Gordon Cormack and Nigel Horspool, Computer Journal 30:6 (December 1987). This program uses Guazzo's version of arithmetic coding. An implementation of Moffat's arithmetic coder is available in http://www.cs.dartmouth.edu/~jmd/ArithCoder.tar.gz Michael Schindler <michael@compressconsult.com> provides a page on Range Coding http://www.compressconsult.com/rangecoder/ which includes an article and source code. According to Michael Schindler, the performance of that coder is a lot faster than the A. Moffat et al. CACAM coder or even the Moffat Data Compression Conference 1995 coder, at least for machines supporting a fast integer multipy and divide.
Subject: [15] Where can I get image compression programs? JPEG: Source code for most any machine (Independent JPEG Group): http://www.ijg.org/ ftp://ftp.uu.net/graphics/jpeg/jpegsrc.v6a.tar.gz ftp://nic.funet.fi/pub/graphics/packages/jpeg/jpegsrc.v6.tar.gz Contact: jpeg-info@uunet.uu.net ftp://havefun.stanford.edu/pub/jpeg/JPEGv1.2.1.tar.Z (has lossless mode) Contact: Andy Hung <achung@cs.stanford.edu> (see item 20 below) ftp://ftp.cs.cornell.edu/pub/multimed/ljpg.tar.Z (lossless jpeg) http://idt.net/~dclunie/jpegls.html (lossless jpeg by David Clunie) xv, an image viewer which can read JPEG pictures, is available in ftp://ftp.cis.upenn.edu/pub/xv/ JPEG-LS (LOCO-I): http://www.hpl.hp.com/loco/ MPEG: If you don't find here what you are looking for, check also http://www.mpeg.org and http://www.powerweb.de/mpeg/ ftp://havefun.stanford.edu/pub/mpeg/ Contact: Andy Hung <achung@cs.stanford.edu> (see item 20 below) ftp://mm-ftp.cs.berkeley.edu/pub/multimedia/mpeg/play/ mpeg_play-2.3-patched-src.tar.gz Contact: mpeg-bugs@cs.berkeley.edu ftp://flash.bu.edu/pub/code/mpeg_system/ (MPEG-I Multi-Stream System Layer encoder/player; includes an enhanced version of mpeg_play) Contact: Jim Boucher <jboucher@spiderman.bu.edu> or Ziv Yaar <zyaar@bu.edu> http://www.bic.mni.mcgill.ca/~greg/mpeglib/ [MPEG library] ftp://ftp.bic.mni.mcgill.ca/pub/mpeg/ Contact: Gregory Ward <greg@bic.mni.mcgill.ca> ftp://nvr.com/pub/NVR-software/ (free demo copy of NVR's software toolkit for SPARCstations) Contact: Todd Brunhoff <toddb@nvr.com> ftp://havefun.stanford.edu/pub/mpeg/ Contact: Andy Hung <achung@cs.stanford.edu> (see item 20 below) ftp://mm-ftp.cs.berkeley.edu/pub/multimedia/mpeg/play/ mpeg_play-2.3-patched-src.tar.gz Contact: mpeg-bugs@cs.berkeley.edu ftp://flash.bu.edu/pub/code/mpeg_system/ (MPEG-I Multi-Stream System Layer encoder/player; includes an enhanced version of mpeg_play) Contact: Jim Boucher <jboucher@spiderman.bu.edu> or Ziv Yaar <zyaar@bu.edu> ftp://ftp.mni.mcgill.ca/pub/mpeg/mpeg_lib-1.2.tar.gz [MPEG library] Contact: Gregory Ward <greg@pet.mni.mcgill.ca> ftp://nvr.com/pub/NVR-software/ (free demo copy of NVR's software toolkit for SPARCstations) Contact: Todd Brunhoff <toddb@nvr.com> http://www.mpeg.org/MSSG or ftp://ftp.mpeg.org/pub/mpeg/mssg/ Contacts: MPEG Software Simulation Group <mssg@mpeg.org> Concerning VMPEG: Stefan Eckart <stefan@chromatic.com> http://www.mpegtv.com (MPEGTV Software MPEG Video Player for Unix) Contact: Tristan Savatier <tristan@mpeg.org> H.261(P*64): havefun.stanford.edu:pub/p64/P64v1.2.tar.Z Contact: Andy Hung <achung@cs.stanford.edu> (see item 20 below) ftp://zenon.inria.fr/rodeo/ivs/last_version/ (Inria videoconference system) Contact: Thierry Turletti <turletti@sophia.inria.fr> (see item 20 below). http://www.angelfire.com/in/H261/index.html H.261 player for Windows95. Contact: kmitl@usa.net H.263: http://www.nta.no/brukere/DVC/h263_software (Telenor Research) http://huizen.dds.nl/~roalt/h263.html (Roalt Aalmoes) JBIG: ftp://nic.funet.fi/pub/graphics/misc/test-images/jbig.tar.gz. ftp://ftp.informatik.uni-erlangen.de/pub/doc/ISO/JBIG/ Contact: Markus Kuhn <mskuhn@cip.informatik.uni-erlangen.de> PNG: For code and sample images, see: http://www.wco.com/~png/ ftp://ftp.uu.net/graphics/png/ ftp://swrinde.nde.swri.edu/pub/png/ mg: (the MG system for compressing and indexing text and images, see item 16) ftp://munnari.oz.au/pub/mg/ Contact: Stuart Inglis <singlis@cs.waikato.ac.nz> BTPC: Binary Tree Predictive Coding http://www.engr.mun.ca/~john/btpc.html Contact: John Robinson <john@monet.uwaterloo.ca> epic: (Efficient Pyramid Wavelet Coder, see item 72) http://www.cis.upenn.edu/~eero/epic.html Contact: Eero P. Simoncelli <eero.simoncelli@nyu.edu> C source code provided. The "Lenna" test image is available as part of the EPIC package, where it is named "test_image". hcompress: (wavelet image compression, see item 72) ftp://stsci.edu/software/hcompress/ wavethresh: (wavelet software for the language S) http://www.stats.bris.ac.uk/pub/software/wavethresh/wavethresh2.2/ Contact: gpn@maths.bath.ac.uk rice-wlet: (wavelet software, see item 72) ftp://cml.rice.edu/pub/dsp/software/rice-wlet-tools.tar.Z Wavelet Transform Coder Construction Kit: http://www.cs.dartmouth.edu/~gdavis/wavelet/wavelet.html Contact: Geoff Davis <gdavis@cs.dartmouth.edu> scalable: (2 & 3 dimensional subband transformation) ftp://robotics.eecs.berkeley.edu/pub/multimedia/ Contact: scalable@robotics.eecs.berkeley.edu SPIHT: (Set Partitioning in Hierarchical Trees, wavelet-based) http://ipl.rpi.edu/SPIHT/ DjVu: Image compression library from AT&T Labs (includes a wavelet-based image compressor) http://www.djvu.att.com/open/ Contact: djvu@www.anything.com compfits: ftp://ftp.cfht.hawaii.edu/pub/compfits/CompFITS-20Nov96.tar.Z Contact: Jim Wright <jwright@cfht.hawaii.edu> fitspress: ftp://cfata4.harvard.edu/pub/ tiff: For source and sample images, see question 18 below. DCT algorithms used to be in: ftp://etro.vub.ac.be/pub/transfer/COMPRESSION/DCT_ALGORITHMS/ Contact: Charilos Christopoulos <chchrist@etro2.vub.ac.be> for the sources xanim: (X11 animation viewer, supports Quicktime and several other formats) ftp://ftp.x.org/contrib/applications/ ftp://ftp.shell.portal.com/pub/podlipec/ A demo of image compression using neural networks is available in http://www.ee.duke.edu/~cec/index.html. For fractal compression programs, see item 17 below. For Vector Quantization software, see item 76 in part 2 of this FAQ. For image compression hardware, see item 85 in part 3 of this FAQ.
Subject: [16] What is the state of the art in lossless image compression? The JBIG algorithm is one of the best available for lossless image compression. For an introduction to JBIG, see question 74 in part 2. JBIG works best on bi-level images (like faxes) and also works well on Gray-coded grey scale images up to about six or so bits per pixel. You just apply JBIG to the bit planes individually. For more bits/pixel, lossless JPEG provides better performance, sometimes. (For JPEG, see question 19 below.) You can find the specification of JBIG in International Standard ISO/IEC 11544 or in ITU-T Recommendation T.82. You can order a copy directly from ISO (www.iso.ch) or ITU (www.itu.ch) or from your National Standards Body. In the USA, call ANSI at (212) 642-4900. See also the MG system containing an implementation of the 'FELICS' algorithm of P.G. Howard and J.S. Vitter. FELICS usually gives better and faster compression than lossless JPEG, at least for 8-bit grayscale images. (See item 15 above for ftp location). From the MG README file: The MG system is a suite of programs for compressing and indexing text and images. Most of the functionality implemented in the suite is as described in the book ``Managing Gigabytes: Compressing and Indexing Documents and Images'', I.H. Witten, A. Moffat, and T.C. Bell; Van Nostrand Reinhold, New York, 1994, ISBN 0-442-01863-0; US $54.95; call 1 (800) 544-0550 to order. These features include: -- text compression using a Huffman-coded semi-static word-based scheme -- two-level context-based compression of bi-level images -- FELICS lossless compression of gray-scale images -- combined lossy/lossless compression for textual images -- indexing algorithms for large volumes of text in limited main memory -- index compression -- a retrieval system that processes Boolean and ranked queries -- an X windows interface to the retrieval system Paul Howard's PhD thesis, which among other things describes FELICS, is available in ftp://ftp.cs.brown.edu/pub/techreports/93/cs93-28.ps.Z JPEG-LS is the emerging ISO standard for lossless/near-lossless compression of continuous-tone images. Marcelo Weinberger <marcelo@hplwein.hpl.hp.com> says about it: JPEG-LS is being developed by ISO/IEC JTC1/SC29/WG1 (final committee draft document FCD14495-1 as of July 1997), and it is based on HP's LOCO-I algorithm (reference: M. Weinberger, G. Seroussi, G. Sapiro, "LOCO-I: A Low Complexity, Context-Based, Lossless Image Compression Algorithm," Proc. IEEE Data Compression Conference, Snowbird, Utah, March-April 1996). [...] The main feature of JPEG-LS is its superior placement in the compression/complexity trade-off curve. Tested over a wide variety of image types, it was shown to be, on the average, within about 4% of the best available lossless image compression at a fraction of the complexity. In particular, JPEG-LS significantly outperforms FELICS and lossless JPEG Huffman at similar levels of complexity (it also outperforms lossless JPEG arithmetic, which is of significantly higher complexity). [...] A software implementation of JPEG-LS, is now available at: http://www.hpl.hp.com/loco/ There, the DCC'96 paper on LOCO-I is also available. The standard draft is also available through a link to the official JPEG Web site. Benchmarks of some lossless image compression programs are in http://www.geocities.com/SiliconValley/Bay/1995/artest11.html
Subject: [17] What is the state of fractal compression? You may want to read first item 77 in part 2 of this FAQ: "Introduction to Fractal compression". from Tal Kubo <kubo@zariski.harvard.edu>: According to Barnsley's book 'Fractals Everywhere', this method is based on a measure of deviation between a given image and its approximation by an IFS code. The Collage Theorem states that there is a convergent process to minimize this deviation. Unfortunately, according to an article Barnsley wrote for BYTE a few years ago, this convergence was rather slow, about 100 hours on a Cray, unless assisted by a person. Barnsley et al are not divulging any technical information beyond the meager bit in 'Fractals Everywhere'. The book explains the idea of IFS codes at length, but is vague about the applic