DocumentCode
890346
Title
Verification of minimum-redundancy prefix codes
Author
Belal, Ahmed ; Elmasry, Amr
Author_Institution
Dept. of Comput. Eng. & Syst., Alexandria Univ., Egypt
Volume
52
Issue
4
fYear
2006
fDate
4/1/2006 12:00:00 AM
Firstpage
1399
Lastpage
1404
Abstract
We show that verifying a given prefix code for optimality requires Ω(nlogn) time, indicating that the verification problem is not asymptotically easier than the construction problem. Alternatively, we give linear-time verification algorithms for several special cases that are either typical in practice or theoretically interesting.
Keywords
Huffman codes; decision trees; linear codes; redundancy; linear-time verification algorithm; minimum-redundancy prefix code; Binary trees; Codes; Data compression; Helium; NP-hard problem; Polynomials; Systems engineering and theory; Tree graphs; Asymptotic complexity; Huffman codes; lower bounds; optimal codes; verification algorithms;
fLanguage
English
Journal_Title
Information Theory, IEEE Transactions on
Publisher
ieee
ISSN
0018-9448
Type
jour
DOI
10.1109/TIT.2006.871578
Filename
1614073
Link To Document