@inproceedings{2fd309457ca3401288f5892835af643a,
title = "Is text compression by prefixes and suffixes practical?",
abstract = "One approach to text compression is to replace high-frequency variable-length fragments of words by fixed-length codes pointing to a compression table containing these high-frequency fragments. It is shown that the problem of optimal fragment compression is NP-hard even if the fragments are restricted to prefixes and suffixes. This seems to be a simplest fragment compression problem which is NP-hard, since a polynomial algorithm for compressing by prefixes only (or suffixes only) has been found recently. Various compression heuristics based on using both prefixes and suffixes have been tested on large Hebrew and English texts. The best of these heuristics produce a net compression of some 37% for Hebrew and 45% for English using a prefix/suffix compression table of size 256.",
author = "Fraenkel, {A. S.} and M. Mor and Y. Perl",
note = "Publisher Copyright: {\textcopyright} 1983, Springer-Verlag.; 5th International ACM SIGIR Conference on Research and Development in Information Retrieval, SIGIR 1982 ; Conference date: 18-05-1982 Through 20-05-1982",
year = "1983",
doi = "10.1007/BFb0036353",
language = "English (US)",
isbn = "9783540119784",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "289--311",
editor = "Gerard Salton and Hans-Jochen Schneider",
booktitle = "Research and Development in Information Retrieval - Proceedings",
address = "Germany",
}