Abstract

Nahla Ahmed Belal
On Updating Huffman Codes
Given a list W = [w1,…, wn] of n positive integer symbol weights, and a list L = [l1,…,ln] of n corresponding integer codeword lengths, it is required to find the new list L when a new value x is ed in when an existing value is d from the list of weights W. The presented algorithm uses the given information about the weights and their corresponding levels in order to perform the required . No other knowledge about the original Huffman tree is assumed to be known. Instead of rebuilding the Huffman tree, the new algorithm redistributes the weights among the levels to obtain the new Huffman code. In many special cases, the d Huffman code can be generated with lower complexity than reconstructing the Huffman tree from scratch by efficiently using the information of weights and their levels. In this paper, we present an updating algorithm that requires a linear complexity in many practical cases rather than the O(n log n) needed for reconstructing the Huffman tree. We also give a practical O(n log n) implementation for our algorithms.