Kas yra urvų-ratų transformacija (bwt)? - apibrėžimas iš techopedijos

Apibrėžimas - ką reiškia „Burrows-Wheeler Transform“ (BWT)?

„Burrows-Wheeler“ transformacija (BWT) yra algoritmas, kuris paima duomenų blokus, pvz., Eilutes, ir pertvarko juos į panašių simbolių eiles. Po transformacijos išvesties bloke yra tie patys tikslūs duomenų elementai, prieš tai, kai jie buvo pradėti, tačiau skiriasi tvarka. Dėl algoritmo pobūdžio panašūs simboliai yra dedami vienas šalia kito, todėl gaunamą duomenų tvarką lengviau suspausti. Taigi jis naudojamas daugelyje glaudinimo algoritmų.

„Techopedia“ aiškina „Burrows-Wheeler Transform“ (BWT)

„Burrows-Wheeler“ transformacijos algoritmas yra palyginti naujas algoritmas, kurį 1994 m. Išrado Michaelas Burrowsas ir Davidas Wheeleris ir kuris grindžiamas dar nepaskelbta transformacija, kurią 1983 m. Atrado Wheeleris, paskelbtoje jų knygoje „Blokuojančio praradimo duomenų suspaudimo algoritmas“.

Paprasčiausias - BWT imasi duomenų, tokių kaip eilutė, bloko, pridedant EOF ženklą ir tada surūšiuojant visus tos eilutės pasisukimus į leksikografinę tvarką. Šis pseudokodas arba žingsniai iliustruoja algoritmą:

1. Sukurkite lentelę, kurioje yra eilutės, vaizduojančios visus galimus eilutės pasisukimus.
2. Rūšiuokite visas eilutes abėcėlės tvarka.
3. Išveskite paskutinį lentelės stulpelį.

Pvz .: žodis „bananas“; pridedant EOF simbolį, jis virsta „banana $“, tada mes taikome algoritmą:

1. Sukurkite lentelę su eilutėmis, vaizduojančiomis visus galimus pasukimus:

bananas $

anana $ b

nana $ ba

ana $ draudimas

na $ bana

dolerių bananą

$ banano

2. Rūšiuokite eilutes abėcėlės tvarka / leksikografiškai pagal pirmą stulpelį:

$ banano

dolerių bananą

ana $ draudimas

anana $ b

bananas $

nana $ ba

na $ bana

3.Grąžinkite paskutinį stulpelį kaip BWT išėjimą: annb $ aa

Gautą eilutę lengviau suspausti, nes pasikartojantys ženklai yra surišti vienas šalia kito. Bet norint, kad būtų galima atlikti atvirkštinę transformaciją, kartu su transformuotais duomenimis turi būti saugomi papildomi duomenys. Nors gaunami transformuoti duomenys yra didesni už pradinę formą, tačiau jų suspaudžiamumas yra padidinamas daug kartų, iš esmės tai daro „nemokamą“ būdą pagerinti glaudinimo metodų efektyvumą.