On the Hardness of Finding Optimal Multiple Preset Dictionaries
Lists
Only you see this
Abstract
We show that the following simple compression problem is NP-hard: given a collection of documents, find the pair of Huffman dictionaries that minimizes the total compressed size of the collection, where the best dictionary from the pair is used to compress each document. We also show the NP-hardness of finding optimal multiple preset dictionaries for LZ'77-based compression schemes. Our reductions make use of the catalog segmentation problem, a natural partitioning problem. Our results justify heuristic attacks used in practice.
BibTeX
@inproceedings{mitzenmacher2001hardness,
author = {Michael Mitzenmacher},
title = {{On the Hardness of Finding Optimal Multiple Preset Dictionaries}},
booktitle = {Data Compression Conference},
year = {2001},
doi = {10.1109/dcc.2001.917172},
}Loading related content...