> mtf | move | front <
// Move-to-Front - Dynamisk omlistning för bättre komprimering
Självanpassande
Anpassar sig automatiskt efter lokala mönster i datat.
Utnyttjar lokalitet
Nyligen använda symboler får lägre index och komprimeras bättre.
Del av bzip2
Används efter BWT i bzip2‑komprimeringskedjan.
>> teknisk info
Hur MTF fungerar:
MTF upprätthåller en lista över alla möjliga symboler. När en symbol kodas skrivs dess aktuella position i listan ut och symbolen flyttas sedan till början. Detta gör att nyligen använda symboler får låga index, vilket ger bättre komprimering med efterföljande entropikodning.
Exempel på kodning:
Text: "banana" Startlista: [a,b,c,d,...] "b": index 1, flytta b→början [b,a,c,d,...] "a": index 1, flytta a→början [a,b,c,d,...] "n": index 13, flytta n→början [n,a,b,c,...] "a": index 1, flytta a→början [a,n,b,c,...] "n": index 1, flytta n→början [n,a,b,c,...] "a": index 1, flytta a→början [a,n,b,c,...] Utdata: [1,1,13,1,1,1]
Varför använda MTF:
- >Förbättrar lokal redundans
- >Fungerar tillsammans med BWT
- >Enkel implementation
- >Reversibel transformation
- >Anpassar sig efter mönster
>> vanliga frågor
Vad är Move-to-Front-kodning?
MTF är en datatransformationsalgoritm som kodar varje symbol som dess index i en dynamiskt uppdaterad lista. Efter varje kodning flyttas symbolen till början av listan, så att ofta använda symboler får låga index.
Varför använda MTF ihop med BWT?
BWT grupperar liknande kontexter och skapar lokala upprepningar. MTF omvandlar dessa upprepningar till små tal (många nollor och ettor) som komprimeras mycket bra med run‑length‑ eller Huffman‑kodning.
Hur fungerar listan i MTF?
Listan startar med alla 256 möjliga bytevärden i ordning. När symboler kodas flyttas använda värden till början. Nyligen använda symboler stannar nära början med låga index, medan sällan använda hamnar vid högre index.
MTF jämfört med andra transformationer?
MTF är särskilt designat för att användas efter BWT. Ensamt är det inte så effektivt, men det är utmärkt på att göra BWT‑utdata lättare att komprimera. Det är enklare än aritmetisk kodning men något mindre optimalt.
// Genomgånget exempel
| # | 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… |
// Kodexempel
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)
>> Fler frågor
F: Vad används Move-to-Front till?
S: MTF är inte komprimering i sig utan en transform: nyligen använda symboler får små index. Det ger många nollor och ettor som en entropikodare (Huffman, aritmetisk) komprimerar bra.
F: Hur hänger MTF ihop med Burrows-Wheeler-transformen?
S: BWT samlar lika tecken i följder. MTF gör dem till följder av små tal, främst 0. Kedjan BWT → MTF → RLE → Huffman används i bzip2.
F: Är MTF förlustfri och reversibel?
S: Ja. Avkodaren startar från samma ursprungslista och följer samma förflyttningar. Ursprungslistan (alfabet och ordning) måste vara identisk på båda sidor.