Sisällysluettelo:
- Määritelmä - Mitä Burrows-Wheeler Transform (BWT) tarkoittaa?
- Techopedia selittää Burrows-Wheeler Transformin (BWT)
Määritelmä - Mitä Burrows-Wheeler Transform (BWT) tarkoittaa?
Burrows-Wheeler-muunnos (BWT) on algoritmi, joka ottaa datalohkoja, kuten merkkijonoja, ja järjestää ne uudelleen samanlaisten merkkien ajoiksi. Muunnon jälkeen lähtölohko sisältää samat tarkat tietoelementit ennen kuin se oli alkanut, mutta eroaa tilauksesta. Algoritmin luonteella on taipumus asettaa samanlaisia merkkejä vierekkäin, mikä tekee tuloksena olevan datajärjestyksen pakattavaksi helpommaksi. Siksi sitä käytetään monissa pakkausalgoritmeissa.
Techopedia selittää Burrows-Wheeler Transformin (BWT)
Burrows-Wheeler-muunnosalgoritmi on suhteellisen uusi algoritmi, jonka Michael Burrows ja David Wheeler keksivät vuonna 1994 ja joka perustuu julkaisemattomaan muutokseen, jonka Wheeler löysi vuonna 1983.
Alkeisimmissa tapauksissa BWT ottaa datalohkon, kuten merkkijonon, lisäämällä EOF-merkin ja lajittelemalla sitten kyseisen merkkijonon kaikki kiertotiedot leksikografiseen järjestykseen. Seuraava pseudokoodi tai vaiheet kuvaavat algoritmia:
- Luo taulukko, joka sisältää rivejä, jotka edustavat merkkijonon kaikkia mahdollisia yhden askeleen kiertoa.
- Lajittele kaikki rivit aakkosjärjestykseen.
- Tulosta taulukon viimeinen sarake.
Esimerkiksi: sana “banaani”; lisäämällä EOF-merkki muuttuu siitä “banana $”, sitten käytämme algoritmia:
1. Luo taulukko riveillä, jotka edustavat kaikkia mahdollisia kiertoja:
banaani $
anana $ b
nana $ ba
ana $ kielto
na $ Bana
$ Banan
$ banaani
2. Lajittele rivit aakkosjärjestyksessä / sanasuunnassa ensimmäisen sarakkeen perusteella:
$ banaani
$ Banan
ana $ kielto
anana $ b
banaani $
nana $ ba
na $ Bana
3.Palaa viimeinen sarake BWT-tulosteena: annb $ aa
Tuloksena olevaa merkkijonoa on helpompi pakata, koska toistuvat merkit niputetaan keskenään. Mutta muunnetun datan kanssa on tallennettava lisätietoja, jotta käänteinen muuntaminen voidaan suorittaa. Vaikka tuloksena oleva muunnettu data on suurempi kuin sen alkuperäinen muoto, mutta sen puristusominaisuutta on kasvatettu moninkertaisesti, tekemällä siitä olennaisesti "vapaa" menetelmä pakkausmenetelmien tehokkuuden parantamiseksi.
