| Autor: |
Bell, T C1 (AUTHOR), Witten, I H (AUTHOR) |
| Předmět: |
|
| Zdroj: |
Journal of the Association for Computing Machinery. Jul1994, Vol. 41 Issue 4, p708-724. 17p. |
| Abstrakt: |
Text compression methods can be divided into two classes: 'symbolwise' and 'parsing.' Symbolwise methods assign codes to individual symbols, while parsing methods assign codes to groups of consecutive symbols (phrase). The set of phrases available to a parsing method is referred to as a 'dictionary.' The vast majority of parsing methods in the literature use 'greedy' parsing. When greedy parsing is used, the coder processes a string from left to right, at each step encoding as many symbols as possible with a phrase from the dictionary. This parsing strategy is not optimal, but an optimal method cannot guarantee a bounded coding delay. An important problem in compression research has been to establish the relationship between symbolwise methods and parsing methods. This paper extends prior work that shows that there are symbolwise methods that simulate a subset of greedy parsing methods. The authors provide a more general algorithm that takes any 'nonadaptive' greedy parsing method and constructs a symbolwise method that achieves exactly the same compression. Combined with the existence of symbolwise equivalents for two of the most significant 'adaptive' parsing methods, this result gives added weight to the idea that research aimed at increasing compression should concentrate on symbolwise methods, while parsing methods should be chosen for speed for temporary storage considerations. [ABSTRACT FROM AUTHOR] |
| Databáze: |
Library, Information Science & Technology Abstracts |
| Externí odkaz: |
|
