The fractional greedy algorithm for data compression

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