home *** CD-ROM | disk | FTP | other *** search
/ Black Box 4 / BlackBox.cdr / progbas / huffman.arj / HUFFMAN.DOC < prev   
Encoding:
Text File  |  1991-12-25  |  5.6 KB  |  160 lines
  1.              ┌──────────────────────────────────┐
  2.              │          An Example of           │
  3.              │       Huffman Compression        │
  4.              │By Rich Geldreich December 24,1991│
  5.              └──────────────────────────────────┘
  6.  
  7.  
  8.      Hello! You just downloaded two QuickBASIC 4.5 programs
  9. that compress/decompress VGA screens(screen 13) with a
  10. Huffman compression algorithm.
  11.      Okay. It's not that fast- but I have been optimizing it
  12. for two or three months now and it is about as good as I can
  13. get it. I didn't have much information about Huffman
  14. compression, just the bare basics. It works, however.
  15.      Huffman compression doesn't even touch LZW compression-
  16. similar to the type used in GIF pictures and PKZIP type
  17. protocols. I decompressed many pictures and recompressed them
  18. with my Huffman compressor and find that they are always
  19. larger than their GIF brothers. Well, Huffman relies on
  20. characters being used more than other characters for its
  21. compression, while GIF's type relies on patterns and repeated
  22. byte sequences for its compression. While one Huffman code
  23. represents one character, one LZW code can represent more
  24. than one character. Well, you got it, so let me explain it. I
  25. think it's pretty neat- hell, it uses a tree. Just with the
  26. Christmas spirit(if it isn't near Christmas when you read
  27. this, than that's too bad!).
  28.  
  29.      Lets say we wanted to compress the following letters
  30. with huffman compression:
  31.  
  32. ABCBDCAAAAB
  33.  
  34. 1. Count how many times each character is used in the file:
  35.  
  36. A- 5 times.
  37. B- 3 times.
  38. C- 2 times.
  39. D- 1 time.
  40.  
  41.  
  42. 2. Start building trees...
  43. (*=not used)
  44.  
  45.      5        3        2        1
  46.     / \      / \      / \      / \
  47.    A   *    B   *    C   *    D   *
  48.  
  49. 3. Find the two lowest "nodes" on the top level and combine
  50. them:
  51. (1 and 2 are the 2 lowest)
  52.  
  53.      5        3           3
  54.     / \      / \         / \
  55.    A   *    B   *       C   D
  56.  
  57. 4. Repeat step 3 until only one node is at the top...
  58. (the two 3's are the lowest)
  59.  
  60.  
  61.      5             6
  62.     / \           / \
  63.    A   *         B   3
  64.                     / \
  65.                    C   D
  66.  
  67. (Now combine those two)
  68.  
  69.  
  70.            11
  71.           /  \
  72.          A    6
  73.              / \
  74.             B   3
  75.                / \
  76.               C   D
  77.  
  78.  
  79.  
  80. 5. To build the codes that represent these characters go down
  81. the tree- each time we go left use a "1" each time we go
  82. right use a "0" (or the other way 'round- doesn't make a
  83. difference as long as the decompressor does the same thing as
  84. the compressor).
  85.  
  86.  
  87. A is 1
  88. B is 01
  89. C is 001
  90. D is 000
  91.  
  92. 6. Now things start to get fuzzy. I'll explain what my
  93. compressor does.
  94.  
  95. 7. Send the tree. There are two ways to send it- in its very
  96. beginning stage(before it was combined) or when it is all
  97. combined. Sending it combined *should* take up less space-
  98. but who knows. If it sent uncombined, then the decompressor
  99. has to combine it.  My compressor sends it all combined with
  100. balls, lights, ooops- wrong subject!  (all right:cheap joke
  101. every text file has a cheap joke somewhere!)
  102.  
  103. 8. Start compressing the data. Here is what our sample text
  104. compresses to:
  105. ABCBDCAAAAB (in Ascii this would take up 88 bits)
  106. 10100101000001111101 (20 bits)
  107.  
  108. Well, looks like our compression ratio was (88-20)/88 or
  109. 68/88 or 34/44 or 17/22- which is about 17/20 or around
  110. 85%(sorry, don't have my calculator).
  111.  
  112. 9. That's it! If you understood this, than you also realize
  113. that this makes a really useful coding system for sending
  114. secret messages; pulses of light, beeps, scratches on wood...
  115. The only hard part is getting the tree over.  There is a type
  116. of compression called "Adaptive Huffman Compression" that
  117. doesn't have to send a tree- but I have only scratched the
  118. surface of that one. I think the decompressor assumes a
  119. predefined character distribution and updates the tree as it
  120. decompresses.
  121.  
  122.  
  123.  
  124.      There are two QuickBASIC 4.5 programs, in ascii format,
  125. that compress a VGA screen 13 (320x200x256) picture. If you
  126. only have EGA then change all the screen 13's in both of the
  127. programs to screen 7's and change the C=rnd*255 to C=rnd*15
  128. in the compressor to allow for the limited amount of colors,
  129. and hopefully everything else should take care of itself.
  130. The compressor doesn't send a palette or anything- I first
  131. made it to work with files but that was horrendously slow.
  132. Give the compressor time- 'specially on slow systems, because
  133. making/combining/& scanning the tree don't go all that quick!
  134. As the compressor sends out codes, a line will disappear from
  135. the screen from left to right(I know- the usually was is up
  136. to down but I wanted to be different!). Note that compiling
  137. it makes it much faster(or at least on my system), but still
  138. too slow on by 12 mhz '286 to use it in a game program to
  139. decompress a title screen or something.
  140.  
  141.      To see my brainchild in action, execute COMPRESS.BAS
  142. first.  After it churns out all of its data, execute
  143. DECOM.BAS. You *should* see the same screen you viewed
  144. before(remember- what can happen WILL happen; and it has!).
  145. I fully documented the programs so they shouldn't be that
  146. hard to follow. (Note: you may have to load QB with the /ah
  147. option?!, because it uses the '$dynamic metacommand.)
  148.      If you have any question, problems, or any other bad
  149. news then send them to me at...
  150.  
  151. Rich Geldreich
  152. 410 Market St.
  153. Gloucester City, New Jersey 08030
  154. (609)-456-0721
  155.  
  156.  
  157. You may use, modify, and change this program to your hearts
  158. desire. I don't care. It's my Christmas present to some poor
  159. fool out there that has been trying to compress things for
  160. months(and he's out there- I just know it...)