×

Dynamic Huffman coding. (English) Zbl 0606.94007

This note shows how to maintain a prefix code that remains optimum as the weights change. A Huffman tree with nonnegative integer weights can be represented in such a way that any weight w at level l can be increased or decreased by unity in O(l) steps, preserving minimality of the weighted path length. One-pass algorithms for file compression can be based on such a representation.

MSC:

94A45 Prefix, length-variable, comma-free codes
68P05 Data structures
68R10 Graph theory (including graph drawing) in computer science
Full Text: DOI