NetNews Usenet Archive 1993 #1

home *** CD-ROM | disk | FTP | other *** search

/ NetNews Usenet Archive 1993 #1 / NN_1993_1.iso / spool / comp / compress / 4369 < prev next >

Wrap

Internet Message Format | 1993-01-06 | 75.7 KB

Xref: sparky comp.compression:4369 news.answers:4978 Path: sparky!uunet!opl.com!cass.ma02.bull.com!mips2!bull.bull.fr!julienas!chorus!chorus.fr From: jloup@chorus.fr (Jean-loup Gailly) Newsgroups: comp.compression,news.answers Subject: comp.compression Frequently Asked Questions (part 1/3) Summary: *** READ THIS BEFORE POSTING *** Keywords: data compression, FAQ Message-ID: <compr1_5jan93@chorus.fr> Date: 5 Jan 93 19:30:03 GMT Expires: 15 Feb 93 16:17:20 GMT Sender: news@chorus.chorus.fr Reply-To: jloup@chorus.fr Followup-To: comp.compression Lines: 1805 Approved: news-answers-request@MIT.Edu Supersedes: <compr1_27nov92@chorus.fr> Archive-name: compression-faq/part1 Last-modified: Jan 5th, 1993 "I've already explained this once, but repetition is the very soul of the net." (from alt.config) 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.) 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. If you don't want to see this FAQ regularly, please add the subject line to your kill file. If you have corrections or suggestions for this FAQ, send them to Jean-loup Gailly <jloup@chorus.fr>. Thank you. 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 list of image compression hardware. I apologize for the the incorrect distribution of part 2 of the Nov 27th FAQ. If this happens again, *email* me, don't post. And look at item 53 below. Main changes relative to the previous version: - new version of compact-pro (item 2) - pkzip 2.04c is released (item 3) - directory for ccitt standards has moved once again (item 11) - new mail server for ccitt standards (item 11) - new version of JPEG software (item 15) - new program (gsm) for audio compression (item 26) - added info on QCELP (item 26) - new version of ADPCM audio compression (item 26) - added a more complete description of JBIG (item 74) - new item 85 (part 3): Image compression hardware 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] The WEB 16:1 compressor. [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 codec. [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! 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 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 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. If you are not experienced in data compression, please post in comp.compression only. 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.sources.wanted, comp.sys.mac.wanted, comp.archives.msdos.d, alt.graphics.pixutils). Please post your request in comp.compression only as a last resource. 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. 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. (wuarchive.wustl.edu: 128.152.135.4, garbo.uwasa.fi: 128.214.87.1) Many other sites (in particular wsmr-simtel20.army.mil: 192.88.110.2) have the same programs. To keep this list to a reasonable size, many programs are not mentioned here. Additional information can be found in the file ux1.cso.uiuc.edu:/doc/pcnet/compression [128.174.5.59] maintained by David Lemson (lemson@uiuc.edu). When several programs can handle the same archive format, only one of them is given. Sources for additional lossless data compressors can be found in garbo.uwasa.fi:/pc/programming/lds_10.zip. For Macintosh programs, look on sumex-aim.stanford.edu:/info-mac [36.44.0.6]. For VM/CMS, look on vmd.cso.uiuc.edu:/public.477 [128.174.5.98]. For Atari, look on terminator.cc.umich.edu:/atari/archivers [141.211.164.8] For Amiga, look on ux1.cso.uiuc.edu:/pub/amiga [128.174.5.59] 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, it is likely that a newer version exists in the same directory. (Tell me <jloup@chorus.fr>) 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.) ext: produced by or read by .arc: arc, pkarc for MSDOS. (LZW algorithm) wuarchive.wustl.edu:/mirrors/msdos/starter/pk361.exe garbo.uwasa.fi:/pc/arcers/pk361.exe arc for Unix wuarchive.wustl.edu:/mirrors/misc/unix/arc521e.tar-z garbo.uwasa.fi:/unix/arcers/arc.tar.Z Contact: Howard Chu <hyc@umix.cc.umich.edu> arc for VMS wuarchive.wustl.edu:/packages/compression/vax-vms/arc.exe arcmac for Mac mac.archive.umich.edu:/mac/utilities/compressionapps/arcmac.hqx arc for Amiga 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> wuarchive.wustl.edu:/mirrors/msdos/arc-lbr/arj230.exe garbo.uwasa.fi:/pc/arcers/arj230ng.exe unarj for Unix. Decompresses only. (There is no arj compressor for Unix. Don't post a request.) wuarchive.wustl.edu:/mirrors/misc/unix/unarj230.tar-z garbo.uwasa.fi:/unix/arcers/unarj230.tar.Z unarj for Mac mac.archive.umich.edu:/mac/util/compression/unarjmac.cpt.hqx unarj for Amiga ftp.funet.fi:pub/amiga/utilities/archivers/unarj-0.5.lha .cpt: Compact Pro for Mac sumex-aim.stanford.edu:/info-mac/util/compact-pro-133.hqx [36.44.0.6] .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. .hqx: Macintosh BinHex format.. (BinHex is *not* a compression program, it is similar to uuencode but handles multiple forks.) for Mac: mac.archive.umich.edu:/mac/utilities/compressionapps/binhex4.0.bin for Unix: sumex-aim.stanford.edu:/info-mac/unix/mcvert-165.shar [36.44.0.6] .lha: .lzh: lha for MSDOS (LZ77 with a trie data structure, plus secondary static Huffman coding on a block basis) wuarchive.wustl.edu:/mirrors/msdos/arc-lbr/lha213.exe (exe) wuarchive.wustl.edu:/mirrors/msdos/arc-lbr/lha211sr.zip (sources) garbo.uwasa.fi:/pc/arcers/lha213.exe lharc for Unix. (LZ77 with hash table and binary trees, plus secondary Huffman coding) Warning: lharc can extract .lzh files created by lharc 1.xx but not those created by lha. See lha for Unix below. wuarchive.wustl.edu:/mirrors/misc/unix/lharc102a.tar-z garbo.uwasa.fi:/unix/arcers/lharcsrc.zoo lharc for VMS. Same warning as for Unix lharc. wuarchive.wustl.edu:/packages/compression/vax-vms/lharc.exe lha for Unix. Warning: all doc is in Japanese. wuarchive.wustl.edu:/mirrors/misc/unix/lha101u.tar-z garbo.uwasa.fi:/unix/arcers/lha-1.00.tar.Z Contact: lha-admin@oki.co.jp lha for Mac mac.archive.umich.edu:/mac/utilities/compressionapps/maclha2.0.cpt.hqx lha for Amiga ftp.funet.fi:pub/amiga/utilities/archivers/LhA_e138.run .pak: pak for MSDOS (LZW algorithm) wuarchive.wustl.edu:/mirrors/msdos/arc-lbr/pak251.exe garbo.uwasa.fi:/pc/arcers/pak251.exe .pit: PackIt (Macintosh) for Mac: sumex-aim.stanford.edu:/info-mac/util/stuffit-151.hqx [36.44.0.6] for Unix: sumex-aim.stanford.edu:/info-mac/unix/mcvert-165.shar [36.44.0.6] .pp: PowerPacker (Amiga) ftp.funet.fi:pub/amiga/fish/501-600/ff561/PPLib.lha .sea: self-extracting archive (Macintosh) Run the file to extract it. The self-extraction code can be removed with: mac.archive.umich.edu:/mac/utilities/compressionapps/desea1.11.cpt.hqx .sit: Stuffit for Macintosh for Mac: sumex-aim.stanford.edu:/info-mac/util/stuffit-lite-30.hqx [36.44.0.6] for Unix: sumex-aim.stanford.edu:/info-mac/unix/unsit-15.shar [36.44.0.6] for Amiga: ftp.funet.fi:pub/amiga/utilities/archivers/unsit-1.5c2.lha .tar: tar is *not* a compression program. However, to be kind for you: for MSDOS wuarchive.wustl.edu:/mirrors/msdos/starter/tarread.exe garbo.uwasa.fi:/pc/unix/tar4dos.zoo for Unix tar (you have it already. To extract: tar xvf file.tar) for VMS wuarchive.wustl.edu:/packages/compression/vax-vms/tar.exe for Macintosh sumex-aim.stanford.edu:/info-mac/util/tar-30.hqx for Amiga: ftp.funet.fi:pub/amiga/fish/401-500/ff445/Tar.lha .tar.Z, .tar-z, .taz: tar + compress For Unix: zcat file.tar.Z | tar xvf - with GNU tar: tar xvZf file.tar.Z Other OS: first uncompress (see .Z below) then untar (see .tar above) .zip: pkzip 1.10 for MSDOS. (LZ77 with hashing, plus secondary static Shannon-Fano encoding on whole file) Contact: pkware.inc@mixcom.com wuarchive.wustl.edu:/mirrors/msdos/zip/pkz110eu.exe. garbo.uwasa.fi:/pc/arcers/pkz110eu.exe. Note: pkz110eu.exe is an 'export' version without encryption. pkzip 1.93a for MSDOS. (LZ77 with hashing, plus secondary static Huffman coding on a block basis) Note: pkzip 1.93a is an alpha version, see item 3 below. pkzip 2.04c should soon become available by ftp (see sites for pkzip 1.10 above) ux1.cso.uiuc.edu:/pc/exec-pc/pkz193a.exe [128.174.5.59] ftp.tu-clausthal.de:/pub/msdos/archive/pkz193a.exe zip 1.9p1 and unzip 5.0 for Unix, MSDOS, VMS, OS/2, Atari, Mac, Amiga,... Compatible with pkzip 1.93a (LZ77 with hashing, plus secondary static Huffman coding on a block basis) Contact: zip-bugs@wkuvx1.bitnet oak.oakland.edu:/pub/msdos/zip/zip19p1.zip (source) oak.oakland.edu:/pub/msdos/zip/zip19p1x.zip (MSDOS exe) oak.oakland.edu:/pub/msdos/zip/unzip50.zip (source) oak.oakland.edu:/pub/misc/unix/unzip50.tar-z (tar.Z source) oak.oakland.edu:/pub/msdos/zip/unzip50.exe (MSDOS exe) quest.jpl.nasa.gov:/pub/AMIGA/unz51dx.* (Amiga exe) quest.jpl.nasa.gov:/pub/AMIGA/zip19hx.zip (Amiga exe) wuarchive.wustl.edu:/mirrors/garbo.uwasa.fi/arcutil/zcrypt19.zip (encryption source. Non US residents must get it from garbo,see below) garbo.uwasa.fi:/unix/arcers/zip19p1.zip garbo.uwasa.fi:/unix/arcers/unzip50.tar.Z. garbo.uwasa.fi:/pc/arcutil/zcrypt19.zip (encryption code) .zoo: zoo 2.10 for MSDOS (algorithm copied from that of lha, see lha above) Contact: Rahul Dhesi <dhesi@cirrus.com> wuarchive.wustl.edu:/mirrors/msdos/zoo/zoo210.exe garbo.uwasa.fi:/pc/arcers/zoo210.exe zoo 2.10 for Unix, VMS wsmr-simtel20.army.mil:pd8:<misc.unix>zoo210.tar-z [192.88.110.2] garbo.uwasa.fi:/unix/arcers/zoo210.tar.Z zoo for Mac mac.archive.umich.edu:/mac/utilities/compressionapps/maczoo.sit.hqx zoo for Amiga ftp.funet.fi:pub/amiga/utilities/archivers/Zoo-2.1.lha .F: freeze for Unix (LZ77 with hashing, plus secondary dynamic Huffman encoding) wuarchive.wustl.edu:/usenet/comp.sources.misc/volume25/freeze/part0[1-2].Z ftp.inria.fr:/system/arch-compr/freeze-2.3.4.tar.Z Contact: Leonid A. Broukhis <leo@s514.ipmce.su> .Y: yabba for Unix, VMS, ... (Y coding, a variant of LZ78) wuarchive.wustl.edu:/usenet/comp.sources.unix/volume24/yabbawhap/part0[1-4].Z ftp.inria.fr:/system/arch-compr/yabba.tar.Z Contact: Dan Bernstein <brnstnd@nyu.edu> .Z: compress for Unix ('the' LZW algorithm) It is likely that your Unix system has 'compress' already. Otherwise: wuarchive.wustl.edu:/packages/compression/compress-4.1.tar (not in .Z format to avoid chicken and egg problem) compress for MSDOS wuarchive.wustl.edu:/mirrors/msdos/compress/comp430[ds].zip garbo.uwasa.fi:/pc/unix/comp430d.zip compress for Macintosh sumex-aim.stanford.edu:/info-mac/util/maccompress-32.hqx compress for Amiga ftp.funet.fi:pub/amiga/utilities/archivers/compress-4.1.lha compress for Vax/VMS wuarchive.wustl.edu:/packages/compression/vax-vms/lzcomp.exe wuarchive.wustl.edu:/packages/compression/vax-vms/lzdcmp.exe ------------------------------------------------------------------------------ Subject: [3] What is the latest PKZIP version? The latest official version is 2.04c. Here is a message found on the PKWare BBS: Last Update: 01/04/93 ********************************************************************* ******* PKZIP 2.04c is shipping. Please allow 7-10 business ******* ******* days to process and ship orders. It will appear on ******* ******* BBS's shortly here after. ******* ********************************************************************* Do not trust or use any version of PKZIP other than 1.10,1.93, and 2.04c. All other versions currently circulating on BBS's are fakes. These fake programs should be considered hostile and not be trusted, they may contain viruses, trojans, or other tricks. ------------------------------------------------------------------------------ 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. Such programs are often combined with tar to create compressed archives (see question 50: "What is this tar compression program?"). ------------------------------------------------------------------------------ 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. The only objective comparisons are speed and compression ratio. Here is a short table comparing various programs on a 33Mhz Compaq 386. All programs have been run on Unix SVR4, except pkzip and arj which only run on MSDOS. Detailed benchmarks have been posted in comp.compression by Peter Gutmann <pgut1@cs.aukuni.ac.nz>. *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. 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. Two programs (hpack and comp-2) 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 wuarchive.wustl.edu:/mirrors/msdos/ddjmag/ddj9102.zip (inner zip file nelson.zip), - hpack is in wuarchive.wustl.edu:/mirrors/misc/unix/hpack75a.tar-z and garbo.uwasa.fi:/unix/arcers/hpack75a.tar.Z - ftp.adelaide.edu.au:/pub/compression/lzrw3-a.c [129.127.40.3] The 14 files used in the comparison are from the standard Calgary Text Compression Corpus, available by ftp on fsa.cpsc.ucalgary.ca [136.159.2.1] in /pub/text.compression.corpus/text.compression.corpus.tar.Z. 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: I still have to add all decompression times.] 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 2.10 1.0(Unix) 2.30 1.93a 1.9 0.75a ah 2.13(MSDOS) -jm -ex -6 ------ ------ ------ ------ ------- ------ ------ bib 40742 40740 36090 35186 34950 35619 29840 book1 339076 339074 318382 313566 312619 306876 237380 book2 228444 228442 210521 207204 206306 208486 174085 geo 68576 68574 69209 68698 68418 58976 64590 news 155086 155084 146855 144954 144395 141608 128047 obj1 10312 10310 10333 10307 10295 10572 10819 obj2 84983 84981 82052 81213 81336 80806 85465 paper1 19678 19676 18710 18519 18525 18607 16895 paper2 32098 32096 30034 29566 29674 29825 25453 pic 52223 52221 53578 52777 55051 51778 55461 progc 13943 13941 13408 13363 13238 13475 12896 progl 16916 16914 16408 16148 16175 16586 17354 progp 11509 11507 11308 11214 11182 11647 11668 trans 22580 22578 20046 19808 18879 20506 21023 1,096,166 1,096,138 1,036,934 1,022,523 1,021,043 1,005,367 890,976 real 4m07s 6m03s 1m49s 1h22m17s 27m05s user 3m47s 4m23s 1m43s 1h20m46s 19m27s sys 0m04s 0m08s 0m02s 0m12s 2m03s MSDOS: 1m49s 2m41s 1m55s 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 wuarchive.wustl.edu:/mirrors/msdos/arc_lbr/ar002.zip). - hpack 0.75a gives slightly different results on SunOS (undeterministic behaviour still under investigation). - 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, Witten, I.H, and Cleary, J.G. "Text Compression", Prentice-Hall 1989. ISBN: 0-13-911991-4. Price: approx. US$40 The reference on text data compression. [Nel 1991] Mark Nelson, "The Data Compression Book" M&T Books, Redwood City, CA, 1991. ISBN 1-55851-216-0. Price $36.95 including two 5" PC-compatible disks 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. [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 [CT 1991] Elements of Information Theory, by T.M.Cover and J.A.Thomas John Wiley & Sons, 1991. 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. ------------------------------------------------------------------------------ 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.] All patents mentioned here are US patents, and thus probably not applicable outside the US. 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: [...] (b) LZ77 - The Gibson & Graybill patent 5,049,881 covers the LZRW1 algorithm previously discovered by Ross Williams. (See item 5 for the ftp site with all LZRW derivatives). 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. The following papers, published before the patent was filed, describe applications of hashing to LZ77 compression: Brent, R.P. "A Linear Algorithm for Data Compression", Australian Computer Journal, Vol.19, No.2 (May 1987), p.64. Bell, T. "Longest match string searching for Ziv-Lempel compression" Res. Rept. 6/89, Dept. of Computer Science, Univ. of Canterbury, New Zealand (Feb 89). - 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. - Robert Jung, author of 'arj', has recently been granted patent 5,140,321 for one variation of LZ77 with hashing. This patent covers 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. (The US patent system allows this because of the 'invention date' rule.) - 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 algorithm previously patented by Eastman-Lempel-Ziv (4,464,650), and the algorithms used in lharc, lha and zoo. - IBM patented (5,001,478) the idea of combining a history buffer (the LZ77 technique) and a lexicon (as in LZ78). (c) LZ78 - 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) and in Postscript Level 2. (Unisys sells the license to modem manufacturers for a onetime $25,000 fee.) The IBM patent application was 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.) - AP coding is patented by Storer (4,876,541). (Get the yabba package for source code, see question 2 above, file type .Y) (d) other data compression algorithms - IBM holds a patent on the Q-coder implementation of arithmetic coding. 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 the JPEG FAQ for details.) - Bacon has patented (4,612,532) some from of Markov modeling. As can be seen from the above list, *all* 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. A number of them are taken from the list maintained by Michael Ernst <mernst@theory.lcs.mit.edu> in mintaka.lcs.mit.edu:/mitlpf/ai/patent-list (or patent-list.Z). 4,464,650 Apparatus and method for compressing data signals and restoring the compressed data signals inventors Lempel, Ziv, Cohn, Eastman assignees Sperry Corporation and At&T Bell Laboratories filed 8/10/81, granted 8/7/84 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 The text for this patent can be ftped from rusmv1.rus.uni-stuttgart.de (129.69.1.12) in /info/comp.patents/US4558302.Z. 4,586,027 Method and system for data compression and restoration assignee Hitachi, inventor Tsukimaya et al. filed 08/07/84, granted 04/29/86 4,612,532 inventor Bacon granted 9/1986 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) 4,872,009 Method and apparatus for data compression and restoration assignee Hitachi, inventor Tsukimaya et al. filed 12/07/87, granted 10/03/89 4,876,541 Stem [sic] for dynamically compressing and decompressing electronic data inventor James A. Storer assignee Data Compression Corporation filed 10/15/87, granted 10/24/89 4,955,066 Compressing and Decompressing Text Files inventor Notenboom, L.A. assignee Microsoft filed 10/13/89, granted 09/04/90 5,001,478 Method of Encoding Compressed Data filed 12/28/89, granted 03/19/91 inventor Michael E. Nagy assignee IBM 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 5,051,745 String searcher, and compressor using same inventor Phillip W. Katz (author of pkzip) filed 8/21/90, granted 9/24/91 4,906,991 Textual substitution data compression with finite length search window inventors Fiala,E.R., and Greene,D.H. filed 4/29/1988, granted 3/6/1990 assignee Xerox Corporation 5,109,433 Compressing and decompressing text files assignee Microsoft 5,140,321 Data compression/decompression method and apparatus filed 9/4/91, granted 8/18/92 inventor Robert Jung assignee Prime Computer ------------------------------------------------------------------------------ Subject: [9] The WEB 16:1 compressor. [WARNING: this topic has generated the greatest volume of news in the history of comp.compression. Read this before posting on this subject.] (a) 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. [...] (b) 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 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. (c) 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. [...] (d) The impossiblity proofs. It is impossible for a given program to compress without loss *all* files greater than a certain size by at least one bit. This can be proven by a simple counting argument. (Many other proofs have been posted on comp.compression, *please* do not post yet another one.) 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. (Stronger results about the number of incompressible files can be obtained, but the proofs are a little more complex.) 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 basic mathematics. 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 or a number of iterations is necessary to decompress the data, the bits providing 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 iteration count or file name, and pretend that the compressed size is zero.) [See also question 73 "What is the theoretical compression limit?" in part 2 of this FAQ.] (e) 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. [...] (f) 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. (g) Conclusion The last report given above should put an end to the WEB story. [Note from the FAQ maintainer: I will keep this long story in the FAQ for a while, and will remove it when the dust has finally settled down.] ------------------------------------------------------------------------------ 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. 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) 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 escape code. Henceforth the data is passed as plain bytes. 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. 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 control code. Thus the method allows the hardware to adapt to the compressibility of the data. The CCITT standards documents used to be available by ftp on ftp.uu.net in /doc/standards/ccitt, but this service has been discontinued. If you ftp to digital.resource.org, in directory pub/standards there is a file that says that making the standards available in the first place was just an experiment. The documents are now on src.doc.ic.ac.uk, in directory /computing/ccitt/standards/ccitt (they used to be in directory doc/ccitt-standards/ccitt, so look around if you don't find them). The v42bis standard is in /computing/ccitt/standards/ccitt/1992/v/v42bis.asc.Z. A mail server for CCITT documents is available at teledoc@itu.arcom.ch. For more information, contact Robert Shaw <shaw@itu.arcom.ch> or Antoinette Bautista <bautista@itu.arcom.ch>. Warning by John Levine <johnl@iecc.cambridge.ma.us>: This teledoc thing is much less than meets the eye. What it actually has is one-page abstracts of some but not all CCITT recommendations, along with junk like lists of the national representatives to CCITT. If you want the actual text of a recommendation, you have to send large amounts of money to Switzerland, same as ever. I'm under the impression that the U.N. bookstore in New York also stocks a lot of CCITT docs, no cheaper but quicker to get if you're in the U.S. ------------------------------------------------------------------------------ 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 wsmr-simtel20.army.mil in pd1:<msdos.compress>ddjcompr.zip. [192.88.110.2] garbo.uwasa.fi:/pc/source/ddjcompr.zip [128.214.87.1] 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 available via anonymous ftp from fsa.cpsc.ucalgary.ca (136.159.2.1) in directory /pub/arithmetic.coding. It only comes with a simple order-0 model but it's set up so that adding your own more sophisticated one is straightforward. A low precision arithmetic coding implementation avoiding hardware division is available on the same site (fsa.cpsc.ucalgary.ca) in /pub/arithmetic.coding/low.precision.version/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 via anonymous ftp from media-lab.media.mit.edu (18.85.0.2), in /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>. ------------------------------------------------------------------------------ Subject: [15] Where can I get image compression programs? JPEG: Source code for most any machine: ftp.uu.net:/graphics/jpeg/jpegsrc.v4.tar.Z [137.39.1.9] nic.funet.fi:/pub/graphics/programs/jpeg/jpegsrc.v4.tar.Z [128.214.6.100] Contact: jpeg-info@uunet.uu.net (Independent JPEG Group) xv, an image viewer which can read JPEG pictures, is available in ftp.cicb.fr:/pub/X11R5/contrib/xv-2.20.tar.Z [129.20.128.2] epic: whitechapel.media.mit.edu:/pub/epic.tar.Z [18.85.0.125] The "Lenna" test image is available as part of the EPIC package, where it is named "test_image". compfits: uwila.cfht.hawaii.edu:/pub/compfits/compfits.tar.Z [128.171.80.50] Contact: Jim Wright <jwright@cfht.hawaii.edu> fitspress: cfata4.harvard.edu:/pub/fitspress08.tar.Z [128.103.40.79] tiff: For source and sample images, see question 18 below. 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 current state-of-the-art is the JBIG algorithm. 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 a description of JBIG in ISO/IEC CD 11544, contained in document ISO/IEC JTC1/SC2/N2285. The only way to get it is to ask your National Standards Body for a copy. In the USA, call ANSI at (212) 642-4900. ------------------------------------------------------------------------------ Subject: [17] What is the state of 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 application of the Collage theorem to specific compression problems. There is reason to believe that Barnsley's company has *no algorithm* which takes a given reasonable image and achieves the compression ratios initially claimed for their fractal methods. The 1000-to-1 compression advertised was achieved only for a 'rigged' class of images, with human assistance. The best unaided performance I've heard of is good lossy compression of about 80-1. Steve Tate <srt@duke.cs.duke.edu> confirms: Compression ratios (unzoomed) seem to range from 20:1 to 60:1... The quality is considerably worse than wavelets or JPEG on most of the non-contrived images I have seen. But Yuval Fisher <fisher@inls1.ucsd.edu> disagrees: Their performance has improved dramatically beyond what they were talking about in BYTE a few years ago. Human assistance to the compression is no longer needed and the compression time is reasonable, although the more time and compute power you throw at the compression, the smaller the resulting file for the same level of quality. Geoffrey A Stephenson <ketlux@ketlux.demon.co.uk> adds: Iterated systems are shipping a general purpose compressor at about 300 Pounds in the UK that claims "640x480 24 bit colour compression of about 1 min at 922k -> 10k on a 486/50 software only, decomp. to 8 bits in 3 secs, etc." At a recent multimedia conference in London they handed out free demo disks that show the decomp. in action. The package runs under both DOS anf WIN (DLLs provided for use in applications). They also sell a board to speed up compression and offer versions supporting full motion video (but not apparently at all SVGA sizes like the static picture version). I have not yet got my hands on a full version to test different types of pictures, but friends have a and claim it looks good. Programs: A fractal image compression program is available by ftp in lyapunov.ucsd.edu:/pub/young-fractal/unifs10.zip. (Unix users, See item 2 above for unzip on Unix.) Note the file size before you ftp it: 1.2 MB. The package contains source for compression and decompression, source for X-windows decompression, MSDOS executables and images. A fractal image decompression program (note: decompression only) is available in /pub/inls-ucsd/fractal-2.0.tar on on the same ftp site (lyapunov.ucsd.edu). Note the file size before you ftp it: 1.3 MB. This file also contains a paper by Yuval Fisher (see reference below), and some executables and sample images. Reading this paper is required to understand how the Young compression program (see above) works. References: A. Jacquin, 'Fractal image coding based on a theory of iterated contractive image transformations', Visual Comm. and Image Processing, vol SPIE-1360, 1990. (The best paper that explains the concept in a simple way.) A. Jacquin, "A Fractal Theory of Iterated Markov Operators with Applications to Digital Image Coding", PhD Thesis, Georgia Tech, 1989. It can be obtained from university microfilms for $35, phone 1-800-521-0600. M. Barnsley, L. Anson, "Graphics Compression Technology, SunWorld, October 1991, pp. 42-52. M.F. Barnsley, A. Jacquin, F. Malassenet, L. Reuter & A.D. Sloan, 'Harnessing chaos for image synthesis', Computer Graphics, vol 22 no 4 pp 131-140, 1988. M.F. Barnsley, A.E. Jacquin, 'Application of recurrent iterated function systems to images', Visual Comm. and Image Processing, vol SPIE-1001, 1988. A. Jacquin, "Image Coding Based on a Fractal Theory of Iterated Contractive Image Transformations" p.18, January 1992 (Vol 1 Issue 1) of IEEE Trans on Image Processing. A.E. Jacquin, 'A novel fractal block-coding technique for digital images', Proc. ICASSP 1990. G.E. Oien, S. Lepsoy & T.A. Ramstad, 'An inner product space approach to image coding by contractive transformations', Proc. ICASSP 1991, pp 2773-2776. D.S. Mazel, Fractal Modeling of Time-Series Data, PhD Thesis, Georgia Tech, 1991. (One dimensional, not pictures) S. A. Hollatz, "Digital image compression with two-dimensional affine fractal interpolation functions", Department of Mathematics and Statistics, University of Minnesota-Duluth, Technical Report 91-2. (a nuts-and-bolts how-to-do-it paper on the technique) Stark, J., "Iterated function systems as neural networks", Neural Networks, Vol 4, pp 679-690, Pergamon Press, 1991. Monro D M and Dudbridge F, "Fractal block coding of images", Electronics Letters 28(11):1053-1054 (1992) Beaumont J M, "Image data compression using fractal techniques", British Telecom Technological Journal 9(4):93-108 (1991) Fisher Y, "Fractal image compression", Siggraph 92 Graf S, "Barnsley's Scheme for the Fractal Encoding of Images", Journal Of Complexity, V8, 72-78 (1992). Books: The Fractal Transform, Michael F. Barnsley and Louisa F. Anson ISBN 0-86720-218-1, ca. 250 pp, $49.95 Fractal Image Compression Michael F. Barnsley and Lyman P. Hurd ISBN 0-86720-457-5, ca. 250 pp., $49.95 Barnsley's company is: Iterated Systems, Inc. 5550A Peachtree Parkway, Suite 545 Norcross, GA 30092 404-840-0728 404-840-0029 (fax) ------------------------------------------------------------------------------ Subject: [18] I need specs and source for TIFF and CCITT group 4 Fax Specs for Group 3 and 4 image coding (group 3 is very similar to group 4) are in CCITT (1988) volume VII fascicle VII.3. They are recommendations T.4 and T.6 respectively. There is also an updated spec contained in 1992 recommendations T.1 to T.6. CCITT specs are available by anonymous ftp (see above answer on V.42bis). The T.4 and T.6 specs are in the directory /computing/ccitt/standards/ccitt/1988/ascii, files 7_3_01.txt.Z and 7_3_02.txt.Z respectively. Source code can be obtained as part of a TIFF toolkit - TIFF image compression techniques for binary images include CCITT T.4 and T.6: sgi.com:/graphics/tiff/v3.0.tar.Z (or v3.2beta.tar.Z) [192.48.153.1] Contact: sam@sgi.com There is also a companion compressed tar file (v3.0pics.tar.Z) that has sample TIFF image files. A draft of TIFF 6.0 is in TIFF6.ps.Z. Concerning TIFF 6.0, Tom Lane <tgl+@cs.cmu.edu> adds: The TIFF document won't do you much good unless you also have the official JPEG standard. That, you have to buy from ANSI or your national ISO member organization (DIN over there, I suppose). Worse, the TIFF 6.0 spec has a number of serious problems in its JPEG features. A clarification note will probably be needed to ensure that TIFF JPEG files are compatible across different implementations. I can't in good faith recommend that anyone use TIFF-JPEG until these problems are resolved. See also question 54 below. ------------------------------------------------------------------------------ Subject: [19] What is JPEG? JPEG (pronounced "jay-peg") is a standardized image compression mechanism. JPEG stands for Joint Photographic Experts Group, the original name of the committee that wrote the standard. JPEG is designed for compressing either full-color or gray-scale digital images of "natural" (real-world) scenes. JPEG does not handle black-and-white (1-bit-per-pixel) images, nor does it handle motion picture compression. (Standards for compressing those types of images are being worked on by other committees, named JBIG and MPEG respectively.) A good introduction to JPEG is posted regularly in news.answers by Tom Lane <tgl+@cs.cmu.edu>. (See question 53 "Where are FAQ lists archived" if this posting has expired at your site.) See also the book "JPEG Still Image Data Compression Standard" by William B. Pennebaker and Joan L. Mitchell. Published by Van Nostrand Reinhold (phone 800/842-3636), ISBN 0-442-01272-1. 650 Pages, $59.95. Review by Tom Lane: "This is by far the most complete exposition of JPEG in existence. It's written by two people who know what they are talking about: both serve on the ISO JPEG standards committee. If you want to know how JPEG works or why it works that way, this is the book to have." For JPEG hardware, see item 85 in part 3 of this FAQ. ------------------------------------------------------------------------------ Subject: [20] I am looking for source of an H.261 codec. The H.261 spec is available on src.doc.ic.ac.uk in /computing/ccitt/standards/ccitt/1992/h/h261.doc.Z (or h261.rtf.Z). For H.261 hardware, see item 85 in part 3 of this FAQ. from Thierry TURLETTI <turletti@sophia.inria.fr>: We have implemented a software version of H.261 codec. It runs on top of UNIX and X-Windows. The coder uses the simple video capture board "VideoPix" provided by SUN for the SparcStation. The output is directed towards a standard TCP connection, instead of the leased lines or switched circuits for which regular H.261 codecs are designed. This enable us to test video conferences over regular internet connections. We have to polish it a bit, but the first release is now available by anonymous ftp from avahi.inria.fr, in "/pub/h261.tar.Z". ------------------------------------------------------------------------------ Subject: [25] Fast DCT (Discrete Cosine Transform) algorithms Here are some references provided by Tom Lane <tgl+@cs.cmu.edu>: Polynomial Transform Computation of the 2-D DCT, Duhamel & Guillemot, ICASSP '90 p. 1515. A Forward-Mapping Realization of the Inverse DCT, McMillan & Westover, DCC '92 p. 219. A Fast Algorithm for 2-D DCT, Cho, Yun & Lee, ICASSP '91 p. 2197. Fast Algorithm and Implementation of 2-D DCT, Cho & Lee, Tr. CAS v38 p. 297. A DCT Chip based on a new Structured and Computationally Efficient DCT Algorithm, Duhamel, Guillemot & Carlach, ICCAS '90 p. 77. Trade-offs in the Computation of Mono- and Multi-dimensional DCTs, Vetterli, Duhamel & Guillemot, ICASSP '89 p. 999. Practical Fast 1-D DCT Algorithms with 11 Multiplications, Loeffler, Ligtenberg & Moschytz, ICASSP '89 p. 988. New Scaled DCT Algorithms for Fused Multiply/Add Architectures, Linzer & Feig, ICASSP '91 p. 2201. Fast Algorithms for the 2-D Discrete Cosine Transform, Kamangar & Rao, IEEE Tr. Computers, v C-31 p. 899. Fast 2-D Discrete Cosine Transform, Vetterli, ICASSP '85 p. 1538. A Two-Dimensional Fast Cosine Transform, Haque, Tr. ASSP v ASSP-33 p. 1532. Real-Time Parallel and Fully Pipelined 2-D DCT Lattice Structures with Application to HDTV Systems, Chiu & Liu, Tr. CAS for Video Tech, v 2 p. 25. The Rao & Yip book cited in the jpeg v3 DCT code (see item 15 above) is a good overall introduction, with an extensive (though now dated) bibliography. ------------------------------------------------------------------------------ Subject: [26] Are there algorithms and standards for audio compression? Yes. See the introduction to MPEG given in part 2 of this FAQ. A lossless compressor for 8bit and 16bit audio data (.au) is available by anonymous ftp at svr-ftp.eng.cam.ac.uk:/pub/misc/shorten-0.4.shar. It works by using Huffman coding of prediction residuals. Compression is generally better than that obtained by applying general purpose compression utilities to audio files. Copied from the comp.dsp FAQ posted by guido@cwi.nl (Guido van Rossum): Strange though it seems, audio data is remarkably hard to compress effectively. For 8-bit data, a Huffman encoding of the deltas between successive samples is relatively successful. For 16-bit data, companies like Sony and Philips have spent millions to develop proprietary schemes. Public standards for voice compression are slowly gaining popularity, e.g. CCITT G.721 and G.723 (ADPCM at 32 and 24 kbits/sec). (ADPCM == Adaptive Delta Pulse Code Modulation.) Free source code for a *fast* 32 kbits/sec ADPCM (lossy) algorithm is available by ftp from ftp.cwi.nl as /pub/adpcm.shar. (** NOTE: if you are using v1.0, you should get v1.1, released 17-Dec-1992, which fixes a serious bug -- the quality of v1.1 is claimed to be better than uLAW **) (Note that U-LAW and silence detection can also be considered compression schemes.) See also the comp.dsp FAQ for more information on: - The U.S. DoD's Federal-Standard-1016 based 4800 bps code excited linear prediction voice coder version 3.2 (CELP 3.2) - The U.S. DoD's Federal-Standard-1015/NATO-STANAG-4198 based 2400 bps linear prediction coder version 53 (LPC-10e v53) - Realtime DSP code and hardware for FS-1015 and FS-1016 You can find the comp.dsp FAQ in comp.dsp or news.answers with subject: "FAQ: Audio File Formats" or by ftp on pit-manager.mit.edu in /pub/usenet/news.answers/audio-fmts/part1. from Markus Kuhn <mskuhn@immd4.informatik.uni-erlangen.de>: One highest quality sound compression format is called ASPEC and has been developped by a team at the Frauenhofer Institut in Erlangen (Germany) and others. ASPEC produces CD like quality and offers several bitrates, one is 128 kbit/s. It is a lossy algorithm that throws away frequencys that aren't registered in the human cochlea in addition to sophisticated entropy coding. The 64 kbit/s ASPEC variant might soon bring hifi quality ISDN phone connections. It has been implemented on standard DSPs. The Layer 3 MPEG audio compression standard now contains what is officially called the best parts of the ASPEC and MUSICAM algorithms. A reference is: K.Brandenburg, G.Stoll, Y.F.Dehery, J.D.Johnston, L.v.d.Kerkhof, E.F.Schroeder: "The ISO/MPEG-Audio Codec: A Generic Standard for Coding of High Quality Digital Audio", 92nd. AES-convention, Vienna 1992, preprint 3336 from Jutta Degener <jutta@cs.tu-berlin.de> and Carsten Bormann <cabo@cs.tu-berlin.de>: GSM 06.10 13 kbit/s RPE/LTP speech compression available -------------------------------------------------------- The Communications and Operating Systems Research Group (KBS) at the Technische Universitaet Berlin is currently working on a set of UNIX-based tools for computer-mediated telecooperation that will be made freely available. As part of this effort we are publishing an implementation of the European GSM 06.10 provisional standard for full-rate speech transcoding, prI-ETS 300 036, which uses RPE/LTP (residual pulse excitation/long term prediction) coding at 13 kbit/s. GSM 06.10 compresses frames of 160 13-bit samples (8 kHz sampling rate, i.e. a frame rate of 50 Hz) into 260 bits; for compatibility with typical UNIX applications, our implementation turns frames of 160 16-bit linear samples into 33-byte frames (1650 Bytes/s). The quality of the algorithm is good enough for reliable speaker recognition; even music often survives transcoding in recognizable form (given the bandwidth limitations of 8 kHz sampling rate). Version 1.0 of the implementation is available per anonymous ftp from tub.cs.tu-berlin.de as /pub/tubmik/gsm-1.0.tar.Z. Questions and bug reports should be directed to toast@tub.cs.tu-berlin.de. Note that the distribution is not available via E-mail (please use one of the ftp-via-E-mail servers). from Bob Kimball <rkimball@qualcomm.com>: I work for Qualcomm Inc. and we are designing a digital cellular telephone system. Our phone uses our variable rate vocoder (QCELP) which is designed for speach and compresses 64Kb/s speach to 8Kb/s through 1Kb/s with 8Kb/s being full rate and 1Kb/s for 1/8 rate speach. It works great for speach. The QCELP process is documented in our Common Air Interface (CAI) which is available for anonymous ftp from lorien.qualcomm.com in /pub/cdma each chapter is a postscript file. The vocoder is described in appendix A. The whole document is quite large. This is the document which is currently going through the TIA standard committee so it is not a final version. The appendix on the vocoder should be almost identical to the final version... whenever that comes out. ------------------------------------------------------------------------------ Subject: [30] My archive is corrupted! The two most common reasons for this are (1) failing to use the magic word "tenex" (when connected to SIMTEL20 and other TOPS20 systems) or "binary" (when connected to UNIX systems) when transferring the file from an ftp site to your host machine. The reasons for this are technical and boring. A synonym for "tenex" is "type L 8", in case your ftp doesn't know what "tenex" means. (2) failing to use an eight-bit binary transfer protocol when transferring the file from the host to your PC. Make sure to set the transfer type to "binary" on both your host machine and your PC. ------------------------------------------------------------------------------ Subject: [31] pkunzip reports a CRC error! The portable zip 1.0 contains many workarounds for undocumented restrictions in pkunzip. Compatibility is ensured for pkunzip 1.10 only. All previous versions (pkunzip 1.0x) have too many bugs and cannot be supported. This includes Borland unzip. So if your pkunzip reports a CRC error, check that you are not using an obsolete version. Get either pkzip 1.10 or unzip 5.0 (see question 2 above for ftp sites). Immediately after zip 1.0 was released, a new undocumented feature of pkunzip was discovered, which causes CRC errors even with pkunzip 1.10 on rare occasions. A patch is available on valeria.cs.ucla.edu in /pub/zip10.patch. ------------------------------------------------------------------------------ Subject: [32] VMS zip is not compatible with pkzip! The problem is most likely in the file transfer program. Many use kermit to transfer zipped files between PC and VMS VAX. The following VMS kermit settings make VMS-ZIP compatible with PKZIP: VMS kermit PC kermit --------------- -------------- Uploading PKZIPped file to be UNZIPped: set fi ty fixed set fi ty bi Downloading ZIPped file to be PKUNZIPped: set fi ty block set fi ty bi If you are not using kermit, transfer a file created by pkzip on MSDOS to VMS, transfer it back to your PC and check that pkunzip can extract it. ------------------------------------------------------------------------------ Subject: [50] What is this 'tar' compression program? tar is not a compression program. It just combines several files into one, without compressing them. tar file are often compressed with 'compress', resulting in a .tar.Z file. See question 2, file type .tar.Z. GNU tar has the capability to (de)compress files as well. When you have to archive a lot of very small files, it is often preferable to create a single .tar file and compress it, than to compress the individual files separately. The compression program can thus take advantage of redundancy between separate files. The disadvantage is that you must uncompress the whole .tar file to extract any member. ------------------------------------------------------------------------------ Subject: [51] I need a CRC algorithm As its name implies (Cyclic Redundancy Check) a crc adds redundancy whereas the topic of this group is to remove it. But since this question comes up often, here is some code (by Rob Warnock <rpw3@sgi.com>). The following C code does CRC-32 in BigEndian/BigEndian byte/bit order. That is, the data is sent most significant byte first, and each of the bits within a byte is sent most significant bit first, as in FDDI. You will need to twiddle with it to do Ethernet CRC, i.e., BigEndian/LittleEndian byte/bit order. [Left as an exercise for the reader.] The CRCs this code generates agree with the vendor-supplied Verilog models of several of the popular FDDI "MAC" chips. u_long crc32_table[256]; /* Initialized first time "crc32()" is called. If you prefer, you can * statically initialize it at compile time. [Another exercise.] */ u_long crc32(u_char *buf, int len) { u_char *p; u_long crc; if (!crc32_table[1]) /* if not already done, */ init_crc32(); /* build table */ crc = 0xffffffff; /* preload shift register, per CRC-32 spec */ for (p = buf; len > 0; ++p, --len) crc = (crc << 8) ^ crc32_table[(crc >> 24) ^ *p]; return ~crc; /* transmit complement, per CRC-32 spec */ } /* * Build auxiliary table for parallel byte-at-a-time CRC-32. */ #define CRC32_POLY 0x04c11db7 /* AUTODIN II, Ethernet, & FDDI */ init_crc32() { int i, j; u_long c; for (i = 0; i < 256; ++i) { for (c = i << 24, j = 8; j > 0; --j) c = c & 0x80000000 ? (c << 1) ^ CRC32_POLY : (c << 1); crc32_table[i] = c; } } ------------------------------------------------------------------------------ Subject: [52] What about those people who continue to ask frequently asked questions in spite of the frequently asked questions document? Just send them a polite mail message, referring them to this document. There is no need to flame them on comp.compression. That would just add more noise to this group. Posted answers that are in the FAQ are just as annoying as posted questions that are in the FAQ. ------------------------------------------------------------------------------ Subject: [53] Where are FAQ lists archived? Many are crossposted to news.answers. That newsgroup should have a long expiry time at your site; if not, talk to your sysadmin. FAQ lists are available by anonymous FTP from rtfm.mit.edu (18.72.1.58). The comp.compression FAQ that you are reading is in directory /pub/usenet/news.answers/compression-faq If you don't have FTP access, you can access the archives by mail server. Send an email message to mail-server@pit-manager.mit.edu containing the commands send usenet/news.answers/compression-faq/part1 send usenet/news.answers/compression-faq/part2 For instructions, send an email message to the same address with the words "help" and "index" (no quotes) on separate lines. If you don't get a reply, check your return address, or add a line such as path myname@foo.edu ------------------------------------------------------------------------------ Subject: [54] I need specs for graphics formats Have a look in directory /pub/graphics.formats on zamenhof.cs.rice.edu. It contains descriptions of gif, tiff, fits, etc... See also the FAQ list for comp.graphics. ------------------------------------------------------------------------------ Subject: [55] Where can I find Lenna and other images? A bunch of standard images (lenna, baboon, cameraman, crowd, moon etc..) are on ftp site eedsp.gatech.edu (130.207.226.2) in directory /database/images. The images are in 256-level grayshades (256x256 pixels, 256 "colors"). The site ftp.ipl.rpi.edu also has standard images, in two directories: ftp.ipl.rpi.edu:/pub/image/still/usc ftp.ipl.rpi.edu:/pub/image/still/canon In each of those directories are the following directories: bgr - 24 bit blue, green, red color - 24 bit red, green, blue gray - 8 bit grayscale uniform weighted gray601 - 8 bit grayscale CCIR-601 weighted And in these directories are the actual images. For example, the popular lena image is in ftp.ipl.rpi.edu:/pub/image/still/usc/color/lena # 24 bit RGB ftp.ipl.rpi.edu:/pub/image/still/usc/bgr/lena # 24 bit BGR ftp.ipl.rpi.edu:/pub/image/still/usc/gray/lena # 8 bit gray All of the images are in Sun rasterfile format. You can use the pbm utilities to convert them to whatever format is most convenient. [pbm is available in ftp.ee.lbl.gov:/pbmplus*.tar.Z]. Questions about the ipl archive should be sent to rodney@ipl.rpi.edu. The archive maintainer at ftp.ipl.rpi.edu is interested in some method of establishing a canonical ftp database of images and could volunteer the ipl to be an ftp site for that database. Send suggestions to rodney@ipl.rpi.edu. Beware: the same image often comes in many different forms, at different resolutions, etc... The original lenna image is 512 wide, 512 high, 8 bits per pel, red, green and blue fields. Gray-scale versions of Lenna have been obtained in two different ways from the original: (1) Using the green field as a gray-scale image, and (2) Doing an RGB->YUV transformation and saving the Y component. Method (1) makes it easier to compare different people's results since everyone's version should be the same using that method. Method (2) produces a more correct image. For the curious: 'lena' or 'lenna' is a digitized Playboy centerfold, from November 1972. (Lenna is the spelling in Playboy, Lena is the Swedish spelling of the name.) Lena Soderberg (ne Sjooblom) was last reported living in her native Sweden, happily married with three kids and a job with the state liquor monopoly. In 1988, she was interviewed by some Swedish computer related publication, and she was pleasantly amused by what had happened to her picture. That was the first she knew of the use of that picture in the computer business. The editorial in the January 1992 issue of Optical Engineering (v. 31 no. 1) details how Playboy has finally caught on to the fact that their copyright on Lenna Sjooblom's photo is being widely infringed. It sounds as if you will have to get permission from Playboy to publish it in the future. Note on the CCITT test images, by Robert Estes <estes@eecs.ucdavis.edu>: The ccitt files are in ftp.ipl.rpi.edu:/image-archive/bitmap/ccitt. They are named ccitt-n.ras.Z where n goes from 1 to 8. Each file has an accompanying doc file called ccitt-n.ras.doc which describes the image file. Here's the doc file for ccitt-1.ras: Name ccitt-1.ras Size 1728 x 2376 x 1 Type 1 bit standard format sun rasterfile Keywords binary standard image 1 bit fax Description One of eight images from the standard binary CCITT test image set. This set is commonly used to compare binary image compression techniques. The images are are 1728x2376 pixels. ------------------------------------------------------------------------------ Subject: [56] I am looking for a message digest algorithm Look on the ftp site rsa.com, in directory /pub. MD4 and MD5 are there. This question would be more appropriate on sci.crypt. End of part 1 of the comp.compression faq.