Lempel Ziv Ross Williams

Lempel Ziv Ross Williams

Reduced Offset Lempel Ziv, (ROLZ) ist ein Datenkompressionsalgorithmus, der von Ross Williams entwickelt wurde. Es handelt sich um ein Wörterbuchverfahren, das auf LZ77 aufbaut, jedoch im Unterschied zu diesem kontextbezogene Methoden nutzt.

Das Konzept wurde erstmals von Malcolm Taylor in dessen Datenkompressionsprogramm RK (beziehungsweise WinRK) umgesetzt. Mit dem QUAD-Kompressor von Ilia Muraviev existiert eine freie Implementation (unter LGPL).

Inhaltsverzeichnis

Versionen des Algorithmus'

Der Versuch, die möglichen Werte der Offsets zu reduzieren, wurde von vielen Autoren unternommen. Bemerkenswert sind hier:

LZFG-C2 (Edward R. Fiala, Daniel H. Greene, 1989)

Übereinstimmungen werden nicht als Paare aus Länge und Offset gespeichert, sondern durch eine spezielle Marke, die zu einer bestimmten Zeile im Wörterbuch gehören.

LZRW4 (Ross Williams, 1991)

Der LZRW4-Algorithmus von Ross Williams entspricht dem ROLZ. Obwohl der Autor keine brauchbare Implementation vornahm, verwirklicht sein Beispielkompressor in groben Zügen den ROLZ-Algorithmus.

LZP1–LZP4 (Charles Bloom, 1995)

LZP ist ein Wörterbuchkompressor, dessen Codierung der Übereinstimmungen vollständig ohne Offsets arbeitet. Dazu wird die Länge der Übereinstimmung mit der auf das letzte Auftreten des vorausgehenden Kontexts folgenden Zeichenkette in einer Liste gespeichert.

LZ77-PM (Dzung T. Hoang, Philip M. Long, Jeffrey Scott Vitter, 1995)

Dieser Algorithmus unterscheidet sich von ROLZ nur dadurch, dass der einer Übereinstimmung vorausgehende Kontext von variabler Länge sein darf, anstatt eines Kontextes festgelegten Grades.

ROLZ (Malcolm Taylor, 1999)

ROLZ2–ROLZ3 (Malcolm Taylor, 2005)

Diese Algorithmen sind Weiterentwicklungen des ursprünglichen ROLZ:

  • ROLZ2 soll maximale Entpackgeschwindigkeiten sicherstellen
  • ROLZ3 zielt auf maximale Packraten mit vernachlässigbaren Geschwindigkeitsverlusten beim Entpacken

Weblinks


Wikimedia Foundation.

Игры ⚽ Поможем написать курсовую

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Ross Williams — infobox person name=Ross Williams birth place = Melbourne, Victoria, Australia nationality = AustralianRoss Neil Williams is an Australian computer scientist and entrepreneur who has made significant contributions to data compression and… …   Wikipedia

  • Reduced Offset Lempel Ziv — Reduced Offset Lempel Ziv, (ROLZ) ist ein Datenkompressionsalgorithmus, der von Ross Williams entwickelt wurde. Es handelt sich um ein Wörterbuchverfahren, das auf LZ77 aufbaut, jedoch im Unterschied zu diesem kontextbezogene Methoden nutzt. Das… …   Deutsch Wikipedia

  • LZRW — Lempel Ziv Ross Williams, (LZRW) refers to variants of the LZ77 lossless data compression algorithms with an emphasis on improving compression speed through the use of hash tables and other techniques. This family was explored by Ross Williams,… …   Wikipedia

  • LZ 77 — LZ77 ist ein Verfahren zur Datenkompression, das 1977 von Abraham Lempel und Jacob Ziv veröffentlicht wurde. Die Autoren machten sich erstmals zu Nutze, dass ganze Wörter, oder zumindest Teile davon, in einem Text mehrfach vorkommen. Im Gegensatz …   Deutsch Wikipedia

  • LZ77 — ist ein Verfahren zur Datenkompression, das 1977 von Abraham Lempel und Jacob Ziv veröffentlicht wurde. Die Autoren machten sich erstmals zunutze, dass ganze Wörter, oder zumindest Teile davon, in einem Text mehrfach vorkommen. Im Gegensatz dazu… …   Deutsch Wikipedia

  • Dateiarchivierung — Datenkompression oder Datenkomprimierung ist die Anwendung von Verfahren zur Reduktion des Speicherbedarfs von Daten bzw. zur Vermeidung von Datenaufkommen, bspw. während der Übertragung von Daten. Die Datenmenge wird reduziert, indem eine… …   Deutsch Wikipedia

  • Dateikompression — Datenkompression oder Datenkomprimierung ist die Anwendung von Verfahren zur Reduktion des Speicherbedarfs von Daten bzw. zur Vermeidung von Datenaufkommen, bspw. während der Übertragung von Daten. Die Datenmenge wird reduziert, indem eine… …   Deutsch Wikipedia

  • Datenkomprimierung — Datenkompression oder Datenkomprimierung ist die Anwendung von Verfahren zur Reduktion des Speicherbedarfs von Daten bzw. zur Vermeidung von Datenaufkommen, bspw. während der Übertragung von Daten. Die Datenmenge wird reduziert, indem eine… …   Deutsch Wikipedia

  • Datenreduktion — Datenkompression oder Datenkomprimierung ist die Anwendung von Verfahren zur Reduktion des Speicherbedarfs von Daten bzw. zur Vermeidung von Datenaufkommen, bspw. während der Übertragung von Daten. Die Datenmenge wird reduziert, indem eine… …   Deutsch Wikipedia

  • Datenreduktionsverfahren — Datenkompression oder Datenkomprimierung ist die Anwendung von Verfahren zur Reduktion des Speicherbedarfs von Daten bzw. zur Vermeidung von Datenaufkommen, bspw. während der Übertragung von Daten. Die Datenmenge wird reduziert, indem eine… …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”