Burrowsova–Wheelerova transformace
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
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)