Burrows–Wheeler-transzformáció

A Burrows–Wheeler-transzformáció (BWT, blokkrendező algoritmus) az adattömörítő eljárásokban, így például a bzip2-ben használt algoritmus, melyet Michael Burrows és David Wheeler dolgozott ki 1994-ben, a Palo Altóban található DEC Systems Research Center-ben való munkájuk során. Alapja egy Wheeler által 1983-ban felfedezett, korábban ki nem adott transzformáció.

Amikor egy sztringet a BWT-vel átalakítanak, egyik karaktere sem változtat értéket. A transzformáció mindössze csak permutálja a karaktereket. Amennyiben az eredeti sztring számos, gyakorta fellelhető részsztringet tartalmazott, akkor a BWT-vel való átalakítás után kijövő sztring számos helyen fog hosszabb, azonos betűből álló sorokat tartalmazni. Ez hasznos az adattömörítésre, hiszen általánosságban elmondható, hogy az ismétlődő mintázatokkal vagy karakterekkel rendelkező sztringeket könnyebb tömöríteni.

Például:

bemenet	SIX.MIXED.PIXIES.SIFT.SIXTY.PIXIE.DUST.BOXES
kimenet	TEXYDST.E.IXIXIXXSSMPPS.B..E.S.EUSFXDIIOIIIT

A kimenetet könnyebb tömöríteni, hiszen jóval több egymás melletti azonos karakter van benne. Konkrétan a kimenet során 6 helyen is futnak egymás után azonos karakterek: XX, SS, PP, .., II, és III, amelyek együttesen a 44 karakteres sztringből 13 karaktert tesznek ki.

Példa

A transzformáció úgy jön létre, hogy a sztring elforgatottjait lexikografikus sorrendben leírják, majd ezek utolsó karakterét veszik. Például az, hogy "^BANANA|" abba megy át, hogy "BNN^AA|A" a következő lépéseken keresztül: (a piros | karakter az EOF fájlvége pointer):

Transzformáció
Input	Minden elforgatás	Minden sor rendezése ábécésorrendben	Az utolsó oszlop vétele	Kimenet
^BANANA|	^BANANA| |^BANANA A|^BANAN NA|^BANA ANA|^BAN NANA|^BA ANANA|^B BANANA|^	ANANA|^B ANA|^BAN A|^BANAN BANANA|^ NANA|^BA NA|^BANA ^BANANA| |^BANANA	ANANA|^B ANA|^BAN A|^BANAN BANANA|^ NANA|^BA NA|^BANA ^BANANA| |^BANANA	BNN^AA|A

Az alábbi pszeudokód egy egyszerű, ám kevéssé hatékony módot mutat be a BWT-re. Úgy veszi, hogy az s sztring tartalmaz egy speciális EOF jelet, amely a szövegben csak és kizárólag az utolsó helyen szerepel és a rendezéskor ignorálva van.

 függvény BWT (sztring s)
   tábla létrehozása, a sorok s minden lehetséges elforgatását jelentik
   sorok ábécérendbe rendezése
   visszatérés (a táblázat utolsó oszlopa)
 
 function inverzBWT (sztring s)
   üres táblázat létrehozása
       
   ismétlés hossz(s) alkalommal
       s beillesztése táblaoszlopként az első táblaoszlop elé // az első beillesztés az első oszlopot hozza létre
       a táblázat sorai ábécében rendezése
   visszatérés (az 'EOF' karakterrel végződő sor)

Annak megértésére, hogy a BWT miért hoz létre tömöríthetőbb adatot, vegyünk egy hosszú angol szöveget, mely gyakorta tartalmazza a "the" (a/az) szót. A szöveg elforgatásainak rendezése gyakran fog "he "-zel kezdődő elforgatottat összerakni, így az elforgatás utolsó karaktere (amely éppen a "he " előtt álló első karakter az eredeti szövegben) gyakran lesz "t", így eredményképp a transzformáció után számos "t" karakter lesz egymás után, pár kivétellel (például, ha tartalmazza azt, hogy "Brahe ") keverve. Így tehát a transzformáció sikere attól is függ, hogy nagy-e az esélye egy karakternek egy sorozat előtt való elhelyezkedésre, tehát általánosságban hosszabb (minimum néhány kilobájtos) adat vagy pedig megfelelő adat (például adott nyelven íródott szöveg) esetén lesz sikeres a BWT.

A BWT-ben nem csak az figyelemreméltó, hogy egy könnyebben tömöríthető adatot hoz létre – ezt egy sima rendezés is megtenné – hanem, hogy visszafordítható, az eredeti dokumentum generálható a transzformáció utániból.

Az inverz eljárás így érthető meg könnyen: vegyük a BWT-algoritmus végső táblázatát, és töröljünk az utolsó oszlopon kívül mindent. Kizárólagosan ezzel az információval az első oszlop könnyen rekonstruálható. Az utolsó oszlop megmondja az összes szövegbeli karaktert, így mindössze ezek ábécérendbe való rendezése megadja az első oszlopot. Ezután az első és utolsó oszlopok együtt megadják az egymást követő karakterek minden párját a dokumentumban, ahol a párok esetében az első és utolsó is párt formál. A párok listájának rendezése megadja az első és második oszlopot. Ilyen módon folytatva a teljes lista rekonstruálható. Ezután a fájlvégjellel ellátott sor (vagy más eljárásoknál ennek hiányában a megadott sorszámú sor) megadja az eredeti szöveget

Inverz transzformáció
Bemenet
BNN^AA|A
Hozzáadás 1	Rendezés 1	Hozzáadás 2	Rendezés 2
B N N ^ A A | A	A A A B N N ^ |	BA NA NA ^B AN AN |^ A|	AN AN A| BA NA NA ^B |^
Hozzáadás 3	Rendezés 3	Hozzáadás 4	Rendezés 4
BAN NAN NA| ^BA ANA ANA |^B A|^	ANA ANA A|^ BAN NAN NA| ^BA |^B	BANA NANA NA|^ ^BAN ANAN ANA| |^BA A|^B	ANAN ANA| A|^B BANA NANA NA|^ ^BAN |^BA
Hozzáadás 5	Rendezés 5	Hozzáadás 6	Rendezés 6
BANAN NANA| NA|^B ^BANA ANANA ANA|^ |^BAN A|^BA	ANANA ANA|^ A|^BA BANAN NANA| NA|^B ^BANA |^BAN	BANANA NANA|^ NA|^BA ^BANAN ANANA| ANA|^B |^BANA A|^BAN	ANANA| ANA|^B A|^BAN BANANA NANA|^ NA|^BA ^BANAN |^BANA
Hozzáadás 7	Rendezés 7	Hozzáadás 8	Rendezés 8
BANANA| NANA|^B NA|^BAN ^BANANA ANANA|^ ANA|^BA |^BANAN A|^BANA	ANANA|^ ANA|^BA A|^BANA BANANA| NANA|^B NA|^BAN ^BANANA |^BANAN	BANANA|^ NANA|^BA NA|^BANA ^BANANA| ANANA|^B ANA|^BAN |^BANANA A|^BANAN	ANANA|^B ANA|^BAN A|^BANAN BANANA|^ NANA|^BA NA|^BANA ^BANANA| |^BANANA
Kimenet
^BANANA|

Optimalizáció

Számos optimalizálási lehetőség van ezen algoritmus hatékonyabb futására a kimenet megváltoztatása nélkül. A BWT-ben nincs szükség a táblázat reprezentálására sem a kódolóban, sem a dekódolóban. A kódolóban minden sort jelölhet egy sztringre mutató pointer. Azonban oda kell figyelni, hogy a kód helyesen kezelje a legrosszabb esetet is, ugyanis a standard könyvtárakban elérhető rendező függvények nem valószínű, hogy pontosak. A dekódolóban szintén nincs szükség a táblázat tárolására, mi több, még rendezés sem szükségeltetik. Az ábécé méretével és a szöveg hosszával arányosan a dekódolt szöveg generálható jobbról balra, egyesével. Egy „karakter” az algoritmusban lehet egy bájt, egy bit vagy más megfelelő méret.

Nincs szükség igazi EOF karakterre. Ehelyett használható egy pointer, hogy megjegyezze, a szövegben hol lenne használat esetén egy EOF jel. Ezen megközelítésben a végső sztringet és a pointer végső értékét is ki kell adnia a programnak. Ez azt jelenti, hogy a BWT egy kicsit megnöveli az inputot. Az inverz transzformáció lecsökkenti az eredeti méretre: egy pointert és egy sztringet kap bemenetként és csak egy sztringet ad ki. Az algoritmusok teljes leírása megtalálható Burrows és Wheeler dolgozatában vagy pedig számos helyen online.

Bijektív variáns

Mivel a bemeneti sztring minden rotációja egyazon kimeneti sztringet eredményez, a BWT nem invertálható egy EOF jel nélkül, vagy pedig az információ kibővítésével (például az EOF helyét mutató pointerrel), amely lehetővé teszi az input sztring felismerését és megkülönböztetését elforgatottjaitól.

Van azonban a BWT-nek egy bijektív változata, amely transzformáció esetén minden adott hosszúságú sztring különbözőekbe megy át.

A bijektív transzformációban először kiszámolják a Lyndon-szavak egy nemnövő sorozatát; egy ilyen felbontás létezik a Chen–Fox–Lyndon-tétel miatt és megtalálható lineáris időben. Ezután az algoritmus együtt rendezi ezen szavak összes rotációját; pont mint a sima Burrows–Wheeler-transzformáció, ez is n sztringet eredményez. Ezután az átalakított sztringek listájában minden oszlop utolsó karakterét kiválasztva kapjuk meg a kódolt sztringet.

Így például a bijektív transzformáció alkalmazásával:

Bemenet	SIX.MIXED.PIXIES.SIFT.SIXTY.PIXIE.DUST.BOXES
Lyndon-szavak	SIX.MIXED.PIXIES.SIFT.SIXTY.PIXIE.DUST.BOXES
Kimenet	STEYDST.E.IXXIIXXSMPPXS.B..EE..SUSFXDIOIIIIT

A bijektív transzformáció nyolc legalább kettes egymást követő azonos karaktert ad: XX, II, XX, PP, .., EE, .., és IIII. Így összességében 18 karakter vesz részt ezekben.

Dinamikus Burrows–Wheeler-transzformáció

A szerkesztett szöveg Burrows–Wheeler-transzformációjának rekonstruálása helyett, Salson et al. egy olyan algoritmust javasol, mely származtatja az új Burrows–Wheeler-transzformációs formát az eredetiből, limitált számú helyi újrarendezéssel az eredeti Burrows–Wheeler-transzformációból.

Példa implementáció

Ez a Python nyelvű példa a sebességet feláldozza az egyszerűség oltárán: a program ugyan rövid, de a kívánt lineáris időnél többet vesz igénybe a lefutása.

A fájlvégjelölő itt a null karakter, míg az s i. rotációja a s[i:] + s[:i], a következő transzformáció minden utolsó sort vesz:

def bwt(s): # BWT függvény
    """Burrows–Wheeler-transzformáció alkalmazása mindenre."""
    assert "\0" not in s, "A bemeneti sztring nem tartalmazhatja a null karaktert ('\\0')" #debugging célok, ha a \0 benne van az inputban: hiba!
    s += "\0" # Az EOF jelzés hozzáadása
    table = sorted(s[i:] + s[:i] for i in range(len(s))) # A sztring rotációinak táblázata, sorrendbe rakva
    last_column = [row[-1:] for row in table] # Minden sor utolsó karaktere
    return "".join(last_column) # A karakterlista sztringgé konvertálása

Ez az inverz transzformáció következetesen inzertálja az r-et a táblázat bal soraként és rendezi a táblázatot. Miután a teljes táblázat felépült, a null-végű sort adja vissza, a null nélkül.

def ibwt(r): # inverz BWT
    """Inverz Burrows–Wheeler transzformáció alkalmazása."""
    table = [""] * len(r) # üres táblázat létrehozása
    for i in range(len(r)): #Amíg nem lesz elég oszlop...
        table = sorted(r[i] + table[i] for i in range(len(r))) # Az r oszlop hozzáadása
    s = [row for row in table if row.endswith("\0")][0] # A megfelelő, \0 végű sor megtalálása
    return s.rstrip("\0") # A null eltávolítása

Itt egy másik, gyorsabb eljárás. Habár hosszabb, hosszú szövegeknél a sebességet jelentősen megnöveli.

def ibwt(r, *args): #inverz BWT
        "Inverz Burrows–Wheeler-transzformáció. Az args az eredeti index \
ha nem jelölte null bájt"

        firstCol = "".join(sorted(r)) #az első oszlop létrehozása
        count = [0]*256 #bájtszámláló, 256 darab 0
        byteStart = [-1]*256 #256 darab -1 bájtkezdet
        output = [""] * len(r) #kimenet, r darab üres sztring
        shortcut = [None]*len(r) #r darab üres sztring
        #Generates shortcut lists
        for i in range(len(r)): #r-ig
                shortcutIndex = ord(r[i]) #r[i] karakterhelye
                shortcut[i] = count[shortcutIndex]
                count[shortcutIndex] += 1 #ennek megszámolása +1
                shortcutIndex = ord(firstCol[i]) #az első oszlop i. eleme
                if byteStart[shortcutIndex] == -1: #ha ott -1-gyel kezdődött...
                        byteStart[shortcutIndex] = i #most már i-vel
                        
        localIndex = (r.index("\x00") if not args else args[0]) #ha args hamis, akkor üres karakter indexe, ha nem, args[0]
        for i in range(len(r)): #r-ig
                #a következő transzformációvektor által meghatározott index
                nextByte = r[localIndex]
                output [len(r)-i-1] = nextByte #a kimenet megfelelő bájtja
                shortcutIndex = ord(nextByte) #az index annak kódja
                #localIndex adása a következő transzformációvektorhoz
                localIndex = byteStart[shortcutIndex] + shortcut[localIndex]
        return "".join(output).rstrip("\x00") #visszatérés, az esetleges null nélkül

Fordítás

Ez a szócikk részben vagy egészben a Burrows-Wheeler transform című angol Wikipédia-szócikk fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.

Források

• A BWT-alapú fájltömörítők tömörítési összehasonlítása
• Mark Nelson cikke a BWT-ről Archiválva 2017. március 25-i dátummal a Wayback Machine-ben
• Gil és Scott: Egy bijektív szövegrendezési algoritmus Archiválva 2011. október 8-i dátummal a Wayback Machine-ben
• Kufleitner: a Burrows–Wheeler-transzformáció bijektív variánsairól
• Blog poszt és projektlap egy nyílt forráskódú, a Burrows–Wheeler-transzformáción alapuló tömörítőprogramra és könyvtárra