| An approximation algorithm for space-optimal encoding of a text | |
| Authors: | J. Katajainen and T. Raita |
| Published in: | The Computer Journal 32,3 (1989), 228-237 |
| Full text: |  PDF (991 kB) |
| DOI: | 10.1093/comjnl/32.3.228 |
| Copyright: | © British Computer Society |
| Abstract: | In many situations text compression is carried out with a previously formed fixed dictionary (code book) expressing those often-occurring substrings of a text which are to be replaced by code words. The problem of encoding a text in a space-optimal manner is equivalent to the problem of finding a shortest path between a given pair of vertices in an acyclic and bandwidth-limited network. By combining an algorithm for finding shortest paths with the string matching algorithm of Aho and Corasick, a time-efficient approximation algorithm for the space-optimal encoding is obtained. The performance of the approximation algorithm depends on the amount of storage space available in the fast memory of a computer. With an unrestricted, though at most linear working storage on the length of the input text, a space-optimal encoding is obtained. However, even a fixed internal memory of moderate size guarantees almost optimal compression, and in spite of this the running time of the algorithm is comparable to that of the longest match heuristic. |
| Related: |  HTML (Conference paper) |
| BibLATEX: | @article{KR1989J,
author = {J. Katajainen and T. Raita},
title = {An approximation algorithm for space-optimal encoding of a text},
journaltitle = {The Computer Journal},
volume = {32},
number = {3},
year = {1989},
pages = {228--237},
}
|