Innholdsfortegnelse:
- Definisjon - Hva betyr Burrows-Wheeler Transform (BWT)?
- Techopedia forklarer Burrows-Wheeler Transform (BWT)
Definisjon - Hva betyr Burrows-Wheeler Transform (BWT)?
Burrows-Wheeler transformasjonen (BWT) er en algoritme som tar blokker med data, for eksempel strenger, og omorganiserer dem til kjør med lignende tegn. Etter transformasjonen inneholder utgangsblokken de samme nøyaktige dataelementene før den hadde startet, men avviker i rekkefølgen. Arten av algoritmen har en tendens til å legge lignende tegn ved siden av hverandre, noe som gjør den resulterende datarekkefølgen enklere å komprimere. Derfor brukes det i mange komprimeringsalgoritmer.
Techopedia forklarer Burrows-Wheeler Transform (BWT)
Burrows-Wheeler transformeringsalgoritme er en relativt ny algoritme som ble oppfunnet i 1994 av Michael Burrows og David Wheeler og basert på en upublisert transformasjon som ble oppdaget av Wheeler i 1983, publisert i papiret “A Block-sorting Lossless Data Compression Algorithm.”
I det mest grunnleggende tar BWT en blokk med data som en streng, legger til et EOF-tegn og deretter sorterer alle rotasjoner av den strengen i leksikografisk rekkefølge. Følgende pseudokode eller trinn illustrerer algoritmen:
- Lag en tabell som inneholder rader som representerer alle mulige rotasjonshastigheter i strengen.
- Sorter alle radene alfabetisk.
- Skriv ut den siste kolonnen i tabellen.
For eksempel: ordet “banan”; å legge til et EOF-tegn gjør det til "banana $", så bruker vi algoritmen:
1. Lag en tabell med rader som representerer alle mulige rotasjoner:
banan $
Añana $ b
nana $ BA
ana $ forbud
na $ bana
en $ Banan
$ banan
2. Sorter radene alfabetisk / leksikografisk basert på den første kolonnen:
$ banan
en $ Banan
ana $ forbud
Añana $ b
banan $
nana $ BA
na $ bana
3.Vend den siste kolonnen som BWT-utgang: annb $ aa
Den resulterende strengen er lettere å komprimere fordi gjentatte tegn er samlet sammen ved siden av hverandre. Men det må lagres ytterligere data med de transformerte dataene, slik at en omvendt transformasjon kan gjøres. Selv om de resulterende transformerte dataene er større enn den opprinnelige formen, men kompressibilitetskarakteristikken er økt mange ganger, noe som i hovedsak gjør det til en "gratis" metode for å forbedre effektiviteten til komprimeringsmetoder.
