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:

1. 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).
2. A kapott mátrix ("A" mátrix) minden sorát abc szerint rendezzük (lexikografikus rendezés), így kapjuk "B" mátrixunkat.
3. 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.
4. 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.

1. A kapott adatsort felírjuk egy n*n méretű mátrix utolsó oszlopaként.
2. Majd az oszlop elemeit abc szerint rendezzük, ezzel meg is kapjuk a "B" mátrix első oszlopát.
3. 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.
4. 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.