Ein lokal adaptives Datakompressionsschema

Ein Datakompressionsschema, das die Lokalität der Referenz ausnutzt, wie sie auftritt, wenn Wörter häufig über kurze Zeiträume hinweg verwendet werden und dann in lange Nutzungszeiten fallen, wird beschrieben. Das Schema basiert auf einer einfachen Heuristik für selbstorganisierende sequenzielle Suche und auf variablen Längen-Codierungen von Ganzzahlen. Wir beweisen, dass es nie viel schlechter abschneidet als Huffman-Codierung und erheblich besser abschneiden kann; Experimente mit echten Dateien zeigen, dass seine Leistung normalerweise ziemlich nah an der von Huffman-Codierung liegt. Unser Schema hat viele Implementierungsvorteile: es ist einfach, ermöglicht schnelles Codieren und Decodieren und erfordert nur einen Durchgang über die zu komprimierenden Daten (statische Huffman-Codierung benötigt zwei Durchgänge).