Burrowsova–Wheelerova transformace

Burrowsova-Wheelerova transformace (anglicky Burrows-Wheeler transform –⁠⁠⁠⁠⁠⁠ zkráceně BWT) je pomocný algoritmus používaný v technikách komprese dat. Transformaci objevili Michael Burrows a David Wheeler.

Samotná transformace data nijak nekomprimuje. Způsobí pouze změnu pořadí symbolů (permutaci). V případě, že vstupní řetězec symbolů má několik podřetězců, které se v něm vyskytují vícekrát, bude mít výstupní řetězec několik míst, kde se vyskytuje stejný symbol několikrát za sebou. To je výhodné například pro RLE kompresi. Transformace ovšem přidává k výstupnímu řetězci informaci o umístění symbolu konce původního řetězce (tzv. EOF symbol).

Princip této transformace spočívá v tom, že se ze vstupního řetězce (zakončeného symbolem EOF) vytvoří všechny jeho možné rotace. Tyto se dále lexikograficky seřadí. Ze seřazeného pole rotací původního řetězce se do výstupního zapíše postupně od počátku poslední symbol z každé rotace. Na výstupu je tedy transformovaný vstup rozšířený o ukazatel na konec původního řetězce.

K transformaci se používá datová struktura sufixový strom, která umožňuje rychlé operace s řetězci. Tuto transformaci využívá například kompresní metoda bzip2.

Příklad

Příklad transformace textového řetězce "^BANANA@" (zavináč značí EOF symbol) je řetězec "BNN^AA@A".

Burrowsova-Wheelerova transformace
Vstup	Všechny rotace	Seřazení rotací	Výstup
^BANANA@	^BANANA@ @^BANANA A@^BANAN NA@^BANA ANA@^BAN NANA@^BA ANANA@^B BANANA@^	ANANA@^B ANA@^BAN A@^BANAN BANANA@^ NANA@^BA NA@^BANA ^BANANA@ @^BANANA	BNN^AA@A

Vstupem zpětné transformace je výstup původní transformace, tedy poslední sloupec seřazené tabulky. Pomocí něj můžeme získat první sloupec jeho seřazením. Známe-li první a poslední sloupec, známe všechny dvojice po sobě následujících znaků, které se v textu vyskytují – a jejich seřazením dostaneme první a druhý sloupec. Takto postupně zrekonstruujeme celou tabulku a posléze odečteme původní řetězec.

Zpětná transformace
Vstup
BNN^AA@A
1 známý sloupec	seřazené	2 známé sloupce	seřazené
B N N ^ A A @ A	A A A B N N ^ @	BA NA NA ^B AN AN @^ A@	AN AN A@ BA NA NA ^B @^
3 známý sloupec	seřazené	4 známé sloupce	seřazené
BAN NAN NA@ ^BA ANA ANA @^B A@^	ANA ANA A@^ BAN NAN NA@ ^BA @^B	BANA NANA NA@^ ^BAN ANAN ANA@ @^BA A@^B	ANAN ANA@ A@^B BANA NANA NA@^ ^BAN @^BA
5 známých sloupů	seřazené	6 známých sloupců	seřazené
BANAN NANA@ NA@^B ^BANA ANANA ANA@^ @^BAN A@^BA	ANANA ANA@^ A@^BA BANAN NANA@ NA@^B ^BANA @^BAN	BANANA NANA@^ NA@^BA ^BANAN ANANA@ ANA@^B @^BANA A@^BAN	ANANA@ ANA@^B A@^BAN BANANA NANA@^ NA@^BA ^BANAN @^BANA
7 známých sloupů	seřazené	8 známých sloupců	seřazené
BANANA@ NANA@^B NA@^BAN ^BANANA ANANA@^ ANA@^BA @^BANAN A@^BANA	ANANA@^ ANA@^BA A@^BANA BANANA@ NANA@^B NA@^BAN ^BANANA @^BANAN	BANANA@^ NANA@^BA NA@^BANA ^BANANA@ ANANA@^B ANA@^BAN @^BANANA A@^BANAN	ANANA@^B ANA@^BAN A@^BANAN BANANA@^ NANA@^BA NA@^BANA ^BANANA@ @^BANANA
Výstup
^BANANA@

Externí odkazy

• Burrows, M.; Wheeler, David J., A block-sorting lossless data compression algorithm. Archivováno 7. 6. 2011 na Wayback Machine. –⁠⁠⁠⁠⁠⁠ původní článek s popisem transformace na stránkách HP Labs (anglicky)