home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1993 #1 / NN_1993_1.iso / spool / comp / compress / 4348 < prev    next >
Encoding:
Text File  |  1993-01-05  |  1.5 KB  |  34 lines

  1. Newsgroups: comp.compression
  2. Path: sparky!uunet!world!rastek
  3. From: rastek@world.std.com (keith losset)
  4. Subject: Huffman Help
  5. Message-ID: <C0EK8n.M69@world.std.com>
  6. Organization: The World Public Access UNIX, Brookline, MA
  7. Date: Tue, 5 Jan 1993 22:38:47 GMT
  8. Lines: 24
  9.  
  10.     Help!  We are attempting to implement a Dynamic Huffman compression
  11. on byte-length source words by using the treatment in Storer's _Data Comp-
  12. ression:  Methods and Theory_ (pg. 42/43).  We have a misunderstanding about
  13. the trie algorithm that involves the following three parts:
  14.  
  15.     1.  Initialize the trie to contain one "unseen leaf".
  16.     2.  When an unknown source word x is received, send its character
  17.         code and the code of the unseen leaf and then create two children
  18.         for the unseen leaf -- a leaf for the character just received and
  19.         a new unseen leaf.
  20.     3.  All the while, increment the weight of each node as it is visited
  21.         and exchange it with its right sibling when and if its weight 
  22.         exceeds that of its right sibling.
  23.  
  24. A code is generated for a redundant character by traversing the tree.
  25.     We read this generalization to mean that if you receive 255 different
  26. characters, that the 255th you would generate a 255 bit code because it would
  27. be 255 levels down the tree thanks to step 2.  Obviously, something is missing
  28. here and we would be very appreciative if someone could clarify it for us.
  29.  
  30.         - poconnor@rastek.com
  31.  
  32. -- 
  33. Keith Losset, Rastek Corporation, 205-882-0882    jkl@hunan.rastek.com
  34.