> 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.