Reihe-Verschlüsselung ist eine Datenkompressionsmethode, die von G. Nigel N. Martin in einer 1979-Papierreihe-Verschlüsselung definiert ist, ist eine Form der Arithmetik, die codiert, der historisch von Interesse war, um einige Patente auf besonderen später entwickelten Arithmetik-Codiertechniken zu vermeiden (obwohl die Patente auf verschiedenen wohl bekannten Arithmetik-Codiermethoden seitdem abgelaufen sind). Encoders, die Reihe encoders normalerweise genannt werden, verwenden eine besondere Art der Durchführung gestützt nah auf dem Papier von Martin, weil, wie man zeigen konnte, solche Durchführungen "vorherige Kunst" in Bezug auf einige spätere Patente auf anderen Arithmetik-Codiertechniken (auf der Grundlage vom Alter der Veröffentlichung von Martin) waren. Nach dem Ablauf des ersten (1978) Arithmetik-Codierpatent ist Reihe-Verschlüsselung geschienen, klar frei von offenen Belastungen zu sein. Das hat besonders Interesse an der Technik in der offenen Quellgemeinschaft gesteuert. Seit dieser Zeit sind Patente auf verschiedenen anderen Arithmetik-Codiertechniken auch abgelaufen.

Wie Reihe-Verschlüsselung arbeitet

Reihe, die begrifflich verschlüsselt, verschlüsselt alle Symbole der Nachricht in eine Zahl verschieden von Huffman, der codiert, der jedes Symbol ein Bit-Muster zuteilt und alle Bit-Muster zusammen verkettet. So kann Reihe-Verschlüsselung größere Kompressionsverhältnisse erreichen, als das ein Bit pro Symbol tiefer zu Huffman gebunden hat, der verschlüsselt, und es die Wirkungslosigkeit nicht erträgt, die Huffman tut, wenn, sich mit Wahrscheinlichkeiten befassend, die nicht genaue Mächte zwei sind.

Das Hauptkonzept hinter der Reihe-Verschlüsselung ist das: In Anbetracht einer genug großen Reihe von ganzen Zahlen und einer Wahrscheinlichkeitsbewertung für die Symbole kann die anfängliche Reihe in Teilbereiche leicht geteilt werden, deren Größen zur Wahrscheinlichkeit des Symbols proportional sind, das sie vertreten. Jedes Symbol der Nachricht kann dann der Reihe nach, durch das Reduzieren der aktuellen Reihe unten auf gerade verschlüsselt werden, dass Teilbereich, der dem folgenden zu verschlüsselnden Symbol entspricht. Der Decoder muss dieselbe Wahrscheinlichkeitsbewertung der verwendete encoder haben, der entweder im Voraus gesandt, bereits aus übertragenen Daten abgeleitet werden oder ein Teil des Kompressors und decompressor sein kann.

Als alle Symbole verschlüsselt worden sind, bloß ist das Identifizieren des Teilbereichs genug, um die komplette Nachricht mitzuteilen (Annahme natürlich, dass der Decoder irgendwie bekannt gegeben wird, als es die komplette Nachricht herausgezogen hat). Eine einzelne ganze Zahl ist wirklich genügend, um den Teilbereich zu identifizieren, und es kann nicht sogar notwendig sein, die komplette ganze Zahl zu übersenden; wenn es eine Folge von solchen Ziffern gibt, dass jede ganze Zahl, die mit diesem Präfix Fälle innerhalb des Teilbereichs beginnt, dann ist das Präfix allein alles, das es erforderlich ist, um den Teilbereich zu identifizieren und so die Nachricht zu übersenden.

Beispiel

Nehmen Sie an, dass wir die Nachricht "AABA verschlüsseln

wollen

Da unser erstes Symbol ein A ist, reduziert es unsere anfängliche Reihe unten darauf. Die zweite Symbol-Wahl verlässt uns mit drei Teilbereichen dieser Reihe, wir zeigen ihnen im Anschluss an das bereits verschlüsselte:

Mit zwei verschlüsselten Symbolen ist unsere Reihe jetzt, und unsere dritten Symbole führt zu den folgenden Wahlen:

Dieses Mal ist es von unseren drei Wahlen zweit, die die Nachricht vertreten, die wir verschlüsseln wollen, und unsere Reihe wird. Es kann härter aussehen, unsere Teilbereiche in diesem Fall zu bestimmen, aber es ist wirklich nicht: Wir können tiefer bestimmt vom oberen bloß Abstriche machen, das verpflichtet ist zu beschließen, dass es 7200 Zahlen in unserer Reihe gibt; dass die ersten 4320 von ihnen 0.60 der Summe vertreten, im nächsten 1440 die folgenden 0.20 vertreten, und restlicher 1440 restliche 0.20 der Summe vertritt. Das Hinzufügen zurück tiefer bestimmt gibt uns unsere Reihen:

Schließlich, mit unserer Reihe, die darauf beschränkt ist, haben wir gerade ein mehr Symbol, um zu verschlüsseln. Mit derselben Technik wie zuvor, für die Reihe zwischen dem niedrigeren und gebundenen oberen zu zerteilen, finden wir, dass die drei Teilbereiche sind:

Und seitdem

Das Hauptproblem kann scheinen, eine anfängliche Reihe groß genug auszuwählen, dass, egal wie viele Symbole wir verschlüsseln müssen, wir immer eine aktuelle Reihe haben werden, die groß genug ist, um uns in Nichtnullteilbereiche zu teilen. In der Praxis, jedoch, ist das nicht ein Problem, weil, anstatt mit einer sehr großen Reihe anzufangen und allmählich sie zu beschränken, der encoder mit einer kleineren Reihe von Zahlen zu jeder vorgegebenen Zeit arbeitet. Nach einer Zahl von Ziffern sind verschlüsselt worden, die leftmost Ziffern werden sich nicht ändern. Im Beispiel nach der Verschlüsselung gerade von drei Symbolen haben wir bereits gewusst, dass unser Endresultat mit "2" anfangen würde. Mehr Ziffern werden in rechts ausgewechselt, als Ziffern links weggeschickt werden. Das wird im folgenden Code illustriert:

interne Nummer niedrig = 0;

int Reihe = 100000;

leerer Lauf

{\

Verschlüsseln Sie (0, 6, 10); //Ein

Verschlüsseln Sie (0, 6, 10); //Ein

Verschlüsseln Sie (6, 2, 10); //B

Verschlüsseln Sie (0, 6, 10); //Ein

Verschlüsseln Sie (8, 2, 10); //

}\

Leere Verschlüsselt (int Anfang, int Größe, int Summe)

{\

//passen Sie die Reihe an, die auf dem Symbol-Zwischenraum gestützt ist

erstrecken Sie sich / = ganz;

niedrig + = fangen * Reihe an;

erstrecken Sie sich * = Größe;

//überprüfen Sie, ob ganz links Ziffer dasselbe überall in der Reihe ist

während (niedrig / 10000 == (niedrig + Reihe) / 10000)

{\

EmitDigit ;

erstrecken Sie sich = (Reihe-% 10000) * 10;

}\

}\

leerer EmitDigit

{\

Konsole. Schreiben Sie (niedrig / 10000);

niedrig = (niedriger % 10000) * 10;

}\

</Quelle>

Um zu enden, müssen wir eventuell einige Extraziffern ausstrahlen. Die Spitzenziffer dessen ist wahrscheinlich zu klein, so müssen wir sie erhöhen, aber wir müssen sicherstellen, dass wir sie vorbei nicht erhöhen. So zuerst müssen wir uns überzeugen ist groß genug.

//strahlen Sie Endziffern aus

während (Reihe

Ein Problem, das mit der Funktion oben vorkommen kann, ist das könnte sehr klein werden, aber und noch das Unterscheiden die ersten Ziffern haben. Das konnte auf den Zwischenraum hinauslaufen, der ungenügende Präzision hat, um zwischen allen Symbolen im Alphabet zu unterscheiden. Wenn das geschieht, müssen wir etwas, Produktion die ersten beiden von Ziffern ausweichen, wenn auch wir durch einen aus sein, und die Reihe wieder anpassen könnten, um uns so viel Zimmer wie möglich zu geben. Der Decoder wird denselben Schritten folgen, so wird er wissen, wenn er das tun muss, um synchron zu behalten.

//das geht kurz vor dem Ende dessen Verschlüsseln über

wenn (Reihe

Basis 10 wurde in diesem Beispiel verwendet, aber eine echte Durchführung würde gerade binär mit der vollen Reihe des heimischen Datentyps der ganzen Zahl verwenden. Statt und würden Sie wahrscheinlich hexadecimal Konstanten solcher als verwenden und. Anstatt eine Ziffer auf einmal auszustrahlen, würden Sie ein Byte auf einmal ausstrahlen und eine Operation der Byte-Verschiebung verwenden, anstatt um 10 zu multiplizieren.

Wenn man

Gebrauch genau decodiert, derselbe Algorithmus mit der Hinzufügung des Nachgehens des aktuellen Werts, der aus den Ziffern besteht, vom Kompressor gelesen. Anstatt die Spitzenziffer von Ihnen auszustrahlen, werfen es gerade weg, aber Sie wechseln auch die Spitzenziffer und Verschiebung in einer neuen vom Kompressor gelesenen Ziffer aus. Verwenden Sie unten statt.

int Code = 0;

leerer InitializeDecoder

{\

AppendDigit ;

AppendDigit ; AppendDigit ; AppendDigit ; AppendDigit ;}\

leerer AppendDigit

{\

codieren Sie = (Code% 10000) * 10 + ReadNextDigit ;

niedrig = (niedriger % 10000) * 10;}\</Quelle>

Um zu bestimmen, welcher Wahrscheinlichkeitszwischenräume, zu gelten, der Decoder auf den aktuellen Wert innerhalb des Zwischenraums [niedrig, low+range schauen) und entscheiden muss, welches Symbol das vertritt.

int GetValue (int Summe)

{\

kehren Sie (Code - niedrig) / (Reihe / ganz) zurück;

}\</Quelle>

Für

Beziehung mit dem arithmetischen Codieren

Das arithmetische Codieren ist dasselbe als Reihe-Verschlüsselung, aber mit den ganzen Zahlen, die genommen sind als, die Zähler von Bruchteilen zu sein. Diese Bruchteile haben einen impliziten, gemeinsamen Nenner, solch, dass alle Bruchteile in der Reihe fallen. Entsprechend wird der resultierende arithmetische Code als Anfang mit einem impliziten "0" interpretiert.. Da das gerade verschiedene Interpretationen derselben Codiermethoden, und wie die resultierende Arithmetik sind und Reihe-Codes identisch sind, ist jeder arithmetische Codierer seine entsprechende Reihe encoder, und umgekehrt. Mit anderen Worten sind das arithmetische Codieren und die Reihe-Verschlüsselung gerade zwei, ein bisschen verschiedene Weisen, dasselbe Ding zu verstehen.

In der Praxis aber neigt so genannte Reihe encoders dazu, ziemlich viel wie beschrieben, in der Zeitung von Martin durchgeführt zu werden, während arithmetische Codierer mehr allgemein dazu neigen, Reihe encoders nicht genannt zu werden. Eine häufig bekannte Eigenschaft solcher Reihe encoders ist die Tendenz, Wiedernormalisierung ein Byte auf einmal, aber nicht ein Bit auf einmal durchzuführen (wie gewöhnlich der Fall ist). Mit anderen Worten neigt Reihe encoders dazu, Bytes als Verschlüsselung von Ziffern, aber nicht Bit zu verwenden. Während das wirklich den Betrag der Kompression reduziert, die durch einen sehr kleinen Betrag erreicht werden kann, ist es schneller als, wenn man Wiedernormalisierung für jedes Bit durchführt.

Siehe auch

• Mehrerklettern Sie Electrophysiology-Format
• Shannon-Fano, der codiert

Außenverbindungen

• Ordnen Sie Encoder an
• "Reihe-Codierer" durch Arturo Campos
• "Anatomie der Reihe Encoder" durch Andrew Polar