> 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.