Skip to main content
eScholarship
Open Access Publications from the University of California

Length limited coding and optimal height-limited binary trees

  • Author(s): Larmore, Lawrence L.
  • et al.
Abstract

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

Main Content
Current View