Sommario:
- Definizione - Cosa significa Burrows-Wheeler Transform (BWT)?
- Techopedia spiega Burrows-Wheeler Transform (BWT)
Definizione - Cosa significa Burrows-Wheeler Transform (BWT)?
La trasformazione Burrows-Wheeler (BWT) è un algoritmo che prende blocchi di dati, come stringhe, e li riorganizza in sequenze di caratteri simili. Dopo la trasformazione, il blocco di output contiene gli stessi esatti elementi di dati prima che fosse avviato, ma differisce nell'ordinamento. La natura dell'algoritmo tende a mettere caratteri simili uno accanto all'altro, facilitando la compressione dell'ordine dei dati risultante. Quindi viene utilizzato in molti algoritmi di compressione.
Techopedia spiega Burrows-Wheeler Transform (BWT)
L'algoritmo di trasformazione di Burrows-Wheeler è un algoritmo relativamente nuovo inventato nel 1994 da Michael Burrows e David Wheeler e basato su una trasformazione inedita scoperta da Wheeler nel 1983, pubblicata nel loro articolo "A Block-sorting Lossless Data Compression Algorithm".
In sostanza, BWT prende un blocco di dati come una stringa, aggiungendo un carattere EOF e quindi ordinando tutte le rotazioni di quella stringa in ordine lessicografico. I seguenti pseudocodici o passaggi illustrano l'algoritmo:
- Creare una tabella che contiene righe che rappresentano tutte le possibili rotazioni a un incremento della stringa.
- Ordina tutte le righe in ordine alfabetico.
- Emette l'ultima colonna della tabella.
Ad esempio: la parola "banana"; l'aggiunta di un carattere EOF lo trasforma in "banana $", quindi applichiamo l'algoritmo:
1. Creare una tabella con righe che rappresentano tutte le possibili rotazioni:
banane $
anana $ b
nana $ ba
ana $ divieto
na $ bana
un $ banan
$ banane
2. Ordinare le righe in ordine alfabetico / lessicografico in base alla prima colonna:
$ banane
un $ banan
ana $ divieto
anana $ b
banane $
nana $ ba
na $ bana
3. Restituire l'ultima colonna come output BWT: annb $ aa
La stringa risultante è più facile da comprimere perché i caratteri ripetuti sono raggruppati uno accanto all'altro. Tuttavia, è necessario che vengano archiviati dati aggiuntivi con i dati trasformati in modo da poter effettuare una trasformazione inversa. Anche se i dati trasformati risultanti sono più grandi della sua forma originale, ma le sue caratteristiche di compressibilità sono molte volte aumentate, rendendolo essenzialmente un metodo "libero" per migliorare l'efficienza dei metodi di compressione.
