Datenkompression


Kriterien

Übersicht Formate

Grundlagen

Kompressionsverfahren

Shannon-Fano

Huffman

Lempel-Ziv (LZ)

arithmetische Kodierung

Run Length Encoding

Burrows-Wheeler (BWT)

Enkodierung

transformierte Daten

Dekodierung

Eigenschaften

Anwendungen

Implementationen

Datenformate


Glossar

Stichwortverzeichnis


Download


www.BinaryEssence.de

Eigenschaften der BWT


Kompression

Die erreichbare Kompressionsleistung ist maßgeblich von der Größe der Matrix abhängig. Eine ausreichende Dimensionierung vorausgesetzt, kann eine Kompressionsrate erreicht werden, die deutlich besser ist als bei herkömmlichen Verfahren, wie z.B. Deflate für ZIP oder GZIP. Mit komplexeren Verfahren (PPM, LZMA) lassen sich etwas bessere Ergebnisse erzielen.


Geschwindigkeit Enkoder

Die Verarbeitungsgeschwindigkeit des Enkoders wird von dem Sortieralgorithmus dominiert. Mit zunehmender Blockgröße steigt dieser exponentiell an.


Geschwindigkeit Dekoder

Die Sortierprozedur muss bei der Dekodierung nur auf den einfachen String und nicht auf die zweidimensionale Matrix angewendet werden. Deshalb erfolgt die Dekodierung deutlich schneller als die Enkodierung.


Arbeitsspeicher

Der erforderliche Arbeitsspeicher für die Enkodierung wird maßgeblich von der Blockgröße bestimmt. Der Speicherbedarf von BZIP2 wird mit der 8-fachen Blockgröße angegeben. Es gibt verschiedene Modelle die Matrix zu speichern, eine Variante stellt jede Zeile mit einem Zeiger auf die Originaldaten dar; d.h. jede Zeile der Matrix erfordert einen Zeiger. Dazu kommt Speicher für den Sortieralgorithmus.


 <   ^   > 

Burrows-Wheeler-Transformation (BWT) BWT: Dekodierung BWT: Anwendungen



Anzeigen:

Informations- und Kodierungstheorie