DocumentCode :
3383932
Title :
Hybrid prefix codes for practical use
Author :
Liddell, Mike ; Moffat, Alistraia
Author_Institution :
Dept. of Comput. Sci. & Software Eng., Melbourne Univ., Vic., Australia
fYear :
2003
fDate :
25-27 March 2003
Firstpage :
392
Lastpage :
401
Abstract :
Prefix-free codes continue to enjoy widespread use in compression systems due to their simple structure and their ease of decoding. Minimum-redundancy prefix codes, such as Huffman codes, are widely used. However, approximate codes also receive considerable attention. Flat prefix codes have an extremely simple structure that facilitates fast decoding, but their compression effectiveness is often regarded as poor. The minimum-redundancy prefix code is much slower to decode than a flat code while the compressed file size is minimized. A hybrid prefix code is presented that exhibits the simple structure of a flat code and retains much of the compression effectiveness of a minimum-redundancy code. The structural constraints of the hybrid code should enable fast decoding and provide fast compressed string searching. Properties of the hybrid codes are discussed as well as the method for their efficient calculation. An algorithm for the efficient construction of minimum-redundancy K-flat codes is presented and tested empirically.
Keywords :
Huffman codes; data compression; decoding; dynamic programming; redundancy; string matching; Huffman code; approximate code; code compression; compressed file size; compressed string searching; compression effectiveness; fast decoding; flat prefix code; hybrid prefix code; minimum-redundancy K-flat code; minimum-redundancy prefix code; prefix-free code; Data compression;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Data Compression Conference, 2003. Proceedings. DCC 2003
ISSN :
1068-0314
Print_ISBN :
0-7695-1896-6
Type :
conf
DOI :
10.1109/DCC.2003.1194030
Filename :
1194030
Link To Document :
بازگشت