Move to front - Versionsgeschichte

imported>APPERbot: Bot: Artikel hat keine Einzelnachweise, leeren Abschnitt mit
2025-03-11T03:04:08Z

Bot: Artikel hat keine Einzelnachweise, leeren Abschnitt mit <references entfernt

Neue Seite
'''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 können.

== Format der Ein- und Ausgabedaten ==

Die Eingabedaten für Move-to-Front sind ein endliches [[Alphabet (Informatik)|Alphabet]] und eine Zeichenkette aus diesem Alphabet. Bei dem Alphabet kann es sich zum Beispiel um [[ASCII]] oder [[Unicode]] handeln, aber auch um [[Byte]]s.

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:
# Schreibe das komplette Alphabet in eine Zeichenkette ''a''.
# Für jedes Zeichen ''z'' der Eingabe:
## Gib die Position von ''z'' in ''a'' aus.
## 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:
# Schreibe das komplette Alphabet in eine Zeichenkette ''a''.
# Für jede Zahl ''z'' der Eingabe:
## Gib das Zeichen an der Position ''z'' von ''a'' aus.
## 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) „ABCIMPSabcimps“.

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

{| class="wikitable"
|- class="hintergrundfarbe5"
! Zeichen || Alphabet || Ausgabe || Alphabet'
|-
| M || ABCIMPSabcimps || 4 || MABCIPSabcimps
|-
| i || MABCIPSabcimps || 10 || iMABCIPSabcmps
|-
| s || iMABCIPSabcmps || 13 || siMABCIPSabcmp
|-
| s || siMABCIPSabcmp || 0 || siMABCIPSabcmp
|-
| i || siMABCIPSabcmp || 1 || isMABCIPSabcmp
|-
| s || isMABCIPSabcmp || 1 || siMABCIPSabcmp
|-
| s || siMABCIPSabcmp || 0 || siMABCIPSabcmp
|-
| i || siMABCIPSabcmp || 1 || isMABCIPSabcmp
|-
| p || isMABCIPSabcmp || 13 || pisMABCIPSabcm
|-
| p || pisMABCIPSabcm || 0 || pisMABCIPSabcm
|-
| i || pisMABCIPSabcm || 1 || ipsMABCIPSabcm
|}

Das Ergebnis der Kodierung ist der Text (4,10,13,0,1,1,0,1,13,0,1). Wenn man die Umsortierung des Alphabets weglässt, erhält man zum Vergleich den Text (4,10,13,13,10,13,13,10,12,12,10). Man kann daran sehen, dass nach einer kurzen „Einarbeitungsphase“ (hier 3 Zeichen lang: 4,10,13) 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 (4,10,13,0,1,1,0,1,13,0,1) soll unter Verwendung des Alphabets „ABCIMPSabcimps“ 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<nowiki>'</nowiki>'' sind genau die gleichen wie in der Kodiertabelle oben.

{| class="wikitable"
|- class="hintergrundfarbe5"
! Position || Alphabet || Zeichen || Alphabet'
|-
| 4 || ABCIMPSabcimps || M || MABCIPSabcimps
|-
| 10 || MABCIPSabcimps || i || iMABCIPSabcmps
|-
| 13 || iMABCIPSabcmps || s || siMABCIPSabcmp
|-
| 0 || siMABCIPSabcmp || s || siMABCIPSabcmp
|-
| 1 || siMABCIPSabcmp || i || isMABCIPSabcmp
|-
| 1 || isMABCIPSabcmp || s || siMABCIPSabcmp
|-
| 0 || siMABCIPSabcmp || s || siMABCIPSabcmp
|-
| 1 || siMABCIPSabcmp || i || isMABCIPSabcmp
|-
| 13 || isMABCIPSabcmp || p || pisMABCIPSabcm
|-
| 0 || pisMABCIPSabcm || p || pisMABCIPSabcm
|-
| 1 || pisMABCIPSabcm || i || ipsMABCIPSabcm
|}

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

== Literatur ==
* {{Literatur| Titel = Packen wie noch nie| Verlag = Verlag Heinz Heise| Ort = Hannover| ISSN = 0724-8679| Sammelwerk= c’t Magazin für Computer Technik| Nummer = 16| Jahr = 2000| Seiten = 194}}

[[Kategorie:Datenkompression]]