> mtf | move | front <
// Move-to-Front - Dynamisk listeomrokering for bedre komprimering
Selvtilpassende
Tilpasser sig automatisk lokale mønstre i data.
Udnytter lokalitet
Nyligt brugte symboler får mindre indeks for bedre komprimering.
Del af bzip2
Bruges efter BWT i bzip2-komprimeringskæden.
>> teknisk info
Sådan fungerer MTF:
MTF vedligeholder en liste over alle mulige symboler. Når et symbol kodes, outputtes dets aktuelle position i listen, hvorefter symbolet flyttes til fronten. Det giver nyligt brugte symboler små indeks, som komprimeres bedre med efterfølgende entropikodning.
Kodningseksempel:
Tekst: "banana" Startliste: [a,b,c,d,...] "b": indeks 1, flyt b→front [b,a,c,d,...] "a": indeks 1, flyt a→front [a,b,c,d,...] "n": indeks 13, flyt n→front [n,a,b,c,...] "a": indeks 1, flyt a→front [a,n,b,c,...] "n": indeks 1, flyt n→front [n,a,b,c,...] "a": indeks 1, flyt a→front [a,n,b,c,...] Output: [1,1,13,1,1,1]
Hvorfor bruge MTF:
- >Forbedrer lokal redundans
- >Arbejder sammen med BWT
- >Simpel implementering
- >Reversibel transform
- >Tilpasser sig mønstre
>> ofte stillede spørgsmål
Hvad er Move-to-Front-kodning?
MTF er en datatransformationsalgoritme, der koder hvert symbol som dets indeks i en dynamisk opdateret liste. Efter hvert symbol er kodet flyttes det til fronten, så ofte brugte symboler får små indeks.
Hvorfor bruge MTF sammen med BWT?
BWT samler lignende kontekster og skaber lokale gentagelser. MTF omsætter derefter gentagelserne til små tal (mange 0'er og 1-taller), som komprimeres meget godt med f.eks. run length- eller Huffman-kodning.
Hvordan fungerer listen?
Listen starter med alle 256 mulige byteværdier i rækkefølge. Når symboler kodes, flyttes de til fronten. Nyligt anvendte symboler forbliver tæt på fronten med små indeks, mens ubrugte symboler glider mod større indeks.
MTF kontra andre transformationer?
MTF er designet specifikt til at blive brugt efter BWT. Det er ikke særligt effektivt alene, men er meget godt til at gøre BWT-output nemt at komprimere. Det er enklere end aritmetisk kodning, men mindre optimalt.