Move-to-front transformace

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í Burrowsovy-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 kodér i dekodér si musejí udržovat seznam symbolů a musejí pracovat ve shodě. Seznam má velikost rovnu počtu symbolů vstupní abecedy.

Typicky se používá v kompresních metodách jako druhá fáze po Burrowsově-Wheelerově transformaci. Právě tyto transformace využívá například kompresní metoda bzip2.

Metoda byla několikrát vylepšena a následně nahrazena sofistikovanějšími algoritmy (Inversion frequencies, Weighted frequency count a další).

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.

Externí odkazy

• (anglicky) J. L. Bentley, D. D. Sleator, R. E. Tarjan, V. K. Wei, A Locally Adaptive Data Compression Scheme – původní článek s popisem transformace