home *** CD-ROM | disk | FTP | other *** search
/ Usenet 1994 October / usenetsourcesnewsgroupsinfomagicoctober1994disk1.iso / answers / compression-faq / part1 next >
Internet Message Format  |  1993-12-16  |  109KB

  1. Path: senator-bedfellow.mit.edu!bloom-beacon.mit.edu!nic.hookup.net!europa.eng.gtefsd.com!howland.reston.ans.net!EU.net!julienas!chorus!chorus.fr
  2. From: jloup@chorus.fr (Jean-loup Gailly)
  3. Newsgroups: comp.compression,comp.compression.research,news.answers,comp.answers
  4. Subject: comp.compression Frequently Asked Questions (part 1/3)
  5. Summary: *** READ THIS BEFORE POSTING ***
  6. Keywords: data compression, FAQ
  7. Message-ID: <compr1_16dec93@chorus.fr>
  8. Date: 16 Dec 93 14:38:28 GMT
  9. Expires: 30 Jan 94 16:17:20 GMT
  10. Sender: news@chorus.chorus.fr
  11. Reply-To: jloup@chorus.fr
  12. Followup-To: comp.compression
  13. Lines: 2534
  14. Approved: news-answers-request@MIT.Edu
  15. Supersedes: <compr1_16nov93@chorus.fr>
  16. Xref: senator-bedfellow.mit.edu comp.compression:9725 comp.compression.research:1197 news.answers:15908 comp.answers:3058
  17.  
  18. Archive-name: compression-faq/part1
  19. Last-modified: Dec 16th, 1993
  20.  
  21.         "I've already explained this once, but repetition is
  22.         the very soul of the net."        (from alt.config)
  23.  
  24. This file is part 1 of a set of Frequently Asked Questions (FAQ) for
  25. the groups comp.compression and comp.compression.research.  If you
  26. can't find part 2 or 3, see item 53 below. A copy of this FAQ is available
  27. by ftp in rtfm.mit.edu:/pub/usenet/news.answers/compression-faq/part[1-3].
  28.  
  29. Certain questions get asked time and again, and this is an attempt to
  30. reduce the bandwidth taken up by these posts and their associated
  31. replies.  If you have a question, *please* check this file before you
  32. post.  It may save a lot of peoples time.
  33.  
  34. If you have not already read the overall Usenet introductory material
  35. posted to "news.announce.newusers", please do. It is also available by
  36. ftp in garbo.uwasa.fi:/pc/doc-net/usenews.zip (see item 2 below about .zip).
  37.  
  38. If you don't want to see this FAQ regularly, please add the
  39. subject line to your kill file. If you have corrections or suggestions
  40. for this FAQ, send them to Jean-loup Gailly <jloup@chorus.fr>.
  41. Thank you.
  42.  
  43. Part 1 is oriented towards practical usage of compression programs.
  44. Part 2 is more intended for people who want to know how compression works.
  45. Part 3 is a long list of image compression hardware.
  46.  
  47. Main changes relative to the previous version: 
  48.  
  49. - added pointer to lzexe (item 2)
  50. - changed location of zip and gzip for Macintosh (item 2)
  51. - added pointer to JBIG software (item 15)
  52. - new mpeg player (item 15)
  53.  
  54.  
  55. Contents
  56. ========
  57.  
  58. General questions:
  59.  
  60. [1]  What are these newsgroups about?
  61. [2]  What is this .xxx file type?
  62.      Where can I find the corresponding compression program?
  63. [3]  What is the latest pkzip version?
  64. [4]  What is an archiver?
  65. [5]  What is the best general purpose compression program?
  66. [7]  Which books should I read?
  67. [8]  What about patents on data compression algorithms?
  68. [9]  The WEB 16:1 compressor.
  69. [11] What is the V.42bis standard?
  70. [12] I need source for the winners of the Dr Dobbs compression contest
  71. [13] I need source for arithmetic coding
  72.  
  73. Image and audio compression:
  74.  
  75. [15] Where can I get image compression programs?
  76. [16] What is the state of the art in lossless image compression?
  77. [17] What is the state of fractal compression?
  78. [18] I need specs and source for TIFF and CCITT group 4 Fax.
  79. [19] What is JPEG?
  80. [20] I am looking for source of an H.261 codec and MPEG
  81. [25] Fast DCT (Discrete Cosine Transform) algorithms
  82. [26] Are there algorithms and standards for audio compression?
  83.  
  84. Common problems:
  85.  
  86. [30] My archive is corrupted!
  87. [31] pkunzip reports a CRC error!
  88. [32] VMS zip is not compatible with pkzip!
  89. [33] I have a problem with Stacker!
  90.  
  91. Questions which do not really belong to comp.compression:
  92.  
  93. [50] What is this 'tar' compression program?
  94. [51] I need a CRC algorithm
  95. [52] What about those people who continue to ask frequently asked questions?
  96. [53] Where are FAQ lists archived?
  97. [54] I need specs for graphics formats
  98. [55] Where can I find Lenna and other images?
  99. [56] I am looking for a message digest algorithm
  100.  
  101.  
  102. Part 2: (Long) introductions to data compression techniques
  103.  
  104. [70] Introduction to data compression (long)
  105.        Huffman and Related Compression Techniques
  106.        Arithmetic Coding
  107.        Substitutional Compressors
  108.           The LZ78 family of compressors
  109.           The LZ77 family of compressors
  110.  
  111. [71] Introduction to MPEG (long)
  112.        What is MPEG?
  113.        Does it have anything to do with JPEG?
  114.        Then what's JBIG and MHEG?
  115.        What has MPEG accomplished?
  116.        So how does MPEG I work?
  117.        What about the audio compression?
  118.        So how much does it compress?
  119.        What's phase II?
  120.        When will all this be finished?
  121.        How do I join MPEG?
  122.        How do I get the documents, like the MPEG I draft?
  123.  
  124. [72] What is wavelet theory?
  125. [73] What is the theoretical compression limit?
  126. [74] Introduction to JBIG
  127. [75] Introduction to JPEG
  128.  
  129.  
  130. Part 3: (Long) list of image compression hardware
  131.  
  132. [85] Image compression hardware
  133. [99] Acknowledgments
  134.  
  135.  
  136. Search for "Subject: [#]" to get to question number # quickly. Some news
  137. readers can also take advantage of the message digest format used here.
  138.  
  139. If you know very little about data compression, read question 70 in
  140. part 2 first.
  141.  
  142. ------------------------------------------------------------------------------
  143.  
  144. Subject: [1] What are these newsgroups about?
  145.  
  146.  
  147. comp.compression is the place to discuss about data compression, both
  148. lossless (for text or data) and lossy (for images, sound, etc..).
  149. comp.compression.research was created later to provide a forum for
  150. current research on data compression and data compression algorithms;
  151. this group is now moderated. If you are not experienced in data compression,
  152. please post in comp.compression only.
  153.  
  154. If you only want to find a particular compression program for a
  155. particular operating system, please read first this FAQ and the
  156. article "How to find sources" which is regularly posted in
  157. news.answers.
  158.  
  159. If you can't resist posting such a request, other groups are probably
  160. more appropriate (comp.binaries.ibm.pc.wanted, comp.os.msdos.apps,
  161. comp.sources.wanted, comp.sys.mac.wanted, comp.archives.msdos.d,
  162. alt.graphics.pixutils). Please post your request in comp.compression
  163. only as a last resource.
  164.  
  165. If your question is about graphics only (no compression), please
  166. post to comp.graphics, *after* reading the comp.graphics FAQ (see
  167. item 54 below). For some unknown reason, many questions about
  168. graphics are incorrectly posted to comp.compression.
  169. For questions related to audio compression, check also comp.dsp.
  170.  
  171. Please do not post any program in binary form to comp.compression.
  172. Very short sources can be posted, but long sources should be be posted
  173. to the specialized source groups, such as comp.sources.* or alt.sources.
  174.  
  175. As for any newsgroups, do not post the same message separately to
  176. comp.compression and comp.compression.research.
  177.  
  178. ------------------------------------------------------------------------------
  179.  
  180. Subject: [2] What is this .xxx file type?
  181.              Where can I find the corresponding compression program?
  182.  
  183.  
  184. All the programs mentioned in this section are lossless.
  185. For most programs, one US and one European ftp site are given.
  186. (wuarchive.wustl.edu: 128.152.135.4, garbo.uwasa.fi: 128.214.87.1)
  187. Many other sites (in particular wsmr-simtel20.army.mil: 192.88.110.2)
  188. have the same programs.
  189.  
  190. To keep this list to a reasonable size, many programs are not
  191. mentioned here. Additional information can be found in the file
  192. ftp.cso.uiuc.edu:/doc/pcnet/compression [128.174.5.61] maintained by
  193. David Lemson (lemson@uiuc.edu). When several programs can handle
  194. the same archive format, only one of them is given.
  195.  
  196. Sources for additional lossless data compressors can be found in
  197. garbo.uwasa.fi:/pc/programming/lds_11.zip and
  198. oak.oakland.edu:/pub/msdos/archivers/lz-comp2.zip.
  199. Sources in Pascal are in garbo.uwasa.fi:/pc/turbopas/preskit2.zip.
  200.  
  201. For Macintosh programs, look on sumex-aim.stanford.edu:/info-mac [36.44.0.6].
  202. For VM/CMS, look on vmd.cso.uiuc.edu:/public.477 [128.174.5.98].
  203. For Atari, look on atari.archive.umich.edu [141.211.165.41]
  204. For Amiga, look on ftp.cso.uiuc.edu:/pub/amiga [128.174.5.59]
  205.     
  206. If you don't know how to use ftp or don't have ftp access, read the
  207. article "How to find sources" which is regularly posted in news.answers.
  208.  
  209. If you can't find a program given below, it is likely that a newer
  210. version exists in the same directory. (Tell me <jloup@chorus.fr>)
  211.  
  212. A very short description of the compression algorithm is given for
  213. most programs. For the meaning of LZ77, LZ78 and LZW, see question 
  214. 70 in part 2 of the FAQ.)
  215.  
  216. ext:  produced by or read by
  217.  
  218. .arc: arc, pkarc for MSDOS. (LZW algorithm)
  219.     wuarchive.wustl.edu:/mirrors/msdos/starter/pk361.exe
  220.     garbo.uwasa.fi:/pc/arcers/pk361.exe
  221.  
  222.       arc for Unix
  223.         wuarchive.wustl.edu:/mirrors/misc/unix/arc521e.tar-z
  224.     garbo.uwasa.fi:/unix/arcers/arc.tar.Z
  225.         Contact: Howard Chu <hyc@umix.cc.umich.edu>
  226.  
  227.       arc for VMS
  228.     wuarchive.wustl.edu:/packages/compression/vax-vms/arc.exe
  229.  
  230.       arcmac for Mac
  231.     mac.archive.umich.edu:/mac/utilities/compressionapps/arcmac.hqx
  232.  
  233.       arc for Amiga
  234.     ftp.funet.fi:pub/amiga/fish/001-100/ff070/arc.lha
  235.  
  236. .arj: arj for MSDOS (LZ77 with hashing, plus secondary static Huffman
  237.           encoding on a block basis)
  238.         Contact: Robert K Jung <robjung@world.std.com>
  239.         wuarchive.wustl.edu:/mirrors/msdos/archivers/arj241a.exe
  240.     garbo.uwasa.fi:/pc/arcers/arj241a.exe
  241.  
  242.       unarj for Unix. Decompresses only. (There is no arj compressor for Unix.
  243.         Don't post a request.)
  244.         wuarchive.wustl.edu:/mirrors/misc/unix/unarj241.tar-z
  245.     garbo.uwasa.fi:/unix/arcers/unarj241.tar.Z
  246.  
  247.       unarj for Mac
  248.         mac.archive.umich.edu:/mac/util/compression/unarjmac.cpt.hqx      
  249.  
  250.       unarj for Amiga
  251.     ftp.funet.fi:pub/amiga/utilities/archivers/unarj-0.5.lha
  252.  
  253. .bck: VMS BACKUP. BACKUP is *not* a compression program. Do "help backup".
  254.  
  255. .cpt: Compact Pro for Mac
  256.         sumex-aim.stanford.edu:/info-mac/util/compact-pro-133.hqx [36.44.0.6]
  257.  
  258.       For Unix:
  259.     sumex-aim.stanford.edu:/info-mac/unix/macutil-20b1.shar
  260.         ftp.cwi.nl:/pub/macutil2.0b3.shar.Z
  261.  
  262. .exe: self-extracting MSDOS executable (creates files on disk when run)
  263.       Run the file, or try unzip, lha or arj on it.
  264.  
  265. .exe: compressed MSDOS executable (decompresses itself in memory then runs
  266.       the decompressed code). To get the original uncompressed .exe:
  267.         oak.oakland.edu:/pub/msdos/execomp/unp312.zip
  268.       To create such files:
  269.         oak.oakland.edu:/pub/msdos/execomp/lzexe91e.zip
  270.  
  271. .gif: gif files are images compressed with the LZW algorithm. See the
  272.       comp.graphics FAQ list for programs manipulating .gif files. See
  273.       suffix .Z below for source of LZW.
  274.  
  275. .gz, .z:  gzip (or pack, see .z below). gzip uses the same algorithm as
  276.           zip 2.0 (see below); it can also extract packed and compressed files.
  277.       For Unix, MSDOS, OS/2, VMS, Atari, Amiga, Primos:
  278.     prep.ai.mit.edu:/pub/gnu/gzip-1.2.4.tar   (or .shar or .tar.z : source)
  279.     prep.ai.mit.edu:/pub/gnu/gzip-msdos-1.2.4.exe (MSDOS, lha self-extract)
  280.     garbo.uwasa.fi:/unix/arcers/gzip-1.2.4.tar.Z  (source)
  281.     garbo.uwasa.fi:/pc/unix/gzip124.zip           (MSDOS exe, self-extract)
  282.     ftp.uu.net:/pub/archiving/zip/VMS/gzip123x.exe (VMS exe)
  283.         mac.archive.umich.edu:/mac/util/compression/macgzip0.1b2.cpt.hqx (Macintosh)
  284.  
  285. .ha:  ha 0.98 for MSDOS (improved PPMC - 4th order Markov modeling)
  286.     garbo.uwasa.fi:/pc/arcers/ha098.exe
  287.  
  288. .hqx: Macintosh BinHex format.. (BinHex is *not* a compression program,
  289.     it is similar to uuencode but handles multiple forks.)
  290.        for Mac:
  291.      mac.archive.umich.edu:/mac/utilities/compressionapps/binhex4.0.bin
  292.  
  293.        for Unix:
  294.          sumex-aim.stanford.edu:/info-mac/cmp/mcvert-212.shar [36.44.0.6]
  295.  
  296.        for MSDOS:
  297.          wuarchive.wustl.edu:/mirrors/msdos/xbin23.zip
  298.  
  299. .lha:
  300. .lzh: lha for MSDOS (LZ77 with a trie data structure, plus secondary static
  301.           Huffman coding on a block basis)
  302.     wuarchive.wustl.edu:/mirrors/msdos/archivers/lha213.exe   (exe)
  303.     wuarchive.wustl.edu:/mirrors/msdos/archivers/lha211sr.zip (sources)
  304.     garbo.uwasa.fi:/pc/arcers/lha255b.exe
  305.  
  306.       lharc for Unix. (LZ77 with hash table and binary trees, plus secondary
  307.           Huffman coding)
  308.            Warning: lharc can extract .lzh files created by
  309.            lharc 1.xx but not those created by lha. See lha for Unix below.
  310.         wuarchive.wustl.edu:/mirrors/misc/unix/lharc102a.tar-z
  311.     garbo.uwasa.fi:/unix/arcers/lharcsrc.zoo
  312.  
  313.       lharc for VMS. Same warning as for Unix lharc.
  314.     wuarchive.wustl.edu:/packages/compression/vax-vms/lharc.exe
  315.  
  316.       lha for Unix. Warning: all doc is in Japanese.
  317.     wuarchive.wustl.edu:/mirrors/misc/unix/lha101u.tar-z
  318.     garbo.uwasa.fi:/unix/arcers/lha-1.00.tar.Z
  319.           Contact: lha-admin@oki.co.jp or oki@wbg.telcom.oki.co.jp
  320.  
  321.       lha for Mac
  322.         mac.archive.umich.edu:/mac/utilities/compressionapps/maclha2.0.cpt.hqx
  323.  
  324.       lha for Amiga
  325.     ftp.funet.fi:pub/amiga/utilities/archivers/LhA_e138.run
  326.  
  327.  
  328. .pak: pak for MSDOS (LZW algorithm)
  329.         wuarchive.wustl.edu:/mirrors/msdos/archivers/pak251.exe
  330.     garbo.uwasa.fi:/pc/arcers/pak251.exe
  331.  
  332. .pit: PackIt (Macintosh)
  333.        for Mac:
  334.          sumex-aim.stanford.edu:/info-mac/util/stuffit-151.hqx  [36.44.0.6]
  335.  
  336.        for Unix:
  337.          sumex-aim.stanford.edu:/info-mac/unix/mcvert-165.shar [36.44.0.6]
  338.  
  339. .pp: PowerPacker (Amiga)
  340.     ftp.funet.fi:pub/amiga/fish/501-600/ff561/PPLib.lha
  341.  
  342. .sea: self-extracting archive (Macintosh)
  343.          Run the file to extract it. The self-extraction code can be
  344.          removed with:
  345.       mac.archive.umich.edu:/mac/utilities/compressionapps/desea1.11.cpt.hqx
  346.  
  347. .sdn: used by the Shareware Distribution Network.
  348.       Try the decompressors for .pak or .arj (see above)
  349.  
  350. .shar:  Shell archive. This is not a compression program. Use "sh foo.shar"
  351.         to extract.
  352.  
  353. .sit: Stuffit for Macintosh
  354.        for Mac:
  355.          sumex-aim.stanford.edu:/info-mac/util/stuffit-lite-30.hqx [36.44.0.6]
  356.  
  357.        for Unix:
  358.          sumex-aim.stanford.edu:/info-mac/cmp/unsit-15-unix.shar [36.44.0.6]
  359.  
  360.        for Amiga:
  361.      ftp.funet.fi:pub/amiga/utilities/archivers/unsit-1.5c2.lha
  362.  
  363.        for MSDOS:
  364.      garbo.uwasa.fi:/pc/arcers/unsit30.zip
  365.  
  366. .?q?: Squeeze for MSDOS (do not confuse with other 'squeeze' below).
  367.       Static Huffman coding.
  368.     oak.oakland.edu:/pub/msdos/starter/sqpc12a.com (squeeze)
  369.     oak.oakland.edu:/pub/msdos/starter/nusq110.com (unsqueeze)
  370.  
  371. .sqz: Squeeze for MSDOS (do not confuse with other 'squeeze' above)
  372.       LZ77 with hashing.
  373.     wuarchive.wustl.edu:/mirrors/msdos/archivers/sqz1083e.exe
  374.         garbo.uwasa.fi:/pc/arcers/sqz1083e.exe
  375.  
  376. .tar: tar is *not* a compression program. However, to be kind for you:
  377.       for MSDOS
  378.     wuarchive.wustl.edu:/mirrors/msdos/starter/tarread.exe
  379.     garbo.uwasa.fi:/pc/unix/tar4dos.zoo
  380.  
  381.       for Unix
  382.         tar (you have it already. To extract: tar xvf file.tar)
  383.  
  384.       for VMS
  385.     wuarchive.wustl.edu:/packages/compression/vax-vms/tar.exe
  386.  
  387.       for Macintosh
  388.         sumex-aim.stanford.edu:/info-mac/util/tar-30.hqx
  389.  
  390.       for Amiga:
  391.     ftp.funet.fi:pub/amiga/fish/401-500/ff445/Tar.lha
  392.  
  393. .tar.Z, .tar-z, .taz: tar + compress
  394.       For Unix:     zcat file.tar.Z | tar xvf -
  395.       with GNU tar: tar xvzf file.tar.Z
  396.       Other OS: first uncompress (see .Z below) then untar (see .tar above)
  397.  
  398. .tar.z, .tgz: tar + gzip
  399.       For Unix: gzip -cd file.tar.z | tar xvf -
  400.       with GNU tar: tar xvzf file.tar.z
  401.       Other OS: first uncompress (see .z below) then untar (see .tar above)
  402.  
  403. .z:   pack or gzip (see .gz above). pack uses static Huffman coding.
  404.       To extract, see .gz above.
  405.  
  406. .zip: pkzip 1.10 for MSDOS. (LZ77 with hashing, plus secondary static
  407.           Shannon-Fano encoding on whole file)
  408.            Contact: pkware.inc@mixcom.com
  409.          wuarchive.wustl.edu:/mirrors/msdos/zip/pkz110eu.exe.
  410.          garbo.uwasa.fi:/pc/goldies/pkz110eu.exe.
  411.            Note: pkz110eu.exe is an 'export' version without encryption.
  412.  
  413.       zip 1.1 for Unix, MSDOS, VMS, OS/2, ... (compatible with pkzip 1.10.
  414.      For corresponding unzip, see unzip 5.0p1 below).
  415.      ftp.uu.net:/pub/archiving/zip/zip11.zip
  416.  
  417.       arcutil 2.0 for VM/CMS (unzip only, not yet compatible with pkzip 2.04)
  418.          vmd.cso.uiuc.edu:/public.477/arcutil.* [128.174.5.98].
  419.  
  420.       pkzip 2.04g for MSDOS. (LZ77 with hashing, plus secondary static
  421.            Huffman coding on a block basis)
  422.      oak.oakland.edu:/pub/msdos/zip/pkz204g.exe
  423.          garbo.uwasa.fi:/pc/arcers/pkz204g.exe
  424.  
  425.       zip 2.0.1 and unzip 5.0p1 for Unix, MSDOS, VMS, OS/2, Amiga, ...
  426.           Compatible with pkzip 2.04g (LZ77 with hashing, plus secondary static
  427.           Huffman coding on a block basis)
  428.             Contact: zip-bugs@wkuvx1.bitnet
  429.      ftp.uu.net:/pub/archiving/zip/zip201.zip          (source)
  430.      ftp.uu.net:/pub/archiving/zip/unz50p1.tar.Z       (source)
  431.      ftp.uu.net:/pub/archiving/zip/MSDOS/zip20x.zip    (MSDOS exe)
  432.      ftp.uu.net:/pub/archiving/zip/MSDOS/unz50p1.exe   (MSDOS exe)
  433.      ftp.uu.net:/pub/archiving/zip/VMS/unz50p1x.exe    (Vax/VMS exe)
  434.      ftp.uu.net:/pub/archiving/zip/VMS/zip20x-vms.zip  (Vax/VMS exe)
  435.      ftp.uu.net:/pub/archiving/zip/AMIGA/unz51d3x.tar.Z(Amiga exe)
  436.      ftp.uu.net:/pub/archiving/zip/AMIGA/zip201x.zip   (Amiga exe)
  437.      ftp.uu.net:/pub/archiving/zip/OS2*/*              (OS/2 exe 16&32 bit)
  438.      ftp.uu.net:/pub/archiving/zip/zcrypt20.zip        (encryption source)
  439.          (Non US residents must get the crypt versions from garbo,see below)
  440.  
  441.      garbo.uwasa.fi:/unix/arcers/zip201.zip    (source)
  442.      garbo.uwasa.fi:/unix/arcers/unz50p1.tar.Z (source)
  443.      garbo.uwasa.fi:/pc/arcers/zip20x.zip      (MSDOS exe)
  444.      garbo.uwasa.fi:/pc/arcers/unz50p1.exe     (MSDOS exe)
  445.          garbo.uwasa.fi:/unix/arcers/zcrypt20.zip  (encryption source)
  446.  
  447.        for Macintosh:
  448.          mac.archive.umich.edu:/mac/util/compression/unzip2.01.cpt.hqx
  449.      mac.archive.umich.edu:/mac/util/compression/unzipmac5.0p1.cpt.hqx
  450.      mac.archive.umich.edu:/mac/util/compression/zipit1.2.cpt.hqx
  451.  
  452. .zoo: zoo 2.10 for MSDOS (algorithm copied from that of lha, see lha above)
  453.       Contact: Rahul Dhesi <dhesi@cirrus.com>
  454.      wuarchive.wustl.edu:/mirrors/msdos/zoo/zoo210.exe
  455.      garbo.uwasa.fi:/pc/arcers/zoo210.exe
  456.  
  457.       zoo 2.10 for Unix, VMS
  458.          wsmr-simtel20.army.mil:pd8:<misc.unix>zoo210.tar-z [192.88.110.2]
  459.      garbo.uwasa.fi:/unix/arcers/zoo210.tar.Z
  460.  
  461.       zoo for Mac
  462.       mac.archive.umich.edu:/mac/utilities/compressionapps/maczoo.sit.hqx
  463.  
  464.       zoo for Amiga
  465.     ftp.funet.fi:pub/amiga/utilities/archivers/Zoo-2.1.lha
  466.  
  467. .F: freeze for Unix (LZ77 with hashing, plus secondary dynamic Huffman
  468.          encoding)
  469.      wuarchive.wustl.edu:/usenet/comp.sources.misc/volume35/freeze/part0[1-3].Z
  470.      ftp.inria.fr:/system/arch-compr/freeze-2.5.tar.Z
  471.      Contact: Leonid A. Broukhis <leo@s514.ipmce.su>
  472.  
  473. .Y: yabba for Unix, VMS, ... (Y coding, a variant of LZ78)
  474.   wuarchive.wustl.edu:/usenet/comp.sources.unix/volume24/yabbawhap/part0[1-4].Z
  475.   ftp.inria.fr:/system/arch-compr/yabba.tar.Z
  476.   Contact: Dan Bernstein <brnstnd@nyu.edu>
  477.  
  478. .Z: compress for Unix ('the' LZW algorithm)
  479.       It is likely that your Unix system has 'compress' already. Otherwise:
  480.     wuarchive.wustl.edu:/packages/compression/compress-4.1.tar
  481.         (not in .Z format to avoid chicken and egg problem)
  482.  
  483.     compress for MSDOS
  484.     wuarchive.wustl.edu:/mirrors/msdos/compress/comp430[ds].zip
  485.     garbo.uwasa.fi:/pc/unix/comp430d.zip
  486.  
  487.     compress for Macintosh
  488.         sumex-aim.stanford.edu:/info-mac/util/maccompress-32.hqx
  489.  
  490.     compress for Amiga
  491.     ftp.funet.fi:pub/amiga/utilities/archivers/compress-4.1.lha
  492.  
  493.     compress for Vax/VMS
  494.     wuarchive.wustl.edu:/packages/compression/vax-vms/lzcomp.exe
  495.     wuarchive.wustl.edu:/packages/compression/vax-vms/lzdcmp.exe
  496.  
  497. ------------------------------------------------------------------------------
  498.  
  499. Subject: [3]  What is the latest PKZIP version?
  500.  
  501. The latest official version is 2.04g. Release 2.04c had serious bugs,
  502. corrected in 2.04e and 2.04g.
  503.  
  504. Be warned that there are countless bogus PKZIP 1.20, 2.0, 2.02,
  505. 3.05 and whatever scams floating around.  They usually are hacks of
  506. PKZIP 1.93A beta test version.  Some of them are trojans and / or
  507. carry computer virii.
  508.  
  509. ------------------------------------------------------------------------------
  510.  
  511. Subject: [4] What is an archiver?
  512.  
  513.  
  514. There is a distinction between archivers and other compression
  515. programs:
  516.  
  517. - an archiver takes several input files, compresses them and produces
  518.   a single archive file. Examples are arc, arj, lha, zip, zoo.
  519.  
  520. - other compression programs create one compressed file for each
  521.   input file. Examples are freeze, yabba, compress. Such programs
  522.   are often combined with tar to create compressed archives (see
  523.   question 50: "What is this tar compression program?").
  524.  
  525. ------------------------------------------------------------------------------
  526.  
  527. Subject: [5] What is the best general purpose compression program?
  528.  
  529.  
  530. The answer is: it depends. (You did not expect a definitive answer,
  531. did you?)
  532.  
  533. It depends whether you favor speed, compression ratio, a standard and
  534. widely used archive format, the number of features, etc...  Just as
  535. for text editors, personal taste plays an important role. compress has
  536. 4 options, arj 2.30 has about 130 options; different people like
  537. different programs. *Please* do not start or continue flame wars on
  538. such matters of taste.
  539.  
  540. The only objective comparisons are speed and compression ratio. Here
  541. is a short table comparing various programs on a 33Mhz Compaq 386.
  542. All programs have been run on Unix SVR4, except pkzip and arj which
  543. only run on MSDOS. (MSDOS benchmarks are available by ftp on
  544. oak.oakland.edu:/pub/msdos/info/arctst*.zip.)
  545.  
  546. *Please* do not post your own benchmarks made on your own files that
  547. nobody else can access. If you think that you must absolutely post yet
  548. another benchmark, make sure that your test files are available by
  549. anonymous ftp.
  550.  
  551. The programs compared here were chosen because they are the most
  552. popular or because they run on Unix and source is available.  For ftp
  553. information, see above. Three programs (hpack, comp-2 and ha) have
  554. been added because they achieve better compression (at the expense of
  555. speed) and one program (lzrw3-a) has been added because it favors
  556. speed at the expense of compression:
  557.  
  558. - comp-2 is in wuarchive.wustl.edu:/mirrors/msdos/ddjmag/ddj9102.zip
  559.   (inner zip file nelson.zip),
  560. - hpack is in wuarchive.wustl.edu:/mirrors/misc/unix/hpack75a.tar-z
  561.   and garbo.uwasa.fi:/unix/arcers/hpack78src.tar.Z
  562. - ha 0.98 is in garbo.uwasa.fi:/pc/arcers/ha098.zip
  563. - ftp.adelaide.edu.au:/pub/compression/lzrw3-a.c  [129.127.40.3]
  564.  
  565. The 14 files used in the comparison are from the standard Calgary
  566. Text Compression Corpus, available by ftp on ftp.cpsc.ucalgary.ca 
  567. [136.159.7.18] in /pub/text.compression.corpus/text.compression.corpus.tar.Z.
  568.  
  569. The whole corpus includes 18 files, but the 4 files paper[3-6] are
  570. generally omitted in benchmarks. It contains several kinds of file
  571. (ascii, binary, image, etc...) but has a bias towards large files.
  572. You may well get different ratings on the typical mix of files that
  573. you use daily, so keep in mind that the comparisons given below are
  574. only indicative.
  575.  
  576. The programs are ordered by decreasing total compressed size. For a
  577. fair comparison between archivers and other programs, this size is
  578. only the size of the compressed data, not the archive size.
  579.  
  580. The programs were run on an idle machine, so the elapsed time
  581. is significant and can be used to compare Unix and MSDOS programs.
  582.  
  583. [Note: I did not have time to run again all benchmarks with more
  584. recent versions of zip, freeze, arj and hpack. To be done for some
  585. future revision of this FAQ.]
  586.  
  587.        size     lzrw3a   compress    lharc    yabba     pkzip    freeze 
  588. version:                   4.0       1.02      1.0       1.10     2.3.5
  589. options:                                    -m300000                    
  590.        ------    -----    ------    ------    ------    ------   ------
  591. bib    111261    49040     46528     46502     40456     41354    41515 
  592. book1  768771   416131    332056    369479    306813    350560   344793 
  593. book2  610856   274371    250759    252540    229851    232589   230861 
  594. geo    102400    84214     77777     70955     76695     76172    68626 
  595. news   377109   191291    182121    166048    168287    157326   155783 
  596. obj1    21504    12647     14048     10748     13859     10546    10453 
  597. obj2   246814   108040    128659     90848    114323     90130    85500 
  598. paper1  53161    24522     25077     21748     22453     20041    20021 
  599. paper2  82199    39479     36161     35275     32733     32867    32693 
  600. pic    513216   111000     62215     61394     65377     63805    53291 
  601. progc   39611    17919     19143     15399     17064     14164    14143 
  602. progl   71646    24358     27148     18760     23512     17255    17064 
  603. progp   49379    16801     19209     12792     16617     11877    11686 
  604. trans   93695    30292     38240     28092     31300     23135    22861 
  605.     3,141,622  1,400,105 1,259,141 1,200,580 1,159,340 1,141,821 1,109,290
  606. real             0m35s     0m59s     5m03s     2m40s              5m27s
  607. user             0m25s     0m29s     4m29s     1m46s              4m58s
  608. sys              0m05s     0m10s     0m07s     0m18s              0m08s
  609. MSDOS:                                                   1m39s
  610.                         
  611.  
  612.          zoo       lha       arj      pkzip    zip      hpack   comp-2    ha
  613.         2.10    1.0(Unix)   2.30      2.04g    1.9      0.75a            0.98
  614.          ah    2.13(MSDOS)   -jm       -ex      -6                        a2
  615.        ------    ------    ------    ------  -------   ------   ------  ------
  616. bib     40742     40740     36090     35186    34950    35619    29840   26927
  617. book1  339076    339074    318382    313566   312619   306876   237380  235733
  618. book2  228444    228442    210521    207204   206306   208486   174085  163535
  619. geo     68576     68574     69209     68698    68418    58976    64590   59356
  620. news   155086    155084    146855    144954   144395   141608   128047  123335
  621. obj1    10312     10310     10333     10307    10295    10572    10819    9799
  622. obj2    84983     84981     82052     81213    81336    80806    85465   80381
  623. paper1  19678     19676     18710     18519    18525    18607    16895   15675
  624. paper2  32098     32096     30034     29566    29674    29825    25453   23956
  625. pic     52223     52221     53578     52777    55051    51778    55461   51639
  626. progc   13943     13941     13408     13363    13238    13475    12896   11795
  627. progl   16916     16914     16408     16148    16175    16586    17354   15298
  628. progp   11509     11507     11308     11214    11182    11647    11668   10498
  629. trans   22580     22578     20046     19808    18879    20506    21023   17927
  630.     1,096,166 1,096,138 1,036,934 1,019,451 1,021,043 1,005,367 890,976 845,854
  631. real    4m07s     6m03s                        1m49s   1h22m17s  27m05s
  632. user    3m47s     4m23s                        1m43s   1h20m46s  19m27s
  633. sys     0m04s     0m08s                        0m02s      0m12s   2m03s
  634. MSDOS:            1m49s     2m41s     1m43s                              14m43s
  635.  
  636. Notes:
  637.  
  638. - the compressed data for 'zoo ah' is always two bytes longer than for
  639.   lha. This is simply because both programs are derived from the same
  640.   source (ar002, written by Haruhiko Okumura, available by ftp in
  641.   wuarchive.wustl.edu:/mirrors/msdos/archivers/ar002.zip).
  642.  
  643. - hpack 0.75a gives slightly different results on SunOS. (To be checked
  644.   with latest version of hpack).
  645.  
  646. - the MSDOS versions are all optimized with assembler code and were run
  647.   on a RAM disk. So it is not surprising that they often go faster than
  648.   their Unix equivalent.
  649.  
  650. ------------------------------------------------------------------------------
  651.  
  652. Subject: [7] Which books should I read?
  653.  
  654.  
  655. [BWC 1989] Bell, T.C, Cleary, J.G. and Witten, I.H, "Text Compression",
  656.     Prentice-Hall 1989. ISBN: 0-13-911991-4. Price: approx. US$60
  657.     The reference on text data compression.
  658.  
  659. [Nel 1991] Mark Nelson, "The Data Compression Book"
  660.     M&T Books, Redwood City, CA, 1991.  ISBN 1-55851-216-0.
  661.     Price $36.95 including two 5" PC-compatible disks bearing
  662.     all the source code printed in the book.
  663.     A practical introduction to data compression.
  664.     The book is targeted at a person who is comfortable reading C code but
  665.     doesn't know anything about data compression.  Its stated goal is to get
  666.     you up to the point where you are competent to program standard
  667.     compression algorithms.
  668.  
  669. [Will 1990] Williams, R.  "Adaptive Data Compression", Kluwer Books, 1990.
  670.     ISBN: 0-7923-9085-7. Price: US$75.
  671.     Reviews the field of text data compression and then addresses the
  672.     problem of compressing rapidly changing data streams.
  673.  
  674. [Stor 1988] Storer, J.A.  "Data Compression: Methods and Theory", Computer
  675.     Science Press, Rockville, MD. ISBN: 0-88175-161-8.
  676.     A survey of various compression techniques, mainly statistical
  677.     non-arithmetic compression and LZSS compression.  Includes complete Pascal
  678.     code for a series of LZ78 variants.
  679.  
  680. [Stor 1992] Storer, J.A. "Image and Text Compression", Kluwer Academic
  681.     Publishers, 1992, ISBN 0-7923-9243-4
  682.  
  683. [ACG 1991] Advances in Speech Coding, edited by Atal, Cuperman, and Gersho,
  684.     Kluwer Academic Press, 1991.
  685.  
  686. [GG 1991] Vector Quantization and Signal Compression, by Gersho and Gray,
  687.     Kluwer Acad. Press, 1991, ISBN 0-7923-9181-0.
  688.  
  689. [CT 1991] Elements of Information Theory, by T.M.Cover and J.A.Thomas
  690.      John Wiley & Sons, 1991. ISBN 0-471-06259-6.
  691.  
  692. Review papers:
  693.  
  694. [BWC 1989] Bell, T.C, Witten, I.H, and Cleary, J.G.  "Modeling for Text
  695.     Compression", ACM Computing Surveys, Vol.21, No.4 (December 1989), p.557
  696.     A good general overview of compression techniques (as well as modeling for
  697.     text compression); the condensed version of "Text Compression".
  698.  
  699. [Lele 1987] Lelewer, D.A, and Hirschberg, D.S.  "Data Compression", ACM
  700.     Computing Surveys, Vol.19, No.3 (September 1987), p.261.
  701.     A survey of data compression techniques which concentrates on Huffman
  702.     compression and makes only passing mention of other techniques.
  703.  
  704.  
  705. ------------------------------------------------------------------------------
  706.  
  707. Subject: [8] What about patents on data compression algorithms?
  708.  
  709.  
  710. [Note: the appropriate group for discussing software patents is
  711. comp.patents (or misc.legal.computing), not comp.compression.]
  712.  
  713. All patents mentioned here are US patents, and thus probably
  714. not applicable outside the US. See item 70, "Introduction to data
  715. compression" for the meaning of LZ77, LZ78 or LZW.
  716.  
  717.  
  718. (a) Run length encoding
  719.  
  720. - Tsukiyama has two patents on run length encoding: 4,586,027 and 4,872,009
  721.   granted in 1986 and 1989 respectively. The first one covers run length
  722.   encoding in its most primitive form: a length byte followed by the
  723.   repeated byte. The second patent covers the 'invention' of limiting the
  724.   run length to 16 bytes and thus the encoding of the length on 4 bits.
  725.   Here is the start of claim 1 of patent 4,872,009, just for pleasure:
  726.  
  727.     1. A method of transforming an input data string comprising a plurality
  728.     of data bytes, said plurality including portions of a plurality of
  729.     consecutive data bytes identical to one another, wherein said data
  730.     bytes may be of a plurality of types, each type representing different
  731.     information, said method comprising the steps of: [...]
  732.  
  733. - O'Brien has patented (4,988,998) run length encoding followed by LZ77.
  734.  
  735.  
  736. (b) LZ77
  737.  
  738. - Waterworth patented (4,701,745) the algorithm now known as LZRW1,
  739.   because Ross Williams reinvented it later and posted it on
  740.   comp.compression on April 22, 1991. (See item 5 for the ftp site
  741.   with all LZRW derivatives.) The *same* algorithm has later been
  742.   patented by Gibson & Graybill (see below). The patent office failed
  743.   to recognize that the same algorithm was patented twice, even though
  744.   the wording used in the two patents is very similar.
  745.  
  746.   The Waterworth patent is now owned by Stac Inc, and used as the basis
  747.   of a lawsuit against Microsoft, concerning the compression feature
  748.   of MSDOS 6.0.
  749.  
  750. - Fiala and Greene obtained in 1990 a patent (4,906,991) on all
  751.   implementations of LZ77 using a tree data structure. Claim 1 of the
  752.   patent is much broader than the algorithms published by Fiala and
  753.   Greene in Comm.ACM, April 89. The patent covers the algorithm
  754.   published by Rodeh and Pratt in 1981 (J. of the ACM, vol 28, no 1,
  755.   pp 16-24).  It also covers the algorithm previously patented by
  756.   Eastman-Lempel-Ziv (4,464,650), and the algorithms used in lharc,
  757.   lha and zoo.
  758.  
  759. - Notenboom (from Microsoft) 4,955,066 uses three levels of
  760.   compression, starting with run length encoding.
  761.  
  762. - The Gibson & Graybill patent 5,049,881 covers the LZRW1 algorithm
  763.   previously patented by Waterworth and reinvented by Ross Williams.
  764.   Claims 4 and 12 are very general and could be interpreted as
  765.   applying to any LZ algorithm using hashing (including all variants
  766.   of LZ78):
  767.  
  768.      4. A compression method for compressing a stream of input data into
  769.      a compressed stream of output data based on a minimum number of
  770.      characters in each input data string to be compressed, said
  771.      compression method comprising the creation of a hash table, hashing
  772.      each occurrence of a string of input data and subsequently searching
  773.      for identical strings of input data and if such an identical string
  774.      of input data is located whose string size is at least equal to the
  775.      minimum compression size selected, compressing the second and all
  776.      subsequent occurrences of such identical string of data, if a string
  777.      of data is located which does not match to a previously compressed
  778.      string of data, storing such data as uncompressed data, and for each
  779.      input strings after each hash is used to find a possible previous
  780.      match location of the string, the location of the string is stored
  781.      in the hash table, thereby using the previously processed data to
  782.      act as a compression dictionary.
  783.  
  784.   Claim 12 is identical, with 'method' replaced with 'apparatus'.  Since
  785.   the 'minimal compression size' can be as small as 2, the claim could
  786.   cover any dictionary technique of the LZ family. However the text of the
  787.   patent and the other claims make clear that the patent should cover the
  788.   LZRW1 algorithm only. (In any case the Gibson & Graybill patent is likely
  789.   to be invalid because of the prior art in the Waterworth patent.)
  790.  
  791. - Phil Katz, author of pkzip, also has a patent on LZ77 (5,051,745)
  792.   but the claims only apply to sorted hash tables, and when the hash
  793.   table is substantially smaller than the window size.
  794.  
  795. - IBM patented (5,001,478) the idea of combining a history buffer (the
  796.   LZ77 technique) and a lexicon (as in LZ78).
  797.  
  798. - Stac Inc patented (5,016,009 and 5,126,739) yet another variation of LZ77
  799.   with hashing. The '009 patent is used in the lawsuit against Microsoft
  800.   (see above). Stac also has patents on LZ77 with parallel lookup in
  801.   hardware (4,841,092 and 5,003,307).
  802.  
  803. - Robert Jung, author of 'arj', has been granted patent 5,140,321
  804.   for one variation of LZ77 with hashing.  This patent covers the LZRW3-A
  805.   algorithm, also previously discovered by Ross Williams. LZRW3-A was posted
  806.   on comp.compression on July 15, 1991. The patent was filed two months later
  807.   on Sept 4, 1991. (The US patent system allows this because of the
  808.   'invention date' rule.)
  809.  
  810. - Chambers 5,155,484 is yet another variation of LZ77 with hashing.
  811.   The hash function is just the juxtaposition of two input bytes,
  812.   this is the 'invention' being patented. The hash table is named
  813.   'direct lookup table'.
  814.  
  815.  
  816. (c) LZ78
  817.  
  818. - One form of the original LZ78 algorithm was patented (4,464,650) by
  819.   its authors Lempel, Ziv, Cohn and Eastman.
  820.  
  821. - The LZW algorithm used in 'compress' is patented by IBM (4,814,746)
  822.   and Unisys (4,558,302). It is also used in the V.42bis compression
  823.   standard (see question 11 on V.42bis below) and in Postscript Level 2.
  824.   (Unisys sells the license to modem manufacturers for a onetime
  825.   $25,000 fee.) The IBM patent application was filed three weeks
  826.   before that of Unisys, but the US patent office failed to recognize
  827.   that they covered the same algorithm. (The IBM patent is more
  828.   general, but its claim 7 is exactly LZW.)
  829.  
  830. - AP coding is patented by Storer (4,876,541). (Get the yabba package
  831.   for source code, see question 2 above, file type .Y)
  832.  
  833.  
  834. (d) arithmetic coding
  835.  
  836. - IBM holds many patents on arithmetic coding (4,286,256 4,295,125
  837.   4,463,342 4,467,317 4,633,490 4,652,856 4,891,643 4,905,297 4,935,882).
  838.   It has patented in particular the Q-coder implementation of arithmetic
  839.   coding.  The arithmetic coding option of the JPEG standard requires
  840.   use of the patented algorithm.  No JPEG-compatible method is
  841.   possible without infringing the patent, because what IBM actually
  842.   claims rights to is the underlying probability model (the heart of
  843.   an arithmetic coder). (See the JPEG FAQ for details.)
  844.  
  845.   AT&T has 3 patents on arithmetic coding (4,973,961, 5,023,611, 5,025,258).
  846.  
  847.  
  848. As can be seen from the above list, some of the most popular compression
  849. programs (compress, pkzip, zoo, lha, arj) are now covered by patents.
  850. (This says nothing about the validity of these patents.)
  851.  
  852. Here are some references on data compression patents. A number of them are
  853. taken from the list prep.ai.mit.edu:/pub/lpf/patent-list.
  854.  
  855. 3,914,586
  856. Data compression method and apparatus
  857. filed 10/25/73, granted 10/21/75
  858. General Motors Corporation, Detroit MI
  859. Duane E. McIntosh, Santa Ynez CA
  860. Data compression apparatus is disclosed is operable in either a bit
  861. pair coding mode of a word coding mode depending on the degree of
  862. redundancy of the data to be encoded.
  863.  
  864. 3,976,844
  865. Data communication system for transmitting data in compressed form
  866. filed Apr. 4, 1975, granted Aug. 24, 1976
  867. inventor  Bernard K. Betz, assignee Honeywell Information Systems, Inc.
  868. [encode differences with previous line]
  869.  
  870. 4,021,782
  871. Data compaction system and apparatus
  872. inventor Hoerning
  873. filed 04/30/1975, granted 05/03/1977
  874. [A primitive form of LZ77 with implicit offsets (compare with previous record)]
  875.  
  876. 4,054,951
  877. Data expansion apparatus
  878. inventor R.D. Jackson, assignee IBM
  879. filed Jun. 30, 1976, granted Oct. 18, 1977
  880. [Covers only decompression of data compressed with a variant of LZ77.]
  881.  
  882. 4,087,788
  883. Data compression system
  884. filed 1/14/77, granted 5/2/78
  885. NCR Canada LTD - NCR Canada Ltee, Mississauga CA
  886. Brian J. Johannesson, Waterloo CA
  887. A data compression system is disclosed in which the left hand boundary
  888. of a character is developed in the form of a sequence of Freeman
  889. direction codes, the codes being stored in digital form within a
  890. processor.
  891.  
  892. 4,286,256
  893. Method and means for arithmetic coding using a reduced number of operations.
  894. granted Aug 25, 1981
  895. assignee IBM
  896.  
  897. 4,295,125
  898. A method and means for pipeline decoding of the high to low order pairwise
  899. combined digits of a decodable set of relatively shifted finite number of
  900. strings
  901. granted Oct 13, 1981
  902. assignee IBM
  903.  
  904. 4,412,306
  905. System for minimizing space requirements for storage and transmission of
  906. digital signals
  907. filed May 14, 1981, granted Oct. 25, 1983
  908. inventor  Edward W. Moll
  909.  
  910. 4,463,342
  911. A method and means for carry-over control in a high order to low order
  912. combining of digits of a decodable set of relatively shifted finite number
  913. strings.
  914. granted Jul 31, 1984
  915. assignee IBM
  916.  
  917. 4,491,934
  918. Data compression process
  919. filed May 12, 1982, granted Jan. 1, 1985
  920. inventor  Karl E. Heinz
  921.  
  922. 4,464,650
  923. Apparatus and method for compressing data signals and restoring the
  924. compressed data signals
  925. inventors Lempel, Ziv, Cohn, Eastman
  926. assignees Sperry Corporation and At&T Bell Laboratories
  927. filed 8/10/81, granted 8/7/84
  928. A compressor parses the input data stream into segments where each
  929. segment comprises a prefix and the next symbol in the data stream
  930. following the prefix.
  931.  
  932. 4,467,317
  933. High-speed arithmetic compression using using concurrent value updating.
  934. granted Aug 21, 1984
  935. assignee IBM
  936.  
  937. 4,494,108
  938. Adaptive source modeling for data file compression within bounded memory
  939. filed Jun. 5, 1984, granted Jan. 15, 1985
  940. invntors Glen G. Langdon, Jorma J. Rissanen
  941. assignee IBM
  942. order 1 Markov modeling
  943.  
  944. 4,558,302
  945. High speed data compression and decompression apparatus and method
  946. inventor Welch
  947. assignee Sperry Corporation (now Unisys)
  948. filed 6/20/83, granted 12/10/85
  949. The text for this patent can be ftped from rusmv1.rus.uni-stuttgart.de
  950. (129.69.1.12) in /info/comp.patents/US4558302.Z.
  951.  
  952. 4,560,976
  953. Data compression
  954. filed 6/5/84, granted 12/24/85
  955. Codex Corporation, Mansfield MA
  956. Steven G. Finn, Framingham, MA
  957. A stream of source characters, which occur with varying relative
  958. frequencies, is encoded into a compressed stream of codewords, each
  959. having one, two or three subwords, by ranking the source characters by
  960. their current frequency of appearance, encoding the source characters
  961. having ranks no higher than a first number as one subword codewords,
  962. source characters having ranks higher than the first number but no
  963. higher than a second number as two subword codewords, and the
  964. remaining source characters as three subword codewords.
  965.  
  966. 4,586,027
  967. Method and system for data compression and restoration
  968. inventor Tsukimaya et al.
  969. assignee Hitachi
  970. filed 08/07/84, granted 04/29/86
  971. patents run length encoding
  972.  
  973. 4,597,057
  974. System for compressed storate of 8-bit ascii bytes using coded strings
  975. of 4-bit nibbles.
  976. inventor Snow, assignee System Development corporation.
  977. filed 12/31/1981, granted 06/24/1986.
  978. Compression using static dictionary of common words, prefixes and suffixes.
  979.  
  980. 4,612,532
  981. Data compression apparatus and method
  982. inventor Bacon, assignee Telebyte Corportion
  983. filed Jun. 19, 1984, granted Sep. 16, 1986
  984. [Uses followsets as in the pkzip 0.92 'reduce' algorithm, but the
  985. followsets are dynamically updated. This is in effect a sort of order-1
  986. Markov modeling.]
  987.  
  988. 4,622,545
  989. Method and apparatus for image compression and Manipulation
  990. inventor William D. Atkinson
  991. assignee Apple computer Inc.
  992. filed 9/30/82
  993. granted 11/11/86
  994.  
  995. 4,633,490
  996. Symmetrical adaptive data compression/decompression system.
  997. granted Dec 30, 1985
  998. assignee IBM
  999.  
  1000. 4,652,856
  1001. A multiplication-free multi-alphabet arithmetic code.
  1002. granted Feb  4, 1986
  1003. assignee IBM
  1004.  
  1005. 4,667,649
  1006. Data receiving apparatus
  1007. filed 4/18/84, granted 6/30/87
  1008. inventors Kunishi et al.
  1009. assignee Canon Kabushiki Kaisha, Tokyo Japan
  1010. compression of Fax images.
  1011.  
  1012. 4,682,150
  1013. Data compression method and apparatus
  1014. inventors Mathes and Protheroe, 
  1015. assignee NCR Corporation, Dayton OH
  1016. A system and apparatus for compressing redundant and nonredundant
  1017. binary data generated as part of an operation of a time and attendance
  1018. terminal in which the data represents the time an employee is present
  1019. during working hours.
  1020.  
  1021. 4,701,745
  1022. Data compression system
  1023. inventor Waterworth John R
  1024. assignee Ferranti PLC GB, patent rights now acquired by Stac Inc.
  1025. filed 03/03/1986 (03/06/1985 in GB), granted 10/20/1987
  1026. Algorithm now known as LZRW1 (see above)
  1027. I claim:
  1028. 1. A data compression system comprising an input store for receiving
  1029. and storing a plurality of bytes of uncompressed data from an outside
  1030. source, and data processing means for processing successive bytes of
  1031. data from the input store;
  1032. the data processing means including circuit means operable to check
  1033. whether a sequence of successive bytes to be processed identical with
  1034. a sequence of bytes already processed, and including hash generating
  1035. means responsive to the application of a predetermined number of
  1036. bytes in sequence to derive a hash code appropriate to those bytes, a
  1037. temporary store in which the hash code may represent the address of a
  1038. storage location, and a pointer counter operable to store in the
  1039. temporary store at said address a pointer indicative of the position
  1040. in the input store of one of the predetermined number of bytes;
  1041. output means operable to apply to a transfer medium each byte of data
  1042. not forming part of such an identical sequence; and
  1043. encoding means responsive to the identification of such a sequence to
  1044. apply to the transfer medium an identification signal which identifies
  1045. both the location in the input store of the previous occurrence of the
  1046. sequence of bytes and the number of bytes contained in the sequence.
  1047.  
  1048. 4,730,348
  1049. Adaptive data compression system
  1050. inventor MacCrisken, assignee Adaptive Computer Technologies
  1051. filed Sep. 19, 1986, granted Mar. 8, 1988
  1052. [order-1 Markov modeling + Huffman coding + LZ77]
  1053.  
  1054. 4,758,899
  1055. Data compression control device
  1056. inventor Tsukiyama, assignee Hitachi
  1057. filed 11/20/1985, granted 07/19/1988
  1058. Limits compression to ensure that tape drive stays busy.
  1059.  
  1060. 4,809,350
  1061. Data compression system
  1062. filed Jan. 30, 1987, granted Feb. 28, 1989
  1063. inventor Yair Shimoni & Ron Niv
  1064. assignee Elscint Ltd., Haifa, Israel
  1065. [Image compression via variable length encoding of differences with
  1066. predicted data.]
  1067.  
  1068. 4,814,746
  1069. Data compression method
  1070. inventors Victor S. Miller, Mark N. Wegman
  1071. assignee IBM
  1072. filed 8/11/86, granted 3/21/89
  1073. A previous application was filed on 6/1/83, three weeks before the
  1074. application by Welch (4,558,302)
  1075. Communications between a Host Computing System and a number of remote
  1076. terminals is enhanced by a data compression method which modifies the
  1077. data compression method of Lempel and Ziv by addition of new character
  1078. and new string extensions to improve the compression ratio, and
  1079. deletion of a least recently used routine to limit the encoding tables
  1080. to a fixed size to significantly improve data transmission efficiency.
  1081.  
  1082. 4,841,092
  1083. continued in 5,003,307
  1084.  
  1085. 4,853,696
  1086. Code converter for data compression/decompression
  1087. filed 4/13/87, granted 8/1/89
  1088. inventor Amar Mukherjee, Maitland FL
  1089. assignee University of Central Florida, Orlando FL
  1090. Another hardware Huffman encoder:
  1091. A code converter has a network of logic circuits connected in reverse
  1092. binary tree fashion with logic paths between leaf nodes and a common
  1093. root node.
  1094.  
  1095. 4,872,009
  1096. Method and apparatus for data compression and restoration
  1097. inventor Tsukimaya et al.
  1098. assignee Hitachi
  1099. filed 12/07/87, granted 10/03/89
  1100. This patent on run length encoding covers the 'invention' of limiting
  1101. the run length to 16 bytes and thus the encoding of the length on 4 bits.
  1102.  
  1103. 4,876,541
  1104. Stem [sic] for dynamically compressing and decompressing electronic data
  1105. filed 10/15/87, granted 10/24/89
  1106. inventor James A. Storer
  1107. assignee Data Compression Corporation
  1108. A data compression system for encoding and decoding textual data,
  1109. including an encoder for encoding the data and for a decoder for
  1110. decoding the encoded data.
  1111.  
  1112. 4,891,643
  1113. Arithmetic coding data compression/de-compression by selectively
  1114. employed, diverse arithmetic encoders and decoders.
  1115. granted Jan  2, 1990
  1116. assignee IBM
  1117.  
  1118. 4,905,297
  1119. granted Feb 27, 1990
  1120. assignee IBM
  1121. Arithmetic coding encoder and decoder system.
  1122.  
  1123. 4,906,991
  1124. Textual substitution data compression with finite length search window
  1125. filed 4/29/1988, granted 3/6/1990
  1126. inventors Fiala,E.R., and Greene,D.H.
  1127. assignee Xerox Corporation
  1128.  
  1129. 4,935,882
  1130. Probability adaptation for arithmetic coders.
  1131. granted Jun 19, 1990
  1132. assignee IBM
  1133.  
  1134. 4,941,193
  1135. Barnsley, fractal compression.
  1136.  
  1137. 4,943,869
  1138. Compression Method for Dot Image Data
  1139. filed 1988-05-04, granted 1990-07-24
  1140. assignee Fuji Photo Film Co.
  1141. Lossy and lossless image compression schemes.
  1142.  
  1143. 4,955,066
  1144. Compressing and Decompressing Text Files
  1145. filed  10/13/89, granted 09/04/90
  1146. inventor Notenboom, L.A.
  1147. assignee Microsoft
  1148. Now extended as 5,109,433
  1149. [Noted in signon screen of Word 5.5 and on the outside of the MS-DOS 5.0
  1150. Upgrade.]
  1151. A method of compressing a text file in digital form is disclosed.
  1152. A full text file having characters formed into phrases is provided by an
  1153. author.  The characters are digitally represented by bytes.  A first pass
  1154. compression is sequentially followed by a second pass compression of the
  1155. text which has previously been compressed.  A third or fourth level of
  1156. compression is serially performed on the compressed text.  For example, in
  1157. a first pass, the text is run-length compressed.  In a second pass, the
  1158. compressed text is further compressed with key phrase compression.  In a
  1159. third pass, the compressed text is further compressed with Huffman
  1160. compression.  The compressed text is stored in a text file having a Huffman
  1161. decode tree, a key phrase table, and a topic index.  The data is
  1162. decompressed in a single pass and provided one line at a time as an output.
  1163. Sequential compressing of the text minimizes the storage space required for
  1164. the file.  Decompressing of the text is performed in a single pass.  As a
  1165. complete line is decompressed, it is output rapidly, providing full text to
  1166. the user.
  1167.  
  1168. 4,973,961
  1169. Method and apparatus for carry-over control in arithmetic coding.
  1170. granted Nov 27, 1990
  1171. assignee AT&T
  1172.  
  1173. 4,988,998
  1174. Data compression system for successively applying at least two data
  1175. compression methods to an input data stream.
  1176. inventor O'Brien
  1177. assignee Storage Technology Corporation, Louisville, Colorado
  1178. filed Sep 5, 1989, granted Jan 29, 1991.
  1179. Run length encoding followed by LZ77.
  1180.  
  1181. 5,001,478
  1182. Method of Encoding Compressed Data
  1183. filed 12/28/89, granted 03/19/91
  1184. inventor Michael E. Nagy
  1185. assignee IBM
  1186. 1. A method of encoding a compressed data stream made up of a sequence of
  1187. literal references, lexicon references and history references, which
  1188. comprises the steps of:
  1189. assigning to each literal reference a literal identifier;
  1190. assigning to each history reference a history identifier;
  1191. assigning to each lexicon reference a lexicon identifier;
  1192. and emitting a data stream with said identifiers assigned to said references.
  1193. Gordon Irlam <gordoni@cs.adelaide.edu.au> says:
  1194. The invention can probably be best understood by considering the
  1195. decompressor.  It consists of a history buffer, and a lexicon buffer, both
  1196. of which are initially empty.  The history buffer contains the last n
  1197. symbols emitted.  Whenever a history buffer reference is to be output the
  1198. string so referenced is subsequently moved to the lexicon buffer for future
  1199. reference.  Thus the history buffer keeps track of strings that may be
  1200. repeated on a very short term basis, while the lexicon buffer stores items
  1201. for a longer time.  Furthermore a history reference involves specifying
  1202. both the offset and length within the history buffer, whereas a lexicon
  1203. reference simply specifies a number denoting the string.  Both buffers have
  1204. a finite size.
  1205.  
  1206. 5,003,307
  1207. Data compression apparatus with shift register search means
  1208. filed Oct. 6, 1989, granted Mar. 26, 1991
  1209. inventors George Glen A, Ivey Glen E, Whiting Douglas L
  1210. assignee Stac Inc
  1211. continuation of 4,841,092
  1212.  
  1213. 5,016,009
  1214. Data compression apparatus and method
  1215. filed 01/13/1989, granted 05/14/1991
  1216. inventors George Glen A, Ivey Glen E, Whiting Douglas L
  1217. assignee Stac Inc
  1218. LZ77 with offset hash table (extended in 5,126,739)
  1219.  
  1220. 5,023,611
  1221. Entropy encoder/decoder including a context extractor.
  1222. granted Jun 11, 1991
  1223. assignee AT&T
  1224.  
  1225. 5,025,258
  1226. Adaptive probability estimator for entropy encoder/decoder.
  1227. granted Jun 18, 1991
  1228. assignee AT&T
  1229.  
  1230. 5,049,881
  1231. Apparatus and method for very high data rate-compression incorporating
  1232. lossless data compression and expansion utilizing a hashing technique
  1233. inventors Dean K. Gibson, Mark D. Graybill
  1234. assignee Intersecting Concepts, Inc.
  1235. filed 6/18/90, granted 9/17/91
  1236. [covers lzrw1, almost identical with Waterworth 4,701,745]
  1237.  
  1238. 5,051,745
  1239. String searcher, and compressor using same
  1240. filed  8/21/90, granted 9/24/91
  1241. inventor  Phillip W. Katz (author of pkzip)
  1242. In the string search method and apparatus pointers to the string to be
  1243. searched are indexed via a hashing function and organized according to the
  1244. hashing values of the string elements pointed to. The hashing function is
  1245. also run on the string desired to be found, and the resulting hashing value
  1246. is used to access the index. If the resulting hashing value is not in the
  1247. index, it is known that the target string does not appear in the string
  1248. being searched. Otherwise the index is used to determine the pointers which
  1249. correspond to the target hashing value, these pointers pointing to likely
  1250. candidates for matching the target string. The pointers are then used to
  1251. sequentially compare each of the locations in the string being searched to
  1252. the target string, to determine whether each location contains a match to
  1253. the target string.
  1254. In the method and apparatus for compressing a stream of data symbols, a
  1255. fixed length search window, comprising a predetermined contiguous portion
  1256. of the symbol stream, is selected as the string to be searched by the
  1257. string searcher. If a string to be compressed is found in the symbol
  1258. stream, a code is output designating the location within the search window
  1259. of the matching string and the length of the matching string.
  1260.  
  1261. 5,065,447
  1262. Barnsley, fractal compression
  1263.  
  1264. 5,109,433
  1265. Compressing and decompressing text files
  1266. inventor Notenboom
  1267. assignee Microsoft
  1268. extension of 4,955,066
  1269.  
  1270. 5,126,739
  1271. Data Compression Apparatus and Method
  1272. filed Nov. 27, 1990, granted June 30, 1992.
  1273. inventor Whiting et. al
  1274. assignee Stac Inc
  1275. LZ77 with offset hash table (extension of 5,016,009)
  1276.  
  1277. 5,140,321
  1278. Data compression/decompression method and apparatus
  1279. filed 9/4/91, granted 8/18/92
  1280. inventor Robert Jung
  1281. assignee Prime Computer
  1282.  
  1283. 5,155,484
  1284. Fast data compressor with direct lookup table indexing into history buffer
  1285. filed 9/13/1991, granted 10/13/1992
  1286. inventor Chambers, IV, Lloyd L., Menlo Park, California
  1287. assignee Salient Software, Inc., Palo Alto, California (02)
  1288. Uses a 64K hash table indexed by the first two characters of
  1289. the input string. Includes several claims on the LZ77 file format
  1290. (literal or offset,length).
  1291.  
  1292. 5,179,378
  1293. file Jul. 30, 1991, granted Jan. 12, 1993
  1294. inventor Ranganathan
  1295. assignee University of South Florida
  1296. Method and apparatus for the compression and decompression of data
  1297. using Lempel-Ziv based techniques.
  1298. [This covers LZ77 hardware compression with a systolic array of
  1299. processors working in parallel.]
  1300.  
  1301. Japan 2-46275
  1302. Coding system
  1303. granted Feb 26, 1990
  1304. [Patents one form of arithmetic coding.]
  1305.  
  1306. ------------------------------------------------------------------------------
  1307.  
  1308. Subject: [9]  The WEB 16:1 compressor.
  1309.  
  1310.  
  1311. [WARNING: this topic has generated the greatest volume of news in the
  1312. history of comp.compression. Read this before posting on this subject.]
  1313.  
  1314. [WARNING 2: it is quite possible that the story is repeating itself
  1315. with a compressor called MINC by Premier Research Corporation, Ltd.
  1316. They claim a breakthrough in lossless data compression using a recursive
  1317. method, that is, applying the compressor to the compressed output of
  1318. the previous run.]
  1319.  
  1320. [WARNING 3: the OWS program, which also claims incredible compression
  1321. ratios, is a hoax. It just remembers the clusters which contained
  1322. the data. The data can be recovered only if those clusters are not
  1323. used again for another file. Needless to say, never trust such a
  1324. lossy program.]
  1325.  
  1326. (a) What the press says
  1327.  
  1328. April 20, 1992  Byte Week Vol 4. No. 25:
  1329.  
  1330.    "In an announcement that has generated high interest - and more than a
  1331.    bit of skepticism - WEB Technologies (Smyrna, GA) says it has
  1332.    developed a utility that will compress files of greater than 64KB in
  1333.    size to about 1/16th their original length.  Furthermore, WEB says its
  1334.    DataFiles/16 program can shrink files it has already compressed."
  1335.    [...]
  1336.    "A week after our preliminary test, WEB showed us the program successfully
  1337.    compressing a file without losing any data.  But we have not been able
  1338.    to test this latest beta release ourselves."
  1339.    [...]
  1340.    "WEB, in fact, says that virtually any amount of data can be squeezed 
  1341.    to under 1024 bytes by using DataFiles/16 to compress its own output
  1342.    multiple times."
  1343.  
  1344. June 1992 Byte, Vol 17 No 6:
  1345.  
  1346.    [...] According to Earl Bradley, WEB Technologies' vice president of
  1347.    sales and marketing, the compression algorithm used by DataFiles/16
  1348.    is not subject to the laws of information theory. [...]
  1349.  
  1350.  
  1351. (b) First details, by John Wallace <buckeye@spf.trw.com>:
  1352.  
  1353. I called WEB at (404)514-8000 and they sent me some product
  1354. literature as well as chatting for a few minutes with me on the phone.
  1355. Their product is called DataFiles/16, and their claims for it are
  1356. roughly those heard on the net.
  1357.  
  1358. According to their flier:
  1359.  
  1360. "DataFiles/16 will compress all types of binary files to approximately
  1361. one-sixteenth of their original size ... regardless of the type of
  1362. file (word processing document, spreadsheet file, image file,
  1363. executable file, etc.), NO DATA WILL BE LOST by DataFiles/16."
  1364. (Their capitalizations; 16:1 compression only promised for files >64K
  1365. bytes in length.)
  1366.  
  1367. "Performed on a 386/25 machine, the program can complete a
  1368. compression/decompression cycle on one megabyte of data in less than
  1369. thirty seconds"
  1370.  
  1371. "The compressed output file created by DataFiles/16 can be used as the 
  1372. input file to subsequent executions of the program.  This feature of 
  1373. the utility is known as recursive or iterative compression, and will 
  1374. enable you to compress your data files to a tiny fraction of the 
  1375. original size.  In fact, virtually any amount of computer data can 
  1376. be compressed to under 1024 bytes using DataFiles/16 to compress its 
  1377. own output files muliple times.  Then, by repeating in reverse the 
  1378. steps taken to perform the recusive compression, all original data 
  1379. can be decompressed to its original form without the loss of a single 
  1380. bit."
  1381.  
  1382. Their flier also claims: 
  1383.  
  1384. "Constant levels of compression across ALL TYPES of FILES"
  1385. "Convenient, single floppy DATA TRANSPORTATION"
  1386.  
  1387. From my telephone conversation, I was was assured that this is an
  1388. actual compression program.  Decompression is done by using only the 
  1389. data in the compressed file; there are no hidden or extra files.
  1390.  
  1391.  
  1392. (c) More information, by Rafael Ramirez <rafael.ramirez@channel1.com>:
  1393.  
  1394.    Today (Tuesday, 28th) I got a call from Earl Bradley of Web
  1395. who now says that they have put off releasing a software version of
  1396. the algorithm because they are close to signing a major contract with
  1397. a big company to put the algorithm in silicon.  He said he could not
  1398. name the company due to non-disclosure agreements, but that they had
  1399. run extensive independent tests of their own and verified that the
  1400. algorithm works. [...]
  1401.  
  1402. He said the algorithm is so simple that he doesn't want anybody
  1403. getting their hands on it and copying it even though he said they
  1404. have filed a patent on it. [...] Mr. Bradley said the silicon version
  1405. would hold up much better to patent enforcement and be harder to copy.
  1406.  
  1407.    He claimed that the algorithm takes up about 4K of code, uses only
  1408. integer math, and the current software implementation only uses a 65K
  1409. buffer.  He said the silicon version would likely use a parallel
  1410. version and work in real-time. [...]
  1411.  
  1412.  
  1413. (d) The impossiblity proofs.
  1414.  
  1415. It is impossible for a given program to compress without loss *all*
  1416. files greater than a certain size by at least one bit. This can be
  1417. proven by a simple counting argument. (Many other proofs have been
  1418. posted on comp.compression, *please* do not post yet another one.)
  1419.  
  1420. Assume that the program can compress without loss all files of size >= N
  1421. bits.  Compress with this program all the 2^N files which have
  1422. exactly N bits.  All compressed files have at most N-1 bits, so there
  1423. are at most (2^N)-1 different compressed files [2^(N-1) files of size
  1424. N-1, 2^(N-2) of size N-2, and so on, down to 1 file of size 0]. So at
  1425. least two different input files must compress to the same output file.
  1426. Hence the compression program cannot be lossless. (Stronger results
  1427. about the number of incompressible files can be obtained, but the
  1428. proofs are a little more complex.)
  1429.  
  1430. This argument applies of course to WEB's case (take N = 64K*8 bits).
  1431. Note that no assumption is made about the compression algorithm.
  1432. The proof applies to *any* algorithm, including those using an
  1433. external dictionary, or repeated application of another algorithm,
  1434. or combination of different algorithms, or representation of the
  1435. data as formulas, etc... All schemes are subject to the counting argument.
  1436. There is no need to use information theory to provide a proof, just
  1437. basic mathematics.
  1438.  
  1439. This assumes of course that the information available to the decompressor
  1440. is only the bit sequence of the compressed data. If external information
  1441. such as a file name or a number of iterations is necessary to decompress
  1442. the data, the bits providing the extra information must be included in
  1443. the bit count of the compressed data. (Otherwise, it would be sufficient
  1444. to consider any input data as a number, use this as the iteration
  1445. count or file name, and pretend that the compressed size is zero.)
  1446. For an example of storing information in the file name, see the program
  1447. lmfjyh in the 1993 International Obfuscated C Code Contest, available
  1448. on all comp.sources.misc archives (Volume 39, Issue 104).
  1449.  
  1450. [See also question 73 "What is the theoretical compression limit?" in
  1451. part 2 of this FAQ.]
  1452.  
  1453.  
  1454. (e) No software version
  1455.  
  1456. Appeared on BIX, reposted by Bruce Hoult <Bruce.Hoult@actrix.gen.nz>:
  1457.  
  1458. tojerry/chaos #673, from abailey, 562 chars, Tue Jun 16 20:40:34 1992
  1459. Comment(s). 
  1460. ----------
  1461. TITLE: WEB Technology
  1462. I promised everyone a report when I finally got the poop on WEB's
  1463. 16:1 data compression. After talking back and forth for a year
  1464. and being put off for the past month by un-returned phone calls,
  1465. I finally got hold of Marc Spindler who is their sales manager.
  1466.  
  1467. _No_ software product is forth coming, period!
  1468.  
  1469. He began talking about hardware they are designing for delivery
  1470. at the end of the year. [...]
  1471.  
  1472.  
  1473. (f) Product cancelled
  1474.  
  1475. Posted by John Toebes <toebes@bnr.ca> on Aug 10th, 1992:
  1476.  
  1477. [Long story omitted, confirming the reports made above about the
  1478. original WEB claims.]
  1479.  
  1480. 10JUL92 - Called to Check Status.  Was told that testing had uncovered a
  1481.           new problem where 'four numbers in a matrix were the same
  1482.           value' and that the programmers were off attempting to code a
  1483.           preprocessor to eliminate this rare case.  I indicated that he
  1484.           had told me this story before.  He told me that the
  1485.           programmers were still working on the problem.
  1486.  
  1487. 31JUL92 - Final Call to Check Status.  Called Earl in the morning and
  1488.           was told that he still had not heard from the programmers. [...]
  1489.           Stated that if they could not resolve the problem then there would
  1490.           probably not be a product.
  1491.  
  1492. 03AUG92 - Final Call.  Earl claims that the programmers are unable to
  1493.           resolve the problem.  I asked if this meant that there would
  1494.           not be a product as a result and he said yes.
  1495.  
  1496.  
  1497. (g) Conclusion
  1498.  
  1499. The last report given above should put an end to the WEB story.
  1500.  
  1501. [Note from the FAQ maintainer: I intended to remove this story from
  1502. the FAQ, but the recent announcement of the MINC compressor has some
  1503. similarities with the WEB story so it is useful to keep it a little
  1504. longer.]
  1505.  
  1506. ------------------------------------------------------------------------------
  1507.  
  1508. Subject: [11] What is the V.42bis standard?
  1509.  
  1510.  
  1511. A description of the V.42bis standard is given in "The V.42bis
  1512. standard for data-compressing modems," by Clark Thomborson
  1513. <cthombor@theory.lcs.mit.edu>, IEEE Micro, Oct 1992, pp. 41-53. 
  1514.  
  1515. Short introduction, by Alejo Hausner <hausner@qucis.queensu.ca>:
  1516.  
  1517. The V.42bis Compression Standard was proposed by the International
  1518. Consultative Committee on Telephony and Telegraphy (CCITT) as an
  1519. addition to the v.42 error-correction protocol for modems. Its purpose
  1520. is to increase data throughput, and uses a variant of the
  1521. Lempel-Ziv-Welch (LZW) compression method.  It is meant to be
  1522. implemented in the modem hardware, but can also be built into the
  1523. software that interfaces to an ordinary non-compressing modem.
  1524.  
  1525. V.42bis can send data compressed or not, depending on the
  1526. data.  There are some types of data that cannot be
  1527. compressed.  For example, if a file was compressed first,
  1528. and then sent through a V.42bis modem, the modem would not
  1529. likely reduce the number of bits sent.  Indeed it is likely
  1530. that the amount of data would increase somewhat.
  1531.  
  1532. To avoid this problem, the algorithm constantly monitors the
  1533. compressibility of the data, and if it finds fewer bits
  1534. would be necessary to send it uncompressed, it switches to
  1535. transparent mode.  The sender informs the receiver of this
  1536. transition through a reserved escape code.  Henceforth the
  1537. data is passed as plain bytes.
  1538.  
  1539. The choice of escape code is clever.  Initially, it is a
  1540. zero byte.  Any occurrence of the escape code is replaced,
  1541. as is customary, by two escape codes.  In order to prevent a
  1542. string of escape codes from temporarily cutting throughput
  1543. in half, the escape code is redefined by adding 51 mod 256
  1544. each time it is used.
  1545.  
  1546. While transmitting in transparent mode, the sender maintains
  1547. the LZW trees of strings, and expects the receiver to do
  1548. likewise.  If it finds an advantage in returning to
  1549. compressed mode, it will do so, first informing the receiver
  1550. by a special control code.  Thus the method allows the
  1551. hardware to adapt to the compressibility of the data.
  1552.  
  1553.  
  1554. The CCITT standards documents used to be available by ftp on
  1555. ftp.uu.net in /doc/standards/ccitt, but this service has been
  1556. discontinued. If you ftp to digital.resource.org, in directory pub/standards
  1557. there is a file that says that making the standards available in the
  1558. first place was just an experiment.
  1559.  
  1560. The documents are now on src.doc.ic.ac.uk, but the directory name
  1561. keeps changing. Check one of:
  1562.   /computing/ccitt/ccitt-standards/ccitt/
  1563.   /computing/ccitt/standards/ccitt
  1564.   /doc/ccitt-standards/ccitt
  1565. in this order. The v42bis standard is in *standards/ccitt/1992/v/v42bis.asc.Z.
  1566.  
  1567. A mail server for CCITT documents is available at teledoc@itu.arcom.ch.
  1568. For more information, contact Robert Shaw <shaw@itu.arcom.ch> or
  1569. Antoinette Bautista <bautista@itu.arcom.ch>. Warning by John Levine
  1570. <johnl@iecc.cambridge.ma.us>:
  1571.  
  1572.   This teledoc thing is much less than meets the eye.  What it
  1573.   actually has is one-page abstracts of some but not all CCITT
  1574.   recommendations, along with junk like lists of the national
  1575.   representatives to CCITT.  If you want the actual text of a
  1576.   recommendation, you have to send large amounts of money to
  1577.   Switzerland, same as ever. However, a closer reading of the Teledoc
  1578.   announcement shows that they say they're planning to make the actual
  1579.   text of some CCITT recommendations available on-line sometime in 1993.
  1580.  
  1581.  
  1582. See also the Standards FAQ posted to news.answers or get it by ftp in
  1583. rtfm.mit.edu:/pub/usenet/news.answers/standards-faq.
  1584.  
  1585. ------------------------------------------------------------------------------
  1586.  
  1587. Subject: [12] I need source for the winners of the Dr Dobbs compression contest
  1588.  
  1589.  
  1590. The source of the top 6 programs of the Feb 91 Dr Dobbs data compression
  1591. contest are available by ftp on
  1592.   wsmr-simtel20.army.mil in pd1:<msdos.compress>ddjcompr.zip. [192.88.110.2]
  1593.   garbo.uwasa.fi:/pc/source/ddjcompr.zip [128.214.87.1]
  1594.  
  1595. The sources are in MSDOS end-of-line format, one directory per
  1596. program.  Unix or VMS users, use "unzip -a ddjcompr" to get correct
  1597. end-of-lines (add -d to recreate the directory structure if you are
  1598. using an obsolete version of unzip such as 4.1). Three of the 6
  1599. programs are not portable and only run on MSDOS. compact and urban
  1600. work on Unix, sixpack only requires minor modifications.
  1601.  
  1602. ------------------------------------------------------------------------------
  1603.  
  1604. Subject: [13] I need source for arithmetic coding
  1605.  
  1606.  
  1607. (See question 70 for an introduction to arithmetic coding.)
  1608.  
  1609. The source for the arithmetic coder described in Chap.5 of Bell,
  1610. Cleary, and Witten's book "Text Compression" (see question 7 above)
  1611. (or, equivalently, in: Witten, Neal, and Cleary's article "Arithmetic
  1612. Coding for data Compression" from Communications of the Association
  1613. for Computing Machinery, 30 (6), pp.520-540, June, 1987) is available
  1614. via anonymous ftp from ftp.cpsc.ucalgary.ca (136.159.7.18) in directory
  1615. /pub/arithmetic.coding.  It only comes with a simple order-0 model but
  1616. it's set up so that adding your own more sophisticated one is
  1617. straightforward.
  1618.  
  1619. A low precision arithmetic coding implementation avoiding hardware
  1620. division is available on the same site (ftp.cpsc.ucalgary.ca)
  1621. in /pub/arithmetic.coding/low.precision.version/low.precision.version.shar.
  1622.  
  1623. Kris Popat <popat@image.mit.edu> has worked on "Scalar Quantization
  1624. with Arithmetic Coding."  It describes an arithmetic coding technique
  1625. which is quite general and computationally inexpensive.  The
  1626. documentation and example C code are available via anonymous ftp from
  1627. media-lab.media.mit.edu (18.85.0.2), in /pub/k-arith-code.
  1628.  
  1629. The program 'urban' in ddjcompr.zip (see item 12 above) is a high order
  1630. arithmetic coder working at the bit level. It is written by Urban Koistinen
  1631. <md85-epi@nada.kth.se>.
  1632.  
  1633. ------------------------------------------------------------------------------
  1634.  
  1635. Subject: [15] Where can I get image compression programs?
  1636.  
  1637.  
  1638. JPEG:
  1639.     Source code for most any machine:
  1640.     ftp.uu.net:/graphics/jpeg/jpegsrc.v4.tar.Z [137.39.1.9]
  1641.     nic.funet.fi:/pub/graphics/packages/jpeg/jpegsrc.v4.tar.Z [128.214.6.100]
  1642.     Contact: jpeg-info@uunet.uu.net (Independent JPEG Group)
  1643.  
  1644.     havefun.stanford.edu:pub/jpeg/JPEGv1.2.tar.Z (supports lossless mode)
  1645.     Contact: Andy Hung <achung@cs.stanford.edu> (see item 20 below)
  1646.  
  1647.     xv, an image viewer which can read JPEG pictures, is available in
  1648.     export.lcs.mit.edu: contrib/xv-2.21.tar.Z [18.24.0.12]
  1649.  
  1650. MPEG:
  1651.     havefun.stanford.edu:/pub/mpeg/MPEGv1.2.alpha.tar.Z
  1652.     Contact: Andy Hung <achung@cs.stanford.edu> (see item 20 below)
  1653.  
  1654.     toe.cs.berkeley.edu:/pub/multimedia/mpeg/mpeg_play-2.0.tar.Z
  1655.     toe.cs.berkeley.edu:/pub/multimedia/mpeg/mpeg_encode-1.0.tar.Z.
  1656.     Contact: mpeg-bugs@cs.berkeley.edu
  1657.  
  1658.     toe.cs.berkeley.edu:/pub/multimedia/mpeg/vmpeg10.zip
  1659.     decel.ecel.uwa.edu.au:/users/michael/mpegw32e.zip (for Windows and NT)
  1660.  
  1661.     nvr.com:/pub/NVR-software/Product-1.0.4.tar.Z   (192.82.231.50)
  1662.     (free demo copy of NVR's software toolkit for SPARCstations)
  1663.     Contact: Todd Brunhoff <toddb@nvr.com>
  1664.  
  1665. H.261(P*64):
  1666.     havefun.stanford.edu:pub/p64/P64v1.2.alpha.tar.Z
  1667.     Contact: Andy Hung <achung@cs.stanford.edu> (see item 20 below)
  1668.  
  1669.     ftp.inria.fr:/INRIA/ivs-2.1.tar.Z (Inria videoconference system)
  1670.  
  1671.     avahi.inria.fr:/pub/h261/h261.tar.Z (see item 20)
  1672.  
  1673. JBIG:
  1674.     nic.funet.fi:/pub/graphics/misc/test-images/jbig.tar.gz.
  1675.  
  1676. epic: (pyramid wavelet coder, see item 72)
  1677.     whitechapel.media.mit.edu:/pub/epic.tar.Z [18.85.0.125]
  1678.     Contact: Eero P. Simoncelli <eero@media.mit.edu>
  1679.     The "Lenna" test image is available as part of the EPIC package,
  1680.     where it is named "test_image".
  1681.  
  1682. hcompress: (wavelet impage compression, see item 72)
  1683.     stsci.edu:/software/hcompress/hcompress.tar.Z
  1684.  
  1685. wavethresh: (wavelet software for the language S)
  1686.     gdr.bath.ac.uk:/pub/masgpn/wavethresh2.2.Z
  1687.     Contact: gpn@maths.bath.ac.uk
  1688.  
  1689. compfits:
  1690.     uwila.cfht.hawaii.edu:/pub/compfits/compfits.tar.Z  [128.171.80.50]
  1691.     Contact: Jim Wright <jwright@cfht.hawaii.edu>
  1692.  
  1693. fitspress:
  1694.     cfata4.harvard.edu:/pub/fitspress08.tar.Z [128.103.40.79]
  1695.  
  1696. tiff:
  1697.     For source and sample images, see question 18 below.
  1698.  
  1699.  
  1700. For image compression hardware, see item 85 in part 3 of this FAQ.
  1701.  
  1702. ------------------------------------------------------------------------------
  1703.  
  1704. Subject: [16] What is the state of the art in lossless image compression?
  1705.  
  1706.  
  1707. The current state-of-the-art is the JBIG algorithm.  For an
  1708. introduction to JBIG, see question 74 in part 2.
  1709.  
  1710. JBIG works best on bi-level images (like faxes) and also works well on
  1711. Gray-coded grey scale images up to about six or so bits per pixel.  You
  1712. just apply JBIG to the bit planes individually.  For more bits/pixel,
  1713. lossless JPEG provides better performance, sometimes. (For JPEG, see
  1714. question 19 below.)
  1715.  
  1716. You can find a description of JBIG in ISO/IEC CD 11544, contained in
  1717. document ISO/IEC JTC1/SC2/N2285.  The only way to get it is to ask
  1718. your National Standards Body for a copy. In the USA, call ANSI at
  1719. (212) 642-4900.
  1720.  
  1721. ------------------------------------------------------------------------------
  1722.  
  1723. Subject: [17] What is the state of fractal compression?
  1724.  
  1725.  
  1726. from Tal Kubo <kubo@zariski.harvard.edu>:
  1727.  
  1728. According to Barnsley's book 'Fractals Everywhere', this method is
  1729. based on a measure of deviation between a given image and its
  1730. approximation by an IFS code.  The Collage Theorem states that there is
  1731. a convergent process to minimize this deviation.  Unfortunately,
  1732. according to an article Barnsley wrote for BYTE a few years ago, this
  1733. convergence was rather slow, about 100 hours on a Cray, unless assisted by
  1734. a person.
  1735.  
  1736. Barnsley et al are not divulging any technical information beyond the
  1737. meager bit in 'Fractals Everywhere'.  The book explains the idea of IFS
  1738. codes at length, but is vague about the application of the Collage theorem
  1739. to specific compression problems.
  1740.  
  1741. There is reason to believe that Barnsley's company has
  1742. *no algorithm* which takes a given reasonable image and achieves
  1743. the compression ratios initially claimed for their fractal methods.
  1744. The 1000-to-1 compression advertised was achieved only for a 'rigged'
  1745. class of images, with human assistance. The best unaided
  1746. performance I've heard of is good lossy compression of about 80-1.
  1747.  
  1748. Steve Tate <srt@duke.cs.duke.edu> confirms:
  1749.  
  1750. Compression ratios (unzoomed) seem to range from 20:1 to 60:1...  The
  1751. quality is considerably worse than wavelets or JPEG on most of the
  1752. non-contrived images I have seen.
  1753.  
  1754. But Yuval Fisher <fisher@inls1.ucsd.edu> disagrees:
  1755.  
  1756. Their performance has improved dramatically beyond what they were
  1757. talking about in BYTE a few years ago.  Human assistance to the
  1758. compression is no longer needed and the compression time is
  1759. reasonable, although the more time and compute power you throw at the
  1760. compression, the smaller the resulting file for the same level of
  1761. quality.
  1762.  
  1763. Geoffrey A Stephenson <ketlux@ketlux.demon.co.uk> adds:
  1764.  
  1765. Iterated systems are shipping a general purpose compressor at about
  1766. 300 Pounds in the UK that claims "640x480 24 bit colour compression of
  1767. about 1 min at 922k -> 10k on a 486/50 software only, decomp. to 8
  1768. bits in 3 secs, etc." At a recent multimedia conference in London they
  1769. handed out free demo disks that show the decomp. in action. The
  1770. package runs under both DOS anf WIN (DLLs provided for use in
  1771. applications). They also sell a board to speed up compression and
  1772. offer versions supporting full motion video (but not apparently at all
  1773. SVGA sizes like the static picture version). I have not yet got my
  1774. hands on a full version to test different types of pictures, but
  1775. friends have a and claim it looks good.
  1776.  
  1777.  
  1778. Thomas W. Colthurst <thomasc@athena.mit.edu> clarifies the distinction
  1779. between IFS and the Fractal Transform:
  1780.  
  1781. It is time, once and for all, to put to death the Barnsley myth that
  1782. IFSs are good for image compression.  They are not.  Various algorithms
  1783. have been proposed for this "inverse problem" ranging from the trendy
  1784. (genetic algorithms) to the deep (moment methods) to the ad hoc (the
  1785. hungry algorithm) to the absurd (the so-called "graduate student
  1786. algorithm", consisting of locking up a grad student in a tiny office
  1787. with a SGI workstation and not letting them out until they come up
  1788. with a good IFS for your image).  They are all useless for practical
  1789. image compression.
  1790.  
  1791. In fact, there are even good theoretical reasons for believing that
  1792. IFSs will never be useful for image compression.  For example, even
  1793. if you have an IFS for object A and an IFS for object B, there is no
  1794. way to combine these IFSs to get an IFS for object A union B or
  1795. object A intersect B.
  1796.  
  1797. Even Barnsley himself admits, in his latest book, that he doesn't use
  1798. IFS image compression.  Instead, he uses the so-called "fractal
  1799. transform," which is really just a variant of vector quantization
  1800. where you use the image itself, sampled at a higher scale, as the
  1801. VQ codebook.  To be fair, the fractal transform can be analyzed using
  1802. local IFSs, but local IFSs are immensely more complicated and general
  1803. than normal IFSs, to the point where one feels suspect even using the
  1804. word "IFS" to describe them.
  1805.  
  1806. It should be emphasized that the fractal transform is a real, working
  1807. method that performs about as well as other existing methods like VQ
  1808. or the discrete cosine transform. The fractal transform will probably
  1809. never beat vector quantization (VQ) as for size of the compressed
  1810. image, but does have the advantage that you don't need to carry your
  1811. codebook around.  The latest results have it slightly winning over
  1812. the discrete cosine transform; only time and more research will tell
  1813. if this advantage persists.  Just like VQ, the fractal transform
  1814. takes a while to compress, but is quick at decompression (Barnsley's
  1815. company has hardware to do this in realtime).
  1816.  
  1817. In short, IFSs are good for just about everything fractals are (and
  1818. more!), but are absolutely horrid for image compression.
  1819.  
  1820.  
  1821. Programs:
  1822.  
  1823. A fractal image compression program is available by ftp in
  1824. lyapunov.ucsd.edu:/pub/young-fractal/unifs10.zip. (Unix users, See
  1825. item 2 above for unzip on Unix.) Note the file size before you ftp it:
  1826. 1.2 MB. The package contains source for compression and decompression,
  1827. source for X-windows decompression, MSDOS executables and images.
  1828. A newer version of the program is in yuvpak20.zip.
  1829.  
  1830. A fractal image decompression program (note: decompression only) is
  1831. available in /pub/inls-ucsd/fractal-2.0.tar on on the same ftp site
  1832. (lyapunov.ucsd.edu). Note the file size before you ftp it: 1.3 MB.
  1833. This file also contains a paper by Yuval Fisher (see reference below),
  1834. and some executables and sample images. Reading this paper is required
  1835. to understand how the Young compression programs (see above) works.
  1836.  
  1837. The source code for the program published in the Oct 93 issue of
  1838. Byte is in ftp.uu.net /published/byte/93oct/fractal.exe. This is
  1839. self-extractible zip file (use "unzip fractal.exe" to extract on
  1840. non MSDOS systems). The source code is for a TARGA video board.
  1841.  
  1842.  
  1843. References:
  1844.   A. Jacquin, 'Fractal image coding based on a theory of iterated
  1845.     contractive image transformations', Visual Comm. and Image
  1846.     Processing, vol SPIE-1360, 1990. (The best paper that explains
  1847.     the concept in a simple way.)
  1848.  
  1849.   A. Jacquin, "A Fractal Theory of Iterated Markov Operators with
  1850.     Applications to Digital Image Coding", PhD Thesis, Georgia Tech, 1989.
  1851.   It can be obtained from university microfilms for $35, phone 1-800-521-0600.
  1852.  
  1853.   M. Barnsley, L. Anson, "Graphics Compression Technology, SunWorld,
  1854.     October 1991, pp. 42-52.
  1855.   M.F. Barnsley, A. Jacquin, F. Malassenet, L. Reuter & A.D. Sloan,
  1856.     'Harnessing chaos for image synthesis', Computer Graphics,
  1857.     vol 22 no 4 pp 131-140, 1988.
  1858.   M.F. Barnsley, A.E. Jacquin, 'Application of recurrent iterated
  1859.     function systems to images', Visual Comm. and Image Processing,
  1860.     vol SPIE-1001, 1988.
  1861.   A. Jacquin, "Image Coding Based on a Fractal Theory of Iterated Contractive
  1862.     Image Transformations" p.18, January 1992 (Vol 1 Issue 1) of IEEE Trans
  1863.     on Image Processing.
  1864.   A.E. Jacquin, 'A novel fractal block-coding technique for digital
  1865.     images', Proc. ICASSP 1990.
  1866.   G.E. Oien, S. Lepsoy & T.A. Ramstad, 'An inner product space
  1867.     approach to image coding by contractive transformations',
  1868.     Proc. ICASSP 1991, pp 2773-2776.
  1869.   D.S. Mazel, Fractal Modeling of Time-Series Data, PhD Thesis,
  1870.     Georgia Tech, 1991.    (One dimensional, not pictures)
  1871.   S. A. Hollatz, "Digital image compression with two-dimensional affine
  1872.     fractal interpolation functions", Department of Mathematics and
  1873.     Statistics, University of Minnesota-Duluth, Technical Report 91-2.
  1874.     (a nuts-and-bolts how-to-do-it paper on the technique)
  1875.   Stark, J., "Iterated function systems as neural networks",
  1876.     Neural Networks, Vol 4, pp 679-690, Pergamon Press, 1991.
  1877.   Monro D M and Dudbridge F, "Fractal block coding of images",
  1878.     Electronics Letters 28(11):1053-1054 (1992)
  1879.   Beaumont J M, "Image data compression using fractal techniques",
  1880.     British Telecom Technological Journal 9(4):93-108 (1991)
  1881.   Fisher Y, "Fractal image compression", Siggraph 92
  1882.   Graf S, "Barnsley's Scheme for the Fractal Encoding of Images",
  1883.     Journal Of Complexity, V8, 72-78 (1992).
  1884.   Monro D.M. 'A hybrid fractal transform', Proc ICASSP 93, pp. V: 169-72
  1885.   Monro D.M. & Dudbridge F. 'Fractal approximation of image blocks',
  1886.     Proc ICASSP 92, pp. III: 485-488
  1887.   Monro D.M., Wilson D., Nicholls J.A. 'High speed image coding with the Bath
  1888.     Fractal Transform', IEEE International Symposium on Multimedia Technologies
  1889.     Southampton, April 1993
  1890.   Jacobs, E.W., Y. Fisher and R.D. Boss.  "Image Compression:  A study
  1891.     of the Iterated Transform Method."  _Signal Processing 29_  (1992) 25-263
  1892.   Vrscay, Edward R.  "Iterated Function Systems:  Theory, Applications,
  1893.     and the Inverse Problem."  _Fractal Geometry and Analysis_,
  1894.     J. Belair and S. Dubuc (eds.)  Kluwer Academic, 1991.  405-468.
  1895.  
  1896. Books:
  1897.     The Fractal Transform,
  1898.     Michael F. Barnsley and Louisa F. Anson
  1899.     ISBN 0-86720-218-1, ca. 250 pp, $49.95
  1900.  
  1901.     Fractal Image Compression
  1902.     Michael F. Barnsley and Lyman P. Hurd
  1903.     ISBN 0-86720-457-5, ca. 250 pp., $49.95
  1904.     Copies can be ordered directly from the publisher by sending a message
  1905.     to kpeters@math.harvard.edu with name, address and a Mastercard or
  1906.     Visa card number with expiration date.
  1907.  
  1908. Barnsley's company is:
  1909.  
  1910. Iterated Systems, Inc.
  1911. 5550A Peachtree Parkway, Suite 650
  1912. Norcross, GA  30092
  1913. tel: 404-840-0310 or 1-800-4FRACTL
  1914. fax: 404-840-0806
  1915.  
  1916. ------------------------------------------------------------------------------
  1917.  
  1918. Subject: [18] I need specs and source for TIFF and CCITT group 4 Fax
  1919.  
  1920.  
  1921. Specs for Group 3 and 4 image coding (group 3 is very similar to group 4)
  1922. are in CCITT (1988) volume VII fascicle VII.3. They are recommendations
  1923. T.4 and T.6 respectively. There is also an updated spec contained in 1992
  1924. recommendations T.1 to T.6.
  1925.  
  1926. CCITT specs are available by anonymous ftp (see above answer on
  1927. V.42bis).  The T.4 and T.6 specs are on src.doc.ic.ac.uk in directory
  1928. /computing/ccitt/ccitt-standards/ccitt/1988/ascii, files 7_3_01.txt.Z and
  1929. 7_3_02.txt.Z respectively.
  1930.  
  1931. The following paper covers T.4, T.6 and JBIG:
  1932.  
  1933.   "Review of standards for electronic imaging for facsimile systems"
  1934.   in Journal of Electronic Imaging, Vol. 1, No. 1, pp. 5-21, January 1992.
  1935.  
  1936.  
  1937. Source code can be obtained as part of a TIFF toolkit - TIFF image
  1938. compression techniques for binary images include CCITT T.4 and T.6:
  1939.  
  1940.     sgi.com:/graphics/tiff/v3.2.tar.Z    [192.48.153.1]
  1941.     Contact: sam@sgi.com
  1942.  
  1943. There is also a companion compressed tar file (v3.0pics.tar.Z) that
  1944. has sample TIFF image files. A draft of TIFF 6.0 is in TIFF6.ps.Z.
  1945. Concerning JPEG compression in TIFF 6.0, Tom Lane <tgl+@cs.cmu.edu> adds:
  1946.  
  1947.   The TIFF document won't do you much good unless you also have the official
  1948.   JPEG standard. You can buy it from ANSI or your national ISO member
  1949.   organization (DIN over there, I suppose). [See also the book by Pennebaker
  1950.   and Mitchell referenced in item 75 of this FAQ.]
  1951.  
  1952.   Worse, the TIFF 6.0 spec has serious problems in its JPEG features.  It is
  1953.   probable that section 22 (JPEG) will be rewritten from scratch.  If you are
  1954.   considering implementing TIFF/JPEG, please contact me at tgl+@cs.cmu.edu for
  1955.   the latest word.
  1956.  
  1957. Software for reading and writing CCITT Group 3 and 4 images is
  1958. also available in directory merry.cs.monash.edu.au:/pub/alanf/TIFF_FAX
  1959. (130.194.67.101). Contact: Alan Finlay <alanf@bruce.cs.monash.edu.au>.
  1960.  
  1961.  
  1962. See also question 54 below.
  1963.  
  1964. ------------------------------------------------------------------------------
  1965.  
  1966. Subject: [19] What is JPEG?
  1967.  
  1968.  
  1969. JPEG (pronounced "jay-peg") is a standardized image compression mechanism.
  1970. JPEG stands for Joint Photographic Experts Group, the original name of the
  1971. committee that wrote the standard.  JPEG is designed for compressing either
  1972. full-color or gray-scale digital images of "natural", real-world scenes.
  1973. It does not work so well on non-realistic images, such as cartoons or line
  1974. drawings.
  1975.  
  1976. JPEG does not handle black-and-white (1-bit-per-pixel) images, nor does it
  1977. handle motion picture compression.  Standards for compressing those types
  1978. of images are being worked on by other committees, named JBIG and MPEG
  1979. respectively.
  1980.  
  1981. Regular JPEG is "lossy", meaning that the image you get out of decompression
  1982. isn't quite identical to what you originally put in.  The algorithm achieves
  1983. much of its compression by exploiting known limitations of the human eye,
  1984. notably the fact that small color details aren't perceived as well as small
  1985. details of light-and-dark.  Thus, JPEG is intended for compressing images that
  1986. will be looked at by humans.  If you plan to machine-analyze your images, the
  1987. small errors introduced by JPEG may be a problem for you, even if they are
  1988. invisible to the eye.  The JPEG standard includes a separate lossless mode,
  1989. but it is not widely used and does not give nearly as much compression as the
  1990. lossy mode.
  1991.  
  1992. Question 75 "Introduction to JPEG" (in part 2 of this FAQ) gives an overview
  1993. of how JPEG works and provides references for further reading.  Also see the
  1994. JPEG FAQ article, which covers JPEG software and usage hints.  The JPEG FAQ is
  1995. posted regularly in news.answers by Tom Lane <tgl+@cs.cmu.edu>.  (See question
  1996. 53 "Where are FAQ lists archived" if this posting has expired at your site.)
  1997.  
  1998. For JPEG software, see item 15 above.
  1999. For JPEG hardware, see item 85 in part 3 of this FAQ.
  2000.  
  2001. ------------------------------------------------------------------------------
  2002.  
  2003. Subject: [20] I am looking for source of an H.261 codec and MPEG
  2004.  
  2005.  
  2006. The H.261 spec is available on src.doc.ic.ac.uk in
  2007. /computing/ccitt/standards/ccitt/1992/h/h261.doc.Z (or h261.rtf.Z).
  2008.  
  2009.  
  2010. For H.261 hardware, see item 85 in part 3 of this FAQ.
  2011.  
  2012. from Thierry TURLETTI <turletti@sophia.inria.fr>:
  2013.  
  2014. We have implemented a software version of H.261 codec. 
  2015. It runs on top of UNIX and X-Windows. The coder uses the simple video capture
  2016. board "VideoPix" provided by SUN for the SparcStation. The output is directed
  2017. towards a standard TCP connection, instead of the leased lines or switched 
  2018. circuits for which regular H.261 codecs are designed. This enable us to test
  2019. video conferences over regular internet connections.
  2020. We have to polish it a bit, but the first release is now available by anonymous
  2021. ftp from avahi.inria.fr, in "/pub/h261/h261.tar.Z".
  2022.  
  2023.  
  2024. from Andy Hung <achung@cs.stanford.edu>:
  2025.  
  2026. Public domain UNIX C source code to do both image and image sequence
  2027. compression and decompression is available by anonymous ftp:
  2028.  
  2029. MPEG-I            havefun.stanford.edu:pub/mpeg/MPEGv1.2.alpha.tar.Z
  2030. CCITT H.261(P*64)    havefun.stanford.edu:pub/p64/P64v1.2.alpha.tar.Z
  2031. JPEG            havefun.stanford.edu:pub/jpeg/JPEGv1.2.beta.tar.Z
  2032.  
  2033. These codecs operate on raw raster scanned images.
  2034.  
  2035. A software program to display raw raster-scanned YUV images and image
  2036. sequences on X grayscale or color monitors is provided by a program in
  2037. the anonymous ftp directory havefun.stanford.edu pub/cv/CVv1.1.tar.Z.
  2038. If you are using the codecs above, we recommend that you ftp this file
  2039. over as well.
  2040.  
  2041. The source code has been compiled on DEC and SUN workstations.
  2042. Caution: the P64 codec has not been tested compliant (any available
  2043. p64 video streams would be much appreciated - please let us know at
  2044. achung@cs.stanford.edu).  The other codecs have been tested with
  2045. streams from other encoders.
  2046.  
  2047. We also have some IPB MPEG-I video coded streams in pub/mpeg/*.mpg;
  2048. and P64 video streams in pub/p64/*.p64 that we have generated using
  2049. our codecs.
  2050.  
  2051. For a more complete description see the file
  2052. havefun.stanford.edu:pub/README.
  2053.  
  2054. ------------------------------------------------------------------------------
  2055.  
  2056. Subject: [25] Fast DCT (Discrete Cosine Transform) algorithms
  2057.  
  2058.  
  2059. Many image compression methods, including the JPEG, MPEG, and H.261 standards,
  2060. are based on the discrete cosine transform.  A good overall introduction to
  2061. DCT is the book "Discrete Cosine Transform---Algorithms, Advantages,
  2062. Applications" by K.R. Rao and P. Yip (Academic Press, London, 1990).
  2063. This has an extensive, though already dated, bibliography.
  2064.  
  2065. Here are some newer references provided by Tom Lane <tgl+@cs.cmu.edu>.
  2066. Most of these are in IEEE journals or conference proceedings, notably
  2067. ICASSP = IEEE Intl. Conf. on Acoustics, Speech, and Signal Processing.
  2068. ICCAS = IEEE Intl. Conf. on Circuits and Systems.
  2069. DCC = Data Compression Conference.
  2070.  
  2071. Polynomial Transform Computation of the 2-D DCT, Duhamel & Guillemot,
  2072.   ICASSP '90 p. 1515.
  2073. A Forward-Mapping Realization of the Inverse DCT, McMillan & Westover,
  2074.   DCC '92 p. 219.
  2075. A Fast Algorithm for 2-D DCT, Cho, Yun & Lee, ICASSP '91 p. 2197.
  2076. Fast Algorithm and Implementation of 2-D DCT, Cho & Lee, Tr. CAS v38 p. 297.
  2077. A DCT Chip based on a new Structured and Computationally Efficient DCT
  2078.   Algorithm, Duhamel, Guillemot & Carlach, ICCAS '90 p. 77.
  2079. Trade-offs in the Computation of Mono- and Multi-dimensional DCTs,
  2080.   Vetterli, Duhamel & Guillemot, ICASSP '89 p. 999.
  2081. Practical Fast 1-D DCT Algorithms with 11 Multiplications,
  2082.   Loeffler, Ligtenberg & Moschytz, ICASSP '89 p. 988.
  2083. New Scaled DCT Algorithms for Fused Multiply/Add Architectures,
  2084.   Linzer & Feig, ICASSP '91 p. 2201.
  2085. Fast Algorithms for the 2-D Discrete Cosine Transform, Kamangar & Rao,
  2086.   IEEE Tr. Computers, v C-31 p. 899.
  2087. Fast 2-D Discrete Cosine Transform, Vetterli, ICASSP '85 p. 1538.
  2088. A Two-Dimensional Fast Cosine Transform, Haque, Tr. ASSP v ASSP-33 p. 1532.
  2089. Real-Time Parallel and Fully Pipelined 2-D DCT Lattice Structures with
  2090.   Application to HDTV Systems, Chiu & Liu, Tr. CAS for Video Tech, v 2 p. 25.
  2091.  
  2092.  
  2093. The free JPEG code (jpegsrc.v4.tar.Z) has one of the fastest implementations
  2094. of the DCT code.  It's all in the files jfwddct.c and jrevdct.c (which do
  2095. the dct and idct, respectively). See item 15 for ftp locations.
  2096.  
  2097. ------------------------------------------------------------------------------
  2098.  
  2099. Subject: [26] Are there algorithms and standards for audio compression?
  2100.  
  2101.  
  2102. Yes. See the introduction to MPEG given in part 2 of this FAQ.
  2103.  
  2104. A lossless compressor for 8bit and 16bit audio data (.au) is available by
  2105. anonymous ftp at svr-ftp.eng.cam.ac.uk:/comp.speech/sources/shorten-1.11.tar.Z.
  2106. An MSDOS executable is in shn109.exe. Shorten works by using Huffman
  2107. coding of prediction residuals.  Compression is generally better than
  2108. that obtained by applying general purpose compression utilities to
  2109. audio files. Shorten version 1.11 also supports lossy compression.
  2110. Contact: Tony Robinson <ajr@dsl.eng.cam.ac.uk>.
  2111.  
  2112. Copied from the comp.dsp FAQ posted by guido@cwi.nl (Guido van Rossum):
  2113.  
  2114.   Strange though it seems, audio data is remarkably hard to compress
  2115.   effectively.  For 8-bit data, a Huffman encoding of the deltas between
  2116.   successive samples is relatively successful.  For 16-bit data,
  2117.   companies like Sony and Philips have spent millions to develop
  2118.   proprietary schemes.
  2119.  
  2120.   Public standards for voice compression are slowly gaining popularity,
  2121.   e.g. CCITT G.721 and G.723 (ADPCM at 32 and 24 kbits/sec).  (ADPCM ==
  2122.   Adaptive Delta Pulse Code Modulation.)  Free source code for a *fast*
  2123.   32 kbits/sec ADPCM (lossy) algorithm is available by ftp from ftp.cwi.nl
  2124.   as /pub/adpcm.shar.  (** NOTE: if you are using v1.0, you should get
  2125.   v1.1, released 17-Dec-1992, which fixes a serious bug -- the quality
  2126.   of v1.1 is claimed to be better than uLAW **)
  2127.  
  2128.   (Note that U-LAW and silence detection can also be considered
  2129.   compression schemes.)
  2130.  
  2131.  
  2132. You can get a G.721/722/723 package by email to teledoc@itu.arcom.ch, with
  2133.  
  2134. GET ITU-3022
  2135.  
  2136. as the *only* line in the body of the message.
  2137.  
  2138.  
  2139. A note on u-law from Markus Kuhn <mskuhn@immd4.informatik.uni-erlangen.de>:
  2140.  
  2141.   u-law (more precisely (greek mu)-law or 5-law if you have an 8-bit
  2142.   ISO terminal) is more an encoding then a compression method,
  2143.   although a 12 to 8 bit reduction is normally part of the encoding.
  2144.   The official definition is CCITT recommendation G.711. If you want
  2145.   to know how to get CCITT documents, check the Standards FAQ
  2146.   posted to news.answers or get the file standards-faq by ftp in
  2147.   directory rtfm.mit.edu:/pub/usenet/news.answers.
  2148.  
  2149.  
  2150. See also the comp.dsp FAQ for more information on:
  2151.  
  2152. - The U.S. DoD's Federal-Standard-1016 based 4800 bps code excited linear
  2153.   prediction voice coder version 3.2a (CELP 3.2a)
  2154. - The U.S. DoD's Federal-Standard-1015/NATO-STANAG-4198 based 2400 bps
  2155.   linear prediction coder version 53 (LPC-10e v53)
  2156. - Realtime DSP code and hardware for FS-1015 and FS-1016
  2157.  
  2158. You can find the comp.dsp FAQ in comp.dsp or news.answers with subject:
  2159. "FAQ: Audio File Formats" or by ftp on rtfm.mit.edu
  2160. in /pub/usenet/news.answers/audio-fmts/part1.
  2161.  
  2162.  
  2163. CELP C code for Sun SPARCs is available for anonymous ftp at
  2164. furmint.nectar.cs.cmu.edu, in directory celp.audio.compression.
  2165. Version 3.2a is also in super.org:/pub/celp_3.2a.tar.Z.
  2166.  
  2167.  
  2168. Recommended reading:
  2169.   Digital Coding of Waveforms: Principles and Applications to Speech and
  2170.   Video.  N. S. Jayant and Peter Noll.  Prentice-Hall, 1984, ISBN
  2171.   0-13-211913-7.
  2172.  
  2173.  
  2174. from Markus Kuhn <mskuhn@immd4.informatik.uni-erlangen.de>:
  2175.  
  2176.   One highest quality sound compression format is called ASPEC and has
  2177.   been developped by a team at the Frauenhofer Institut in Erlangen (Germany)
  2178.   and others.
  2179.  
  2180.   ASPEC produces CD like quality and offers several bitrates, one is
  2181.   128 kbit/s. It is a lossy algorithm that throws away frequencys that
  2182.   aren't registered in the human cochlea in addition to sophisticated
  2183.   entropy coding. The 64 kbit/s ASPEC variant might soon bring hifi
  2184.   quality ISDN phone connections. It has been implemented on standard DSPs.
  2185.  
  2186.   The Layer 3 MPEG audio compression standard now contains what is officially
  2187.   called the best parts of the ASPEC and MUSICAM algorithms. A reference is:
  2188.  
  2189.     K.Brandenburg, G.Stoll, Y.F.Dehery, J.D.Johnston, L.v.d.Kerkhof,
  2190.     E.F.Schroeder: "The ISO/MPEG-Audio Codec: A Generic Standard for Coding
  2191.     of High Quality Digital Audio",
  2192.     92nd. AES-convention, Vienna 1992, preprint 3336
  2193.  
  2194.  
  2195. from Jutta Degener <jutta@cs.tu-berlin.de> and Carsten Bormann
  2196. <cabo@cs.tu-berlin.de>:
  2197.  
  2198.   GSM 06.10 13 kbit/s RPE/LTP speech compression available
  2199.   --------------------------------------------------------
  2200.  
  2201.   The Communications and Operating Systems Research Group (KBS) at the
  2202.   Technische Universitaet Berlin is currently working on a set of
  2203.   UNIX-based tools for computer-mediated telecooperation that will be
  2204.   made freely available.
  2205.  
  2206.   As part of this effort we are publishing an implementation of the
  2207.   European GSM 06.10 provisional standard for full-rate speech
  2208.   transcoding, prI-ETS 300 036, which uses RPE/LTP (residual pulse
  2209.   excitation/long term prediction) coding at 13 kbit/s.
  2210.  
  2211.   GSM 06.10 compresses frames of 160 13-bit samples (8 kHz sampling
  2212.   rate, i.e. a frame rate of 50 Hz) into 260 bits; for compatibility
  2213.   with typical UNIX applications, our implementation turns frames of 160
  2214.   16-bit linear samples into 33-byte frames (1650 Bytes/s).
  2215.   The quality of the algorithm is good enough for reliable speaker
  2216.   recognition; even music often survives transcoding in recognizable 
  2217.   form (given the bandwidth limitations of 8 kHz sampling rate).
  2218.  
  2219.   Version 1.0 of the implementation is available per anonymous ftp from
  2220.   tub.cs.tu-berlin.de as /pub/tubmik/gsm-1.0.tar.Z.  Questions and bug
  2221.   reports should be directed to toast@tub.cs.tu-berlin.de.  
  2222.   Note that the distribution is not available via E-mail (please use one
  2223.   of the ftp-via-E-mail servers).
  2224.  
  2225.  
  2226. from Bob Kimball <rkimball@qualcomm.com>:
  2227.  
  2228.   I work for Qualcomm Inc. and we are designing a digital cellular telephone
  2229.   system.  Our phone uses our variable rate vocoder (QCELP) which is designed
  2230.   for speach and compresses 64Kb/s speach to 8Kb/s through 1Kb/s with 8Kb/s
  2231.   being full rate and 1Kb/s for 1/8 rate speach.  It works great for speach.
  2232.  
  2233.   The QCELP process is documented in our Common Air Interface (CAI) which is
  2234.   available for anonymous ftp from lorien.qualcomm.com in /pub/cdma
  2235.   each chapter is a postscript file.  The vocoder is described in appendix A.
  2236.   The whole document is quite large.  This is the document which is currently
  2237.   going through the TIA standard committee so it is not a final version.  The
  2238.   appendix on the vocoder should be almost identical to the final version...
  2239.   whenever that comes out.
  2240.  
  2241.  
  2242. from Nicola Ferioli <ser1509@cdc835.cdc.polimi.it>:
  2243.  
  2244.   On wsmr-simtel20.army.mil, pd1:<msdos.sound>
  2245.   VOCPAK20.ZIP    Lossless 8-bit sound file compressor
  2246.  
  2247.   VOCPACK is a compressor/decompressor for 8-bit digital sound using a
  2248.   lossless algorithm; it is useful to save disk space without degrading
  2249.   sound quality.  It can compress signed and unsigned data, sampled at any
  2250.   rate, mono or stereo.  Since the method used is not lossy, it isn't
  2251.   necessary to strip file headers before compressing.
  2252.  
  2253.   VOCPACK was developed for use with .VOC (SoundBlaster) and .WAV (Windows)
  2254.   files, but any 8-bit sound can be compressed since the program takes no
  2255.   assumptions about the file structure.
  2256.  
  2257.   The typical compression ratio obtained goes from 0,8 for files sampled at
  2258.   11 KHz to 0,4 for 44 Khz files.  The best results are obtained with 44 KHz
  2259.   sounds (mono or stereo): general-purpose archivers create files that can be
  2260.   twice longer than the output of VOCPACK.  You can obtain smaller values
  2261.   using lossy compressors but if your goal is to keep the sound quality
  2262.   unaltered you should use a lossless program like VOCPACK.
  2263.  
  2264. ------------------------------------------------------------------------------
  2265.  
  2266. Subject: [30] My archive is corrupted!
  2267.  
  2268.  
  2269. The two most common reasons for this are
  2270.  
  2271. (1) failing to use the magic word "tenex" (when connected to SIMTEL20 and
  2272.     other TOPS20 systems) or "binary" (when connected to UNIX systems) when
  2273.     transferring the file from an ftp site to your host machine.  The
  2274.     reasons for this are technical and boring.  A synonym for "tenex" is
  2275.     "type L 8", in case your ftp doesn't know what "tenex" means.
  2276.  
  2277. (2) failing to use an eight-bit binary transfer protocol when transferring
  2278.     the file from the host to your PC.  Make sure to set the transfer type
  2279.     to "binary" on both your host machine and your PC.
  2280.  
  2281. ------------------------------------------------------------------------------
  2282.  
  2283. Subject: [31] pkunzip reports a CRC error!
  2284.  
  2285.  
  2286. The portable zip 1.1 contains many workarounds for undocumented restrictions
  2287. in pkunzip. Compatibility is ensured for pkunzip 1.10 only. All previous
  2288. versions (pkunzip 1.0x) have too many bugs and cannot be supported. This
  2289. includes Borland unzip.
  2290.  
  2291. So if your pkunzip reports a CRC error, check that you are not using
  2292. an obsolete version. Get either pkzip 2.04g or unzip 5.0p1 (see question
  2293. 2 above for ftp sites). To generate zip files compatible with pkunzip 1.10,
  2294. use zip 1.1 (see item 2 above for ftp site).
  2295.  
  2296. ------------------------------------------------------------------------------
  2297.  
  2298. Subject: [32] VMS zip is not compatible with pkzip!
  2299.  
  2300.  
  2301. The problem is most likely in the file transfer program.
  2302.  
  2303. Many use kermit to transfer zipped files between PC and VMS VAX.  The
  2304. following VMS kermit settings make VMS-ZIP compatible with PKZIP:
  2305.  
  2306.                                              VMS kermit        PC kermit
  2307.                                            ---------------   --------------
  2308.  
  2309. Uploading PKZIPped file to be UNZIPped:    set fi ty fixed    set fi ty bi
  2310. Downloading ZIPped file to be PKUNZIPped:  set fi ty block    set fi ty bi
  2311.  
  2312. If you are not using kermit, transfer a file created by pkzip on MSDOS
  2313. to VMS, transfer it back to your PC and check that pkunzip can extract it.
  2314.  
  2315. ------------------------------------------------------------------------------
  2316.  
  2317. Subject: [33] I have a problem with Stacker!
  2318.  
  2319.  
  2320. The newsgroup comp.compression is *not* the appropriate place to
  2321. discuss about one specific program on one specific operating system.
  2322. Since you have bought a legal copy of Stacker, you have the
  2323. documentation of your product; please read it. If you can't find the
  2324. answer in the documentation, please report the problem to the Stac
  2325. customer support.  If you really feel that the net has to know about
  2326. your problem, please post in one of the MSDOS newsgroups, such as
  2327. comp.os.msdos.apps or comp.binaries.ibm.pc.d.
  2328.  
  2329. ------------------------------------------------------------------------------
  2330.  
  2331. Subject: [50] What is this 'tar' compression program?
  2332.  
  2333.  
  2334. tar is not a compression program. It just combines several files
  2335. into one, without compressing them. tar file are often compressed with
  2336. 'compress', resulting in a .tar.Z file. See question 2, file type .tar.Z.
  2337. GNU tar has the capability to (de)compress files as well.
  2338.  
  2339. When you have to archive a lot of very small files, it is often
  2340. preferable to create a single .tar file and compress it, than to
  2341. compress the individual files separately. The compression program can
  2342. thus take advantage of redundancy between separate files.  The
  2343. disadvantage is that you must uncompress the whole .tar file to
  2344. extract any member.
  2345.  
  2346. ------------------------------------------------------------------------------
  2347.  
  2348. Subject: [51] I need a CRC algorithm
  2349.  
  2350.  
  2351. As its name implies (Cyclic Redundancy Check) a crc adds redundancy
  2352. whereas the topic of this group is to remove it. But since this
  2353. question comes up often, here is some code (by Rob Warnock <rpw3@sgi.com>).
  2354.  
  2355. The following C code does CRC-32 in BigEndian/BigEndian byte/bit order.
  2356. That is, the data is sent most significant byte first, and each of the bits
  2357. within a byte is sent most significant bit first, as in FDDI. You will need
  2358. to twiddle with it to do Ethernet CRC, i.e., BigEndian/LittleEndian byte/bit
  2359. order. [Left as an exercise for the reader.]
  2360.  
  2361. The CRCs this code generates agree with the vendor-supplied Verilog models
  2362. of several of the popular FDDI "MAC" chips.
  2363.  
  2364. u_long crc32_table[256];
  2365. /* Initialized first time "crc32()" is called. If you prefer, you can
  2366.  * statically initialize it at compile time. [Another exercise.]
  2367.  */
  2368.  
  2369. u_long crc32(u_char *buf, int len)
  2370. {
  2371.         u_char *p;
  2372.         u_long  crc;
  2373.  
  2374.         if (!crc32_table[1])    /* if not already done, */
  2375.                 init_crc32();   /* build table */
  2376.         crc = 0xffffffff;       /* preload shift register, per CRC-32 spec */
  2377.         for (p = buf; len > 0; ++p, --len)
  2378.                 crc = (crc << 8) ^ crc32_table[(crc >> 24) ^ *p];
  2379.         return ~crc;            /* transmit complement, per CRC-32 spec */
  2380. }
  2381.  
  2382. /*
  2383.  * Build auxiliary table for parallel byte-at-a-time CRC-32.
  2384.  */
  2385. #define CRC32_POLY 0x04c11db7     /* AUTODIN II, Ethernet, & FDDI */
  2386.  
  2387. init_crc32()
  2388. {
  2389.         int i, j;
  2390.         u_long c;
  2391.  
  2392.         for (i = 0; i < 256; ++i) {
  2393.                 for (c = i << 24, j = 8; j > 0; --j)
  2394.                         c = c & 0x80000000 ? (c << 1) ^ CRC32_POLY : (c << 1);
  2395.                 crc32_table[i] = c;
  2396.         }
  2397. }
  2398.  
  2399. See also ftp.uni-erlangen.de:/pub/doc/ISO/english/async-HDLC, and the
  2400. source of all archivers, such as the file makecrc.c in the sources of
  2401. zip 2.0 (see item 2).
  2402.  
  2403. ------------------------------------------------------------------------------
  2404.  
  2405. Subject: [52] What about those people who continue to ask frequently asked
  2406.               questions in spite of the frequently asked questions document?
  2407.  
  2408.  
  2409. Just send them a polite mail message, referring them to this document.
  2410. There is no need to flame them on comp.compression.  That would just
  2411. add more noise to this group.  Posted answers that are in the FAQ are
  2412. just as annoying as posted questions that are in the FAQ.
  2413.  
  2414. ------------------------------------------------------------------------------
  2415.  
  2416. Subject: [53] Where are FAQ lists archived?
  2417.  
  2418.  
  2419. Many are crossposted to news.answers.  That newsgroup should have a
  2420. long expiry time at your site; if not, talk to your sysadmin.
  2421.  
  2422. FAQ lists are available by anonymous FTP from rtfm.mit.edu.
  2423. The comp.compression FAQ that you are reading is in directory
  2424.    /pub/usenet/news.answers/compression-faq
  2425.  
  2426. If you don't have FTP access, you can access the archives by mail
  2427. server.  Send an email message to mail-server@rtfm.mit.edu
  2428. containing the commands
  2429.     send usenet/news.answers/compression-faq/part1
  2430.     send usenet/news.answers/compression-faq/part2
  2431.     send usenet/news.answers/compression-faq/part3
  2432. For instructions, send an email message to the same address with the
  2433. words "help" and "index" (no quotes) on separate lines. If you don't
  2434. get a reply, check your return address, or add a line such as
  2435.     path myname@foo.edu
  2436.  
  2437. ------------------------------------------------------------------------------
  2438.  
  2439. Subject: [54] I need specs for graphics formats
  2440.  
  2441.  
  2442. Have a look in directory /pub/graphics.formats on zamenhof.cs.rice.edu.
  2443. It contains descriptions of gif, tiff, fits, etc...
  2444.  
  2445. See also the FAQ list for comp.graphics. See item 53 for an ftp site.
  2446.  
  2447. ------------------------------------------------------------------------------
  2448.  
  2449. Subject: [55] Where can I find Lenna and other images?
  2450.  
  2451.  
  2452. A bunch of standard images (lenna, baboon, cameraman, crowd, moon
  2453. etc..) are on ftp site eedsp.gatech.edu (130.207.226.2) in directory
  2454. /database/images. The images are in 256-level grayshades (256x256
  2455. pixels, 256 "colors").
  2456.  
  2457. [Note: the site ipl.rpi.edu mentioned below keeps changing. Images
  2458. stay there for a while then disappear. The information is kept in this
  2459. FAQ in case the image directories become available again.]
  2460.  
  2461. The site ipl.rpi.edu (128.113.14.50) has standard images in two
  2462. directories:
  2463.    ipl.rpi.edu:/pub/image/still/usc 
  2464.    ipl.rpi.edu:/pub/image/still/canon
  2465. (The directory /pub/image/sequence has been taken offline because of
  2466. possible copyright problems.)
  2467.  
  2468. In each of those directories are the following directories:
  2469.    bgr     - 24 bit blue, green, red
  2470.    color   - 24 bit red, green, blue
  2471.    gray    - 8 bit grayscale uniform weighted
  2472.    gray601 - 8 bit grayscale CCIR-601 weighted
  2473.  
  2474. And in these directories are the actual images.  
  2475.  
  2476. For example, the popular lena image is in
  2477.    ipl.rpi.edu:/pub/image/still/usc/color/lena  # 24 bit RGB
  2478.    ipl.rpi.edu:/pub/image/still/usc/bgr/lena    # 24 bit BGR
  2479.    ipl.rpi.edu:/pub/image/still/usc/gray/lena   # 8 bit gray
  2480.  
  2481. All of the images are in Sun rasterfile format.  You can use the pbm
  2482. utilities to convert them to whatever format is most convenient.
  2483. [pbm is available in ftp.ee.lbl.gov:/pbmplus*.tar.Z].
  2484. Questions about the ipl archive should be sent to help@ipl.rpi.edu.
  2485.  
  2486.  
  2487. There are few gray-scale still images and some raw data of test results
  2488. available in directory nic.funet.fi:/pub/graphics/misc/test-images.
  2489.  
  2490.  
  2491. Rodney Peck <rodney@balltown.cma.com> is interested in some method
  2492. of establishing a canonical ftp database of images but does not have
  2493. the resources to provide an ftp site for that database. Send suggestions to
  2494. rodney@balltown.cma.com.
  2495.  
  2496.  
  2497. Beware: the same image often comes in many different forms, at
  2498. different resolutions, etc... The original lenna image is 512 wide,
  2499. 512 high, 8 bits per pel, red, green and blue fields.  Gray-scale
  2500. versions of Lenna have been obtained in two different ways from the
  2501. original:
  2502.  (1) Using the green field as a gray-scale image, and
  2503.  (2) Doing an RGB->YUV transformation and saving the Y component.
  2504. Method (1) makes it easier to compare different people's results since
  2505. everyone's version should be the same using that method.  Method (2)
  2506. produces a more correct image.
  2507.  
  2508. For the curious: 'lena' or 'lenna' is a digitized Playboy centerfold,
  2509. from November 1972. (Lenna is the spelling in Playboy, Lena is the
  2510. Swedish spelling of the name.) Lena Soderberg (ne Sjooblom) was last
  2511. reported living in her native Sweden, happily married with three kids
  2512. and a job with the state liquor monopoly.  In 1988, she was
  2513. interviewed by some Swedish computer related publication, and she was
  2514. pleasantly amused by what had happened to her picture.  That was the
  2515. first she knew of the use of that picture in the computer business.
  2516.  
  2517. The editorial in the January 1992 issue of Optical Engineering (v. 31
  2518. no. 1) details how Playboy has finally caught on to the fact that
  2519. their copyright on Lenna Sjooblom's photo is being widely infringed.
  2520. It sounds as if you will have to get permission from Playboy to
  2521. publish it in the future.
  2522.  
  2523.  
  2524. Note on the CCITT test images, by Robert Estes <estes@eecs.ucdavis.edu>:
  2525.  
  2526. The ccitt files are in ipl.rpi.edu:/image-archive/bitmap/ccitt
  2527. (128.113.14.50). They are named ccitt-n.ras.Z where n goes from 1 to 8.
  2528. Each file has an accompanying doc file called ccitt-n.ras.doc which
  2529. describes the image file. Here's the doc file for ccitt-1.ras:
  2530.  
  2531. Name ccitt-1.ras
  2532. Size 1728 x 2376 x 1
  2533. Type 1 bit standard format sun rasterfile 
  2534. Keywords binary standard image 1 bit fax
  2535. Description
  2536. One of eight images from the standard binary CCITT test image set.
  2537.  
  2538. This set is commonly used to compare binary image compression
  2539. techniques. The images are are 1728x2376 pixels.
  2540.  
  2541. ------------------------------------------------------------------------------
  2542.  
  2543. Subject: [56] I am looking for a message digest algorithm
  2544.  
  2545.  
  2546. Look on the ftp site rsa.com, in directory /pub. MD4 and MD5 are there.
  2547. This question would be more appropriate on sci.crypt.
  2548.  
  2549.  
  2550.  
  2551.           End of part 1 of the comp.compression faq.
  2552.