Datenkompression


Kriterien

Übersicht Formate

Grundlagen

Kompressionsverfahren

Datenformate


arithmetische Kodierung (AC)

Prinzip der AC

Aufteilung in Intervalle

Zuordnung Kodes

nachfolgende Intervalle

Kodetabelle für 2 Zeichen

Schema Intervalle "aaaa"

Schema Intervalle "abcd"

allgemeiner Algorithmus

AC versus Huffman

Daten hoher Redundanz

adaptive AC

Implementationen


Glossar

Stichwortverzeichnis


Download


www.BinaryEssence.de

Aufteilung in Intervalle


Ausgehend von einem bekannten Alphabet werden die Auftrittswahrscheinlichkeit aller Zeichen ermittelt und in Intervalle umgesetzt. Die Intervallgröße ist linear abhängig von der Wahrscheinlichkeit für das Auftreten eines Zeichens. Liegt diese beispielsweise bei 50%, so umfaßt das zugehörige Teilintervall die Hälfte des aktuellen Intervalls. Für das erste Zeichen wird das Gesamtintervall in den Grenzen von [0; 1) zugrunde gelegt:


Beispiel Intervallteilung [0,0; 1,0)


      Häufigkeit
Zeichen       Wahrscheinlichkeit Teilintervall
    a     4       0,4            [0,0; 0,4)
    b     2       0,2            [0,4; 0,6)
    c     2       0,2            [0,6; 0,8)
    d     1       0,1            [0,8; 0,9)
    e     1       0,1            [0,9; 1,0)
Summe    10       1,0            [0,0; 1,0)

Beispiel Intervallteilung [0,9; 1,0)


      Häufigkeit
Zeichen       Wahrscheinlichkeit Teilintervall
    a     4       0,4            [0,90; 0,94)
    b     2       0,2            [0,94; 0,96)
    c     2       0,2            [0,96; 0,98)
    d     1       0,1            [0,98; 0,99)
    e     1       0,1            [0,99; 1,00)

Beispiel Intervallteilung [0,99; 1,00)


      Häufigkeit
Zeichen       Wahrscheinlichkeit Teilintervall
    a     4       0,4            [0,990; 0,994)
    b     2       0,2            [0,994; 0,996)
    c     2       0,2            [0,996; 0,998)
    d     1       0,1            [0,998; 0,999)
    e     1       0,1            [0,999; 1,000)

Ein Zahl im Bereich von 0,999 bis < 1,000 repräsentiert denmach die Zeichenkette "eee".


 <   ^   > 

oben zurück weiter



Anzeigen:

Informations- und Kodierungstheorie