Burrows-Wheelerova transformace
Kategorie: Nezařazeno (celkem: 23181 referátů a seminárek)
Informace o referátu:
- Přidal/a: anonymous
- Datum přidání: 12. srpna 2008
- Zobrazeno: 1785×
- Licence: GNU Free Documentation License
- Seznam autorů a změn
- Vyloučení odpovědnosti
Příbuzná témata
Burrows-Wheelerova transformace
Burrows-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 klasicky setřídí. Ze setříděné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. Příklad transformace textového řetězce "^BANANA@" (zavináč značí EOF symbol) je řetězec "BNN^AA@A". Příklad komprese je podrobně vysvětlen na en:Burrows-Wheeler transform.
Tuto transformaci využívá například kompresní metoda bzip2.