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. Martinhttp://www.compressconsult.com/rangecoder/#download. Aufgrund des Alters des Dokumentes wird angenommen, dass Implementationen des darin beschriebene Verfahren 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
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 ein Mehrfaches von zwei 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 Dekoder 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 zur Übertragung der Nachricht aus den Unterbereich anzuzeigen, natürlich vorausgesetzt, dass der Dekodierer erfährt, wenn die Nachricht wieder vollständig ist. Eine einzige Ganzzahl reicht aus den Unterbereich anzuzeigen und es muss nicht einmal nötig sein die gesamte Ganzzahl zu übertragen, sondern es reichen vielleicht schon die ersten der Stellen aus, die ursprüngliche Nachricht eindeutig zu beschreiben.
Beispiel
Es soll die Nachricht "AABA
Da das erste Symbol ein A ist, reduziert dieses den ursprünglichen Bereich auf
Nachdem schon zwei Symbole kodiert sind, bleibt der Bereich
Diesmal ist es die zweite der drei Möglichkeiten, die die gewünschte Nachricht beschreibt, und der Bereich wird auf
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:
Um das letzte Symbol zu kodieren ist der Bereich nun schon bis auf
Das letzte Symbol
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.
Siehe auch
Shannon-Fano-Kodierung
Referenzen
Externe Verweise
• Bereichskodierer
• "Range coder" von Arturo Campos
