Kazalo:
- Opredelitev - Kaj pomeni transformacija Burrows-Wheeler (BWT)?
- Tehopedija pojasnjuje transformacijo Burrows-Wheeler (BWT)
Opredelitev - Kaj pomeni transformacija Burrows-Wheeler (BWT)?
Preobrazba Burrows-Wheeler (BWT) je algoritem, ki prevzame bloke podatkov, kot so strune, in jih preuredi v zaporedje podobnih znakov. Po pretvorbi izhodni blok vsebuje enake natančne podatkovne elemente, preden se je začel, vendar se razlikuje po vrstnem redu. Narava algoritma ponavadi postavlja podobne znake drug ob drugega, kar posledično naredi podatke lažje stisne. Zato se uporablja v mnogih algoritmih stiskanja.
Tehopedija pojasnjuje transformacijo Burrows-Wheeler (BWT)
Algoritem preobrazbe Burrows-Wheeler je relativno nov algoritem, ki sta ga leta 1994 izumila Michael Burrows in David Wheeler in temelji na neobjavljeni preobrazbi, ki jo je odkril Wheeler leta 1983 in je objavil v svojem prispevku "Algoritem stiskanja podatkov brez izgub."
Najosnovnejši BWT prevzame niz podatkov, kot je niz, doda znak EOF in nato razvrsti vse rotacije tega niza v leksikografski vrstni red. Naslednji psevdokod ali koraki ponazarjajo algoritem:
- Ustvari tabelo, ki vsebuje vrstice, ki predstavljajo vse možne enostopenjske rotacije niza.
- Razvrsti vse vrstice po abecednem redu.
- Vstavite zadnji stolpec tabele.
Na primer: beseda „banana“; Če dodamo znak EOF, ga pretvorimo v "banana $", nato uporabimo algoritem:
1. Ustvari tabelo z vrsticami, ki predstavljajo vse možne rotacije:
banana $
anana $ b
nana $ ba
ana $ ban
na $ bana
$ banan
$ banana
2. Vrstice razvrstite po abecedi / leksikografsko na podlagi prvega stolpca:
$ banana
$ banan
ana $ ban
anana $ b
banana $
nana $ ba
na $ bana
3.Ponovno vrnite zadnji stolpec kot izhod BWT: annb $ aa
Nastali niz je lažje stisniti, ker so ponovljeni znaki združeni drug ob drugem. Vendar pa je treba s preoblikovanimi podatki shraniti dodatne podatke, da se lahko opravi obratna transformacija. Čeprav so dobljeni preoblikovani podatki večji od svoje prvotne oblike, vendar je njegova značilnost stisljivosti večkrat povečana, kar v bistvu omogoča "brezplačno" metodo za izboljšanje učinkovitosti metod stiskanja.
