JUCS - Journal of Universal Computer Science 3(11): 1167-1179, doi: 10.3217/jucs-003-11-1167
Optimum Extendible Prefix Codes
expand article infoCristian S. Calude‡, Ioan Tomescu§
‡ Computer Science Department, The University of Auckland, Auckland, New Zealand§ Bucharest University, Bucharest, Romania

Corresponding author: Cristian Calude

© Cristian Calude, Ioan Tomescu.
This article is freely available under the J.UCS Open Content License.
Citation: Calude CS, Tomescu I (1997) Optimum Extendible Prefix Codes. JUCS - Journal of Universal Computer Science 3(11): 1167-1179. https://doi.org/10.3217/jucs-003-11-1167
Open Access
Abstract
Suppose that we have L messages coded by a prefix code (over an alphab et M with m letters) having a minimum weighted length. The problem addressed in this paper is the following: How to find s codewords for new messages so that by leaving unchanged the codification of the first L messages (by compatibility rea sons), the resulting extended code is still prefix (over M) and has a minimum weighted length? To this aim we introduce the notion of optimum extendible prefix code and then, by modifying Huffman s algorithm, we give an effcient algorithm to construct the opti mum extension of a non-complete prefix code, provided the initial code is optimal. 1.) Proceedings of the First Japan-New Zealand Workshop on Logic in Computer Science, special issue editors D.S. Bridges, C.S. Calude, M.J. Dinneen and B. Khoussainov.
Keywords
Kraft's inequality, Huffman tree, optimum extendible prefix code