Donald Bren School of Information and Computer Sciences
Length limited coding and optimal height-limited binary trees
- Author(s): Larmore, Lawrence L.
- et al.
A new O(nL)-time algorithm is given for finding an optimal prefix-free binary code for a weighted alphabet of size n, with the restriction that no code string be longer than L. An O(nL logn)-time algorithm is given for the corresponding alphabetic problem problem, which is equivalent to optimizing a dictionary of n words, implemented as a binary tree of height h