Move-to-front transformace

Z Wikipedie, otevřené encyklopedie
Skočit na: Navigace, Hledání

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ší).[1]

Příklad[editovat | editovat zdroj]

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.

Reference[editovat | editovat zdroj]

  1. J. Abel, Post BWT stages of the Burrows–Wheeler compression algorithm. Software: Practice and Experience, 40, pp. 751–777, 2010. doi: 10.1002/spe.982

Externí odkazy[editovat | editovat zdroj]