Burrowsova–Wheelerova transformace

(přesměrováno z BWT)

Burrowsova-Wheelerova transformace, anglicky Burrows-Wheeler transform (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

editovat

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

editovat