Please use this identifier to cite or link to this item: https://doi.org/10.1080/0020716031000087140
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
Source: 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. https://doi.org/10.1080/0020716031000087140
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
URI: http://scholarbank.nus.edu.sg/handle/10635/39539
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.

SCOPUSTM   
Citations

1
checked on Dec 5, 2017

WEB OF SCIENCETM
Citations

1
checked on Dec 5, 2017

Page view(s)

42
checked on Dec 11, 2017

Google ScholarTM

Check

Altmetric


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