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). +more 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ě. +more 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. +more Sekvence znaků „ananas“ bude zakódována jako 1, 14, 2, 2, 2, 19.

Reference

Externí odkazy

[url=http://www. cs. +morecmu. edu/~sleator/papers/Adaptive-data-compression. htm]J. L. Bentley, D. D. Sleator, R. E. Tarjan, V. K. Wei, A Locally Adaptive Data Compression Scheme[/url] - původní článek s popisem transformace.

Kategorie:Kompresní algoritmy