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) dadzą lepsze wyniki; może 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 kodowaniaEdytuj

W algorytmie kodowania (i dekodowania) potrzebna jest tablica   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   W tablicy wyszukiwany jest kod odpowiadający   – wynikiem wyszukiwania jest indeks (pozycja)   w tablicy. Na wyjście zapisywany jest indeks   natomiast tablica   modyfikowana w ten sposób, że  -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   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 kodowaniaEdytuj

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   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   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   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   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   i   – 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:         stąd  
  • ciąg zakodowany:       stąd  

Entropia   ciągu zakodowanego jest wyraźnie mniejsza niż entropia   ciągu źródłowego.

Algorytm dekodowaniaEdytuj

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 CEdytuj

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;
    }
}