Variations on a Theme by Huffman.

摘要

In honor of the twenty-fifth anniversary of Huffman Coding,four new results about Huffman codes are presented. The first result shows that a binary prefix condition code is a Huffman code if the intermediate and terminal nodes in the code tree can be listed by non-increasing probability so that each node in the list is adjacent to its sibling. The second result upper bounds the redundancy (expected length minus entropy) of a binary Huffman code by (P sub 1) + (log to the base 2)(2 (log to the base 2) e)/e) = (P sub 1) + .086where (P sub 1) is the probability of the most likely source letter. The third results shows that one can always leave a code word of length 2unused and still have a redundancy of at most one. The fourth result is a simple algorithm for adapting a Huffman code to slowly varying estimates of the source probabilities. In essence,one maintains a running count of uses of each node in the code tree and lists the nodes in order of these counts. Whenever the occurrence of a message increases a node count about the count of the next node in the list,the nodes,with their attached subtrees,are interchanged.