Burrows-Wheeler Transzformáció (BWT algoritmus)
A Burrows–Wheeler transzformációt (BWT, vagy hívják még blokk-rendező algoritmusnak is), ezt az algoritmust sok tömörítő használja, mint például a bzip2 is.
Az algoritmust Michael Burrows és David Wheeler dolgozta ki 1994-ben. Maga az algoritmus nem tömörít, az eredeti adattal egyező méretű adathalmazt hoz létre (leszámítva egy számértéket, lásd lentebb), de a bemeneti karakterláncot úgy alakítja át, hogy azt egy statisztikai alapú (pl. LZ) tömörítő sokkal jobban tudja tömöríteni, mint az eredeti adatot. Tulajdonképpen a tömörítendő adatot előkészíti a tömörítési algoritmusnak.
A BWT algoritmus működése:
- Az eredeti adatot (EMESESMSE) egy n*n méretű (n most az adat hosszával egyezik, tehát 9) mátrixban úgy írjuk fel, hogy minden sorát egy karakterrel eltoljuk (permutáljuk).
- A kapott mátrix ("A" mátrix) minden sorát abc szerint rendezzük (lexikografikus rendezés), így kapjuk "B" mátrixunkat.
- Kész is a Burrows Wheeler transzformáció, a "B" mátrix utolsó oszlopa adja az átalakított szöveget, illetve fontos még megjegyezni egyetlen információt ahhoz, hogy az eredeti adatot helyre állítsuk.
- Ez az információ nem más, mint a "B" mátrix azon sorának száma ami az eredeti szöveget tartalmazza. Jelen esetben ez a 2. sor.
BWT transzformáció:
EMESESMSE EEMESESMS
MESESMSEE EMESESMSE <--- 2. sor tartalmazza az eredeti adatot
ESESMSEEM ESESMSEEM
SESMSEEME ESMSEEMES
ESMSEEMES MESESMSEE
SMSEEMESE MSEEMESES
MSEEMESES SEEMESESM
SEEMESESM SESMSEEME
EEMESESMS SMSEEMESE
az eredmény: SEMSESMEE
Inverz BWT transzformáció működése:
Tehát a BWT transzformáció után van nekünk egy SEMSESMEE adatunk és egy sorszámunk, a kettes. Ebből kell vissza állítani az eredeti adatot. Ezt a következő lépésekkel lehet megtenni.
- A kapott adatsort felírjuk egy n*n méretű mátrix utolsó oszlopaként.
- Majd az oszlop elemeit abc szerint rendezzük, ezzel meg is kapjuk a "B" mátrix első oszlopát.
- Ezt követően a meglévő adatunkat (SEMSESMEE) beírjuk az imént rendezett oszlop elé, balról, majd a két oszlopot abc szerint (lexikografikusan) rendezzük, így kapjuk meg az eredeti "A" mátrix első két oszlopát.
- Hozzáadjuk újból az adatunkat az imént rendezett oszlopok elé, ismét balról, majd megint rendezünk... ezt ismételjük míg meg nem kapjuk "B" mátrixunkat, amiből a megjegyzett 2. sorszám alapján tudjuk kiolvasni az eredeti adatot.
| 1. az utolsó oszlop felírása | első oszlop felírása |
oszlop hozzáadás balról |
| ________S ________E ________M ________S ________E ________S ________M ________E ________E |
E________ E________ E________ E________ M________ M________ S________ S________ S________ |
SE_______ EE_______ ME_______ SE_______ EM_______ SM_______ MS_______ ES_______ ES_______ |
| rendezés | oszlop hozzáadás balról | rendezés |
| EE_______ EM_______ ES_______ ES_______ ME_______ MS_______ SE_______ SE_______ SM_______ |
SEE_______ EEM_______ MES_______ SES_______ EME_______ SMS_______ MSE_______ ESE_______ ESM_______ |
EEM_______ EME_______ ESE_______ ESM_______ MES_______ MSE_______ SEE_______ SES_______ SMS_______ |
| oszlop hozzáadás balról | rendezése | az elkészült "B" mátrix |
| SEEM______ EEME______ MESE______ SESM______ EMES______ SMSE______ MSEE______ ESES______ ESMS______ |
... | EEMESESMS EMESESMSE <--- 2. sor tartalmazza az eredeti adatot ESESMSEEM ESMSEEMES MESESMSEE MSEEMESES SEEMESESM SESMSEEME SMSEEMESE |
A BWT által készült adatokat nagyon jól lehet tovább optimalizálni tömörítők számára a move-to-front (MTF) és run-length encoding (RLE) eljárásokkal.
