> mtf | move | front <
// Move-to-Front - Dynamisch herschikken van lijsten voor betere compressie
Zelfadaptief
Past zich automatisch aan lokale patronen in de gegevens aan.
Benut localiteit
Recent gebruikte symbolen krijgen kleinere indexen voor betere compressie.
Onderdeel van bzip2
Wordt gebruikt na BWT in de bzip2-compressiepijplijn.
>> technische info
Hoe MTF werkt:
MTF onderhoudt een lijst met alle mogelijke symbolen. Bij het coderen van een symbool wordt de huidige positie in de lijst uitgegeven en daarna wordt het symbool naar voren verplaatst. Hierdoor krijgen recent gebruikte symbolen kleine indexen, die met daaropvolgende entropiecodering beter comprimeren.
Voorbeeld van codering:
Tekst: "banana" Initiële lijst: [a,b,c,d,...] "b": index 1, verplaats b→voor [b,a,c,d,...] "a": index 1, verplaats a→voor [a,b,c,d,...] "n": index 13, verplaats n→voor [n,a,b,c,...] "a": index 1, verplaats a→voor [a,n,b,c,...] "n": index 1, verplaats n→voor [n,a,b,c,...] "a": index 1, verplaats a→voor [a,n,b,c,...] Uitvoer: [1,1,13,1,1,1]
Waarom MTF gebruiken:
- >Verbetert lokale redundantie
- >Werkt samen met BWT
- >Eenvoudige implementatie
- >Omkeerbare transformatie
- >Past zich aan patronen aan
>> veelgestelde vragen
Wat is Move-to-Front-codering?
MTF is een datatransformatie-algoritme dat elk symbool codeert als zijn index in een dynamisch bijgewerkte lijst. Na het coderen wordt het symbool naar voren verplaatst, zodat vaak gebruikte symbolen kleine indexen hebben.
Waarom MTF samen met BWT gebruiken?
BWT groepeert vergelijkbare contexten en creëert lokale herhalingen. MTF zet deze herhalingen om in kleine getallen (veel nullen en enen) die zeer goed comprimeren met run-length- of Huffman-codering.
Hoe werkt de lijst precies?
De lijst start met alle 256 mogelijke bytewaarden in volgorde. Terwijl symbolen worden gecodeerd, verplaatsen gebruikte waarden naar voren. Recent gebruikte symbolen blijven bij de voorkant met kleine indexen, terwijl ongebruikte symbolen naar grotere indexen opschuiven.
MTF versus andere transformaties?
MTF is specifiek ontworpen om na BWT te worden gebruikt. Op zichzelf is het minder effectief, maar het is uitstekend in het omzetten van BWT-uitvoer naar een vorm die goed comprimeert. Het is eenvoudiger dan aritmetische codering, maar iets minder optimaal.