Datenkompression


Kriterien

Übersicht Formate

Grundlagen

Kompressionsverfahren

Shannon-Fano

Beispiel

Algorithmus

schrittw. Aufbau

SF versus Huffman

Huffman

Lempel-Ziv (LZ)

arithmetische Kodierung

Run Length Encoding

Burrows-Wheeler (BWT)

Implementationen

Datenformate


Glossar

Stichwortverzeichnis


Download


www.BinaryEssence.de

Shannon-Fano versus Huffman


Hinsichtlich der Effektivität des Datenkompression stellt sich die Frage, ob die mit der Shannon-Fano-Kodierung erreichte Kompressionsrate ggfls. mit anderen Verfahren übertreffen läßt. Entsprechend der Informationstheorie müsste sich eigentlich eine bessere Kodeeffizienz erreichen lassen.


Zum Vergleich wird deshalb das vorhergehende Beispiel nach dem Huffman-Algorithmus kodiert:


Huffman-Code


            Shannon-Fano    Huffman
 Z. Häufig. Kode Län. ges.  Kode Län. ges.
------------------------------------------
 A    24     00   2    48    0    1    24
 B    12     01   2    24    100  3    36
 C    10     10   2    20    101  3    30
 D     8     110  3    24    110  3    24
 E     8     111  3    24    111  3    24
------------------------------------------
ges. 186              140             138
    (3-Bit-Kode)

Die Shannon-Fano-Kodierung bietet nicht die optimale Kodeeffizienz für das beschriebene Beispiel. Dies ist nicht notwendigerweise in jedem Fall so, sondern variiert, je nach Inhalt der betrachteten Daten. Allerdings ergibt die Shannon-Fano-Kodierung bestenfalls ein gleichwertiges Ergebnis, die Effizienz der Huffman-Kodierung wird aber niemals übertroffen. Die optimale Kodierung (134,882 Bit) wird aber auch von der Huffman-Kodierung nicht erreicht.


 <   ^   > 

Shannon-Fano-Kodierung schrittweiser Aufbau eines Shannon-Fano-Kodes Huffman-Kodierung



Anzeigen:

Informations- und Kodierungstheorie