Title:

Die Ziv-Lempel-Kompression.

Description:  Der tabellengesteuerte Algorithmus codiert Symbolketten variabler Länge als Token, die einen Verweis in ein Phrasenverzeichnis darstellen.
Author:Marc-Alexander Jäger
deutsch
  
ISBN: 3423050012   ISBN: 3423050012   ISBN: 3423050012   ISBN: 3423050012 
 
|<< First     < Previous     Index     Next >     Last >>|
  Wir empfehlen:       
 
Proseminar Redundanz, Fehlertoleranz und Kompression

Die Ziv-Lempel-Kompression


1. Geschichte

Der Ursprung der modernen tabellengesteuerten Komprimierung kann auf Jacob Ziv und Abraham Lempel zurückgeführt werden. Diese beiden israelischen Forscher entwickelten in den späten 70er Jahren die ersten tabellengesteuerten Algorithmen. In ihrem 1977 veröffentlichten Arktikel "A Universal Algorithm for Sequential Data Compression" beschrieben sie ihren ersten Algorithmus. Hierbei handelte es sich um eine "gleitende Fenster"-Technik. Dieses Verfahren wird als LZ77 bezeichnet. 1978 veröffentlichten sie einen weiteren Algorithmus in dem Artikel "Compression of Individual Sequences via Variable-Rate Codeing" der als LZ78 bezeichnet wird.

Bis zum Jahre 1977 richtete sich das Hauptaugenmerk der Datenkomprimierungsforschung auf die neuen und verbesserten Methoden zur Steuerung von Huffman-Codierungsprogrammen. Die Veröffentlichung der beiden Artikel hatte einen direkten Einfluß auf das Gebiet der Informationstheorie.

Die Auswirkungen waren für Programmierer aber erst 1984 mit dem erscheinen des Artikels "A Technique for High-Performance Data Compression" von Terry Welch zu spüren. In dieser Veröffentlichung beschrieb er seine Implementation des LZ78-Algorithmus, den er LZW nannte. Kurz darauf erschien das Unix-Komprimierungsprogramm "compress" welches auf diesem Algorithmus basiert und zum Standard für Unix-Systeme wurde. Im MS-DOS-Bereich wurde "ARC" zum Standard, welches ebenfalls auf dem LZ78 Algorithmus beruht. Später allerdings gab "ARC" seine Vorrangstellung im PC-Bereich an Konkurrenten wie "PKZIP" und "ARJ" ab, welche "nur" auf dem LZ77-Algorithmus basieren.

2. Tabellengesteuerte Komprimierung

  • Statistische Methode: Vor der tabellengesteuerten Komprimierung wurden fast ausschließlich statistische Modelle verwendet. Bei diesem Modell wird die Komprimierung durch Kodieren der Symbole als Bitstrings erreicht, die weniger Bit als die Orginalsymbole beanspruchen. Damit hängt der Komprimierungsgrad davon ab, wie gut ein Programm ein Modell einrichten kann. Dieses Modell muß vorhersagen, mit welchen Wahrscheinlichkeiten die Symbole auftreten und die Wahrscheinlichkeiten der Symbole, die vom Mittelwert abweichen. Ein großer Nachteil dabei ist, dass diese Methoden nur von einer shannonschen Informationsquelle ausgehen und deshalb Redundanzen, die aus Mustern im Datenstrom entstehen, nicht erkennen und ausnutzen können.
  • Tabellengesteuerte Methode: Der tabellengesteuerte Algorithmus codiert Symbolketten variabler Länge als Token, die einen Verweis in ein Phrasenverzeichnis darstellen. Sind diese Token kleiner als die Phrasen, die sie ersetzen, kommt es zur Komprimierung. Damit kann dieser Algorithmus immer auf den Text reagieren und muß keine Wahrscheinlichkeiten vorhersagen.

3. LZ77

3.1. Der Algorithmus

Bei der LZ77-Komprimierungsmethode wird zuvor gelesener Text als Tabelle genutzt. Phrasen aus dem Eingabetext werden durch Zeiger in die Tabelle ersetzt. Hierfür arbeitet der Algorithmus mit einem Textfenster und einem nach vorn gerichteten Puffer. Im Textfenster befindet sich der zu letzt eingelesene Text, im Puffer befinden sich die aus dem Eingabestrom eingelesenen aber noch nicht codierten Zeichen. Das Textfenster ist im allgemeinen um ein vielfaches größer als der Puffer. Der Algorithmus versucht nun, zum Inhalt des nach vorn gerichteten Puffer einen möglichst langen, passenden String in der Tabelle zu finden. Übereinstimmender Text wird durch ein "Token" ersetzt. Jedes Token besteht aus drei verschiedenen Datenelementen. Bei diesen Elementen handelt es sich um:
  1. Einen Offset auf eine Phrase im Textfenster,
  2. die Phrasenlänge und
  3. um das erste Symbol im nach vorn gerichteten Puffer, das auf die Phrase folgt.
Der Komprimierungsgrad hängt dabei von der Länge der Übereinstimmung im Textfenster und im nach vorn gerichteten Puffer ab.

Der Dekomprimierungsalgorithmus ist noch simpler, da keine Vergleichsoperationen ausgeführt werden müssen. Ein Token wird eingelesen, die entsprechende Phrase und das darauffolgende Zeichen werden ausgegeben, das Textfenster wird weitergeschoben und der ganze Vorgang wird wiederholt.

 

  
Bürgerliches Gesetzbuch BGB: mit Allgemeinem Gleichbehandlungsgesetz, BeurkundungsG, BGB-Informationspflichten-Verordnung, Einführungsgesetz, ... Rechtsstand: 1. August 2012
Siehe auch:
Handelsgesetzbuch HGB: ohne Seehandelsrecht, mit …
Strafgesetzbuch StGB: mit Einführungsgesetz, …
Grundgesetz GG: Menschenrechtskonvention, …
Arbeitsgesetze
Basistexte Öffentliches Recht: Rechtsstand: 1. …
Aktiengesetz · GmbH-Gesetz: mit …
 
   
 
     
|<< First     < Previous     Index     Next >     Last >>| 

This web site is a part of the project StudyPaper.com.
We are grateful to Marc-Alexander Jäger for contributing this article.

Back to the topic site:
StudyPaper.com/Startseite/Computer/Informatik

External Links to this site are permitted without prior consent.
   
  deutsch  |  Set bookmark  |  Send a friend a link  |  Copyright ©  |  Impressum