Nach vorne verschieben

Die Move-to-Front-Transformation (MTF) ist eine Datenkodierung ( typischerweise ein Byte -Stream) , die die Leistung von Entropiekodierungsverfahren zur Komprimierung verbessert . Bei effizienter Implementierung ist sie so schnell, dass ihre Vorteile in der Regel die Integration als zusätzlichen Schritt in den Datenkomprimierungsalgorithmus rechtfertigen .

Dieser Algorithmus wurde erstmals 1980 von Boris Ryabko unter dem Namen „Buchstapel“ veröffentlicht. ^{[ 1 ]} Später wurde er 1986 von JK Bentley et al. wiederentdeckt, ^{[ 2 ]} wie in der erläuternden Anmerkung belegt ist. ^{[ 3 ]}

Die Grundidee besteht darin, jedes Symbol in den Daten durch seinen Index in der Liste der zuletzt verwendeten Symbole zu ersetzen. Beispielsweise werden lange Sequenzen identischer Symbole durch Nullen ersetzt, während ein Symbol, das lange nicht verwendet wurde, durch eine große Zahl ersetzt wird. So werden die Daten schließlich in eine Folge von ganzen Zahlen umgewandelt; weisen die Daten viele lokale Korrelationen auf, sind diese Zahlen tendenziell klein.

Um es genauer zu beschreiben: Nehmen wir der Einfachheit halber an, dass die Symbole in den Daten Bytes sind . Jeder Byte-Wert wird durch seinen Index in einer Byte- Liste kodiert , die sich im Laufe des Algorithmus ändert. Die Liste ist anfänglich nach Byte-Wert sortiert (0, 1, 2, 3, ..., 255). Daher wird das erste Byte immer durch seinen eigenen Wert kodiert. Nach der Kodierung eines Bytes wird dieser Wert jedoch an den Anfang der Liste verschoben, bevor mit dem nächsten Byte fortgefahren wird.

Ein Beispiel verdeutlicht die Funktionsweise der Transformation. Stellen Sie sich vor, wir kodieren Werte im Alphabet (a–z) anstatt mit Bytes. Wir möchten die folgende Sequenz transformieren:

Bananen 

Konventionsgemäß lautet die Liste anfänglich (abcdefghijklmnopqrstuvwxyz). Der erste Buchstabe in der Sequenz ist b, der an Index 1 erscheint (die Liste ist von 0 bis 25 indiziert). Wir schreiben eine 1 in den Ausgabestream:

1 

Das b rückt an den Anfang der Liste und erzeugt (bacdefghijklmnopqrstuvwxyz). Der nächste Buchstabe ist a, der nun an Index 1 erscheint. Daher addieren wir eine 1 zum Ausgabestream. Wir erhalten:

1,1 

und wir verschieben den Buchstaben a wieder an den Anfang der Liste. Auf diese Weise fortfahrend, stellen wir fest, dass die Sequenz wie folgt kodiert ist:

1,1,13,1,1,1,0,0 

Man sieht leicht, dass die Transformation umkehrbar ist. Man behält einfach dieselbe Liste bei und dekodiert, indem man jeden Index im kodierten Datenstrom durch den entsprechenden Buchstaben in der Liste ersetzt. Beachten Sie den Unterschied zur Kodierungsmethode: Der Index in der Liste wird direkt verwendet, anstatt jeden Wert einzeln nach seinem Index zu durchsuchen.

Das heißt, man beginnt wieder mit (abcdefghijklmnopqrstuvwxyz). Man nimmt die „1“ des codierten Blocks und schlägt sie in der Liste nach, was „b“ ergibt. Dann verschiebt man das „b“ an den Anfang, was zu (bacdef...) führt. Dann nimmt man die nächste „1“, schlägt sie in der Liste nach, was „a“ ergibt, verschiebt das „a“ an den Anfang ... usw.

Die Details der Implementierung sind für die Leistung, insbesondere beim Dekodieren, wichtig. Beim Kodieren bietet die Verwendung einer verketteten Liste keinen klaren Vorteil , daher ist die Verwendung eines Arrays zur Speicherung der Liste akzeptabel, mit einer Worst-Case-Performance von O ( nk ) , wobei n die Länge der zu kodierenden Daten und k die Anzahl der Werte (im Allgemeinen eine Konstante für eine gegebene Implementierung) ist.

Die typische Performance ist besser, da häufig verwendete Symbole eher am Anfang stehen und somit schneller Treffer erzielen. Dies ist auch das Prinzip hinter einer selbstorganisierenden Liste, die Elemente nach vorne verschiebt .

Für die Dekodierung können wir jedoch spezielle Datenstrukturen verwenden, um die Leistung erheblich zu verbessern.

Dies ist eine mögliche Implementierung des Move-to-Front-Algorithmus in Python .

from collections.abc import Generator , Iterableclass MoveToFront : """  >>> mtf = MoveToFront()  >>> list(mtf.encode("Wikipedia"))  [87, 105, 107, 1, 112, 104, 104, 3, 102]  >>> mtf.decode([87, 105, 107, 1, 112, 104, 104, 3, 102])  'Wikipedia'  >>> list(mtf.encode("wikipedia"))  [119, 106, 108, 1, 113, 105, 105, 3, 103]  >>> mtf.decode([119, 106, 108, 1, 113, 105, 105, 3, 103])  'wikipedia'  """ def __init__ ( self , common_dictionary : Iterable [ int ] = range ( 256 )): """  Anstatt immer ein "ursprüngliches" Wörterbuch zu übertragen, ist es einfacher ,  sich auf einen Anfangssatz zu einigen.  Hier verwenden wir die 256 möglichen Werte eines Bytes.  """ # Das Iterable wird verbraucht , damit es mehrfach verwendet werden kann self.common_dictionary = list ( common_dictionary )def encode ( self , plain_text : str ) -> Generator [ int ] : # Das gemeinsame Wörterbuch zu ändern ist keine gute Idee. Erstelle eine Kopie . dictionary = list ( self.common_dictionary )# Jedes Zeichen in den Klartext einlesen . encode ( " latin - 1 " ): # In Bytes für 256 umwandeln. # Rang des Zeichens im Wörterbuch finden [O(k)] rank = dictionary.index ( c ) # das kodierte Zeichen yield rank# Aktualisiere das Wörterbuch [Θ(k) für insert] dictionary . pop ( rank ) dictionary . insert ( 0 , c )defdecode(self,compressed_data:Iterable[int])->str:""" Inverse function that recover the original text """dictionary=list(self.common_dictionary)plain_text=[]# Read in each rank in the encoded textforrankincompressed_data:# Remove the character of that rank from the dictionarye=dictionary.pop(rank)plain_text.append(e)# Insert the character at the beginning of dictionarydictionary.insert(0,e)returnbytes(plain_text).decode("latin-1")# Return original string

In this example we can see the MTF code taking advantage of the three repetitive i's in the input word. The common dictionary here, however, is less than ideal since it is initialized with more commonly used ASCII printable characters put after little-used control codes, against the MTF code's design intent of keeping what's commonly used in the front. If one rotates the dictionary to put the more-used characters in earlier places, a better encoding can be obtained:

fromitertoolsimportchaindefblock32(x):returnrange(x,x+32)class MoveToFrontMoreCommon ( MoveToFront ): """  >>> mtf = MoveToFrontMoreCommon()  >>> list(mtf.encode("Wikipedia"))  [55, 10, 12, 1, 17, 9, 9, 3, 7]  """ def __init__ ( self ): super () . __init__ ( chain ( # Sortiere die ASCII-Blöcke: block32 ( ord ( "a" ) - 1 ), # zuerst Kleinbuchstaben, block32 ( ord ( "A" ) - 1 ), # dann Großbuchstaben, block32 ( ord ( "!" ) - 1 ), # Satzzeichen/Zahlen, block32 ( 0 ), # Steuerzeichen, range ( 128 , 256 ), # und schließlich die Nicht-ASCII-Zeichen ) )if __name__ == "__main__" : import doctest doctest . testmod ()

Die MTF-Transformation nutzt lokale Frequenzkorrelationen, um die Entropie einer Nachricht zu reduzieren. Dadurch bleiben kürzlich verwendete Buchstaben weiter vorne in der Liste; weisen die Buchstaben lokale Korrelationen auf, führt dies zu einer großen Anzahl kleiner Zahlen wie „0“ und „1“ im Ergebnis.

Allerdings weisen nicht alle Daten diese Art von lokaler Korrelation auf, und bei manchen Nachrichten kann die MTF-Transformation die Entropie sogar erhöhen.

Eine wichtige Anwendung der MTF-Transformation liegt in der Komprimierung mittels Burrows-Wheeler-Transformation . Die Burrows-Wheeler-Transformation eignet sich hervorragend zur Erzeugung einer Sequenz, die lokale Frequenzkorrelationen aus Texten und bestimmten anderen Datenklassen aufweist. Die Komprimierung profitiert erheblich davon, der Burrows-Wheeler-Transformation vor dem abschließenden Entropiekodierungsschritt eine MTF-Transformation hinzuzufügen.

Nehmen wir beispielsweise an, wir möchten Hamlets Monolog ( „Sein oder Nichtsein… “) komprimieren. Die Größe dieser Nachricht lässt sich mit 7033 Bit berechnen. Naiv betrachtet, könnten wir versuchen, die MTF-Transformation direkt anzuwenden. Das Ergebnis wäre eine Nachricht mit 7807 Bit (größer als das Original). Der Grund dafür ist, dass englischer Text im Allgemeinen keine hohe lokale Frequenzkorrelation aufweist. Wenden wir jedoch zuerst die Burrows-Wheeler-Transformation und anschließend die MTF-Transformation an, erhalten wir eine Nachricht mit 6187 Bit. Die Burrows-Wheeler-Transformation verringert die Entropie der Nachricht nicht; sie ordnet die Bytes lediglich so um, dass die MTF-Transformation effektiver wird.

Ein Problem der grundlegenden MTF-Transformation besteht darin, dass sie für jedes Zeichen unabhängig von seiner Häufigkeit die gleichen Änderungen vornimmt. Dies kann zu einer verminderten Komprimierung führen, da selten vorkommende Zeichen häufig vorkommende Zeichen zu höheren Werten verschieben können. Aus diesem Grund wurden verschiedene Modifikationen und Alternativen entwickelt. Eine gängige Änderung besteht darin, Zeichen oberhalb eines bestimmten Wertes nur bis zu einem bestimmten Schwellenwert zu verschieben. Eine andere Methode verwendet einen Algorithmus, der die lokale Häufigkeit jedes Zeichens zählt und anhand dieser Werte die Zeichenreihenfolge bestimmt. Viele dieser Transformationen reservieren weiterhin Nullen für wiederholte Zeichen, da diese nach der Burrows-Wheeler-Transformation oft am häufigsten in den Daten vorkommen.

• Der Begriff „Move To Front“ (MTF) wird auch in einem etwas anderen Kontext verwendet, nämlich als Bezeichnung für eine Art dynamisch verketteter Liste . In einer MTF-Liste wird jedes Element beim Zugriff an den Anfang verschoben. ^{[ 4 ]} Dadurch wird sichergestellt, dass die häufiger aufgerufenen Elemente mit der Zeit leichter zugänglich sind.

• „Nach vorne rücken“ von Arturo San Emeterio Campos