Move-To-Front

Move-To-Front

Move to front (englisch „Nach vorne verschieben“) ist ein Kodierungsverfahren, das sich gut eignet, um Daten, die aus der Burrows-Wheeler-Transformation stammen, weiterzuverarbeiten, um sie anschließend effektiver komprimieren zu können.

Inhaltsverzeichnis

Format der Ein- und Ausgabedaten

Die Eingabedaten für Move-to-Front sind ein endliches Alphabet und eine Zeichenkette aus diesem Alphabet. Bei dem Alphabet kann es sich zum Beispiel um ASCII oder Unicode handeln, aber auch um Bytes.

Die Ausgabe von Move-to-Front ist eine Folge natürlicher Zahlen, wobei jede der Zahlen kleiner als die Länge des Alphabets ist.

Funktionsweise

Move-to-Front-Kodierung:

  1. Schreibe das komplette Alphabet in eine Zeichenkette a.
  2. Für jedes Zeichen z der Eingabe:
    1. Gib die Position von z in a aus.
    2. Entferne z aus a und füge es vorne wieder an.

Dieser Ablauf führt dazu, dass Zeichen, die häufig in der Eingabe vorkommen, während der Kodierung relativ weit vorne im Alphabet a stehen. Dadurch wiederum enthält die Ausgabe mehr kleine Zahlen als große, und das wiederum ist nützlich, um die Zahlenfolge anschließend zu komprimieren, etwa mit der Huffman-Kodierung.

Move-to-Front-Dekodierung:

  1. Schreibe das komplette Alphabet in eine Zeichenkette a.
  2. Für jede Zahl z der Eingabe:
    1. Gib das Zeichen an der Position z von a aus.
    2. Entferne dieses Zeichen aus a und füge es vorne wieder an.

Die Dekodierung funktioniert fast genauso wie die Kodierung, nur dass die Position, an der das Alphabet geändert wird, schon bekannt ist (die Zahl aus der Eingabe), während sie bei der Kodierung erst bestimmt werden muss.

Beispiel

Die Zeichenkette „Mississippi“ soll mit dem MTF-Algorithmus kodiert werden. Das Alphabet, das dabei verwendet wird, sei (der Kürze wegen) „IMPSimps“.

In der folgenden Tabelle ist Zeichen jeweils das Eingabezeichen, Alphabet das aktuelle Alphabet. Die Ausgabe ist die Position des Zeichens im Alphabet (beginnend mit 0), und Alphabet' ist das neue Alphabet, das dadurch entsteht, dass das Eingabezeichen an den Anfang verschoben wird.

Zeichen Alphabet Ausgabe Alphabet'
M IMPSimps 1 MIPSimps
i MIPSimps 4 iMIPSmps
s iMIPSmps 7 siMIPSmp
s siMIPSmp 0 siMIPSmp
i siMIPSmp 1 isMIPSmp
s isMIPSmp 1 siMIPSmp
s siMIPSmp 0 siMIPSmp
i siMIPSmp 1 isMIPSmp
p isMIPSmp 7 pisMIPSm
p pisMIPSm 0 pisMIPSm
i pisMIPSm 1 ipsMIPSm

Das Ergebnis der Kodierung ist der Text (1,4,7,0,1,1,0,1,7,0,1). Wenn man die Umsortierung des Alphabets weglässt, erhält man zum Vergleich den Text (1,4,7,7,4,7,7,4,6,6,4). Man kann daran sehen, dass nach einer kurzen „Einarbeitungsphase“ (hier 3 Zeichen lang: 1,4,7) relativ häufig kleine Zahlen ausgegeben werden, was gut für eine anschließende Komprimierung ist.

Um MTF wieder zu dekodieren, geht man den umgekehrten Weg:

Die Zahlenfolge (1,4,7,0,1,1,0,1,7,0,1) soll unter Verwendung des Alphabets „IMPSimps“ dekodiert werden. In der folgenden Tabelle ist Position die Zahl aus der zu dekodierenden Zahlenfolge und Zeichen das dekodierte Zeichen. Die Spalten Alphabet und Alphabet' sind genau die gleichen wie in der Kodiertabelle oben.

Position Alphabet Zeichen Alphabet'
1 IMPSimps M MIPSimps
4 MIPSimps i iMIPSmps
7 iMIPSmps s siMIPSmp
0 siMIPSmp s siMIPSmp
1 siMIPSmp i isMIPSmp
1 isMIPSmp s siMIPSmp
0 siMIPSmp s siMIPSmp
1 siMIPSmp i isMIPSmp
7 isMIPSmp p pisMIPSm
0 pisMIPSm p pisMIPSm
1 pisMIPSm i ipsMIPSm

Die Ausgabe der Dekodierung ist also wie erwartet „Mississippi“.

Literatur

  • c't Magazin für computer technik, Hannover 16/00, S. 194: Packen wie noch nie

Weblinks


Wikimedia Foundation.

Игры ⚽ Нужно решить контрольную?

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Move-to-Front — (englisch „Nach vorne verschieben“) ist ein Kodierungsverfahren, das sich gut eignet, um Daten, die aus der Burrows Wheeler Transformation stammen, weiterzuverarbeiten, um sie anschließend effektiver komprimieren zu können. Inhaltsverzeichnis 1… …   Deutsch Wikipedia

  • Move To Front — (englisch „Nach vorne verschieben“) ist ein Kodierungsverfahren, das sich gut eignet, um Daten, die aus der Burrows Wheeler Transformation stammen, weiterzuverarbeiten, um sie anschließend effektiver komprimieren zu können. Inhaltsverzeichnis 1… …   Deutsch Wikipedia

  • Move to front — (englisch „Nach vorne verschieben“, auch: Rotierende Kodierung) ist ein Kodierungsverfahren, das sich gut eignet, um Daten, die aus der Burrows Wheeler Transformation stammen, weiterzuverarbeiten, um sie anschließend effektiver komprimieren zu… …   Deutsch Wikipedia

  • Move-to-front — L algorithme MTF (pour Move to Front, déplacer vers l avant) est un système de transformation de flot utilisé notamment dans le domaine de la compression de données en informatique. Il consiste à remplacer chaque caractère par un indice, donné… …   Wikipédia en Français

  • Move to Front — L algorithme MTF (pour Move to Front, déplacer vers l avant) est un système de transformation de flot utilisé notamment dans le domaine de la compression de données en informatique. Il consiste à remplacer chaque caractère par un indice, donné… …   Wikipédia en Français

  • Move-To-Front — L algorithme MTF (pour Move to Front, déplacer vers l avant) est un système de transformation de flot utilisé notamment dans le domaine de la compression de données en informatique. Il consiste à remplacer chaque caractère par un indice, donné… …   Wikipédia en Français

  • Move-To-Front — Движение к началу (англ. move to front, MTF)  преобразование для кодирования данных (обычно потока байтов), разработанное для улучшения производительности энтропийного кодирования. При хорошей реализации, оно достаточно быстро для… …   Википедия

  • Move-to-front transform — The move to front transform (or MTF) is an encoding of data (typically a stream of bytes) designed to improve the performance of entropy encoding techniques of compression. When efficiently implemented, it is fast enough that its benefits usually …   Wikipedia

  • Move-to-front heuristic — …   Википедия

  • Front loop — is the name given to a trick performed by a windsurfer (also known as a forward loop) whereby the rider performs a jump from a wave face and forces the sail, board and rider to perform a forward somersault in one motion. In its basic form, the… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”