Datová komprese – princip slovníkových metod, RLE, MTF, BWT, příklady aplikací této třídy kódů

Metoda proudového kódování – RLE

Princip je založena na kompresi opakujících se symbolů. Tato bezztrátová komprese je užívána tam, kde se vyskytují skupiny opakujících se symbolů (znaků). Tyto skupiny se vyjadřují tzv. počítadlem.

Počítadlo = zvláštní symbol tzv. indikátor (zarážka) – počítadlo – znak.

Užití například PCX, nebo preprocessing pro další typ komprese (Huffman)

RLE(Run Length Encoding) někdy též RLC (Run Length Compression) tedy definuje speciální znak, pomocí kterého je identifikována komprimovaná sekvence. Po indikátoru komprimace obvykle následuje znak, který je komprimován a poté následuje údaj o počtu opakování tohoto znaku. Pokud použijeme standardní kódy ASCII nebo EBDIC, je vhodné jako indikátor komprimace (zarážku) vybrat takový symbol, který se jinak ve vstupním proudu dat nevyskytuje. Princip je patrný z následujícího příkladu.

Burrows-Wheelerova transformace(BWT)

BWT byla uvedena roku 1994 pány Davidem Burrowsem a Michaelem Wheelerem, ale vymyšlena byla již v roce 1984 Wheelerem. Je to velice elegantní algoritmus, který přeskupí znaky vstupního textu tak, že shodné znaky budou pravděpodobně vedle sebe (tzn. že to tak nutně být nemusí!). Tato pravděpodobnost, jak si ukážeme, vychází z vlastností jazyka. BWT je vskutku jenom transformace a ne kompresní metoda, čímž se snažím naznačit, že pouze permutuje (přehází) vstup (a přidává jedno pomocné číslo). Ale z vlastností Huffmanova kódu vyplývá, že samotnou transformací bychom jistě lepšího kompresního poměru nedosáhli (četnost znakův textu se permutací nijak nemění) a zde je tedy čas na použití MTF, který většinu transformovaných znaků převádí na nuly. Nechceme-li se zabývat MTF, pak na výstup z BWT použijeme kupříkladu RLE, či nějakou slovníkovou metodu komprese, které stačí opakující se poslopunosti stejných znaků. Po MTF bude mít nula vysokou četnost a text bude nanejvýš vhodný pro zakódování pomocí Huffmanova kódu. Výhodou Huffmanova kódování je to, že se na něj nevztahuje žádný patent a tedy se za jeho použití nemusí platit (to je asi též důvod, proč je použit právě v bzip2).

BWT - kódování

Kódování je u BWT, myslím si, mnohem srozumitelnější než opačný proces, tedy dekódování. Vstupní text budeme zpracovávat po blocích o konstantní velikosti. Čím jsou bloky větší, tím je kódování účinnější (ve výsledné permutaci budou delší posloupnosti stejných znaků). Skutečné účinnosti BWT dosahuje pro bloky délky desítek tisíc znaků (někdy se díky zpracovávání po blocích tomuto algoritmu také říká Block Sorting algorithm). Mějme tedy blok o délce N, vytvoříme si N cyklických posunů o jeden znak doleva (jako bychom měli blok na kruhové pásce a tuto pásku pootočili - první znak se dostane na poslední místo a ostatní se posunou o jednu pozici dopředu). Tímto vzniká pomyslná matice N*N, kde v řádcích jsou právě cyklické posuny původního bloku. Zvolme na ukázku text 'astma mast' (nic lepšího mě nenapadlo:). Pak zmíněná matice vypadá následovně:

Dalším krokem je lexikografické setřídění řádků této matice (setřídění podle abecedy). V další tabulce je stejná matice jako v minulé tabulce, ale tentokrát setříděná:

A to je vše. Poslední sloupec matice je výsledná transformace. K této permutaci musíme ještě přidat číslo řádku, na kterém se v seřazené matici nalézá původní vstup. Což znamená, že blok 'astma mast' se transformoval na 'ammtt aass' a výstup BWT je 'ammtt aass4'. Na začátku jsme si řekli, že výsledkem BWT bude permutace vstupního textu a vskutku tomu tak je. Stačí si totiž uvědomit, že v každém sloupci se nachází všechny znaky vstupního bloku, tudíž je každý sloupec permutací vstupu. Na výstupu můžeme vidět, že se stejná písmena víceméně seskupila k sobě. Vstup byl ovšem zvolen tak, aby tato tendence vynikla, protože jak jsme si již řekli u délky bloku 10 ještě BWT není zdaleka efektivní (u naprosté většiny vstupů této délky nebude tendence ani pozorovatelná). Ale proč mají stejné znaky tendenci seskupovat se k sobě? Hezkým příkladem je anglický určitý člen 'the'. Toto slovo se v anglickém textu vyskytuje velice často. Jaká situace nastane v naší matici? Bude-li se řetězec 'the' v bloku vyskytovat 50 krát, pak v matici bude 50 krát v posledním sloupci znak 't' (díky rotacím). To ale znamená, že na prvních dvou místech se 50 krát ocitnou znaky 'he'. Je tedy velice provděpodobné, že řádky začínající na 'he' budou (po lexikografickém setřídění) blízko u sebe a velice pravděpodobně budou hned pod sebou. A to samé musí samozřejmě platit i pro poslední znaky těchto řádku (to je právě znak 't').

BWT - dekódování

Jak bylo výše uvedeno, dekódování je o něco málo složitější než kódování. Nejdříve je nutno si uvědomit, co vlastně máme pro dekódování k dispozici. Vezmeme-li v úvahu předchozí matici, pak jistě známe poslední sloupec matice, protože tak je definován výstup BWT. Ale nejen to, my máme k dispozici také první sloupec, jelikož obsahuje stejné znaky jako sloupec poslední, jen jsou abecedně seřazeny. A poslední informace, jež máme k dispozici je číslo řádku matice ve kterém se skrýva originální text (poslední znak výstupu BWT). A z těchto tří informací (i když se to možná zdá nepravděpodobné) jsme schopni zrekonstruovat náš vstupní text. Situace vypadá následovně:

Vytvoříme tzv. transformační vektor , což je pole čísel z rozmezí 1-N (indexy řádků), kde na i-tém místě je index řádku, který vznikne rotací i-tého řádku (nebo tak spíše vznikne text v něm). Takový vektor nám úplně postačuje k rekonstrukci vstupu. Známe totiž řádek, kde se vyskytuje první písmeno (nechť je to řádek j) a tedy máme k dispozici první písmeno původního vstupu (první sloupec). A taky víme, kde se nachází druhé písmeno textu - je v prvním sloupci na řádku, kam ukazuje j-tá složka transformačního vektoru (po rotaci se druhé písmeno dostane na první místo)! Nyní tedy zbýva ukázat si, jak vektor sestrojit. Pro písmena, která se vyskytují ve vstupu pouze jednou to není těžké. Řekněme, že jsme na řádku i a v prvním sloupci je písmeno 'x', když na tento řádek zrotujeme do leva, pak se písmeno 'x' dostane na konec. Z toho vyplývá:
vektor[i]='číslo řádku, kde je v posledním sloupci znak 'x''.
Ale co když nastane situace, že se znak 'x' vyskytuje ve vstupu několikrát? Pak v posledním sloupci najdeme více znaků 'x' a který je tedy ten náš zrotovaný? Vezměme první výskyt znaku 'x' v prvním sloupci (prvni od shora), pak mu odpovídá (ukazuje tam transformační vektor) první výskyt 'x' v posledním sloupci. Proč? Vyplývá to z toho, že řetězce jsou lexikograficky setříděny, vyskytuje-li se na prvním místě vícekrát znak 'x', pak se tyto řetězce musí lišit na druhém místě (pro jednoduchost - jinak můžou být stejné i na druhém místě a lišit se až na některém dalším, ale princip je stejný). Po rotaci se tento druhý znak dostane na první místo a znak 'x' na poslední. A právě ten druhý znak nyní rozhoduje o pořadí řádku, čili o pořadí znaku 'x' v posledním sloupci. Tento princip platí stejně i pro i-tý výskyt znaku 'x'. Jak bude tedy vypadat transformační vektor pro náš vstup?

Zde můžeme vidět to, co jsme si o pár řádků výše vysvětlili. Tak například s prvním polem vektoru není žádná potíž, podíváme-li se totiž na předchozí tabulku (kde známe pouze první a poslední sloupcec) je jasné, že první řádek se po zrotování a seřazení ocitl na šestém místě, protože na šestém řádku je v posledním sloupci mezera. Další pole už nejsou tak jednoznačná a je třeba ne ně použít druhou popsanou metodu. První 'a' v prvním sloupci odpovídá podle návodu prvnímu 'a' v posledním slopuci. Druhé 'a' v prvním sloupci odpovídá druhému 'a' v posledním sloupci atd.

MTF (Move-To-Front) filter

Jak jsme si již řekli, MTF transformuje většinu znaků, které mají charakteristiku výstupu BWT (tzn. často se vyskytující stejné znaky v za sebou), na nuly. To je pochopitelně vstup velice výhodný pro, v minulých článcích vysvětlené, Huffmanovo kódování. MTF není zdaleka tak 'složitý' jako BWT, jak se hned přesvědčíme.

MTF kódování

K zakódování budeme potřebovat jednu pomocnou strukturu a tou je zásobník naplněný tak, že na i-tém místě v zásobníku je znak s (ASCII) kódem i. Postup kódování je následující. Postupně bereme znaky ze vstupu a na výstup dáváme číslo pozice v zásobníku, kde se znak nachází a znak přesuneme na začátek zásobníku. Výhoda z toho plynoucí pro druh vstupu, který máme, je zřejmá. První znak posloupnosti stejných znaků ve vstupu je kódován číslem své pozice na zásobníku, poté se přesune na začátek zásobníku (jeho pozice je tudíž po tomto přesunu 0) a všechny další (stejné) znaky z posloupnosti se kódují jako 0. Jak bude vypadat náš výstup z BWT (ammtt aass4) po průchodem MTF filtrem?

Možná se divíte, proč se číslo řádku, kde se skrývá originální text netransformovalo jako ostatní znaky. Důvod je ten, že toto číslo je výhodnější ukládat jako integer a ne jako samostatnou posloupnost znaků - číslic, protože pak nejsou problémy při načítání znaků při dekódování (načteme tolik znaků, kolik je velikost bloku a pak jeden integer). Jen pro úplnost - ASCII kódy použitých znaků jsou:

MTF dekódování

Zde není mnoho co říci, protože dekódování u MTF probíhá skoro stejně jako kódvání. Vezmeme poslopunost čísel a budeme postupovat naprosto stejně jako u kódování s tím malým rozdílem, že na výstup nebudeme dávat čísla, nýbrž znaky jim odpovídající.