Inhoudsopgave:
- Definitie - Wat betekent Burrows-Wheeler Transform (BWT)?
- Techopedia verklaart Burrows-Wheeler Transform (BWT)
Definitie - Wat betekent Burrows-Wheeler Transform (BWT)?
De Burrows-Wheeler-transformatie (BWT) is een algoritme dat gegevensblokken, zoals tekenreeksen, neemt en deze in reeksen van vergelijkbare tekens herschikt. Na de transformatie bevat het uitvoerblok dezelfde exacte gegevenselementen voordat het was gestart, maar verschilt in de volgorde. De aard van het algoritme heeft de neiging soortgelijke tekens naast elkaar te plaatsen, waardoor de resulterende gegevensvolgorde gemakkelijker kan worden gecomprimeerd. Daarom wordt het in veel compressiealgoritmen gebruikt.
Techopedia verklaart Burrows-Wheeler Transform (BWT)
Het Burrows-Wheeler-transformatiealgoritme is een relatief nieuw algoritme uitgevonden door Michael Burrows en David Wheeler in 1994 en gebaseerd op een niet-gepubliceerde transformatie ontdekt door Wheeler in 1983, gepubliceerd in hun paper "A Block-sorting Lossless Data Compression Algorithm."
In de meest elementaire volgorde neemt BWT een gegevensblok zoals een string, voegt een EOF-teken toe en sorteert vervolgens alle rotaties van die string in lexicografische volgorde. De volgende pseudocode of stappen illustreren het algoritme:
- Maak een tabel met rijen die alle mogelijke rotaties met één stap van de reeks vertegenwoordigen.
- Sorteer alle rijen alfabetisch.
- Voer de laatste kolom van de tabel uit.
Bijvoorbeeld: het woord "banaan"; door een EOF-karakter toe te voegen, verandert het in "banana $" en dan passen we het algoritme toe:
1. Maak een tabel met rijen die alle mogelijke rotaties vertegenwoordigen:
banaan $
anana $ b
nana $ ba
ana $ ban
Na $ bana
een $ banan
$ banaan
2. Sorteer de rijen alfabetisch / lexicografisch op basis van de eerste kolom:
$ banaan
een $ banan
ana $ ban
anana $ b
banaan $
nana $ ba
Na $ bana
3.Sterug de laatste kolom als BWT-uitvoer: annb $ aa
De resulterende tekenreeks is gemakkelijker te comprimeren omdat herhaalde tekens naast elkaar worden geplaatst. Maar er moeten extra gegevens worden opgeslagen met de getransformeerde gegevens, zodat een omgekeerde transformatie kan worden uitgevoerd. Hoewel de resulterende getransformeerde gegevens groter zijn dan de oorspronkelijke vorm, maar de compressibiliteitskarakteristiek veelvoudig is toegenomen, waardoor het in wezen een "gratis" methode is om de efficiëntie van compressiemethoden te verbeteren.
