> 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.
// Gjennomregnet 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ørsmål
S: Hva brukes Move-to-Front til?
S: MTF er ikke komprimering i seg selv, men en transformasjon: nylig brukte symboler får små indekser. Det gir mange nuller og enere som en entropikoder (Huffman, aritmetisk) komprimerer godt.
S: Hvordan henger MTF sammen med Burrows-Wheeler-transformasjonen?
S: BWT samler like tegn i rekker. MTF gjør dem til rekker av små tall, særlig 0. Kjeden BWT → MTF → RLE → Huffman brukes i bzip2.
S: Er MTF tapsfri og reversibel?
S: Ja. Dekoderen starter fra samme startliste og følger de samme flyttingene. Startlisten (alfabet og rekkefølge) må være lik på begge sider.