Burrows-Wheelerova transformace je kódování, které se používá před kompresí, aby zvýšilo její efektivitu. Tato transformace způsobí, že se frekventované symboly a jejich skupiny přesunou blíže k sobě.

Burrows-Wheelerova transformace se typicky používá jako pre-processing před použitím kompresního algoritmu. Po dekompresi se musí opět provést zpětná transformace (podobně jako u každého jiného složeného zobrazení).

Transformace

Nejprve se vytvoří všechny cyklické rotace zadaného řetězce.

Index řádkuPosunutý řetězec
0ABRABABRA (eof)
1(eof) ABRABABRA
2A (eof) ABRABABR
3RA (eof) ABRABAB
4BRA (eof) ABRABA
5ABRA (eof) ABRAB
6BABRA (eof) ABRA
7ABABRA (eof) ABR
8RABABRA (eof) AB
9BRABABRA (eof) A

Potom se všechny řetězce vzniklé rotací lexikograficky seřadí.

Index řádkuPosunutý řetězec
7ABABRA (eof) ABR
0ABRABABRA (eof)
5ABRA (eof) ABRAB
2A (eof) ABRABABR
6BABRA (eof) ABRA
9BRABABRA (eof) A
4BRA (eof) ABRABA
8RABABRA (eof) AB
3RA (eof) ABRABAB
1(eof) ABRABABRA

Z této seřazené posloupnosti řetězců se jako výstup použije poslední sloupec:

R (eof) BRAAABBA

Ve výsledném řetězci je například vidět trojnásobné opakování symbolu A a dvojnásobné opakování symbolu B. To je pro kompresní algoritmy většinou výhodnější, než původní řetězec.

Inverzní transformace

Vstupem pro inverzní transformaci bude řetězec R (eof) BRAAABBA. Tento řetězec se vloží jako poslední sloupec prázdné tabulky.

Index řádkuPosunutý řetězec
0R
1(eof)
2B
3R
4A
5A
6A
7B
8B
9A

Řádky se po každém kroku seřadí lexikograficky:

Index řádkuPosunutý řetězec
0A
1A
2A
3A
4B
5B
6B
7R
8R
9(eof)

Opět vložíme vstupní řetězec R (eof) BRAAABBA:

Index řádkuPosunutý řetězec
0RA
1(eof) A
2BA
3RA
4AB
5AB
6AB
7BR
8BR
9A (eof)

A řádky opět seřadíme:

Index řádkuPosunutý řetězec
0AB
1AB
2AB
3A (eof)
4BA
5BR
6BR
7RA
8RA
9(eof) A

Takto se postupuje stále dál, dokud není tabulka zaplněna.

Index řádkuPosunutý řetězec
0ABABRA (eof) ABR
1ABRABABRA (eof)
2ABRA (eof) ABRAB
3A (eof) ABRABABR
4BABRA (eof) ABRA
5BRABABRA (eof) A
6BRA (eof) ABRABA
7RABABRA (eof) AB
8RA (eof) ABRABAB
9(eof) ABRABABRA

Výsledek zpětné transformace se nachází na řádku, který končí symbolem pro konec vstupu (eof). V tomto případě je to řádek s indexem 1.

ABRABABRA (eof)

Asymptotická složitost

Při implementaci se samozřejmě nemusí vytvářet žádné tabulky v paměti, protože by zabíraly mnoho místa. Proto se pracuje s ukazateli. V případě použití efektivních metod tvorby tabulky a řazení řetězců je asymptotická časová složitost €O(n\cdot\log(n))€. Při použití datové struktury Suffix Array může klesnout až na €O(n)€.

Reference