ISSN:
1436-5057
Keywords:
94A15
;
Optimal and heuristic encoding
;
shortest paths
;
textual substitution
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
Description / Table of Contents:
Zusammenfassung Es werden Text-Komprimierungsprobleme behandelt, bei denen Teilworte durch Codeworte ersetzt werden, sodaß der ursprüngliche Text durch eine kürzere Codesequenz repräsentiert wird. Das geschieht mit Hilfe eines statischen Wörterbuchs. Wir führen eine neue effiziente on-line Heuristik ein, welche die lokale Komprimierungsrate maximiert. Von diesem fractional greedy Verfahren wird das Verhalten im schlechtesten Fall für verschiedene Typen von Wörterbüchern untersucht.
Notes:
Abstract Text-compression problems are considered where substrings are substitued by code-words according to a static dictionary such that the original text is encoded by a shorter code sequence. We introduce a new efficient on-line heuristic which locally maximizes the compaction ratio. The worst-case behaviour of this fractional greedy heuristic is investigated for several types of dictionaries.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF02238290
