home *** CD-ROM | disk | FTP | other *** search
/ Simtel MSDOS - Coast to Coast / simteldosarchivecoasttocoast.iso / starter / squeeze.txt < prev    next >
Text File  |  1994-03-07  |  12KB  |  279 lines
  1.                     Data Compression Techniques
  2.                           Using SQ and USQ
  3.  
  4.                            Mark DiVecchio
  5.                     San Diego IBM PC Users Group
  6.  
  7. In any computer system, efficient management of the file storage
  8. space is important.  The two programs SQ and USQ reduce the size of
  9. data files by using the Huffman Data Compression Algorithm.
  10.  
  11. A file is composed of a sequence of bytes.  A byte is composed of 8
  12. bits.  That byte can have a decimal value between 0 and 255.  A
  13. typical text file, like a C language program, is composed of the
  14. ASCII character set (decimal 0 to 127).  This character set only
  15. requires seven of the eight bits in a byte.  Just think -- if there
  16. were a way to use that extra bit for another character, you could
  17. reduce the size of the file by 12.5%.  For those of you who use
  18. upper case characters only, you use only about 100 of the ASCII
  19. codes from 0 to 255.  You could save 60% of your storage if the bits
  20. not needed within each byte could be used for other characters.
  21. What if you could encode the most frequently used characters in the
  22. file with only one bit?  For example, if you could store the letter
  23. "e" (the most commonly used letter in the English language) using
  24. only one bit :  "1", you could save 87.5% of the space that the "e"
  25. would normally take if it were stored as the ASCII "0110 0101"
  26. binary.
  27.  
  28. The answer to these questions is the SQ and USQ programs.
  29.  
  30. The SQ program uses the Huffman coding technique to search for the
  31. frequency of use of each of the 256 possible byte patterns, and it
  32. then assigns a translation for each character to a bit string.  All
  33. of these bit strings are placed end to end and written onto a disk
  34. file.  The encoding information is also put on the file since the
  35. USQ program needs to know the character distribution of the original
  36. file.
  37.  
  38. The USQ program reads in the encoding information and then reads in
  39. the encoded file.  It is a simple matter to scan the encoded file
  40. and produce an output file which is identical to the file that SQ
  41. started with.
  42.  
  43.                       Huffman Coding Technique
  44.  
  45. This is by far the most popular encoding technique in use today.
  46. The Huffman encoding replaces fixed bit characters with variable
  47. length bit strings.  The length of the bit string is roughly
  48. inversely proportional to the frequency of occurrence of the
  49. character.  For those of you inclined to such symbolism:
  50.  
  51. Length of bit  ~= log  (character
  52.      string          2  probability)
  53.  
  54. The implementation of the algorithm which we will discuss encodes
  55. fixed bit strings of length 8.
  56.  
  57. This algorithm requires two passes through the input file. The first
  58. pass builds a table of 256 entries showing the frequency of each
  59. occurrence of each of the 256 possible values for a byte of
  60. information.
  61.  
  62. Once the counting is complete, the algorithm must decide which bit
  63. strings to associate with each of the 256 characters that were found
  64. in the file.  Note that if a particular byte value was never used,
  65. no string association is needed.
  66.  
  67. The second pass through the input file converts each byte into its
  68. encoded string.  Remember that when the output file is created, the
  69. information used for encoding must also be written on the file for
  70. use by the decoding program.
  71.  
  72. The decoding program reads the encoding information from the file
  73. and then starts reading the bit strings.  As soon as enough bits are
  74. read to interpret a character, that character is written onto the
  75. final output file.  See the next two sections on how SQ and USQ
  76. actually implement this.
  77.  
  78. Even though this article primarily has addresses ASCII input files,
  79. there is nothing which restricts this algorithm to ASCII.  It will
  80. work on binary files (.COM or .EXE) as well. But since the length of
  81. the encoded bit string is approximately equal to the inverse of the
  82. frequency of occurrence of each 8 bit byte, a binary file may not
  83. compress very much.  This is because a binary file most likely has a
  84. uniform distribution over the 256 values in a byte.  A machine
  85. language program is not like the English language where the letter
  86. "e" is used far more than other letters.  If the distribution is
  87. uniform, the encoded bit strings will all be the same length and the
  88. encoded file could be longer than the original (because of the
  89. encoding information on the front of the file).  All of this has to
  90. be qualified, because machine language programs tend to use a lot of
  91. "MOV" instructions and have a lot of bytes of zeros so that encoding
  92. .COM and .EXE files does save some disk space.
  93.  
  94.                                  SQ
  95.  
  96. The SQ program is an example of the Huffman algorithm.
  97.  
  98. The first thing that SQ does is read through the input file and
  99. create a distribution array for the 256 possible characters.  This
  100. array contains counts of the number of occurrences of each of the
  101. 256 characters.  The program counts these values in a 16 bit number.
  102. It makes sure that, if you are encoding a big file, counts do not
  103. exceed a 16 bit value.  This is highly unlikely, but it must be
  104. accounted for.
  105.  
  106. At the same time, SQ removes strings of identical characters and
  107. replaces them with the ASCII character DLE followed by a character
  108. count of 2-255.  SQ replaces the ASCII DLE with the pair of
  109. characters:  DLE DLE.  This is not related to the Huffman algorithm
  110. but just serves to compress the file a little more.
  111.  
  112. Once SQ has scanned the input file, it creates a binary tree
  113. structure containing this frequency occurrence information. The most
  114. frequently occurring characters have the shortest path from the root
  115. to the node, and the least frequently occurring characters have the
  116. longest path.  For example, if your file were:
  117.  
  118. ABRACADABRA   (a very simple and
  119.                magical example)
  120.  
  121. The table of frequency of occurrences would be:
  122.  
  123. Letter         # of Occurrences
  124. ------         ---------------
  125.   A                 5
  126.   B                 2
  127.   C                 1
  128.   D                 1
  129.   R                 2
  130.   all the rest      0
  131.  
  132. Since the letter "A" occurs most often, it should have the shortest
  133. encoded bit string.  The letters "C" and "D" should have the
  134. longest.  The other characters which don't appear in the input file
  135. don't need to be considered.
  136.  
  137. SQ would create a binary tree to represent this information. The
  138. tree might look something like this (for purposes of discussion
  139. only):
  140.  
  141.              root    <---Computer trees are
  142.           /    \      always upside down!
  143.         1       0   <-- This is called a
  144.       /       /   \        node.
  145.      A      1       0
  146.           /       /   \  <--This is called
  147.         B       1       0    branch.
  148.               /       /   \
  149.             C       1       0
  150.                   /           \
  151.                 D               R  <-This
  152.                                      is a
  153.                                      leaf
  154.  
  155.  
  156. From this our encoded bit strings which are kept in a translation
  157. table would be:
  158.  
  159.   Table Entry  Character  Binary
  160.   -----------  ---------  ------
  161.        1           A      1
  162.        2           B      01
  163.        3           C      001
  164.        4           D      0001
  165.        5           R      0000
  166.  
  167.  
  168. The output file would be:
  169.  
  170.  
  171.     A B  R    A C   A D    A B  R    A
  172.     ----------------------------------
  173.     1 01 0000 1 001 1 0001 1 01 0000 1
  174.     (binary)
  175.  
  176.     A1 31 A1
  177.     (hex)
  178.  
  179.  
  180. We have reduced the size of your file from ten bytes to three bytes
  181. for a 70% savings.  For this simple example, things aren't that well
  182. off since we must put the binary tree encoding information onto the
  183. file as well.  So the file size grew a lot.  But consider a file
  184. with the word ABRACADABRA repeated 100,000 times.  Now the encoding
  185. information is going to be a very very small percentage of the
  186. output file and the file will shrink tremendously.
  187.  
  188. SQ opens the output file and writes out the binary tree information.
  189. Then SQ rewinds the input file and rereads it from the beginning.
  190. As it reads each character, it looks into the translation table and
  191. outputs the corresponding bit string.
  192.  
  193. SQ is a little more complicated than what I have outlined since it
  194. must operate in the real world of hardware, but this is a fairly
  195. complete description of the algorithm.
  196.  
  197.                                 USQ
  198.  
  199. The USQ program is very straightforward.  It reads in the encoding
  200. information written out by SQ and builds the identical binary tree
  201. that SQ used to encode the file.
  202.  
  203. USQ then reads the input file as if it were a string of bits.
  204. Starting at the root of the tree, it traverses one branch of the
  205. tree with each input bit.  If it has reached a leaf, it has a
  206. character and that character is written to the output file.  USQ
  207. then starts at the root again with the next bit from the input file.
  208.  
  209.                        What does it all mean?
  210.  
  211. Now that we understand the algorithm and a little about how the SQ
  212. and USQ programs work, we can use that knowledge to help us run our
  213. systems a little more efficiently.  (So all of this theory is worth
  214. something after all!).
  215.  
  216. 1.  Files must be above a threshold size, or else the output file
  217. will be longer than the input file because of the decoding
  218. information put at the beginning of the compressed data.  We don't
  219. know the exact size of the threshold because the encoding binary
  220. tree information depends on the distribution of the characters in a
  221. file.  At least we know to check the size of the encoded file after
  222. we run SQ to make sure our file didn't grow.
  223.  
  224. 2.  Some files will not compress well if they have a uniform
  225. distribution of byte values, for example, .COM or .EXE files. This
  226. is because of the way SQ builds the tree.  Remember that bytes with
  227. the same frequency of occurrence are at the same depth (usually) in
  228. the tree.  So if all of the bytes have the same depth, the output
  229. strings are all the same length.
  230.  
  231. 3.  SQ reads the input file twice.  If you can, use RAM disk at
  232. least for the input file and for both files if you have the room.
  233. The next best case is to use two floppy drives, one for input and
  234. one for output.  This will cause a lot of disk starts and stops but
  235. not much head movement.  Worst case is to use one floppy drive for
  236. both input and output.  This will cause a lot of head movement as
  237. the programs alternate between the input and output files.
  238.  
  239.                     Other Compression Techniques
  240.  
  241.                         RUN-LENGTH ENCODING
  242.  
  243. Run-length encoding is a technique whereby sequences of identical
  244. bytes are replaced by the repeated byte and a byte count.  As you
  245. might guess, this method is effective only on very specialized
  246. files.  One good candidate is a screen display buffer.  A screen is
  247. made up mostly of "spaces".  A completely blank line could be
  248. reduced from 80 bytes of spaces to one space followed by a value of
  249. 80.  To go from 80 bytes down to two bytes is a savings of almost
  250. 98%.  You might guess that for text files or binary files, this
  251. technique does not work well at all.
  252.  
  253.                         ADAPTIVE COMPRESSION
  254.  
  255. This technique replaces strings of characters of code.  For example,
  256. the string "ABRACADABRA" would be replaced by a code.  Typical
  257. algorithms use a 12 bit code.  The algorithm is unique in that it
  258. only requires a single pass through the input file as the encoding
  259. is taking place.  The current incarnation of this procedure is
  260. called the LZW method (after co-inventors; A.  Lempel, J.  Ziv and
  261. T.  Welch).  This algorithm claims a savings of 66% on machine
  262. language files and up to 83% on COBOL files.
  263.  
  264.                            Other Reading
  265.  
  266. If you are interested in reading more about data compression
  267. techniques, you may be interested in these articles:
  268.  
  269.  
  270. H.K. Reghbati, "An Overview of Data Compression Techniques,"
  271. Computer Magazine, Vol. 14, No. 4, April 1981, pp. 71-76.
  272.  
  273. T.A. Welch, "A Technique for High-Performance Data Compression",
  274. Computer Magazine, Vol 17, No. 6, June 1984, pp. 8-19.
  275.  
  276. J. Ziv and A. Lempel, "A Universal Algorithm for Sequential Data
  277. Compression," IEEE Transactions on Information Theory, Vol. It-23,
  278. No.3, May 1977, pp. 337-343.
  279.