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

Beispiel Shannon-Fano-Kodierung


Um einen Kodebaum nach Shannon und Fano zu definieren wird eine nach Häufigkeit geordnete Tabelle aller auftretenden Zeichen ausgewertet. Diese wird solange geteilt, bis jedem Zeichen ein Blatt des Baums zugeordnet ist. Die Teilung erfolgt immer so, dass die Summe der Häufigkeiten im oberen und unteren Teil möglichst gleich groß sind.


Zeichen  Häufig-  Kode-  Kode  Gesamt-
          keit    länge        länge
------------------------------------------
   A       24       2     00     48
   B       12       2     01     24
   C       10       2     10     20
   D        8       3     110    24
   E        8       3     111    24
------------------------------------------
   ges. 62 Zeichen  SF-kodiert: 140 Bit
        linear (3 Bit/Zeichen): 186 Bit


Beispiel Shannon-Fano-Kodebaum


Mit Hilfe des Shannon-Fano-Kodes lassen sich die zugrundegelegten Originaldaten mit 2,26 Bit kodieren. Für eine lineare Kodierung sind bei 5 Zeichen 3 Bit pro Zeichen erforderlich. Allerdings muß die Tabelle vorher bekannt oder aus den vorhergehenden Daten heraus entwickelt werden.


 <   ^   > 

Shannon-Fano-Kodierung Shannon-Fano-Kodierung Algorithmus Enkodierung



Anzeigen:

Informations- und Kodierungstheorie