Štěpán Roh

Alive But Sleepy
About Software Archives Contact @stepanroh Feed Search (CC) BY-NC-ND
← Detaily a příklady použití widgetu GtkTextView
Saturday, November 29, 2003

Burrows-Wheelerova transformace

by Štěpán Roh

Úvod aneb trocha historie

Burrows-Wheelerova transformace (BWT) je metoda, jak přeměnit hůře komprimovatelná data na lépe komprimovatelná. Odtud také název "transformace". Jejími tvůrci jsou Michael Burrows a David Wheeler, kteří v roce 1994 publikovali zprávu o své práci u Digital Systems Research (viz), ve které podrobně rozebrali celý postup komprese pomocí BWT a několika doplňujících algoritmů. Vlastní BWT objevil Wheeler již v roce 1983, ale nikde ji nepublikoval. V současné době se používá např. v bzipu2 (viz), který se postupně stává hlavním komprimačním nástrojem pro Linux (a nejen pro něj).

Transformace

Celá BWT spočívá ve vratném setřídění bloku dat. Výstup obsahuje ta samá data jako byla ta původní, ale jejich struktura je mnohem vhodnější pro kompresi klasickými algoritmy (např. Huffmanovým kódováním).

Jako vstupní blok dat zvolme například řetězec "ema ma maso" (v reálné implementaci se tranformuje najednou mnohem větší blok, ale pro naše účely stačí těchto 11 písmen). Předpokládejme, že tento řetězec je umístěn v kruhovém bufferu a umístěme postupně stejně dlouhé řetězce začínajících na pozici 0 až 10 do bufferu takto : 


	 0 ema ma maso
	 1 ma ma masoe
	 2 a ma masoem
	 3  ma masoema
	 4 ma masoema 
	 5 a masoema m
	 6  masoema ma
	 7 masoema ma 
	 8 asoema ma m
	 9 soema ma ma
	10 oema ma mas

Ve skutečné implementaci se samozřejmě tento buffer nevytváří a reprezentuje se napřiklad pomocí ukazatelů do vstupního bloku dat.

Nyní tuto tabulku lexikograficky (tj. dle abecedy) setřiďme po řádcích. 


	   F         L
	 0  ma masoema
	 1  masoema ma
	 2 a ma masoem
	 3 a masoema m
	 4 asoema ma m
	 5 ema ma maso		<--
	 6 ma ma masoe
	 7 ma masoema 
	 8 masoema ma 
	 9 oema ma mas
	10 soema ma ma

Šipkou je označen původní blok dat. Jak vidno, v tabulce jsou navíc ještě dvě značky. F označuje první sloupec, kde jsou setříděny všechny znaky vstupních dat, v našem případě " aaaemmmos". L označuje poslední sloupec, který není setříděn, zato každý znak v něm obsažený je prefixovým znakem pro řetězec začínající ve stejném řádku ve sloupci F (což bude později důležité). Výstupem transformace je sloupec L a tzv. primární index, což je číslo řádku s původními daty. V našem případě ("aammmoe sa", 5). Povšimněte si seskupení stejných písmen k sobě (důvod, proč se výstup tak krásně komprimuje).

Zpětná transformace

Ač se to na první pohled nezdá, tak BWT je skutečně vratná. Nejprve se setřídí sloupec L, čímž vznikne sloupec F (neboli první sloupec setříděného bufferu). Nyní nastává ta horší část.

Máme sloupec F a sloupec L, který je prefixovým sloupcem sloupce F. Tato informace nám stačí, abychom spočetli transformační vektor T. T je jakýmsi řetězcem určujícím návaznost jednotlivých písmen na sebe (tedy před sebe, protože se postupuje odzadu). Podívejme se tedy na způsob, jakým se tvoří.

Podíváme-li se znovu na setříděný buffer, 


	   F         L
	 0  ma masoema
	 1  masoema ma
	 2 a ma masoem
	 3 a masoema m
	 4 asoema ma m
	 5 ema ma maso
	 6 ma ma masoe
	 7 ma masoema 
	 8 masoema ma 
	 9 oema ma mas
	10 soema ma ma

a vezmeme-li v úvahu, že známe pouze sloupce F a L, jak určíme vektor T? Jednak víme, že prvky z L předchází prvkům z F, tzn. že máme dvojice následník (z F) - předchůdce (z L). Ale, jak je spojit do jednoho řetězce? Samozřejmě, mohou se propojit přes stejné prvky (z m-a a a-s vznikne m-a-s). Leč má to háček. Přes jaké prvky, neboť je jich tam více stejných, že? Stačí si všimnout, že jak řetězce začínající v F na nějaký znak (např. "a"), tak ty začínající v L na ten samý znak, jsou řazeny stejně, od 2. znaku (řetězce v F jsou řazeny i dle 1., ale ten je stejný), tedy, jejich pořadí je shodné, pouze mohou být poněkud vzdáleny od sebe. Tím pádem, hledáme-li předchůdce pro druhé "a" z L, najdeme ho v 2. řádku začínajícím na "a" (s "a" ve sloupci F).

V našem případě je výsledkem transformační vektor T : 


	    0  1  2  3  4  5  6  7  8  9 10
	L   a  a  m  m  m  o  e        s  a
	F         a  a  a  e  m  m  m  o  s
	T   2  3  6  7  8  9  5  0  1  10 4

Vytvořili jsme řetězec "ameosam am " (začali jsem ve sloupci L na pozici 0) převedeno do správného pořadí " ma masoema". Nyní vezměme primární index, který vygenerovala původní transformace, tedy číslo 5. Ten určoval pozici originálního textu v setříděném bufferu, což znamená, že kam se transformuje prvek z pozice 5 ve sloupci L, tam končí vstupní text. V tomto případě je vstupní text "ema ma maso" (ve skutečnosti se primární index bere do úvahy již při vytváření řetězce, kdy se začíná od něj). Jednoduché, ne?

Jaký to mělo význam

Přestože to vypadá jako by se nám povedlo transformovat vstup na ještě větší vstup, není to tak docela pravda. Stačí se podívat na výše uvedený příklad, kdy jsme transformovali text "ema ma maso" na ("aammmoe sa", 5). Již zde je vidět, že se nám podařilo docílit seskupení stejných písmen, což je pro klasické algoritmy jako Huffmanovo či aritmetické kódování mnohem lepší (samozřejmě u tohoto příkladu je to vcelku jedno, neboť je příliš malý). Tohoto jevu je docíleno jednoduše. Uvedu příklad (převzatý od Burrowse a Wheelera - viz) se, v angličtine často se opakujícím, slovem "the" (v našem příkladu jeho roli zastalo "ma"). Kdekoliv se v setříděném bufferu vyskytne na začátku řádky "he" je vysoká pravděpodobnost, že se ve sloupci L vyskytne "t" a jelikož jsou všechny řádky setříděné, tak se všechna takováto "t" vyskytnou blízko sebe.

Doplňkové algoritmy

Ačkoliv by se mohlo zdát, že BWT bohatě stačí, pro lepší kompresi je třeba výstup z transformace ještě trochu pozměnit. Toho se dociluje algoritmem zvaným Move-to-front coding (MTF). Jeho výstup se již komprimuje klasickým Huffmanovým nebo aritmetickým kódováním.

MTF kódování

Vezměme náš příklad výstupu z BWT - ("aammmoe sa", 5). Utvořme si zásobník, kde od pozice 0 (tj. vrcholu) postupně umístíme všech 256 možných hodnot. Pro každý znak ze vstupu je nahlédnuto do zásobníku, kde se nachází, jeho pozice je zapsána na výstup a on sám je v zásobníku posunut na vrchol. Pro náš příklad je výstupem (97, 0, 109, 0, 0, 111, 103, 36, 0, 115, 5, 5) Jak vidno, primární index z BWT se nekóduje. Toto je čistě kvůli přehledu, ve skutečnosti je to zcela jedno. Na našem příkladu to sice není vidět, ale MTF způsobuje snížení hodnot, což vede k většímu se opakování (zde např. čtyři nuly oproti třem "m") a k lepší kompresi.

MTF dekódování

Nic jednoduššího už neexistuje. Zásobník se vytvoří stejným způsobem jako při kódování. Pro každý znak ze vstupu se nejprve nahlédne na danou pozici do zásobníku, na výstup se vypíše tam nalezená hodnota, která se poté přesune na vrchol.

Neduhy a vylepšení

Prvním (a jediným neduhem) je radikální zpomalení při vysoké redundanci dat ve vstupním bloku. To způsobí, že veliká část řetězců z BWT bufferu začíná stejným dlouhým úsekem, což zpomaluje třídění. Mark Nelson (viz) navrhuje zakódovat nejprve vstupní data pomocí RLE komprese, aby se redundance odstranila. V bzipu2 Juliana Sewarda (viz) se používá přidání nadbytečných dat do redundantního kódu.

Vylepšeních navrhují autoři docela dost. Kromě rychlého a úsporného třídícího algoritmu (zájemci nechť nahlédnou sem) například navrhují provést dvě paralelní komprese výstupu z MTF. Odděleně se komprimují řetězce nul a zbytek dat. Zbytek se komprimuje např. Huffmanovým kódováním, zatímco nuly se kódují svou délkou, což přináší znatelnou úsporu (Huffmanovo kódování má limit 1 bit na 1 byte zatímco takto by šlo dosáhnout konstantních cca. 17 bitů na libovolnou délku). Taktéž kódování MTF se dá zlepšit tak, aby méně časté hodnoty nepřesouvalo až na úplný vrchol zásobníku, ale spíš někam doprostřed.

Na závěr

Testy ukazují, že BWT je o dost lepší a přitom stejně rychlá jako Lempel-Ziv komprese a dosahuje téměr takových výsledků jako statistické metody, přičemž není příliš náročná na (horší) implementaci.

Malé srovnání kompresních programů
programkompresevelikost
--143360
gzipLZ7728648
bzip2BWT25463

Použitá literatura a zdroje

← Detaily a příklady použití widgetu GtkTextView ↑Back to top