## Abstract

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 language | English (US) |
---|---|

Pages (from-to) | 202-214 |

Number of pages | 13 |

Journal | Journal of the ACM (JACM) |

Volume | 22 |

Issue number | 2 |

DOIs | |

State | Published - Apr 1 1975 |

Externally published | Yes |

## All Science Journal Classification (ASJC) codes

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

## Keywords

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