Indholdsfortegnelse:
- Definition - Hvad betyder Burrows-Wheeler Transform (BWT)?
- Techopedia forklarer Burrows-Wheeler Transform (BWT)
Definition - Hvad betyder Burrows-Wheeler Transform (BWT)?
Burrows-Wheeler-transformation (BWT) er en algoritme, der tager blokke af data, såsom strenge, og omorganiserer dem til kørsler med lignende tegn. Efter transformationen indeholder outputblokken de samme nøjagtige dataelementer, før den var startet, men adskiller sig i rækkefølgen. Arten af algoritmen har en tendens til at placere lignende tegn ved siden af hinanden, hvilket gør den resulterende datarækkefølge lettere at komprimere. Derfor bruges det i mange komprimeringsalgoritmer.
Techopedia forklarer Burrows-Wheeler Transform (BWT)
Burrows-Wheeler-transformeringsalgoritmen er en relativt ny algoritme, der blev opfundet i 1994 af Michael Burrows og David Wheeler og baseret på en upubliceret transformation opdaget af Wheeler i 1983, der blev offentliggjort i deres papir "A Block-sorting Lossless Data Compression Algorithm."
I det mest basale tager BWT en blok af data såsom en streng, tilføjer et EOF-tegn og sorterer derefter alle rotationer af denne streng i leksikografisk rækkefølge. Følgende pseudokode eller trin illustrerer algoritmen:
- Opret en tabel, der indeholder rækker, der repræsenterer alle mulige rotationer med en forøgelse af strengen.
- Sorter alle rækker alfabetisk.
- Output den sidste kolonne i tabellen.
For eksempel: ordet "banan"; tilføjelse af et EOF-tegn gør det til "banan $", så anvender vi algoritmen:
1. Opret en tabel med rækker, der repræsenterer alle mulige rotationer:
banan $
Anana $ B
nana $ ba
ana $ forbud
na $ bana
en $ banan
$ banan
2. Sorter rækkerne alfabetisk / leksikografisk baseret på den første kolonne:
$ banan
en $ banan
ana $ forbud
Anana $ B
banan $
nana $ ba
na $ bana
3.Vend den sidste kolonne som BWT-output: annb $ aa
Den resulterende streng er lettere at komprimere, fordi gentagne tegn samles ved siden af hinanden. Men der skal lagres yderligere data sammen med de transformerede data, så der kan foretages en omvendt transformation. Selvom de resulterende transformerede data er større end den oprindelige form, men kompressibilitetskarakteristikken forøges mange gange, hvilket i det væsentlige gør dem til en "gratis" metode til at forbedre effektiviteten af komprimeringsmetoder.
