Bereichscodierung - Range coding
Bereich Codierung (oder Bereich Codierung ) ist eine Entropiecodierung Methode definiert durch G. Nigel N. Martin in einem 1979 Papier, das effektiv den FIFO arithmetischen Code neu entdeckt zuerst von Richard Clark Pasco 1976 Bei einem Strom von Symbolen und die Wahrscheinlichkeiten eingeführt, ein Bereichscodierer erzeugt einen platzsparenden Bitstrom, um diese Symbole darzustellen, und bei gegebenem Strom und den Wahrscheinlichkeiten kehrt ein Bereichsdecoder den Prozess um.
Die Bereichscodierung ist der arithmetischen Codierung sehr ähnlich , außer dass die Codierung mit Ziffern in einer beliebigen Basis statt mit Bits erfolgt und daher bei Verwendung größerer Basen (z. B. ein Byte ) bei geringen Kosten der Komprimierungseffizienz schneller ist . Nach Ablauf des ersten (1978) Patents für arithmetische Codierung schien die Bereichscodierung eindeutig frei von Patentbelastungen zu sein. Dies weckte insbesondere das Interesse an der Technik in der Open-Source- Community. Seitdem sind auch Patente für verschiedene bekannte arithmetische Codierungstechniken abgelaufen.
So funktioniert die Bereichscodierung
Die Bereichscodierung codiert konzeptionell alle Symbole der Nachricht in eine Zahl, im Gegensatz zur Huffman-Codierung , die jedem Symbol ein Bitmuster zuweist und alle Bitmuster miteinander verkettet. Somit kann die Bereichscodierung größere Kompressionsverhältnisse als die Ein-Bit-pro-Symbol-Untergrenze bei der Huffman-Codierung erreichen und leidet nicht unter den Ineffizienzen, die Huffman macht, wenn es um Wahrscheinlichkeiten geht, die keine exakte Zweierpotenz sind .
Das zentrale Konzept der Bereichscodierung ist folgendes: Bei einem ausreichend großen Bereich von ganzen Zahlen und einer Wahrscheinlichkeitsschätzung für die Symbole kann der anfängliche Bereich leicht in Unterbereiche unterteilt werden, deren Größe proportional zur Wahrscheinlichkeit des Symbols ist, das sie darstellen. Jedes Symbol der Nachricht kann dann wiederum codiert werden, indem der aktuelle Bereich auf genau den Unterbereich reduziert wird, der dem nächsten zu codierenden Symbol entspricht. Der Decoder muss die gleiche Wahrscheinlichkeitsschätzung wie der verwendete Encoder aufweisen, die entweder vorab gesendet, aus bereits übertragenen Daten abgeleitet oder Teil des Kompressors und Dekompressors sein kann.
Wenn alle Symbole codiert wurden, reicht die bloße Identifizierung des Unterbereichs aus, um die gesamte Nachricht zu übermitteln (natürlich vorausgesetzt, dass der Decodierer irgendwie benachrichtigt wird, wenn er die gesamte Nachricht extrahiert hat). Tatsächlich reicht eine einzelne ganze Zahl aus, um den Unterbereich zu identifizieren, und es ist möglicherweise nicht einmal erforderlich, die gesamte ganze Zahl zu übertragen; Wenn es eine Ziffernfolge gibt, bei der jede ganze Zahl, die mit diesem Präfix beginnt, in den Unterbereich fällt, ist allein das Präfix erforderlich, um den Unterbereich zu identifizieren und somit die Nachricht zu übertragen.
Beispiel
Angenommen, wir möchten die Nachricht "AABA<EOM>" codieren, wobei <EOM> das Nachrichtenende-Symbol ist. Für dieses Beispiel wird angenommen, dass der Decoder weiß, dass wir beabsichtigen, genau fünf Symbole im Zahlensystem zur Basis 10 zu codieren (wobei 10 5 verschiedene Kombinationen von Symbolen mit dem Bereich [0, 100000) berücksichtigt werden) unter Verwendung der Wahrscheinlichkeitsverteilung {A: . 60; B: 0,20; <EOM>: .20}. Der Encoder zerlegt den Bereich [0, 100000) in drei Teilbereiche:
A: [ 0, 60000) B: [ 60000, 80000) <EOM>: [ 80000, 100000)
Da unser erstes Symbol ein A ist, reduziert es unsere anfängliche Spanne auf [0, 60000). Die zweite Symbolwahl lässt uns drei Unterbereiche dieses Bereichs. Wir zeigen sie nach dem bereits codierten 'A':
AA: [ 0, 36000) AB: [ 36000, 48000) A<EOM>: [ 48000, 60000)
Mit zwei codierten Symbolen beträgt unser Bereich jetzt [0, 36000) und unser drittes Symbol führt zu den folgenden Auswahlmöglichkeiten:
AAA: [ 0, 21600) AAB: [ 21600, 28800) AA<EOM>: [ 28800, 36000)
Diesmal ist es die zweite unserer drei Auswahlmöglichkeiten, die die Botschaft darstellen, die wir codieren möchten, und unsere Reichweite beträgt [21600, 28800). Es mag in diesem Fall schwieriger erscheinen, unsere Unterbereiche zu bestimmen, aber das ist es tatsächlich nicht: Wir können lediglich die Untergrenze von der Obergrenze subtrahieren, um festzustellen, dass unser Bereich 7200 Zahlen enthält; dass die ersten 4320 von ihnen 0,60 der Gesamtsumme darstellen, die nächsten 1440 die nächsten 0,20 darstellen und die restlichen 1440 die verbleibenden 0,20 der Gesamtsumme darstellen. Durch Hinzufügen der unteren Schranke erhalten wir unsere Reichweiten:
AABA: [21600, 25920) AABB: [25920, 27360) AAB<EOM>: [27360, 28800)
Schließlich haben wir, da unser Bereich auf [21600, 25920] eingeengt ist, nur noch ein weiteres Symbol zu codieren. Unter Verwendung der gleichen Technik wie zuvor zum Aufteilen des Bereichs zwischen der unteren und der oberen Grenze finden wir die drei Unterbereiche:
AABAA: [21600, 24192) AABAB: [24192, 25056) AABA<EOM>: [25056, 25920)
Und da <EOM> unser letztes Symbol ist, ist unser endgültiger Bereich [25056, 25920). Da alle fünfstelligen ganzen Zahlen, die mit "251" beginnen, in unseren endgültigen Bereich fallen, ist dies eines der dreistelligen Präfixe, die wir übertragen könnten, die unsere ursprüngliche Nachricht eindeutig übermitteln würden. (Die Tatsache, dass es insgesamt acht solcher Präfixe gibt, impliziert, dass wir immer noch Ineffizienzen haben. Sie wurden durch die Verwendung der Basis 10 anstelle der Basis 2 eingeführt .)
Das zentrale Problem scheint darin zu bestehen, einen Anfangsbereich auszuwählen, der groß genug ist, dass wir, egal wie viele Symbole wir codieren müssen, immer einen aktuellen Bereich haben, der groß genug ist, um in Unterbereiche ungleich Null aufzuteilen. In der Praxis stellt dies jedoch kein Problem dar, denn anstatt mit einem sehr großen Bereich zu beginnen und diesen allmählich einzugrenzen, arbeitet der Encoder jeweils mit einem kleineren Zahlenbereich. Nachdem eine bestimmte Anzahl von Ziffern codiert wurde, ändern sich die Ziffern ganz links nicht. Im Beispiel wussten wir nach der Codierung von nur drei Symbolen bereits, dass unser Endergebnis mit „2“ beginnen würde. Rechts werden mehr Ziffern eingeschoben, während die linken Ziffern abgeschickt werden. Dies wird im folgenden Code veranschaulicht:
int low = 0;
int range = 100000;
void Run()
{
Encode(0, 6, 10); // A
Encode(0, 6, 10); // A
Encode(6, 2, 10); // B
Encode(0, 6, 10); // A
Encode(8, 2, 10); // <EOM>
// emit final digits - see below
while (range < 10000)
EmitDigit();
low += 10000;
EmitDigit();
}
void EmitDigit()
{
Console.Write(low / 10000);
low = (low % 10000) * 10;
range *= 10;
}
void Encode(int start, int size, int total)
{
// adjust the range based on the symbol interval
range /= total;
low += start * range;
range *= size;
// check if left-most digit is same throughout range
while (low / 10000 == (low + range) / 10000)
EmitDigit();
// readjust range - see reason for this below
if (range < 1000)
{
EmitDigit();
EmitDigit();
range = 100000 - low;
}
}
Zum Abschluss müssen wir möglicherweise ein paar zusätzliche Ziffern eingeben. Die oberste Ziffer von lowist wahrscheinlich zu klein, daher müssen wir sie erhöhen, aber wir müssen sicherstellen, dass sie nicht über low+range. Also müssen wir zuerst sicherstellen, dass rangees groß genug ist.
// emit final digits
while (range < 10000)
EmitDigit();
low += 10000;
EmitDigit();
Ein Problem , das mit der auftreten kann Encodeüber Funktion ist , dass rangekönnte sich sehr klein , aber lowund low+rangenoch haben unterschiedliche erste Ziffern. Dies könnte dazu führen, dass das Intervall eine unzureichende Genauigkeit hat, um zwischen allen Symbolen im Alphabet zu unterscheiden. Wenn dies passiert, müssen wir ein wenig fummeln, die ersten paar Ziffern ausgeben, auch wenn wir vielleicht um eins daneben liegen, und den Bereich neu anpassen, um uns so viel Platz wie möglich zu geben. Der Decoder führt die gleichen Schritte aus, damit er weiß, wann er dies tun muss, um synchron zu bleiben.
// this goes just before the end of Encode() above
if (range < 1000)
{
EmitDigit();
EmitDigit();
range = 100000 - low;
}
In diesem Beispiel wurde die Basis 10 verwendet, aber eine echte Implementierung würde nur Binär verwenden, mit dem gesamten Bereich des nativen Integer-Datentyps. Anstelle von 10000und 1000würden Sie wahrscheinlich hexadezimale Konstanten wie 0x1000000und verwenden 0x10000. Anstatt eine Ziffer nach der anderen auszugeben, würden Sie ein Byte nach dem anderen ausgeben und eine Byte-Shift-Operation verwenden, anstatt mit 10 zu multiplizieren.
Die Dekodierung verwendet genau den gleichen Algorithmus, wobei zusätzlich der aktuelle codeWert verfolgt wird, der aus den vom Kompressor gelesenen Ziffern besteht. Anstatt die oberste Ziffer von lowIhnen auszugeben, werfen Sie sie einfach weg, aber Sie verschieben auch die oberste Ziffer des codeKompressors und schieben eine neue Ziffer ein, die vom Kompressor gelesen wird. Verwenden Sie AppendDigitunten anstelle von EmitDigit.
int code = 0;
int low = 0;
int range = 1;
void InitializeDecoder()
{
AppendDigit(); // with this example code, only 1 of these is actually needed
AppendDigit();
AppendDigit();
AppendDigit();
AppendDigit();
}
void AppendDigit()
{
code = (code % 10000) * 10 + ReadNextDigit();
low = (low % 10000) * 10;
range *= 10;
}
void Decode(int start, int size, int total) // Decode is same as Encode with EmitDigit replaced by AppendDigit
{
// adjust the range based on the symbol interval
range /= total;
low += start * range;
range *= size;
// check if left-most digit is same throughout range
while (low / 10000 == (low + range) / 10000)
AppendDigit();
// readjust range - see reason for this below
if (range < 1000)
{
AppendDigit();
AppendDigit();
range = 100000 - low;
}
}
Um zu bestimmen, welche Wahrscheinlichkeitsintervalle anzuwenden sind, muss der Decoder den aktuellen Wert codeinnerhalb des Intervalls [niedrig, niedrig + Bereich) betrachten und entscheiden, welches Symbol dies darstellt.
void Run()
{
int start = 0;
int size;
int total = 10;
InitializeDecoder(); // need to get range/total >0
while (start < 8) // stop when receive EOM
{
int v = GetValue(total); // code is in what symbol range?
switch (v) // convert value to symbol
{
case 0:
case 1:
case 2:
case 3:
case 4:
case 5: start=0; size=6; Console.Write("A"); break;
case 6:
case 7: start=6; size=2; Console.Write("B"); break;
default: start=8; size=2; Console.WriteLine("");
}
Decode(start, size, total);
}
}
int GetValue(int total)
{
return (code - low) / (range / total);
}
Für das obige AABA<EOM>-Beispiel würde dies einen Wert im Bereich von 0 bis 9 zurückgeben. Die Werte 0 bis 5 würden A darstellen, 6 und 7 würden B darstellen und 8 und 9 würden <EOM> darstellen.
Zusammenhang mit arithmetischer Kodierung
Die arithmetische Codierung ist die gleiche wie die Bereichscodierung, jedoch werden die ganzen Zahlen als Zähler von Brüchen verwendet . Diese Brüche haben einen impliziten gemeinsamen Nenner, sodass alle Brüche in den Bereich [0,1) fallen. Dementsprechend wird der resultierende arithmetische Code als beginnend mit einer impliziten "0" interpretiert. Da dies nur unterschiedliche Interpretationen der gleichen Codierverfahren sind und die resultierenden arithmetischen und Bereichscodes identisch sind, ist jeder arithmetische Codierer sein entsprechender Bereichscodierer und umgekehrt. Mit anderen Worten, arithmetische Codierung und Bereichscodierung sind nur zwei leicht unterschiedliche Arten, dasselbe zu verstehen.
In der Praxis allerdings sogenannter Bereich Encoder sind in der Regel ziemlich umgesetzt werden wie in Martin Papier beschrieben, während arithmetische Codierer allgemein nicht dazu neigen , genannt Bereich Encoder werden. Ein häufig erwähntes Merkmal solcher Entfernungscodierer ist die Tendenz, die Renormierung jeweils byteweise statt bitweise durchzuführen (wie es normalerweise der Fall ist). Mit anderen Worten, Bereichscodierer neigen dazu, eher Bytes als Codierziffern als Bits zu verwenden. Dies verringert zwar den Komprimierungsbetrag, der erreicht werden kann, um einen sehr kleinen Betrag, ist jedoch schneller als bei der Durchführung einer Renormierung für jedes Bit.
Siehe auch
- Arithmetische Kodierung
- Asymmetrische Zahlensysteme
- Datenkompression
- Entropiekodierung
- Huffman-Codierung
- Multiskalen-Elektrophysiologie-Format
- Shannon-Fano-Codierung
Verweise
- ^ a b G. Nigel N. Martin, Bereichscodierung: Ein Algorithmus zum Entfernen von Redundanz aus einer digitalisierten Nachricht , Video & Data Recording Conference, Southampton , UK, 24.–27. Juli 1979.
- ^ "Quellcodieralgorithmen für schnelle Datenkomprimierung" Richard Clark Pasco, Stanford, CA 1976
- ^ " Auf dem Overhead von Range Coders ", Timothy B. Terriberry, Technical Note 2008
- ^ US-Patent 4,122,440 – (IBM) Eingereicht am 4. März 1977, erteilt am 24. Oktober 1978 (jetzt abgelaufen)