Cuprins:
- Definiție - Ce înseamnă Burrows-Wheeler Transform (BWT)?
- Techopedia explică Transformarea Burrows-Wheeler (BWT)
Definiție - Ce înseamnă Burrows-Wheeler Transform (BWT)?
Transformarea Burrows-Wheeler (BWT) este un algoritm care preia blocuri de date, cum ar fi șiruri de caractere, și le rearanjează în rulaje cu caractere similare. După transformare, blocul de ieșire conține aceleași elemente de date exacte înainte de a fi început, dar diferă în ordonare. Natura algoritmului tinde să pună caractere similare unul lângă altul, făcând astfel compresia mai ușoară a datelor rezultate. Prin urmare, este utilizat în mai mulți algoritmi de compresie.
Techopedia explică Transformarea Burrows-Wheeler (BWT)
Algoritmul de transformare Burrows-Wheeler este un algoritm relativ nou inventat în 1994 de Michael Burrows și David Wheeler și bazat pe o transformare nepublicată descoperită de Wheeler în 1983, publicată în lucrarea lor „Un algoritm de compresiune a datelor fără pierderi de blocare a datelor.”
În cele mai de bază, BWT preia un bloc de date, cum ar fi un șir, adăugând un caracter EOF și apoi sortează toate rotațiile acelui șir în ordine lexicografică. Următoarele pseudocod sau pași ilustrează algoritmul:
- Creați un tabel care conține rânduri care să reprezinte toate rotațiile posibile cu o incrementare a șirului.
- Sortează toate rândurile în ordine alfabetică.
- Ieșiți ultima coloană a tabelului.
De exemplu: cuvântul „banană”; adăugarea unui caracter EOF îl transformă în „banana $” apoi aplicăm algoritmul:
1. Creați un tabel cu rânduri care să reprezinte toate rotațiile posibile:
banane $
Anana $ b
nana $ ba
ana $ ban
na $ Bana
un $ Banan
$ banane
2. Sortează rândurile alfabetic / lexicografic pe baza primei coloane:
$ banane
un $ Banan
ana $ ban
Anana $ b
banane $
nana $ ba
na $ Bana
3. Returnați ultima coloană ca ieșire BWT: anulare $ aa
Șirul rezultat este mai ușor de comprimat, deoarece caracterele repetate sunt grupate unul lângă altul. Dar trebuie să fie stocate date suplimentare cu datele transformate, astfel încât să se poată face o transformare inversă. Chiar dacă datele transformate rezultate sunt mai mari decât forma sa originală, dar caracteristica de compresibilitate este multiplicată, făcând-o în esență o metodă „liberă” de îmbunătățire a eficienței metodelor de compresie.
