Please use this identifier to cite or link to this item:
Title: Optimal prefix codes and huffman codes
Authors: Long, D.
Jia, W.
Li, M. 
Keywords: Data transmission and compression
Huffman code
Maximal prefix code
Optimal prefix code
Issue Date: 2003
Citation: Long, D., Jia, W., Li, M. (2003). Optimal prefix codes and huffman codes. International Journal of Computer Mathematics 80 (6) : 727-742. ScholarBank@NUS Repository.
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.
Source Title: International Journal of Computer Mathematics
ISSN: 00207160
DOI: 10.1080/0020716031000087140
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.


checked on Oct 4, 2022


checked on Oct 4, 2022

Page view(s)

checked on Sep 22, 2022

Google ScholarTM



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.