Move To Front

Move To Front (MTF) – prosta transformacja strumienia danych, używana jako część niektórych procesów kompresji, której zastosowanie może spowodować zmniejszenie entropii. Co za tym idzie, algorytmy kompresji zależne od tej własności (kodowanie Shannona, Shannona-Fano, Huffmana, arytmetyczne) dają lepsze wyniki; mogą także wyprodukować sekwencje lepiej kompresowane metodą RLE.

To, czy zastosowanie MTF rzeczywiście doprowadzi do zmniejszenia entropii, zależy od danych – zmniejszenie entropii występuje, gdy częstotliwości występowania symboli wykazują lokalną spójność.

Dane o takiej charakterystyce są tworzone przez transformatę Burrowsa-Wheelera, dlatego MTF jest zwykle używana w połączeniu właśnie z nią. (Uwaga: sama transformata Burrowsa-Wheelera nie powoduje zmniejszenia entropii).

Jak wspomniano, algorytm kodowania i dekodowania jest bardzo prosty, dlatego jego implementacje są bardzo efektywne.

Algorytm kodowania

W algorytmie kodowania (i dekodowania) potrzebna jest tablica $L$ przechowująca kody wszystkich symboli – zwykle będzie to 256 kodów ASCII, tak jak w przykładowym programie. Początkowo w tablicy kody są uporządkowane rosnąco.

W jednym kroku kodowania rozpatruje się jeden symbol $s.$ W tablicy wyszukiwany jest kod odpowiadający $s$ – wynikiem wyszukiwania jest indeks (pozycja) $i$ w tablicy. Na wyjście zapisywany jest indeks $i,$ natomiast tablica $L$ modyfikowana w ten sposób, że $i$-ty element jest przesuwany na pierwszą pozycję tablicy (na początek).

Jeśli kolejne symbole występują mniej więcej tak samo często (lokalna spójność częstotliwości), wówczas na początkowych pozycjach tablicy będą występowały właśnie one, co spowoduje, że na wyjściu będą pojawiały się indeksy $i$ o małych wartościach. (W zamieszczonym niżej przykładzie zostało to przerysowane: na wyjściu dominuje jeden indeks).

Schemat przesuwania może być też inny, np. symbol jest umieszczany nie na pierwszej, lecz na drugiej pozycji, zaś przemieszczenie na pierwszą pozycję jest możliwe tylko z drugiej pozycji (w ten sposób dominujący indeks ma szansę nie zostać usunięty z pierwszej pozycji); jeszcze inny sposób to przesuwanie tylko o jedną pozycję w stronę początku (zapobiega szybkiej zmianie indeksów).

Przykład kodowania

Dla uproszczenia zamiast 256 niech będą cztery symbole a, b, c, d. Zakodowany zostanie ciąg ddddddbbbbbccccaaa.

Początkowo tablica L ma poniższą postać, wyjście W jest puste.

1 2 3 4
L = (a, b, c, d)
W = ()

Pierwszy symbol $d$ występuje na pozycji 4.: na wyjście wypisywana jest 4, a symbol przesuwany na początek L.

1 2 3 4
L = (d, a, b, c)
W = (4)

Kolejne pięć liter $d$ występuje na pozycji 1.: na wyjściu pojawia się teraz pięć jedynek (tablica L nie zmienia się).

1 2 3 4
L = (d, a, b, c)
W = (4, 1, 1, 1, 1, 1)

Następnie występuje pierwszy symbol $b,$ który znajduje się na pozycji 3.: na wyjście wypisywana jest 3, a symbol przesuwany na początek L.

1 2 3 4
L = (b, d, a, c)
W = (4, 1, 1, 1, 1, 1, 3)

Kolejne cztery symbole $b$ występuje na pozycji 1.: na wyjściu pojawiają się teraz cztery jedynki (tablica L się nie zmienia).

1 2 3 4
L = (b, d, a, c)
W = (4, 1, 1, 1, 1, 1, 3, 1, 1, 1, 1)

Podobnie rzecz ma się z następnymi podciągami liter $c$ i $a$ – ostatecznie ciąg wyjściowy ma postać:

W = (4, 1, 1, 1, 1, 1, 3, 1, 1, 1, 1, 4, 1, 1, 1, 4, 1, 1)

Widać, że na wyjściu pojawiły się trzy symbole – o jeden mniej niż na wejściu. Widać również, że jeden z tym symboli występuje o wiele częściej niż pozostałe.

Jeśli obliczyć entropię dla danych wejściowych i zakodowanych, mamy:

• ciąg źródłowy: $p_{a}={\frac {3}{18}},$ $p_{b}={\frac {5}{18}},$ $p_{c}={\frac {4}{18}},$ $p_{d}={\frac {6}{18}},$ stąd $H_{S}(p_{a},p_{b},p_{c},p_{d})=1{,}954;$
• ciąg zakodowany: $p_{1}={\frac {14}{18}},$ $p_{3}={\frac {1}{18}},$ $p_{4}={\frac {3}{18}},$ stąd $H_{Z}(p_{1},p_{3},p_{4})=0{,}944.$

Entropia $H_{Z}$ ciągu zakodowanego jest wyraźnie mniejsza niż entropia $H_{S}$ ciągu źródłowego.

Algorytm dekodowania

Algorytm dekodowania jest praktycznie taki sam: występuje taka sama tablica i wraz z pojawianiem się kolejnych indeksów wejściowych modyfikowana tak, jak przy kodowaniu.

Przykładowa implementacja w C

void mtf_encode_buf (unsigned char *buf_in, unsigned char *buf_out, int size)
{
 int i,j;
 unsigned char state[256];

 for(i=0; i <256; ++i)
 state[i] = i;
 for (i=0; i<size; i++) {
 buf_out[i] = state[buf_in[i]];
 for (j=0; j<256; ++j)
 if (state[j] < state[buf_in[i]])
 ++state[j];
 state[buf_in[i]] = 0;
 }
}

void mtf_decode_buf (unsigned char *buf_in, unsigned char *buf_out, int size)
{
 int i,j;
 unsigned char state[256];
 unsigned char tmp;

 for (i=0; i<256; ++i)
 state[i] = i;
 for (i=0; i<size; ++i) {
 buf_out[i] = state[buf_in[i]];
 tmp = state[buf_in[i]];
 for (j=buf_in[i]; j ; --j)
 state[j] = state[j-1];
 state[0] = tmp;
 }
}