Regex illesztés NFA-val, ahogy kell

Tehát a téma még mindig: regexet akarunk illeszteni, gyorsan.

Az előző post végén arra jutottunk, hogy a determinisztikus automata, amit az input regexhez elkészíthetünk, túl nagy is lehet ahhoz, hogy praktikusan használható legyen. (Ha valaki nem hiszi, hogy néha kell hosszú regexekkel dolgozni, nézzen rá az RFC822-re, ami egy regex valid email címre ;-) )

Amit valójában érdemes használni: nemdeterminisztikus automatát.

A nemdeterminizmus, bármilyen számítási modellről (automata, veremautomata, Turing-gép, RAM program stb) is beszélünk, mindig olyasmit jelent, hogy a számítás egy-egy konfigurációjából (egy konfiguráció mindig egy "snapshot" a számítás aktuális helyzetéről, amit ha "kimentenénk" és később visszatöltenénk, akkor onnan folytatni tudjuk a számítást, ahol abbahagytuk. Automata esetében pl. egy konfigurációban az aktuális állapot és az input string még hátralevő része szerepel, ennyi már elég ahhoz, hogy ha leállítjuk a számítást, akkor ennyit megjegyezve később folytatni tudjuk) nem feltétlenül csak egy következő konfigurációba tudunk átmenni, hanem esetleg több rákövetkező is lehet; a számítás során a "gép" választ, hogy ezek közül melyik irányba "akar" továbbmenni. Képzeljük el úgy, mintha a gépnek az lenne a "célja", hogy elfogadja az inputot és tévedhetetlenül "ráérezne", ha csak egyetlen mód is van arra, hogy elfogadja azt, akkor meg is találna egy ilyen utat.

Automaták esetében ez annyit tesz, hogy

• δ nem függvény, hanem reláció: egy Q×Σ → P(Q) leképezés, azaz egy állapotból és egy betűből a lehetséges következő állapotok egy halmaza van megadva;

• ez rajzban annyit tesz, hogy lehetnek olyan p állapotok, melyekből nem csak egyfelé lehet menni valamelyik a betűvel, hanem esetleg többfelé is (akár 0-fele is megengedett, ami nyilván azt jelenti, hogy az automata ha ebben az állapotban ezt az input betűt kéne feldolgozza, akkor azonnal el is utasítja az inputot);

• akkor fogadja el az automata az input stringet, ha lehet úgy haladni a kezdőállapotból egy végállapotba, hogy közben az éleken pont az input stringet olvassuk össze.

Például

egy nemdeterminisztikus automata, ami pl. onnan látszik, hogy q₀-ból az a jel hatására el lehet fáradni q₀-ba is, q₁-be is. (Más "valódi" ok nincs. Igaz, hogy pl. q₅-ből nem lehet elmenni sehova, de az nem nagy baj, ilyenkor egy csapdaállapotot, ami nem végállapot, felveszünk, abba átirányítunk minden definiálatlan esetet, őt magát is, és kész is van).

Az látszik, hogy ha q₁-be jut a fenti automata, akkor onnan ha négybetűs szót kap, akkor azt q₅-ben elfogadja, mást pedig nem. q₁-be pedig úgy kerül, hogy először q₀-ban olvasgatja az input első karaktereit, aztán "egyszer csak" egy a hatására q₁-be ugrik onnan - hogy melyik ez az a, azt vezényli a nemdeterminisztikus kontroll. Látszik, hogy ha az inputban hátulról az ötödik karakter a, akkor az automata ezt az inputot el tudja fogadni - tehát ilyenkor el is fogadja, mert nemdeterminisztikusan "ráérez", hogy épp mikor kellene ugorjon, hogy az a végén jó legyen neki (aka elfogadó állapotba jusson), más esetben viszont nincs olyan futás, aminek a végén elfogad. Tehát, ez a nemdeterminisztikus automata (NFA) pont azokat a szavakat fogadja el, melyeknek hátulról ötödik betűje a.

Persze ezt lehet általánosítani hátulról az n. betűre is, azt n+1 állapotú NFA-val el tudjuk fogadni. A felvezető postban pedig láttuk, hogy ha ragaszkodnánk a determinisztikus változathoz, ahhoz kb 2ⁿ állapot kéne

(tudjátok, gombóc)

ezért részesítjük előnyben az NFA-t a DFA-val szemben, mert lényegesen kompaktabb tud lenni.

Ígértem "ezen lehet dolgozni" típusú bekezdéseket is. Nos, az ismert, hogy ha van egy input n hosszú regexem, akkor lehet készíteni vele ekvivalens NFA-t, melynek O(n(logn)²) átmenete van (nemdeterminisztikus automaták "méretére" az állapotszám nem annyira jó jellemző, hiszen az élsűrűség nem adott, mint determinisztikus esetben. Az automata letárolására amennyi tárat kell használjunk, az is az élszámmal tűnik jól mérhetőnek). Van is rá írva algoritmus, ld pl itt vagy egy gyorsabbért itt. A Thompson-algoritmusból származó NFA (mindjárt látni fogjuk) pedig O(n²) méretű.

Ami engem itt érdekel, az az, hogy

a gyakorlatban használt regexek esetében melyik módszer "jobb" a kettő közül?

Mert hiába néz ki kisebbnek az O(n(logn)²), ha esetleg csak csillagászati méretű regexekre győzi le a négyzetest, akkor a négyzetest használjuk. A feladat tehát implementálni és elméleti úton és/vagy generált regexek seregén tesztelve összemérni a két (esetleg három) algoritmust.

Hozzá kell tegyem, hogy ebbe a feladatba páran már belebuktak - úgy tűnik, hogy nem mindenkinek fekszik egy "itt ez a cikk, benne egy algoritmus, kódold le" feladat programtervező informatikusként. Oh well.

Vissza a Thompson-algoritmusra, az először egy lineáris méretű NFA-t épít az input regexhez, melyben vannak üres (spontán, ε) átmenetek is. Ezeket úgy használjuk, hogy ha a (nemdeterminisztikus) automatának van lehetősége valahonnan üres átmenettel (amit most úgy fogok rajzolni, hogy nem írok fölé betűt, máskor esetleg írok fölé ε betűt) átlépni egy másikba, akkor átugorhat és közben az inputból nem kell új betűt olvasson.

Az algoritmus még annyit tud, hogy tetszőleges input regexből olyan NFA-t készít, melynek pontosan egy végállapota van, s ez nem ugyanaz, mint a kezdőállapot, továbbá a végállapotból nem lehet továbbmenni, a kezdőállapotba pedig nem lehet visszajutni. Ha csak egy betűnk van, tehát a regex R = a, arra könnyű ilyen automatát adni:

Ha a regexünk R = R1R2, akkor a rekurzív algoritmus csak "összeragasztja" az R1-hez és az R2-höz készített automatákat: az R1 végállapotát és az R2 kezdőállapotát mergeli.

Ha a regexünk R = R1 + R2, akkor pedig mergeljük a két kezdőállapotot is és a két végállapotot is.

Az iteráció, R = R1*, az egyetlen kicsit komplikáltabb történet: vissza kell tudnunk ugrani a végállapotból a kezdőállapotba, hogy iterációt csináljunk, de emellé még egy-egy új kezdő- és végállapotot kell felvegyünk, hogy ne sérüljön a "kezdőbe nem uthatunk máshonnan, végállapotból nem mehetünk el" feltétel. És kell egy közvetlen ugrás a kezdőállapotból a végállapotba is, hogy a nulla darab ismétlést is megengedjük.

Nem akarok túlzottan belemenni most (és rajzolni se), akit az algoritmus technikai részletei érdekelnek, nézze meg wikin a képeket. (Az uniót ők másképp csinálják.) Elég azt tudnunk most, hogy van olyan algoritmus, ami egy n hosszú regexből egy O(n) állapotú NFA-t épít, melyben vannak üres átmenetek is.

Persze az üres átmenetes NFA nem sokat érne, ha nem tudnánk hatékonyan szimulálni. Meg lehet oldani backtrackinggel, kipróbálva az összes lehetséges számítási útvonalat, hogy van-e közte elfogadó, de ez azért megint egy félelmetesen alulkulturált módszer, ami exponenciális futásidőt eredményez, és ráadásul nem is a rövid regex, hanem a hosszú input string hosszában exponenciálist. Ez kábé a legrosszabb, ami történhet, ha ez lenne a főműsor, akkor nem használnánk NFA-t regex illesztésre.

Van jobb módszer: minden karakter feldolgozása után nyilvántartjuk, hogy melyik állapotokban lehetünk ekkor. Alapból, mikor még nem olvastunk be semmit, lehetünk a kezdőállapotban, vaaagy az abból üres átmenetekkel elérhető bármelyik állapotban (átmehetünk bárhova üres átmenetekkel, ahova csak lehet, még mielőtt egyetlen betűt is beolvastunk). Az összes ilyen állapot halmazával inicializáljuk az aktuális S halmazunkat. Eztán egyesével feldolgozzuk a betűket: ha épp az S halmazban vagyunk valahol, és jön egy a betű, akkor az új halmazunk legyen az összes olyan állapot halmaza, ahova valamelyik S-beli állapotból átléphetünk egy a betű hatására, majd esetleg még néhány üres átmenettel. Ezt a ciklust iteráljuk addig, míg el nem fogy az input.

Formálisabban δ(S,a) nem más, mint az ⋃s∈S δ(s,a) halmazból (ide lehet a-val átlépni S-ből) az üres átmenetekkel elérhető összes állapot halmaza (aka lezártja). (Ez nem véletlenül ugyanaz a képzési szabály, mint a determinizáló algoritmusé, aki azt ismeri: a szimulálás során nyilván nem teszünk mást, mint on-the-fly építjük az NFA-val ekvivalens DFA-t és azt szimuláljuk. De nem tároljuk le a DFA-t, így nem kell exp sok hely.)

Ennek az algoritmusnak a futásideje, ha m állapotú a szimulált NFA és n hosszú az input string, O(nm), lépésenként az unió képzése az legfeljebb az m állapotszám darab halmaznak az uniója, innen jön a karakterenkénti O(m) lépés, ami még mindig viselhető, ahhoz képest, hogy a backtrack időigénye O(2ⁿ) lenne. Egy, a backtracking hiányosságait kihasználó "gonosz" regexet már egy harminc-negyven karakteres stringre (egy sorra) sem biztos, hogy egy órán belül sikerül illeszteni egy backtracking algoritmussal. Erre a célra az NFA motor egyszerűen nagyságrendekkel jobb, mint pl a backtrack.

Persze ennek ellenére vannak olyan programozási nyelvek, ahol backtrackkel van implementálva a regex illesztés NFA szimulálás helyett. Ahol a nyelv szabvány könyvtárában lévő szabvány implementáció egy backtrack.

Hallani vélem lelki füleimmel az "ó, azok a balfékek" felsóhajtást?

igen?

nos, akkor épp most balfékeztétek le a Java, a PHP, a Perl, a Ruby és számos más mainstream nyelv fejlesztőit. Ezekben bizony backtrack van beégetve.

hogy miért? az egész úgy kezdődött, hogy...

folytköv