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.

Avast vírusírtó letöltés ingyen Buy Bitcoin at CEX.IO