Obsah:
- Definícia - Čo znamená Burrows-Wheeler Transform (BWT)?
- Techopedia vysvetľuje transformáciu Burrows-Wheeler (BWT)
Definícia - Čo znamená Burrows-Wheeler Transform (BWT)?
Burrows-Wheelerova transformácia (BWT) je algoritmus, ktorý berie bloky údajov, napríklad reťazce, a usporiada ich do cyklov podobných znakov. Po transformácii obsahuje výstupný blok rovnaké presné dátové prvky pred začatím, ale líši sa v usporiadaní. Povaha algoritmu má tendenciu umiestňovať podobné znaky vedľa seba, takže výsledné poradie údajov sa ľahšie komprimuje. Preto sa používa v mnohých kompresných algoritmoch.
Techopedia vysvetľuje transformáciu Burrows-Wheeler (BWT)
Algoritmus transformácie Burrows-Wheeler je relatívne nový algoritmus, ktorý vymysleli v roku 1994 Michael Burrows a David Wheeler a ktorý vychádza z nepublikovanej transformácie objavenej Wheelerom v roku 1983, uverejnenej vo svojom článku „Blokovo-triediaci bezstratový algoritmus kompresie dát“.
V najzákladnejšej podobe BWT berie blok údajov, napríklad reťazec, pridáva znak EOF a potom triedi všetky rotácie tohto reťazca do lexikografického poradia. Algoritmus ilustrujú nasledujúce pseudokódy alebo kroky:
- Vytvorte tabuľku, ktorá obsahuje riadky, ktoré predstavujú všetky možné rotácie reťazca o jeden prírastok.
- Zoradiť všetky riadky podľa abecedy.
- Výstup posledného stĺpca tabuľky.
Napríklad: slovo „banán“; pridanie znaku EOF ho zmení na „banánový $“, potom použijeme algoritmus:
1. Vytvorte tabuľku s riadkami, ktoré predstavujú všetky možné rotácie:
banán $
Anana $ b
nana $ ba
Zákaz ana $
na $ bana
a $ banan
$ banán
2. Riadky usporiadajte podľa abecedy / lexikograficky podľa prvého stĺpca:
$ banán
a $ banan
Zákaz ana $
Anana $ b
banán $
nana $ ba
na $ bana
3.Vráťte posledný stĺpec ako výstup BWT: annb $ aa
Výsledný reťazec sa ľahšie komprimuje, pretože opakujúce sa znaky sú zoskupené vedľa seba. S transformovanými údajmi je však potrebné uložiť ďalšie údaje, aby bolo možné vykonať spätnú transformáciu. Výsledné transformované údaje sú síce väčšie ako pôvodná forma, ale ich kompresná charakteristika sa mnohonásobne zvýšila, čo v podstate robí z tejto metódy „bezplatnú“ metódu zlepšovania efektívnosti kompresných metód.
