Obsah:
- Definice - Co znamená Burrows-Wheeler Transform (BWT)?
- Techopedia vysvětluje Burrows-Wheeler Transform (BWT)
Definice - Co znamená Burrows-Wheeler Transform (BWT)?
Burrows-Wheelerova transformace (BWT) je algoritmus, který bere bloky dat, například řetězce, a přeskupuje je do běhů podobných znaků. Po transformaci obsahuje výstupní blok stejné přesné datové prvky před začátkem, ale liší se v pořadí. Povaha algoritmu má tendenci umisťovat vedle sebe podobné znaky, což usnadňuje komprimaci výsledných dat. Proto se používá v mnoha kompresních algoritmech.
Techopedia vysvětluje Burrows-Wheeler Transform (BWT)
Algoritmus transformace Burrows-Wheeler je relativně nový algoritmus vynalezený v roce 1994 Michaelem Burrowsem a Davidem Wheelerem a založený na nepublikované transformaci objevené Wheelerem v roce 1983, zveřejněné v jejich příspěvku „Blokovací třídění bezeztrátových datových kompresních algoritmů.“
V nejzákladnější podobě BWT vezme blok dat, jako je řetězec, přidá znak EOF a poté roztřídí všechny rotace tohoto řetězce do lexikografického pořadí. Algoritmus ilustrují následující pseudokód nebo kroky:
- Vytvořte tabulku, která obsahuje řádky, které představují všechny možné rotace řetězce o jeden přírůstek.
- Seřadit všechny řádky podle abecedy.
- Výstup posledního sloupce tabulky.
Například: slovo „banán“; přidání znaku EOF ho změní na „banán $“, poté použijeme algoritmus:
1. Vytvořte tabulku s řádky představujícími všechny možné rotace:
banán $
anana $ b
nana $ ba
ana $ zákaz
na $ bana
$ banan
$ banán
2. Řadit řádky abecedně / lexikograficky podle prvního sloupce:
$ banán
$ banan
ana $ zákaz
anana $ b
banán $
nana $ ba
na $ bana
3.Vraťte poslední sloupec jako výstup BWT: annb $ aa
Výsledný řetězec se snáze komprimuje, protože opakované znaky jsou seskupeny vedle sebe. S transformovanými daty však musí být uložena další data, aby bylo možné provést reverzní transformaci. I když výsledná transformovaná data jsou větší než původní forma, ale její kompresní charakteristika se mnohonásobně zvýšila, což v podstatě činí „bezplatnou“ metodu pro zlepšení účinnosti kompresních metod.
