Data Compression
Criteria
Survey Formats
Basics
Compression Methods
Data Formats
Huffman Code
Example
Characteristics
Variants
Dynamic Huffman Code
Adaptive Huffman Code
Initialization
Algorithm
Table Code Tree
Update Procedure
New Symbols
Update Code Tree
Decoding
Example
Glossary
Index
Download

Algorithm Adaptive Huffman Code
A number of rules and conventions is required for the algorithm described hereinafter. It bases on a procedure starting with an empty tree and introducing a special control character. No preventive assumptions about the code distribution will be made.
 Control character for symbols that are not part of the tree
 A control character is defined in addition to the original set of symbols. This control character identifies symbols that, at runtime, do not belong to the current code tree. In the literature this control character is denoted as a NYA or NYT (Not Yet Available or Transmitted).
 Weight of a node.
 Any node has an attribute called the weight of the node. The weight of a leaf node is equal to the frequency with which the corresponding symbol had been coded so far. The weight of the interior nodes is equal to the sum of the two subordinated nodes. The control character NYA gets the weight 0.
 Structure of the Code Table
 All nodes are sorted according to their weight in ascending order. The NYA node always provides the lowest node in the hierarchy.
 Sibling Property
 Any pair of nodes that are neighbours in the hierarchy refer to the same parent node (node 2^{n1} and 2^{n} > 1 & 2, 3 & 4, 5 & 6, etc.). The parent node is always ordered at a higher level in the hierarchy because its weight results from the sum of the subordinated nodes. This is denoted as sibling property.
 Root
 The node with the highest weight is placed at the highest level in the hierarchy and forms the current root of the tree.
 Intitial Tree
 The initial tree only contains the NYA node with the weight 0.
 Data format for uncoded symbols
 In the simplest case symbols which are not contained in the code tree are encoded linearly (e.g. with 8 bit from a set of 256 symbols). A better compression efficiency could be achieved, if the data format will be adapted to the number of remaining symbols. A variety of options are available to optimize the code length. A suitable procedure will be presented guaranteeing full utilization of the range of values.
 Maximum number of nodes
 Assuming a set of n symbols the total number of nodes results in 2n1 (leaf and interior nodes). Accordingly the maximum number of nodes is 511 if the standard unit is the byte.
 Block
 All nodes of identical weight will be summarized logically to a block. Nodes which are part of a block are always neighbouring in the code table representing the code tree.
< ^ >

