Bereichskodierung

Die Bereichskodierung (engl. range encoding) ist ein Datenkompressionsverfahren zur Entropiekodierung, das eine Art des arithmetischen Kodierens realisiert.

Die Bereichskodierung wird oft als alternative Beschreibung des Arithmetischen Kodierens und als im Grunde identisch mit diesem angesehen. Sie basiert auf dem 1979 veröffentlichten Dokument "Range encoding: an algorithm for removing redundancy from a digitised message" (engl., zu deutsch etwa Bereichskodierung, ein Algorithmus um Redundanz aus digitalisierten Nachrichten zu entfernen), von G. N. N. Martin^[1]. Aufgrund des Alters des Dokumentes wird angenommen, dass Implementationen des darin beschriebenen Verfahrens zur arithmetischen Kodierung nicht von den Patenten auf die arithmetische Kodierung betroffen sind. Dies hat besonders in der Freie-Software-Gemeinde Interesse an der Technik geweckt.

Funktionsweise[Bearbeiten | Quelltext bearbeiten]

Die Bereichskodierung kodiert im Prinzip alle Symbole einer Nachricht in eine Nummer – im Unterschied zur Huffman-Kodierung, die jedem Symbol ein Bitmuster zuweist und die Bitmuster wieder hintereinanderreiht. Daher hat die Bereichskodierung nicht wie diese die Obergrenze jeweils mindestens ein Bit für ein Symbol verwenden zu müssen und leidet auch nicht wie diese an der Ineffizienz im Umgang mit Auftrittswahrscheinlichkeiten, die nicht exakt eine Zweierpotenz sind. So können damit bessere Kompressionsraten erzielt werden.

Das zentrale Konzept hinter der Bereichskodierung ist vereinfacht folgendes: Hat man einen ausreichenden Bereich (engl. range) von Ganzzahlwerten als Symbole und eine Wertung der Auftrittswahrscheinlichkeiten der Symbole, so kann der ursprüngliche Bereich leicht in Unterbereiche zerteilt werden, deren Größen proportional zu den Auftrittswahrscheinlichkeiten der Symbole sind, die sie repräsentieren. Damit kann jedes Symbol der Nachricht kodiert werden, indem der Wertebereich auf den Unterbereich reduziert wird, der dem nächsten zu kodierenden Symbol entspricht. Dem Dekodierer muss dabei die gleiche Wahrscheinlichkeitsannahme wie dem Kodierer zur Verfügung stehen, die entweder vorher übertragen, aus bereits übertragenen Daten gewonnen oder Teil der Kodierer und Dekodierer sein kann.

Wenn alle Symbole kodiert sind, reicht es zur Übertragung der Nachricht aus, den Unterbereich anzuzeigen, natürlich vorausgesetzt, dass der Dekodierer erfährt, wann die Nachricht wieder vollständig ist. Eine einzige Ganzzahl reicht aus, um den Unterbereich anzuzeigen, und es muss nicht einmal nötig sein, die gesamte Ganzzahl zu übertragen, sondern es reichen vielleicht schon die ersten der $n$ Stellen aus, um die ursprüngliche Nachricht eindeutig zu beschreiben.

Beispiel[Bearbeiten | Quelltext bearbeiten]

Es soll die Nachricht "AABA<EOM>" kodiert werden, wobei <EOM> das Ende der Nachricht (end of message) kennzeichnet. Für dieses Beispiel wird angenommen, dass dem Dekodierer bekannt ist, dass ein Dezimalsystem, ein Bereich von [0, 100000) sowie die Häufigkeitswertung {A: 0,60; B: 0,20; <EOM>: 0,20} verwendet wird. Das erste Symbol zerlegt den Bereich [0, 100000) in drei Unterbereiche:

A:     [     0,  60000)
B:     [ 60000,  80000)
<EOM>: [ 80000, 100000)

Da das erste Symbol ein A ist, reduziert dieses den ursprünglichen Bereich auf [0, 60000). Die zweite Symbol-Entscheidung zerteilt diesen Unterbereich wiederum in drei Unterbereiche, im Folgenden nach dem schon kodierten 'A' dargestellt:

AA:     [     0,  36000)
AB:     [ 36000,  48000)
A<EOM>: [ 48000,  60000)

Nachdem schon zwei Symbole kodiert sind, bleibt der Bereich [000000, 036000) und das dritte Symbol entscheidet zwischen den folgenden Bereichen:

AAA:     [     0,  21600)
AAB:     [ 21600,  28800)
AA<EOM>: [ 28800,  36000)

Diesmal ist es die zweite der drei Möglichkeiten, die die gewünschte Nachricht beschreibt, und der Bereich wird auf [21600, 28800) beschränkt. Es mag nun für diesen Fall schwieriger erscheinen die Unterbereiche auszumachen, doch sie ergeben sich recht einfach: Durch Abziehen des unteren Grenzwertes vom oberen ergibt sich, dass der Bereich 7200 Nummern umfasst, die sich nach dem Wahrscheinlichkeitsmuster aufteilen in 4320 für den ersten ,60-Anteil und jeweils 1400 für die nächsten zwei ,20-Anteile des Gesamt(teil)bereiches. Auf den Unteren Grenzwert des Gesamt(teil)bereiches zurückaddiert ergeben sich die Unterbereiche:

AABA:     [21600, 25920)
AABB:     [25920, 27360)
AAB<EOM>: [27360, 28800)

Um das letzte Symbol zu kodieren ist der Bereich nun schon bis auf [21600, 25920) eingeschränkt. Dieser zerteilt sich dafür nun wieder nach eben beschriebener Methode zwischen den Grenzwerten in folgende Unterbereiche:

AABAA:     [21600, 24192)
AABAB:     [24192, 25056)
AABA<EOM>: [25056, 25920)

Das letzte Symbol <EOM> legt den letztendlichen Bereich fest auf [25056, 25920). Da alle Nummern, die mit "251" beginnen, in diesen Bereich fallen, wird die Nachricht schon dadurch eindeutig beschrieben. (Da acht solcher eindeutiger Nummern tatsächlich existieren, ist die Kodierung immer noch nicht optimal; dadurch, dass das Dezimalsystem anstatt beispielsweise des Binärsystems verwendet wurde.)

Es mag nun als das Hauptproblem erscheinen zu Beginn einen ausreichend großen Bereich zu wählen, um alle Symbole zu kodieren, ohne beim Aufteilen die Ganzzahlen zu verlassen oder Null zu erhalten. Praktisch ergibt sich dieses Problem jedoch nicht, da der Kodierer die Zahl nach und nach vergrößern kann und ersten Stellen, die bereits feststehen, schon ausgeben kann und nicht mehr für die Berechnungen braucht. So wird zu jeder Zeit mit einem kleinen Nummernbereich gearbeitet, indem feststehende Nummern ausgegeben und dafür an der anderen Seite welche hinzugenommen werden. Im Beispiel stand schon nach der Verarbeitung der ersten drei Symbole die "2" als erste Stelle des Ergebnisses fest und hätte nicht mehr mitberechnet werden müssen.