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

Prinzip der arithmetischen Kodierung


Die gesamte zu kodierende Datenmenge wird durch eine rationale Zahl dargestellt, die in einem Bereich von 0 bis 1 liegt. Dieser Bereich wird in Teilintervalle gegliedert, die ihrerseits einzelne Zeichen repräsentieren. Die Anzahl der Teilintervalle ist identisch mit der Anzahl der Zeichen im aktuellen Zeichenvorrat und die Größe ist proportional zur deren Auftrittswahrscheinlichkeit. Für jedes Zeichen in den Ausgangsdaten erfolgt eine neue Intervallteilung, ausgehend von dem letzten Teilintervall.


Beispiel Teilintervalle


  Wahrscheinlichkeit Startintervall
a  0,5   (50%)       [0,0; 0,5)
b  0,3   (30%)       [0,5; 0,8)
c  0,2   (20%)       [0,8; 1,0)
           Intervallgröße: 1,0

  Start      'b'              'a'
a [0,0; 0,5)     [0,50; 0,65) --> [0,500; 0,575)
b [0,5; 0,8) --> [0,65; 0,74)     [0,575; 0,620)
c [0,8; 1,0)     [0,74; 0,80)     [0,620; 0,650)
       Intervallgröße:  0,30              0,150

Ausgehend von der initialen Intervallteilung wird das Zeichen 'b' mit einer Zahl kodiert, die größer oder gleich 0,5 und kleiner als 0,8 ist. Würde das Zeichen 'b' für sich allein stehen, könnte eine beliebige Zahl aus diesem Intervall ausgewählt werden.


Für das folgende Zeichen geht man von dem aktuellen Intervall [0,5; 0,8) aus und gliedert dieses wieder in Teilintervalle. Ist das zweite Zeichen ein 'a', so wird eine beliebige Zahl aus dem Intervall [0,50; 0,65) kodiert. Mit jedem weiteren Zeichen wird das zuletzt aktuelle Intervall weiter geteilt, die Anzahl von signifikanten Nachkommanstellen der zu kodierenden Zahl wächst immer weiter an.


Auch wenn die Genauigkeit der zu kodierenden Zahl immer größer wird, so braucht diese nicht vollständig bearbeitet zu werden. Mit Hilfe geeigneter Algorithmen lassen sich nicht mehr relevante Anteile eliminieren.


 <   ^   > 

oben zurück weiter



Anzeigen:

Informations- und Kodierungstheorie