Move-to-front transformace

Z Wikipedie, otevřené encyklopedie

Move-to-Front (MTF; česky „přesuň na začátek“) transformace je transformace používaná v algoritmech pro kompresi dat. Obvykle se používá po provedení Burrows-Wheelerovy transformace; ještě před použitím entropického kódování. Transformace mění entropii vstupních dat.

Základní myšlenkou je nahrazovat symboly vstupní abecedy za jejich indexy ze seznamu symbolů a naopak (transformace je invertibilní). Přičemž aktuálně kódovaný symbol je přesunut v tomto seznamu vždy na počátek (odtud název). Lokálně tedy platí, že často vyskytující se symboly jsou umístěny blíže začátku seznamu.

Transformace pracuje proudově, nikoli blokově. Data se musejí dekódovat ve stejném pořadí, v jakém byla zakódována, protože enkodér i dekodér si musejí udržovat seznam symbolů a musejí pracovat ve shodě. Seznam má velikost rovnu počtu symbolů vstupní abecedy. Tuto transformaci využívá například kompresní metoda bzip2.

[editovat] Příklad

Bude se kódovat sekvence znaků a…z (řekněme 26 možných symbolů). Na počátku je seznam inicializován znaky v abecedním pořadí, tedy znak a na indexu 1, n na indexu 14. Sekvence znaků "ananas" bude zakódována jako 1,14,2,2,2,19.