Title :
On the hardness of finding optimal multiple preset dictionaries
Author :
Mitzenmacher, Michael
Author_Institution :
Div. of Eng. & Appl. Sci., Harvard Univ., Cambridge, MA, USA
Abstract :
Preset dictionaries for Huffman codes are used effectively in fax transmission and JPEG encoding. A natural extension is to allow multiple preset dictionaries instead of just one. We show, however, that finding optimal multiple preset dictionaries for Huffman and LZ77-based compression schemes is NP-hard
Keywords :
Huffman codes; computational complexity; data compression; facsimile; optimisation; Huffman codes; Huffman-based compression; JPEG encoding; LZ77-based compression; NP-hard problem; catalog segmentation; fax transmission; optimal multiple preset dictionaries; Code standards; Computational efficiency; Costs; Decoding; Dictionaries; Encoding; Engineering profession; Huffman coding; Marketing and sales; Transform coding;
Conference_Titel :
Data Compression Conference, 2001. Proceedings. DCC 2001.
Conference_Location :
Snowbird, UT
Print_ISBN :
0-7695-1031-0
DOI :
10.1109/DCC.2001.917172
