Efficient Generation of Optimal Prefix Code: Equiprobable Words Using Unequal Cost Letters

An algorithm for constructing an optimal prefix code of n eqmprobable words over r unequal cost coding letters is given. The discussion is in terms of rooted labeled trees. The algorithm consists of two parts. The first one is an extension algorithm which constructs a prefix code of n words. This code is either optimal or is a “good” approximation The second part is a mending algorithm which changes the code constructed by the extension algorithm into an optimal code in case it is not already optimal. The validity of the combined algorithm is proved and its structure is analyzed. The analysis leads to further improvement of the algorithm's efficiency. It is shown that the number of steps required is at mnst O(r.n.log n), if a heap data structure is used Alternatively, one can use a data structure of r queues, in which case the number of steps is bounded by O(r.n).