> mtf | move | front <
// Move-to-Front - Dynamisk omorganisering av lister for bedre komprimering
Selvtilpassende
Tilpasser seg automatisk lokale mønstre i dataene.
Utnytter lokalitet
Nylig brukte symboler får mindre indekser for bedre komprimering.
En del av bzip2
Brukes etter BWT i bzip2-komprimeringspipelinjen.
>> teknisk info
Hvordan MTF fungerer:
MTF holder en liste over alle mulige symboler. Når et symbol kodes, skrives den gjeldende posisjonen i listen ut, og symbolet flyttes deretter til starten. Dermed får nylig brukte symboler små indekser, som komprimeres bedre med påfølgende entropikoding.
Eksempel på koding:
Tekst: "banana" Startliste: [a,b,c,d,...] "b": indeks 1, flytt b→start [b,a,c,d,...] "a": indeks 1, flytt a→start [a,b,c,d,...] "n": indeks 13, flytt n→start [n,a,b,c,...] "a": indeks 1, flytt a→start [a,n,b,c,...] "n": indeks 1, flytt n→start [n,a,b,c,...] "a": indeks 1, flytt a→start [a,n,b,c,...] Utdata: [1,1,13,1,1,1]
Hvorfor bruke MTF:
- >Forbedrer lokal redundans
- >Fungerer sammen med BWT
- >Enkel implementasjon
- >Reversibel transformasjon
- >Tilpasser seg mønstre
>> ofte stilte spørsmål
Hva er Move-to-Front-koding?
MTF er en datatransformasjonsalgoritme som koder hvert symbol som indeksen i en dynamisk oppdatert liste. Etter at et symbol er kodet, flyttes det til starten av listen slik at ofte brukte symboler får små indekser.
Hvorfor bruke MTF sammen med BWT?
BWT grupperer like kontekster og skaper lokale repetisjoner. MTF gjør disse repetisjonene om til små tall (mange 0 og 1), som komprimeres svært godt med run-length- eller Huffman-koding.
Hvordan fungerer listen i MTF?
Listen starter med alle 256 mulige byteverdier i rekkefølge. Etter hvert som symboler kodes, flyttes de brukte verdiene til starten. Nylig brukte symboler holder seg nær starten med små indekser, mens ubrukte symboler gradvis flyttes til større indekser.
MTF sammenlignet med andre transformasjoner?
MTF er spesielt designet for å brukes etter BWT. Det er ikke veldig effektivt alene, men er svært godt egnet til å gjøre BWT-utdata lett å komprimere. Det er enklere enn aritmetisk koding, men noe mindre optimalt.