Satura rādītājs:
- Definīcija - ko nozīmē Burrows-Wheeler Transform (BWT)?
- Techopedia skaidro Burrows-Wheeler Transform (BWT)
Definīcija - ko nozīmē Burrows-Wheeler Transform (BWT)?
Burrows-Wheeler transformācija (BWT) ir algoritms, kas ņem datu blokus, piemēram, virknes, un pārkārto tos līdzīgu rakstzīmju virknēs. Pēc pārveidošanas izvades bloks satur tos pašus precīzos datu elementus pirms tā sākuma, bet atšķiras secībā. Algoritma būtībai ir tendence līdzīgas rakstzīmes izvietot blakus, padarot iegūto datu secību vieglāk saspiežamu. Tāpēc tas tiek izmantots daudzos saspiešanas algoritmos.
Techopedia skaidro Burrows-Wheeler Transform (BWT)
Burrows-Wheeler pārveidošanas algoritms ir salīdzinoši jauns algoritms, kuru 1994. gadā izgudroja Maikls Burrows un Deivids Vellers, un kas balstās uz nepublicētu transformāciju, ko 1981. gadā atklāja Wheeler un kas tika publicēts viņu rakstā “Bloķēšanas šķirošanas nezaudētu datu saspiešanas algoritms”.
Visvienkāršākajā gadījumā BWT uzņem tādu datu bloku kā virkne, pievienojot EOF rakstzīmi un pēc tam sakārtojot visas šīs virknes rotācijas leksikogrāfiskā secībā. Algoritmu ilustrē šāds pseidokods vai darbības:
- Izveidojiet tabulu, kurā ir rindas, kas attēlo visas iespējamās virknes pagriešanas.
- Kārtojiet visas rindas alfabēta secībā.
- Izvadiet tabulas pēdējo kolonnu.
Piemēram: vārds “banāns”; pievienojot EOF rakstzīmi, tas tiek pārveidots par “banana $”, tad mēs izmantojam algoritmu:
1. Izveidojiet tabulu ar rindām, kas attēlo visas iespējamās rotācijas:
banāns $
anana $ b
nana $ ba
ana $ aizliegums
na $ bana
$ banāns
$ banāns
2. Kārtojiet rindas alfabēta secībā / leksikogrāfiski, pamatojoties uz pirmo kolonnu:
$ banāns
$ banāns
ana $ aizliegums
anana $ b
banāns $
nana $ ba
na $ bana
3.Atgrieziet pēdējo kolonnu kā BWT izvadi: annb $ aa
Iegūto virkni ir vieglāk saspiest, jo atkārtotas rakstzīmes tiek saliktas blakus. Bet kopā ar pārveidotajiem datiem ir jāglabā papildu dati, lai varētu veikt apgrieztu pārveidi. Kaut arī iegūtie pārveidotie dati ir lielāki nekā to sākotnējā forma, bet to saspiežamības īpašība ir daudzkārt palielināta, būtībā padarot to par “bezmaksas” metodi kompresijas metožu efektivitātes uzlabošanai.
