> mtf | move | front <
// Move-to-Front - Dynamiczne porządkowanie listy dla lepszej kompresji
Samoadaptacyjny
Automatycznie dopasowuje się do lokalnych wzorców w danych.
Wykorzystanie lokalności
Niedawno użyte symbole otrzymują mniejsze indeksy, co poprawia kompresję.
Część bzip2
Używany po BWT w potoku kompresji bzip2.
>> informacje techniczne
Jak działa MTF:
MTF utrzymuje listę wszystkich możliwych symboli. Podczas kodowania symbolu wyprowadzana jest jego bieżąca pozycja na liście, a następnie symbol ten przenoszony jest na początek. Dzięki temu często używane symbole mają małe indeksy, które lepiej się kompresują w późniejszych etapach kodowania entropijnego.
Przykład kodowania:
Tekst: "banana" Lista początkowa: [a,b,c,d,...] "b": indeks 1, przenieś b→początek [b,a,c,d,...] "a": indeks 1, przenieś a→początek [a,b,c,d,...] "n": indeks 13, przenieś n→początek [n,a,b,c,...] "a": indeks 1, przenieś a→początek [a,n,b,c,...] "n": indeks 1, przenieś n→początek [n,a,b,c,...] "a": indeks 1, przenieś a→początek [a,n,b,c,...] Wyjście: [1,1,13,1,1,1]
Dlaczego warto używać MTF:
- >Poprawia lokalną redundancję
- >Dobrze współpracuje z BWT
- >Prosta implementacja
- >Odwracalna transformacja
- >Dostosowuje się do wzorców
>> najczęściej zadawane pytania
Czym jest kodowanie Move-to-Front?
MTF to algorytm przekształcania danych, który koduje każdy symbol jako jego indeks na dynamicznie aktualizowanej liście. Po zakodowaniu symbol jest przenoszony na początek listy, dzięki czemu często używane symbole mają małe indeksy.
Dlaczego używać MTF razem z BWT?
BWT grupuje podobne konteksty i tworzy lokalne powtórzenia. MTF przekształca te powtórzenia w małe liczby (wiele zer i jedynek), które bardzo dobrze kompresują się przy użyciu kodowania długości serii lub kodowania Huffmana.
Jak działa lista w MTF?
Lista zaczyna się od wszystkich 256 możliwych wartości bajtów w ustalonej kolejności. W miarę kodowania symbole używane są przenoszone na początek. Ostatnio używane symbole pozostają blisko początku z małymi indeksami, natomiast rzadko używane przesuwają się w stronę większych indeksów.
MTF a inne transformacje?
MTF został zaprojektowany specjalnie do stosowania po BWT. Sam w sobie nie jest bardzo skuteczny, ale świetnie nadaje się do przekształcania wyjścia BWT w formę łatwą do kompresji. Jest prostszy niż kodowanie arytmetyczne, lecz nieco mniej optymalny.
// Przykład krok po kroku
| # | Symbol | Index | List |
|---|---|---|---|
| 1 | b | 1 | abcdefg… |
| 2 | a | 1 | bacdefg… |
| 3 | n | 13 | abcdefg… |
| 4 | a | 1 | nabcdef… |
| 5 | n | 1 | anbcdef… |
| 6 | a | 1 | nabcdef… |
// Przykłady kodu
Input banana initial list: a b c d ... z (index from 0)
Output 1 1 13 1 1 1
Encode output the index of the symbol, then move it to the front
Decode read index, output list[index], move it to the front
Use after BWT: runs of equal symbols become runs of 0s,
which RLE and Huffman/arithmetic coding then compress well (bzip2)
>> Więcej pytań
P: Do czego służy Move-to-Front?
O: MTF to nie sama kompresja, lecz transformacja: ostatnio użyte symbole dostają małe indeksy. Powstaje dużo 0 i 1, które dobrze kompresuje koder entropijny (Huffman, arytmetyczny).
P: Jak MTF łączy się z transformatą Burrowsa-Wheelera?
O: BWT grupuje jednakowe znaki w serie. MTF zamienia je w ciągi małych liczb, głównie 0. Łańcuch BWT → MTF → RLE → Huffman stosuje bzip2.
P: Czy MTF jest bezstratny i odwracalny?
O: Tak. Dekoder startuje z tej samej listy początkowej i powtarza te same przesunięcia. Lista początkowa (alfabet i kolejność) musi być identyczna po obu stronach.