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 |