home *** CD-ROM | disk | FTP | other *** search
/ SuperHack / SuperHack CD.bin / CODING / MISC / HUFFMAN.ZIP / HUFFMAN.TXT
Encoding:
Text File  |  1996-03-16  |  5.0 KB  |  168 lines

  1. Subject: Huffman Encoding / Decoding, example
  2. Date: 10 Aug 1994 10:12:26 -0700
  3. References: <31okc9$1n4@kodak.rdcs.Kodak.COM> <31r4po$oin@watnews2.watson.ibm.com>
  4.  
  5. :In article <31r4po$oin@watnews2.watson.ibm.com> bkr@watson.ibm.com (Barry Rosen) writes:
  6. ::In article <31okc9$1n4@kodak.rdcs.Kodak.COM>,
  7. ::axman@axbrau.Kodak.COM (Mike Axman) writes:
  8. ::|> Can someone provide me with some pointers to research papers, books, 
  9. ::|> patents, and other publications that teach algorithms for doing 
  10. ::|> "the fastest" 
  11. ::|> .- Huffman decoding 
  12. ::|> .- linear/bilinear interpolation
  13. ::
  14. ::For Huffman coding, one good reference is
  15. ::        D.S. Hirshberg and D.A. Lelewer
  16. ::        Efficient Decoding of Prefix Codes
  17. ::        Comm. ACM 33(4) April 1990
  18. ::        449-459
  19. ::=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
  20. ::Barry Rosen at IBM Research (Yorktown) will receive e-mail addressed to
  21. ::               bkr@watson.ibm.com on Internet
  22. ::               PHONE : 914-945-2144    FAX : 914-945-2141
  23. ::=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
  24.  
  25.  
  26.     Here is a quick tutorial on generating a huffman tree from a value/frequency
  27.     set.
  28.  
  29.     Lets say you have a set of numbers and their frequency of use and
  30.     want to create a huffman encoding for them:
  31.  
  32. .frequency.value
  33.     .5..1
  34.     .7..2
  35.     .10..3
  36.     .15..4
  37.     .20..5
  38.     .45..6
  39.  
  40.     Creating a huffman tree is simple.  Sort this list by frequency and
  41.     make the two-lowest elements into leaves, creating a parent node
  42.     with a frequency that is the sum of the two lower element's frequencies:
  43.  
  44.     .12:*
  45.     ./  \
  46.       5:1   7:2
  47.  
  48.     The two elements are removed from the list and the new parent node,
  49.     with frequency 12, is inserted into the list by frequency.  So now the 
  50.     list, sorted by frequency, is:
  51.  
  52.         10:3
  53.         12:*
  54.         15:4
  55.         20:5
  56.         45:6
  57.  
  58.     You then repeat the loop, combining the two lowest elements.  This
  59.     results in:
  60.  
  61.     .22:*
  62.     ./   \
  63.      10:3   12:*
  64.      .    /   \
  65. .  5:1   7:2
  66.  
  67.     list now:
  68.  
  69. .15:4
  70. .20:5
  71. .22:*
  72. .45:6
  73.  
  74.  
  75.     You repeat until there is only one element left in the list.  
  76.  
  77.     .35:*
  78.     ./   \
  79.       15:4  20:5
  80.  
  81.       .22:*
  82.       .35:*
  83.       .45:6
  84.  
  85.  
  86.  
  87.  
  88.       .    57:*
  89.       .___/    \___
  90.        /            \
  91.      22:*          35:*
  92.     /   \          /   \
  93.  10:3   12:*     15:4   20:5
  94.         /   \
  95.       5:1   7:2
  96.  
  97.  
  98. .45:6
  99. .57:*
  100.  
  101.  
  102.                                    112:*
  103.                 __________________/    \__
  104.                /                          \
  105.       .    57:*                         45:6
  106.       .___/    \___
  107.        /            \
  108.      22:*          35:*
  109.     /   \          /   \
  110.  10:3   12:*     15:4   20:5
  111.         /   \
  112.       5:1   7:2
  113.  
  114.  
  115. .list: one element containing 112:*, you are done.
  116.  
  117.  
  118.     This element becomes the root of your binary huffman tree.  To generate
  119.     a huffman code you traverse the tree to the value you want, outputing
  120.     a '0' every time you take a lefthand branch, and a '1' every time you
  121.     take a righthand branch.  (normally you traverse the tree backwards
  122.     from the code you want and build the binary huffman encoding string
  123.     backwards as well, since the 'first' bit must start from the top).
  124.  
  125.     Example:  The encoding for the value 4 (15:4) is:  '010'.  The encoding
  126.     for the value 6 (45:6) is '1'
  127.  
  128.     Decoding a huffman encoding is just as easy... as you read bits in
  129.     from your input stream you traverse the tree beginning at the root,
  130.     taking the left hand path if you read a '0' and the right hand path
  131.     if you read a '1'.  When you hit a leaf, you have found the code.
  132.  
  133.     Generally, any huffman compression scheme also requires the huffman
  134.     tree to be written out as part of the file, otherwise the reader cannot
  135.     decode the data!  For a static tree, you don't have to do this since
  136.     the tree is known and fixed.
  137.  
  138.     The easiest way to output the huffman tree itself is to, starting at
  139.     the root, dump first the left hand side then the right hand side.
  140.     For each node you output a 0, for each leaf you output a 1 followed
  141.     by N bits representing the value.  For example, the partial tree in
  142.     my last example above using 4 bits per value can be represented as
  143.     follows:
  144.  
  145. .000100.fixed 6 bit byte indicates how many bits the 'value'
  146. .. for each leaf is stored in.  In this case, 4.
  147. .0.root is a node
  148. ..left hand side is
  149. .10011.a leaf with value 3
  150. ..right hand side is
  151. .0.another node
  152. ..recurse down, left hand side is
  153. .10001.a leaf with value 1
  154. ..right hand side is
  155. .10010.a leaf with value 2
  156. ..recursion return
  157.  
  158.     So the partial tree can be represented with 00010001001101000110010, or 23
  159.     bits.  Not bad!
  160.  
  161. ......-Matt
  162.  
  163.     Matthew Dillon..dillon@apollo.west.oic.com
  164.     1005 Apollo Way..ham: KC6LVW (no mail drop)
  165.     Incline Village, NV. 89451.Obvious Implementations Corporation
  166.     USA ...Sandel-Avery Engineering
  167.     [always include a portion of the original email in any response!]
  168.