On the Hardness of Finding Optimal Multiple Preset Dictionaries

Michael Mitzenmacher

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.
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...

Figure