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

Y. Perl, M. R. Garey, S. Even

Research output: Contribution to journalArticlepeer-review

34 Scopus citations


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).

Original languageEnglish (US)
Pages (from-to)202-214
Number of pages13
JournalJournal of the ACM (JACM)
Issue number2
StatePublished - Apr 1 1975
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Software
  • Control and Systems Engineering
  • Information Systems
  • Hardware and Architecture
  • Artificial Intelligence


  • equiprobable code words
  • minimum redundancy code
  • optimal code
  • prefix code
  • tree


Dive into the research topics of 'Efficient Generation of Optimal Prefix Code: Equiprobable Words Using Unequal Cost Letters'. Together they form a unique fingerprint.

Cite this