> 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.
// Gennemregnet eksempel
| # | 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… |
// Kodeeksempler
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)
>> Flere spørgsmål
S: Hvad bruges Move-to-Front til?
S: MTF er ikke komprimering i sig, men en transformation: nyligt brugte symboler får små indeks. Det giver mange nuller og ettaller, som en entropikoder (Huffman, aritmetisk) komprimerer godt.
S: Hvordan hænger MTF sammen med Burrows-Wheeler-transformationen?
S: BWT samler ens tegn i følger. MTF gør dem til følger af små tal, især 0. Kæden BWT → MTF → RLE → Huffman bruges i bzip2.
S: Er MTF tabsfri og reversibel?
S: Ja. Afkoderen starter fra samme startliste og følger de samme flytninger. Startlisten (alfabet og rækkefølge) skal være ens på begge sider.