Ugrás a tartalomhoz

Burrows–Wheeler-transzformáció

Ellenőrzött
A Wikipédiából, a szabad enciklopédiából

A Burrows–Wheeler-transzformáció (BWT, blokkrendező algoritmus[1]) 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.[2] 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

[szerkesztés]

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[3]) 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ó

[szerkesztés]

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.[3] 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

[szerkesztés]

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.[4]

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.[5] 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ó

[szerkesztés]

A szerkesztett szöveg Burrows–Wheeler-transzformációjának rekonstruálása helyett, Salson et al.[6] 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ó

[szerkesztés]

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

Jegyzetek

[szerkesztés]
  1. Burrows–Wheeler-transzformáció (BWT-algoritmus)
  2. Burrows M and Wheeler D (1994), A block sorting lossless data compression algorithm, Technical Report 124, Digital Equipment Corporation, <http://www.hpl.hp.com/techreports/Compaq-DEC/SRC-RR-124.html> Archiválva 2011. június 7-i dátummal a Wayback Machine-ben Archivált másolat. [2011. június 7-i dátummal az eredetiből archiválva]. (Hozzáférés: 2012. július 6.)
  3. a b Compression with the Burrows-Wheeler Transform (james.fabpedigree.com)
  4. Gil, J. & Scott, D. A. (2009), A bijective string sorting transform, <http://bijective.dogma.net/00yyy.pdf> Archiválva 2011. október 8-i dátummal a Wayback Machine-ben Archivált másolat. [2011. október 8-i dátummal az eredetiből archiválva]. (Hozzáférés: 2012. július 6.). Kufleitner, Manfred (2009), "On bijective variants of the Burrows-Wheeler transform", in Holub, Jan & Žďárek, Jan, Prague Stringology Conference, pp. 65–69, <http://www.stringology.org/event/2009/p07.html>.
  5. Duval, Jean-Pierre (1983), "Factorizing words over an ordered alphabet", Journal of Algorithms 4 (4): 363–381, DOI 10.1016/0196-6774(83)90017-2.
  6. Salson M, Lecroq T, Léonard M and Mouchard L (2009). „A Four-Stage Algorithm for Updating a Burrows–Wheeler Transform”. Theoretical Computer Science 410 (43), 4350. o. DOI:10.1016/j.tcs.2009.07.016. 

Fordítás

[szerkeszté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

[szerkesztés]