Szóval volt az a kínos ügy, mikor is az $a?^na^n$ regexet illesztve az $a^n$ szövegre kaptunk egy exponenciális illesztési időt, meg a másik kínos ügy, amikor is az $(a^*)^*b$ regexet illesztettük az $a^n$-re és szintén exponenciális futásidőt kaptunk.
A korrektség kedvéért hozzátenném, hogy az $a?a?a?a?a?$ regex nem pont az, amit középkategóriás regex crafter leír, hiszen van ismétlés operátor: $R\{min,max\}$ azt jelenti, hogy az $R$ regexet legalább $min$, legfeljebb $max$ számúszor ismételjük. Alapból greedy operátor, tehát minél több iterációt szeretne csinálni a lehetőségein belül. Így az $a?^na^n$ regexet normális körülmények közt $a\{n,2n\}$ jegyzi. Még az ennél sokkal butább $(a?)\{n\}a\{n\}$ regexről is azt hinnénk, hogy szintén produkálja az exponenciális lassulást az $a^n$ stringen
de nem
az $(a?)\{n\}a\{n\}$ regex nagy $n$-ekre is pár ms alatt illeszkedik $a^n$-re. Még az én szubnotinom is $n=400$-nál megy fel 0ms-ről 1ms-re egyáltalán az illesztés. De miért?
A kérdés érdekesebbé válik akkor, ha illesztjük az $(aa?)\{n\}$ regexet az $a^n$ stringre, mert ekkor
megint exponenciális ideig vergődik vele
amit viszont már értek, szemben az előzővel, hogy mitől gyorsult az $(a?)\{n\}a\{n\}$ ennyire fel.
Beletúrva a java.regex.Pattern.Loop osztályba azt találtam, hogy valószínűleg arról van szó, hogy iterált csoportot nem illesztenek nulla hosszon, elkerülendő a végtelen ciklust, de nem mentem utána valami mélyen.
Mindenesetre a $(a^*)^*$ és az $a^*$ regexek nem teljesen ugyanazt mondják. Ugyanis, a sima zárójel egy mai regexben (ne felejtsük el, ha "reguláris kifejezést" mondok, az jelenti a matematikai konstrukciót, a "regex" pedig a jelenkori implementációkat) egy capturing groupot jelöl: illeszkedés tekintetében valóban ekvivalens, de sikeres illesztés után le lehet kérdezni az illesztő motortól, hogy ez a subregex az input string melyik substringjére illeszkedett. Nézzük ezt meg egy olyan példán, amire jó a regex: input egy XML file, nyerjük ki belőle a tageket (attribútumok, whitespace és szöveges cdata törlésével)! Tehát pl. az 'Ez egy < i spock="vulcan" >html <b>teszt</b>része</i>' inputra szeretnénk egy "<i><b></b></i>" szöveget kapni. Most feltételezzük, hogy attribútum belsejében nincs < vagy > jel, meg úgy alapból egy XML-helyes string az input. Akkor pl. eljárhatunk úgy, hogy
Ha nem szeretnénk kinyerni egy (mondjuk precedencia miatt) zárójeles subregex tartalmát, akkor mindenképp érdemes non-capturing groupingot használjunk (kivéve esetleg az olvashatósági szempontokat :P ), aminek jele a $(?:\ldots)$. Ha pl. az $(?:a^*)^*$ regexet nézzük, na az már ekvivalens az $a^*$ regexszel: simán zárójelbe rakva még illesztés után visszakaphatjuk, hogy a belső $a^*$ rész mire illeszkedik tulajdonképpen (az első összefüggő $a$-sorozatra fog), de ebben a non-capturing formában nem tudjuk ezt meg.
A non-capturing groupokat azért is érdemes használni, mert sok motorban korlátozva van a használható backreference-ek száma, javában a javadoc alapján kilencre saccolom. A backreference, avagy visszahivatkozás, de felőlem Berke Ferenc is lehet, egy regexen belülre írt $\backslash n$ kifejezés, ahol $n$ egy szám (javában tán egy pozitív számjegy lehet), ha ilyet lát a motor, oda behelyettesíti az $n$. capturing group legutoljára elfogott tartalmát. Pl. ha két egyforma számjegy ismétlődését akarjuk szűrni, akkor arra egy kifejezés a $(\backslash d)\backslash 1$. Ha egy szövegben szóismétlődést keresünk, akkor arra pl. egy regex a $\backslash b (\backslash w^*)\backslash b\backslash s^*\backslash 1$, ami az első capturing groupba bele is teszi nekünk a szó első előfordulását. (Ha valakinek nem rémlik, a $\backslash b$ a szóhatár metakarakter, nulla hosszon illeszkedik szavak határára.)
Nézzünk egy példát, amit legegyszerűbb backreferencekkel megoldani: ha jön be két karakter, akkor mondjuk "pár"-nak őket, ha egyformák, vagy van köztük $0$ (a nulla a "joker"). Ha csak annyi a feladat, hogy mondjuk meg, hogy az input string pár-e, akkor erre ezek szerint egy jó regex: $(.)\backslash 1|0.|.0$, az első opció lekezeli a "valódi" párokat, a második ha az első karakter a "joker", a harmadik ha a második karakter a joker. Mi van, ha a kérdést úgy módosítjuk, hogy az input string párok sorozata-e? "csillagozzuk meg", mondja az egyszeri jóember: $(?:(.)\backslash 1|0.|.0)^*$, aki még arra is figyelt, hogy a külső, csillagozott csoport non-capturing legyen, mert különben az lenne az egyes csoport és ekkor az első alternatvában $\backslash 1$ helyett $\backslash 2$ kéne szerepeljen. (Egyébként a nyitójelek sorrendje határozza meg, hogy hanyas számú a capturing group.)
ha ugyanis ezt a csillagos regexet mondjuk a $0^{2n+1}$ (páratlan hosszú, tehát kizárt, hogy illeszkedő) textre illesztjük, akkor mi történik? A csillag szépen mindig próbálja illeszteni az első alternatívát (ami most a $(.)\backslash 1$), illeszkedik, örül, továbbmegy, elér a string végéig, hopp, backtrackel és mivel a második és harmadik alternatívák is illeszkednek a $00$ stringre, ezért
Ez a fajta catastrophic behaviour egyébként mindig megtörténhet, ha olyan alternatívás regexet csillagozunk meg, ahol az alternatívák nem diszjunkt szóhalmazokra illeszkednek (!), ha a $w$ szó illeszkedik két alternatívára legalább, akkor a $w^n$ kezdetű, de végül nem illeszkedő inputokra exp ideig fut a motor. Azt már korábban láttuk, hogy ha egy csillagozott csoporthoz van olyan $w$ szó, hogy egy $w^k$ és egy másik, $w^m$ szó is illeszkedik a csoportra (pl illeszkedik rá az ababab és az abababab is, akkor $w=ab$, $k=3$, $m=4$, értjük), akkor egy $w^N$ alakú, végül nem illeszkedő inputtal exponenciális illesztést lehet belőle kicsalni. Itt arról van most szó, hogy ugyanaz a $w$ szó illeszkedik többféleképp a csoportra.
A backtracket többféleképp elkerülhetjük. Egyrészt átírhatjuk a regexet diszjunkt alternatívákra is: (?:(.)\1|0[^0]|[^0]0)*. Ez megoldja most a problémát, de nem mindig tudunk így tenni (pl. van, hogy nehéz meghatározni a két nyelv metszetét egyáltalán, és persze van, hogy nem lehet ilyen egyszerűen kitiltani a metszetet, mint most az egyetlen $00$ szót).
Egy másik lehetőség, hogy ún. atomi csoportot használunk. Az atomi csoport annyit tesz, hogy nem backtrackel semmiképp: ha talál egy illeszkedést, és később a motor visszatér rá backtrack üzemben, akkor (ellentétben az eddig látott csoportokkal, amik ekkor elkezdenek keresni egy másik illesztést, legközelebb egy harmadikat, stb..) nem is próbálkozik többet, hanem dobja tovább a backtracket. (Persze ha legközelebb megint illeszteni próbálják egy másik pozícióra, akkor ott ismét keres egy első találatot.) Ha tehát az eredeti regexünket (?>(.)\1|0.|.0)* formába írjuk át (az atomi csoport jele a $(?>\ldots)$, ahogy láthatjuk), az is megoldja a problémát és backtrack nélkül, mint a szél, illeszti a kifejezést. A három regex itt.
Azért persze ne rohanjunk minden csoportot atomira átírni, néha kell a backtrack. Pl. ha egy stringről azt akarjuk megtudni, hogy $ww$ alakú-e, arra egy példa regex a $(.^*)\backslash 1$, ahogy már láttunk pár ilyet. Ha az első csoportot atomira rakjuk, akkor hát az első probléma az lesz, hogy atomi csoport nem capture csoport (semelyik, $?$-lel kezdődő csoport sem az btw). Ezt még megoldhatjuk azzal, hogy az atomi csoportot berakjuk egy elfogóba: $((?>.^*))\backslash 1$, de ez így
Amikor viszont kockázat nélkül atomivá tehetünk egy csoportot, az pl. az az eset, mikor a csoport egy prefixmentes nyelvre illeszkedik: azaz, ha egy szóra illeszkedik, akkor annak semelyik valódi prefixére nem. Ekkor ugyanis ha bejön egy adott pozíciótól kezdve egy találat, akkor másik találatokat úgyse találnánk a backtrack során (hiszen a "másik" az vagy prefixe lenne a már meglevőnek, vagy a meglevő lenne prefixe neki, egyik se fordul elő prefixmentes nyelvnél). A példánkban levő "párok" nyelve az prefixmentes (mert minden szó konkrétan kettő hosszú benne, nyilván nem prefixei egymásnak), ezért ezt teljes nyugalomban atomivá tehetjük.
Technikailag javában az atomi csoportot betudták egyfajta kérdőjeles csoportnak, ami nekem furcsa egy kicsit, de ízlések és pofonok, erre hamarosan visszatérünk.
Beletúrva a java.regex.Pattern.Loop osztályba azt találtam, hogy valószínűleg arról van szó, hogy iterált csoportot nem illesztenek nulla hosszon, elkerülendő a végtelen ciklust, de nem mentem utána valami mélyen.
Mindenesetre a $(a^*)^*$ és az $a^*$ regexek nem teljesen ugyanazt mondják. Ugyanis, a sima zárójel egy mai regexben (ne felejtsük el, ha "reguláris kifejezést" mondok, az jelenti a matematikai konstrukciót, a "regex" pedig a jelenkori implementációkat) egy capturing groupot jelöl: illeszkedés tekintetében valóban ekvivalens, de sikeres illesztés után le lehet kérdezni az illesztő motortól, hogy ez a subregex az input string melyik substringjére illeszkedett. Nézzük ezt meg egy olyan példán, amire jó a regex: input egy XML file, nyerjük ki belőle a tageket (attribútumok, whitespace és szöveges cdata törlésével)! Tehát pl. az 'Ez egy < i spock="vulcan" >html <b>teszt</b>része</i>' inputra szeretnénk egy "<i><b></b></i>" szöveget kapni. Most feltételezzük, hogy attribútum belsejében nincs < vagy > jel, meg úgy alapból egy XML-helyes string az input. Akkor pl. eljárhatunk úgy, hogy
- megkeressük az első < jelet a szövegben
- skippeljük utána a whitespace-t
- ami karaktersorozat utána jön az a tag maga, mondjuk whitespace-ig vagy > jelig; ezt egy capturing groupba tesszük
- utána mindent skippelünk az első > jelig
- kiírjuk az elkapott csoport tartalmát mondjuk <> jelek közé rakva, és ismételjük az egészet, amíg csak találunk illeszkedést.
Ha nem szeretnénk kinyerni egy (mondjuk precedencia miatt) zárójeles subregex tartalmát, akkor mindenképp érdemes non-capturing groupingot használjunk (kivéve esetleg az olvashatósági szempontokat :P ), aminek jele a $(?:\ldots)$. Ha pl. az $(?:a^*)^*$ regexet nézzük, na az már ekvivalens az $a^*$ regexszel: simán zárójelbe rakva még illesztés után visszakaphatjuk, hogy a belső $a^*$ rész mire illeszkedik tulajdonképpen (az első összefüggő $a$-sorozatra fog), de ebben a non-capturing formában nem tudjuk ezt meg.
A non-capturing groupokat azért is érdemes használni, mert sok motorban korlátozva van a használható backreference-ek száma, javában a javadoc alapján kilencre saccolom. A backreference, avagy visszahivatkozás, de felőlem Berke Ferenc is lehet, egy regexen belülre írt $\backslash n$ kifejezés, ahol $n$ egy szám (javában tán egy pozitív számjegy lehet), ha ilyet lát a motor, oda behelyettesíti az $n$. capturing group legutoljára elfogott tartalmát. Pl. ha két egyforma számjegy ismétlődését akarjuk szűrni, akkor arra egy kifejezés a $(\backslash d)\backslash 1$. Ha egy szövegben szóismétlődést keresünk, akkor arra pl. egy regex a $\backslash b (\backslash w^*)\backslash b\backslash s^*\backslash 1$, ami az első capturing groupba bele is teszi nekünk a szó első előfordulását. (Ha valakinek nem rémlik, a $\backslash b$ a szóhatár metakarakter, nulla hosszon illeszkedik szavak határára.)
Nézzünk egy példát, amit legegyszerűbb backreferencekkel megoldani: ha jön be két karakter, akkor mondjuk "pár"-nak őket, ha egyformák, vagy van köztük $0$ (a nulla a "joker"). Ha csak annyi a feladat, hogy mondjuk meg, hogy az input string pár-e, akkor erre ezek szerint egy jó regex: $(.)\backslash 1|0.|.0$, az első opció lekezeli a "valódi" párokat, a második ha az első karakter a "joker", a harmadik ha a második karakter a joker. Mi van, ha a kérdést úgy módosítjuk, hogy az input string párok sorozata-e? "csillagozzuk meg", mondja az egyszeri jóember: $(?:(.)\backslash 1|0.|.0)^*$, aki még arra is figyelt, hogy a külső, csillagozott csoport non-capturing legyen, mert különben az lenne az egyes csoport és ekkor az első alternatvában $\backslash 1$ helyett $\backslash 2$ kéne szerepeljen. (Egyébként a nyitójelek sorrendje határozza meg, hogy hanyas számú a capturing group.)
bad move
ha ugyanis ezt a csillagos regexet mondjuk a $0^{2n+1}$ (páratlan hosszú, tehát kizárt, hogy illeszkedő) textre illesztjük, akkor mi történik? A csillag szépen mindig próbálja illeszteni az első alternatívát (ami most a $(.)\backslash 1$), illeszkedik, örül, továbbmegy, elér a string végéig, hopp, backtrackel és mivel a második és harmadik alternatívák is illeszkednek a $00$ stringre, ezért
végigpróbálja mind a $3^n$ lehetőséget
mielőtt rájönne, hogy nem illeszkedik.Ez a fajta catastrophic behaviour egyébként mindig megtörténhet, ha olyan alternatívás regexet csillagozunk meg, ahol az alternatívák nem diszjunkt szóhalmazokra illeszkednek (!), ha a $w$ szó illeszkedik két alternatívára legalább, akkor a $w^n$ kezdetű, de végül nem illeszkedő inputokra exp ideig fut a motor. Azt már korábban láttuk, hogy ha egy csillagozott csoporthoz van olyan $w$ szó, hogy egy $w^k$ és egy másik, $w^m$ szó is illeszkedik a csoportra (pl illeszkedik rá az ababab és az abababab is, akkor $w=ab$, $k=3$, $m=4$, értjük), akkor egy $w^N$ alakú, végül nem illeszkedő inputtal exponenciális illesztést lehet belőle kicsalni. Itt arról van most szó, hogy ugyanaz a $w$ szó illeszkedik többféleképp a csoportra.
A backtracket többféleképp elkerülhetjük. Egyrészt átírhatjuk a regexet diszjunkt alternatívákra is: (?:(.)\1|0[^0]|[^0]0)*. Ez megoldja most a problémát, de nem mindig tudunk így tenni (pl. van, hogy nehéz meghatározni a két nyelv metszetét egyáltalán, és persze van, hogy nem lehet ilyen egyszerűen kitiltani a metszetet, mint most az egyetlen $00$ szót).
Egy másik lehetőség, hogy ún. atomi csoportot használunk. Az atomi csoport annyit tesz, hogy nem backtrackel semmiképp: ha talál egy illeszkedést, és később a motor visszatér rá backtrack üzemben, akkor (ellentétben az eddig látott csoportokkal, amik ekkor elkezdenek keresni egy másik illesztést, legközelebb egy harmadikat, stb..) nem is próbálkozik többet, hanem dobja tovább a backtracket. (Persze ha legközelebb megint illeszteni próbálják egy másik pozícióra, akkor ott ismét keres egy első találatot.) Ha tehát az eredeti regexünket (?>(.)\1|0.|.0)* formába írjuk át (az atomi csoport jele a $(?>\ldots)$, ahogy láthatjuk), az is megoldja a problémát és backtrack nélkül, mint a szél, illeszti a kifejezést. A három regex itt.
Azért persze ne rohanjunk minden csoportot atomira átírni, néha kell a backtrack. Pl. ha egy stringről azt akarjuk megtudni, hogy $ww$ alakú-e, arra egy példa regex a $(.^*)\backslash 1$, ahogy már láttunk pár ilyet. Ha az első csoportot atomira rakjuk, akkor hát az első probléma az lesz, hogy atomi csoport nem capture csoport (semelyik, $?$-lel kezdődő csoport sem az btw). Ezt még megoldhatjuk azzal, hogy az atomi csoportot berakjuk egy elfogóba: $((?>.^*))\backslash 1$, de ez így
csak az üres stringre fog illeszkedni
mert először a $.^*$ csoport a csillag mohósága miatt bescanneli az egész inputot, aztán rájön, hogy ezután nincs ott az egész input még egyszer, aztán visszalép egyet, úgy is megnézné, hogy ami utána következik, az az első csoport (most már eggyel rövidebb) tartalma-e, stb. Amikor eljut a string feléhez, ha $ww$ alakú, észre fogja venni, de ehhez $|w|$-szer kell backtrackelni és egy-egy karaktert elengedni. Atomi csoportnál nem indul el a backtrack, a csillag lenyel mindent, azt mondja, hogy az input hátralevő részére a backreference nem illeszkedik, és visszadobja az egészet találat nélkül.Amikor viszont kockázat nélkül atomivá tehetünk egy csoportot, az pl. az az eset, mikor a csoport egy prefixmentes nyelvre illeszkedik: azaz, ha egy szóra illeszkedik, akkor annak semelyik valódi prefixére nem. Ekkor ugyanis ha bejön egy adott pozíciótól kezdve egy találat, akkor másik találatokat úgyse találnánk a backtrack során (hiszen a "másik" az vagy prefixe lenne a már meglevőnek, vagy a meglevő lenne prefixe neki, egyik se fordul elő prefixmentes nyelvnél). A példánkban levő "párok" nyelve az prefixmentes (mert minden szó konkrétan kettő hosszú benne, nyilván nem prefixei egymásnak), ezért ezt teljes nyugalomban atomivá tehetjük.
Technikailag javában az atomi csoportot betudták egyfajta kérdőjeles csoportnak, ami nekem furcsa egy kicsit, de ízlések és pofonok, erre hamarosan visszatérünk.
No comments:
Post a Comment