Innehållsförteckning:
- Definition - Vad betyder Burrows-Wheeler Transform (BWT)?
- Techopedia förklarar Burrows-Wheeler Transform (BWT)
Definition - Vad betyder Burrows-Wheeler Transform (BWT)?
Burrows-Wheeler-transformen (BWT) är en algoritm som tar block av data, till exempel strängar, och omorganiserar dem till körningar med liknande tecken. Efter omvandlingen innehåller utgångsblocket samma exakta dataelement innan det startade, men skiljer sig i beställningen. Algoritmens karaktär tenderar att sätta liknande tecken bredvid varandra, vilket gör den resulterande datanordning enklare att komprimera. Därför används det i många komprimeringsalgoritmer.
Techopedia förklarar Burrows-Wheeler Transform (BWT)
Burrows-Wheeler-transformeringsalgoritmen är en relativt ny algoritm som uppfanns 1994 av Michael Burrows och David Wheeler och baserad på en opublicerad transformation som upptäcktes av Wheeler 1983, publicerad i sitt papper "En block-sortering Lossless Data Compression Algoritm."
I det mest grundläggande tar BWT ett block med data som en sträng, lägger till ett EOF-tecken och sorterar sedan alla rotationer i den strängen i lexikografisk ordning. Följande pseudokod eller steg illustrerar algoritmen:
- Skapa en tabell som innehåller rader som representerar alla möjliga rotationsriktningar med en inkrement.
- Sortera alla rader alfabetiskt.
- Skriv ut den sista kolumnen i tabellen.
Till exempel: ordet "banan"; lägger till ett EOF-tecken förvandlas det till "banan $" och sedan använder vi algoritmen:
1. Skapa en tabell med rader som representerar alla möjliga rotationer:
banana $
anana $ b
Nana $ ba
ana $ förbud
na $ bana
en $ banan
$ banan
2. Sortera raderna alfabetiskt / leksikografiskt baserat på den första kolumnen:
$ banan
en $ banan
ana $ förbud
anana $ b
banana $
Nana $ ba
na $ bana
3. Återställ den sista kolumnen som BWT-utgång: annb $ aa
Den resulterande strängen är lättare att komprimera eftersom upprepade tecken samlas intill varandra. Men det måste finnas ytterligare data lagrade med de transformerade dataen så att en omvänd omvandling kan göras. Även om den resulterande transformerade datan är större än den ursprungliga formen men kompressibilitetskarakteristiken ökas många gånger, vilket i huvudsak gör det till en "gratis" metod för att förbättra kompressionsmetodernas effektivitet.
