Publisher： Taylor & Francis Ltd
ISSN： 0020-7160
Source： International Journal of Computer Mathematics, Vol.80, Iss.6, 2003-06, pp. : 727-742
Disclaimer: Any content in publications that violate the sovereignty, the constitution or regulations of the PRC is not accepted or approved by CNPIEC.
Abstract
Existence of the optimal prefix codes is shown in this paper. Relationship between the optimal prefix code and the Huffman code is also discussed. We prove that all Huffman codes are optimal prefix codes and conversely optimal prefix codes need not be Huffman codes. Especially, the problem of whether the optimal prefix code has to be maximal is presented. Although for information source alphabets of being not greater than four letters we show that an optimal prefix code must be maximal, it remains to be an open problem in general. As seen from Huffman codes, optimal prefix codes are used not only for statistical modeling but also for dictionary methods. Moreover, it is obtained that the complexity of breaking an optimal prefix code is NP-complete from the viewpoint of computational difficulty.
Related content
Access to resources
Recommend
Optimal Identifying Codes in Cycles and Paths
Graphs and Combinatorics, Vol. 28, Iss. 4, 2012-07 ,pp. :
On some classes of optimal and near-optimal polynomial codes
By Aydin N. Ray-Chaudhuri D.K.
Finite Fields and Their Applications, Vol. 10, Iss. 1, 2004-01 ,pp. :
Optimal cyclic quaternary constant‐weight codes of weight three
JOURNAL OF COMBINATORIAL DESIGNS, Vol. 26, Iss. 4, 2018-04 ,pp. :