regex matching algorithm: a success story (NOT)

..szóval úgy volt, hogy Ken Thompson a '60-as évek közepén ugye kitalálta a remek időigényű algoritmusát regex illesztésre, $m$ hosszú regexet $N$ hosszú szövegre $O(m\cdot N)$ idő alatt illeszt véges, nemdeterminisztikus automatát használva.

Amit nem tett bele a Unix-ba '71-ben, sem a grep-be: ehelyett backtracket implementált. Erre azért jó oka volt: amit akkor támogattak ezek a rendszerek, abba se a $|$ (unió), se a $+$ (iteráció), se a $?$ (opcionális) jelek nem kerültek bele, így lényegében kb csak karakterosztályokat lehetett konkatenálni, arra jó a backtrack, szintén lineáris időigénye lesz.

Alfred Aho viszont megcsinálta '79-re a teljes "klasszikus" regex illesztő motort a grepbe, majd később '85-ben a Unix-ba is. Az ő implementációja a regex$\to$NFA$\to$DFA, majd illesztés vonalat követte, így még $O(2^m\cdot N)$ időigényű volt. (Still a better love story than twilight, mert a regex általában rövid. Habár azért ránézhetünk az RFC822-re, hogy mi is az "official" regex emailcím validálásra...) 

Aztán jött Rob Pike, aki lényegében feltalálta még egyszer Ken Thompson algoritmusát és a sam szövegszerkesztőbe már ez került bele a '80-as évek közepén, egy remek kis $O(m\cdot N)$-es időigényű regex illesztő motor, ami libként bekerült a Unix nyolcadik kiadásába.

End of story, happy end?

nem hát.

Ezt követően ugyanis jött Henry Spencer, aki, ahogy a wikin olvashatjuk, "wrote a non-proprietary replacement for regex(3), the Unix library for handling regular expressions, and made it freely available; his API followed that of Eighth Edition Research Unix". Tehát, a Unix nyolcas változatában levő regex illesztőnek elkészítette egy ingyenes, nyílt forrású változatát, ugyanazzal az API-val.

hja, API-val. az input és az output specifikáció tényleg ugyanaz lett.

csak azt nem tudta, hogy a motor hogy működik, ezért backtrackkel implementálta le ezt a nyílt forrású változatot. Értjük? a hatékony, szélvészgyors, de nem nyílt forrású regex illesztő motor helyett Spencer backtrack implementációja ment ki a köztudatba és terjedt el, mert az volt a nyílt forrású. Ez belekerült a perl nyelv motorjába, ami egy, a regex matchinget nyelvi szinten támogató programozási nyelv, és innen a PCRE (perl compatible regular expression) libraryvel szépen továbbment pl. a PHP (pcre_... függvények), Java (java.util.regex.Matcher és java.util.regex.Pattern), Ruby, Python, stb. programozási nyelvekbe is, amik ezért

a mai napig backtrackkel végzik az illesztést

és ez nem is valószínű, hogy meg fog változni.

Ez azért elég komoly problémákat tud okozni. Ha például az $(a?)^na^n$ regexet akarjuk illeszteni az $a^n$ textre (valamekkora $n$-re), annak nyilván illeszkednie kéne: az opcionális $a?$-eket végig kihagyjuk, és a maradék $a^n$ a regexből szépen illeszkedik az $a^n$ textre.

Itt egy Java kód hozzá, ezt az illesztést csinálja forciklussal $n=1\ldots 30$ közt. Ha ezt pl. ideone.com-on futtatjuk (az osztályt default package-be kell átrakni és System.err helyett System.out-ra printelni, hogy lássuk), ezt kapjuk:

i = 1 found in 2522746 nanoseconds.
i = 2 found in 110668 nanoseconds.
i = 3 found in 43774 nanoseconds.
i = 4 found in 53771 nanoseconds.
i = 5 found in 311331 nanoseconds.
i = 6 found in 126130 nanoseconds.
i = 7 found in 214845 nanoseconds.
i = 8 found in 817853 nanoseconds.
i = 9 found in 443221 nanoseconds.
i = 10 found in 1894930 nanoseconds.
i = 11 found in 310500 nanoseconds.
i = 12 found in 572593 nanoseconds.
i = 13 found in 1135540 nanoseconds.
i = 14 found in 2214628 nanoseconds.
i = 15 found in 4528347 nanoseconds.
i = 16 found in 9271553 nanoseconds.
i = 17 found in 19245308 nanoseconds.
i = 18 found in 39593656 nanoseconds.
i = 19 found in 79272588 nanoseconds.
i = 20 found in 168863023 nanoseconds.
i = 21 found in 346571873 nanoseconds.
i = 22 found in 725774631 nanoseconds.
i = 23 found in 1445924416 nanoseconds.

és ezután elszáll timeouttal. Az elejét nem kell nézni, az még akkor történik, mikor melegszik a Java HotSpot, $i=11$ körülre bemelegszik és onnan mit látunk? $i=12$-től kezdve szinte tökéletes konzisztenciával mindegyik futásidő duplája az előzőnek. Ez annyira látványosan exponenciális futásidő, hogy azt tanítani kéne :D

Ez itt egy PHP kód, ugyanerre. Ha ezt futtatjuk, jön az output:

preg_match (a?)<sup>n</sup>a<sup>n</sup> on a<sup>n</sup>...<br/>
i = 1: 0.00009 seconds, answer: 1<br/>
i = 2: 0.00003 seconds, answer: 1<br/>
i = 3: 0.00002 seconds, answer: 1<br/>
i = 4: 0.00002 seconds, answer: 1<br/>
i = 5: 0.00003 seconds, answer: 1<br/>
i = 6: 0.00002 seconds, answer: 1<br/>
i = 7: 0.00003 seconds, answer: 1<br/>
i = 8: 0.00005 seconds, answer: 1<br/>
i = 9: 0.00007 seconds, answer: 1<br/>
i = 10: 0.00012 seconds, answer: 1<br/>
i = 11: 0.00025 seconds, answer: 1<br/>
i = 12: 0.00047 seconds, answer: 1<br/>
i = 13: 0.00095 seconds, answer: 1<br/>
i = 14: 0.00193 seconds, answer: 1<br/>
i = 15: 0.00392 seconds, answer: 1<br/>
i = 16: 0.00815 seconds, answer: 1<br/>
i = 17: 0.01643 seconds, answer: 1<br/>
i = 18: 0.03618 seconds, answer: 1<br/>
BULLSHIT! i = 19: 0.06781 seconds, answer: <br/>
BULLSHIT! i = 20: 0.06848 seconds, answer: <br/>
BULLSHIT! i = 21: 0.06995 seconds, answer: <br/>
BULLSHIT! i = 22: 0.06708 seconds, answer: <br/>
BULLSHIT! i = 23: 0.06774 seconds, answer: <br/>
BULLSHIT! i = 24: 0.06841 seconds, answer: <br/>
BULLSHIT! i = 25: 0.06767 seconds, answer: <br/>
BULLSHIT! i = 26: 0.06967 seconds, answer: <br/>
BULLSHIT! i = 27: 0.06852 seconds, answer: <br/>
BULLSHIT! i = 28: 0.06655 seconds, answer: <br/>
BULLSHIT! i = 29: 0.07058 seconds, answer: <br/>
BULLSHIT! i = 30: 0.06759 seconds, answer: <br/>
BULLSHIT! i = 31: 0.06765 seconds, answer: <br/>
BULLSHIT! i = 32: 0.06806 seconds, answer: <br/>
BULLSHIT! i = 33: 0.06781 seconds, answer: <br/>
BULLSHIT! i = 34: 0.07048 seconds, answer: <br/>
BULLSHIT! i = 35: 0.06778 seconds, answer: <br/>
BULLSHIT! i = 36: 0.06683 seconds, answer: <br/>
BULLSHIT! i = 37: 0.06969 seconds, answer: <br/>
BULLSHIT! i = 38: 0.06829 seconds, answer: <br/>
BULLSHIT! i = 39: 0.06688 seconds, answer: <br/>
BULLSHIT! i = 40: 0.06711 seconds, answer: <br/>
BULLSHIT! i = 41: 0.06732 seconds, answer: <br/>
BULLSHIT! i = 42: 0.06824 seconds, answer: <br/>
BULLSHIT! i = 43: 0.06870 seconds, answer: <br/>
BULLSHIT! i = 44: 0.07062 seconds, answer: <br/>
BULLSHIT! i = 45: 0.07048 seconds, answer: <br/>
BULLSHIT! i = 46: 0.06767 seconds, answer: <br/>
BULLSHIT! i = 47: 0.06768 seconds, answer: <br/>
BULLSHIT! i = 48: 0.06814 seconds, answer: <br/>
BULLSHIT! i = 49: 0.06778 seconds, answer: <br/>

ez még mókásabb, mint a Java: $i=9$-re felmelegszik, onnan kezdve szépen duplázódik az idő $i=18$-ig, meg is találja, hogy illeszkedik, de aztán! aztán mivel a backtracking motor túl sokáig fut, a függvény kilövi (how to handle backtrack 101 :D ), és azzal jön vissza lejárt időlimit után, hogy nem illeszkedik a regexre a string. Nem tudnám megmondani, hogy ez a mindenféle hibakód nélkül visszajövő hibás válasz, vagy a Java-féle timeout a jobb megoldás :D

Bottom line: ha regexet illesztesz egy mainstream programozási nyelvben, jó eséllyel egy csonthülye backtracking algoritmus fogja neked csekkolni az illeszkedést. Emiatt egymásba ágyazott csillagoknál, alternálásnál egész jó esélyed van arra, hogy ne sikerüljön az illesztés, hanem timeouttal elszálljon az egész.

Legközelebb megnézünk egy-két tippet, hogy ha már backtracking motort kell használj, mert az van a nyelvedben, akkor hogy érdemes megszerkeszteni azt a regexet, hogy gyorsabban lefusson a backtrack :)

folytköv

(források: itt)