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