Datenkompression: Verlustfreie Verfahren: Wörterbuchbasierte Verfahren: LZRW

zurück

5.2 Wörterbuchbasierte Verfahren

5.2.1 LZ77 - Lempel, Ziv (1977)

5.2.2 LZ78 - Lempel, Ziv (1978)

5.2.3 LZSS - Storer, Szymanski (1982)

5.2.4 LZW - Welch (1984)

5.2.5 LZPP - Pylak (2003)

5.2.6 LZFG - Fiala, Green

5.2.7 LZRW - Williams (1989-1991)

5.2.8 LZV - Vogt (1994)

5.2.9 LZMW - Miller, Wegman (1985)

5.2.10 LZC - ?

5.2.11 LZT - Tischer (1987)

5.2.12 LZJ - Jakobsson

5.2.13 LZR - Rodeh, Pratt, Even

5.2.14 LZB - Bell

5.2.15 LZH - Herd

5.2.16 LZO - Oberhumer

5.2.17 LZP/LZCB - Bloom (1996)

5.2.18 LZAP - Storer (1988)

5.2.19 LZY - Yabba

5.2.20

LZRW - Williams 1989-1991

LZRW1

Ross N. Williams stellte im Jahr 1991 seine Arbeit "An Extremely Fast Data Compression Algorithm" auf der Data Compression Conference un Utah (7-11 April 1991). Der erste von ihm programmierte Algorithmus funktionierte nicht deterministisch. Das bedeutet, dass sein Packalgorithmus verschiedene gepackte Repräsentationen erzeugen konnte, die sich jedoch in das gleiche Resultat entpacken ließen.

LZRW2

Diese Variante ist eine Erweiterung des Algorithmus LZRW1-A, hat aber die Eigenschaft eine bessere Kompression zu erreichen und deterministisch zu sein. Dafür ist er langsamer und verbraucht etwas mehr Speicher zur Laufzeit.

• (Übertragung der Länge und eines Phrasentabellen-Index, statt Länge und Offset)
• (Durch den Schritt über die Phrasetable und dessen Index ist es möglich eine größere Historie zu adressieren, einmal eingetragene Werte werden nicht in die Phrasetable aufgenommen statt 4096 Bytes 4096 Phrasen)

LZRW3

Eine Phrase wird nur vergessen, wenn sie einen gleichen Hash hat wie bereits eine existierende Phrase.

LZRW4

• Hashtable mit Partitionen zu je 32 Pointern -> 1 Megabyte adressierbar
• LZRW4 hasht die beiden zuletzt gesehenen Zeichen und ermittelt eine Partition von 0..4095
• die 32 Pointer werden nun verwendet um die größtmögliche Übereinstimmung zu finden. Es wird
• die Trefferlänge wird in 3 Bit codiert (2,3,4,5,6,7,8,16) und die Pointer Number 5 Bit 0..31 codiert und übertragen.
• einzelnes Controlbit für ein normales Zeichen oder für ein codiertes Zeichen.
• Nun sind Tabellenindexe und Zeichen gleich lang (8bit)
• Rotation des gewinnenden Pointers
• Alles in Allem eine Kontext-Modellierung

LZRW5

Als Ross Williams diese Variante seiner Variation seiner Lempel und Ziv-Algorithmen vorstellte, erhielt er eine E-Mail von Daniel Bernstein, der diese Variante bereits ein Jahr zuvor in sein LZY (Yabbawhap-Kompressions Paket) implementiert hatte. Ross Williams beschrieb das in etwa so, dass er sich mit seiner Idee und seiner LZRW4 und LZRW5 Variante beschäftigte und ansonsten schwer mit anderen Dingen beschäftigt war und es deswegen versäumte den Quellcode von Daniel Bernstein zu lesen.