4. gyakorlat

A backtracking regex motorok illesztési mechanizmusa¶

Láttuk már korábban, hogy a Java és a grep időnként egész más találatokat hoz fel, ez a motorjuk közti különbség miatt van:

a grep ha tud, véges automatát épít és azt használja az illesztéshez;
a Java pedig egy visszalépéses kereső, azaz backtracking motor.

A backtracking motorok mechanizmusa kb a következő: egy kifejezést egy pozícióra mikor illesztenek, akkor valamilyen sorrendben adnak fel találatokat, előbb az elsőt, újrakérés esetén a másodikat, stb, végül egy "nincs több lehetőség ezen a pozíción" jelzést.

karakterek, vagyolás, szorzat¶

ha egy a karaktert illesztünk valahol, akkor legfeljebb egyetlen találatot ad: ha a következik, akkor azt, ha nem a következik, akkor failel, ugyanúgy, mintha az a feladása után kérnénk tőle a következőt.
ha egy R|T kifejezést illesztünk valahol, akkor a sorrend: először R összes találatát adja fel sorrendben, majd ha R failel, akkor T összes találatát sorrendben, majd ha már T is failel, akkor failel ez a kifejezés is.
ha egy RT kifejezést illesztünk valahol, akkor
először lekéri R első találatát, ez tart egy pozícióig,
ettől a pozíciótól kezdve elkéri T első találatát,
ha kérjük a következő illesztést, akkor továbbra is R első találatát tartja meg és kéri T következő találatát mellé,
ha T failel, akkor kéri el R következő találatát, és az annak a záró pozíciójától kezdő T első találatát,
majd ha már R is failel, akkor fog RT is failelni az adott pozíción.
lényegében tehát mint egy egymásba ágyazott ciklus, a külső ciklus R illesztése, a belső pedig T illesztése.

Nézzük meg eddig pl. az egyik első példánkat kicsit módosítva, az (alm|alma|al)(malom|l) regex illesztését az almalom szóra:

ez egy szorzat, előbb az első tagját illeszti a legelső pozícióra
az (alm|alma|al) illesztésekor először az alm részt próbálja illeszteni az almalom elején
ez egy háromtényezős szorzat, de most ennek a részletezését kihagyva: az alm illeszkedik, az első tag ezt dobja fel első találatnak
most az alom szó elejére próbálja illeszteni hozzá a malom|l regexet
ez egy vagyolás, először a malommal próbálkozik, ez failel ezen a pozíción
majd az l-lel próbálkozik, ez is failel ezen a pozíción, ezért az egész vagyolás, a (malom|l) failel
mivel a (alm|alma|al)(malom|l) illesztésekor a második tag failelt, ezért most az elsővel nézzük a következő találatot, az almalom szó elejétől
az alm alternatíva egyetlen féleképp illeszkedik, ez a második kérdezéskor failel
kipróbáljuk a második alternatívát: az alma illeszkedik, ezt dobja fel találatnak
így most a (malom|l) regexet a lom szó elejétől próbáljuk illeszteni
az első alternatíva nem illik ide, failel, a második viszont igen, az feldobja az l-t mint első találatot (ha újra kérnénk tőle, akkor failelne, ez az egy találata van)
így az (alm|alma|al)(malom|l) szorzatunk feldobja első találatnak az almal-t az almalom szó elejéről
ha esetleg ez egy hosszabb regex része lenne, és további illesztési failek miatt kérnénk tőle a következő találatot ugyanitt, akkor pedig az almalom-ot dobná fel, mint az al és malom illesztését a két tagból, ha újra kérnénk, akkor már failelne.

Látszik tehát, hogy az alternatívák sorrendje számít backtrack motoroknál (és nem számít a grepnél). Általában ha csak egy találatot szeretnénk megkapni, érdemes úgy rendezni az alternatívák sorrendjét, hogy előre tegyük azt, ami várakozásaink szerint leggyakrabban fogja feladni a nekünk jó találatot, ezzel gyorsítva az illesztési folyamatot.

kérdőjel¶

Ha egy R? regexet illesztünk egy pozíción, akkor a találatok sorrendje: először feladja találatnak sorban az R regex illeszkedéseit a megadott inputra, majd ha végül failel az R, akkor még feladja az üres stringet is, és ezután failel.

Ezt úgy is mondjuk, hogy a kérdőjel mohó: preferálja az "illeszkedik valami" opciót a "nincs itt semmi"vel szemben.

Mi történik például, ha az a?a?a?aaa regexet illesztjük az aaa stringre?

először az első a? feladja az első a-t mint találatot, most az a?a?aaa-t kell illesszük a megmaradt aa-ra
most a második a? is lenyel egy a-t, marad a?aaa vs. a
a harmadik is: aaa vs üres string, és ez failel. Visszalépünk az előző állapotba és kérünk egy másik opciót.
most a harmadik a? feladja az üres stringet mint illeszkedést, marad aaa vs. a
az első a még illeszkedik, de az aa vs. üres string failel. Visszalépünk, az a is failel azzal, hogy nincs több opció, majd a harmadik a? is failel azzal, hogy már feladta az üres stringet is
a második a?-hez visszajut a vezérlés, aki egy a-t adott fel, most feladja az üres stringet. Most az a?aaa stringet a megmaradt aa stringre próbáljuk illeszteni.
a harmadik a? már egy új menetben van, hiszen korábban már végigfailelte az illesztést, most ezt előlről kezdjük, hiszen nem jobbról, az a felől, hanem balról, a második a? felől érkezik a motor, feladja az a-t mint első illeszkedést
az aaa vs a illesztés failel megint, mert az aa vs üres string illesztés failel
visszaérünk a harmadik a?-ig, ezúttal feladja az üres stringet mint következő találatot, marad az aa string
az aaa vs aa illesztés is failel, visszamegyünk a harmadik a?-ig, ő már feladta az utolsó opcióját, visszamegyünk a második a?-ig, mostanra ő is, visszamegyünk az első a?-ig
aki feldobja második opcióként az üres stringet, most az a?a?aaa regexet illesztjük az aaa stringre
a második a? és a harmadik is először megint az a-t dobják fel mint találatot, de az aaa vs a illesztés failel
a harmadik a? elengedi az a-t, feladja az üres stringet, aa vs a megint failel
eztán a második a? elengedi az a-t, feladja az üres stringet, de a harmadik megint restartolva lenyeli az a-t
fail után engedi el és így jutunk el oda, hogy mindhárom kérdőjeles kifejezés az üres stringet dobja fel és a maradék három a illik az input aaa-ra.

Ez elég sok lépés: összesen 8 lehetőség van arra, hogy a kérdőjeles a-k közül melyik legyen a és melyik üres string és a mohóság miatt az utolsó lesz, ami végül találatot ad. Általában ha n hosszú a?-lel indítunk, majd n darab a-val és ezt illesztjük n darab a-ra, a backtrack motorok ezen eltöltenek 2ⁿ lépést...

Próbáljuk is ki: mérve a futásidőt, egyesével növeljük az a-k számát és figyeljük meg, hogyan növekszik az illesztés ideje Javában vs grepben!

csillag, plusz¶

Az R* kifejezés illesztési sorrendje:

először illeszti a pozíción R-t, feljön az első találat, ha ez üres string, akkor kéri a következőt,
ezután a találat végétől újra illeszti R*-ot (majd annak az első találatának a végétől újra és újra)
amikor ebben az RRRR..R találatsorozatban egy R már failel, akkor ezt az eddigi illeszkedést dobja fel első találatként, jegyezve az összes belső R-ben, hogy éppen melyik találatot dobták fel
ha újat kérnek, akkor az utolsó R-től mint R*-tól kéri a következő, majd a következő találatot
ha az utolsó R már failel, akkor a következő találatát úgy készíti, hogy eltávolítja az utolsó R-t (így eggyel kevesebb "tagból rakja ki" a találatot, mint eddig)
az ezutáni találatán a (most már) utolsó R-től mint R*-tól kéri a következő találatot...
... és így tovább, egészen addig, míg oda nem jut, hogy csak egy R illeszkedik és az is mint R* már feladta az utolsó találatát, ekkor utolsó lépésben feldobja az üres stringet mint találatot
és ezután failel.

Az R+ annyiban tér el ettől, hogy utolsó találatként nem dobja fel az üres stringet.

Nézzünk erre is egy példát: illesszük az ^(a|aa)*b$ regext az aaaa stringre (melyre nem illeszkedik)!

A találatok sorrendje, ahol a b-t kezdi majd illeszteni (és nem találja sehol) a következő lesz, szóközzel választom el a belső R-ek határait:

a a a a (mindenből az első találatot választjuk, amíg el nem érünk az input végéig)
a a a (feladjuk az utolsó a-t, helyette a második aa nem illeszkedik, az utolsó komponenst elengedjük)
a a aa (az utolsó komponenst mint (a|aa)*-ot léptetjük tovább, a következő találata aa, utána már nincs illeszkedés, ezt adjuk fel
a a (az utolsó komponenst léptetnénk tovább, failel, elengedjük)
a aa a (a második a-t léptetjük tovább mint (a|aa)*-ot: egyrészt az a utáni következő találat az aa lesz, de illeszt tovább és még a következő (a|aa) blokk első találatát is hozzáveszi)
a aa (léptetnénk az utolsó komponenst, failel, elengedjük)
a (léptetnénk az utolsó komponenst, failel, elengedjük)
aa a a (léptetjük az utolsó komponenst, az aa lesz az első tényezőjében, majd megint illeszkedik, első találat a, megint, annak is első találata a, most már nem, ezt adjuk fel következőnek)
aa a (léptetnénk tovább az utolsó komponenst, nem illeszkedik a másik alternatíva, az aa, a maradék inputra, ami a, failel, elengedjük)
aa aa (léptetjük az utolsó komponenst, aa, tovább nem tudjuk ismételni, ezt adja fel)
aa (léptetnénk tovább az utolsó komponenst, failel, elengedjük)
üres string (elengedtük az utolsó komponenst, utoljára feladjuk az üres stringet)
fail (vége)

Ez így szintén az, aminek látszik: exponenciális futásidejű illesztés, azaz catastrophic backtracking.

Kézbe osztott párok¶

Pókerben a lapok értékét a [02-9TJQKA] karakterosztállyal kódolhatjuk, ahol 0 a joker lap. Ha kapok két karaktert ebből az osztályból, az egy pár akkor, ha megegyeznek, vagy ha legalább egyikük joker.

Ha egy pár felismerésére kell regext írjunk, az ember előállhat pl. a (?:0.|.0|(.)\1) regexszel: vagy az első lap joker, vagy a második, vagy az elsőt captureöljük és ugyanaz követi. Ezzel magában még nincs is semmi gond első ránézésre.

Ha viszont pár-sorozatok felismerésére kell regext írnunk, azaz egy olyat, mely pl. illeszkedik az 5502JJ30QQ stringre, de nem illeszkedik pl. az 5502JT30QQ stringre, akkor előállhatunk a következő ötlettel:

^(?:0.|.0|(.)\1)+$

Abból a szempontból ez nem hibás, hogy valóban a kért stringekre illeszkedik: iterált csoporton belül a backreference mindig az aktuális csoport"példány"on belül tárolja le az illeszkedést.

Mi történik, ha ezt a regext az 0000000 (hét darab nulla) stringre illesztjük?

iterálás: először a 0. illeszkedik az első két nullára, majd a 0. a következő kettőre, majd a 0. a következő kettőre, utána a három alternatíva közül egyik sem az egyetlen maradék nullánkra, ezt dobja fel a +-os rész első találatnak, de a $ nem matchel, fail.
látjuk, hogy a 00 stringre mind a három alternatívánk illeszkedik! az illesztési sorrendben azt írom, hogy az egyes 00 substringekre a motor sorban melyik alternatívák illesztését jelenti le, szóközzel elválasztva, tehát az első feldobott találat a 0. 0. 0. volt, és a $-nál failelt
az utolsó iterált rész léptetésével kapjuk a 0. 0. .0 illeszkedést, majd
0. 0. (.)\1
0. 0.
0. .0 0.
0. .0 .0
0. .0 (.)\1
0. .0
0. (.)\1 0.
0. (.)\1 .0
0. (.)\1 (.)\1
0. (.)\1
0.
.0 0. 0.
...

ez 39 lehetőség végigpróbálását jelenti, általában ha 2n+1 hosszú az input, csupa 0, akkor kb. 3ⁿ lépést igényel az illesztés. Próbáljuk ki ezt is Javában és greppel is!

A catastrophic backtracking problémájával ebben a formában tudunk találkozni, amikor van egy (R|T)* vagy (R|T)+* alakú olyan rész a regexünkben, ahol is létezik olyan x string, ami illik R-re is és T-re is (mint most volt a 00): ilyenkor ha nincs találat, de az inputban sok x követi egymást ezen a ponton, akkor az kivált egy exponenciális idejű illesztést, míg a motor rájön, hogy nincs illeszkedés.

Ezt ebben a feladatban könnyen ki tudjuk védeni, pl. az eredeti helyett a 0[^0]|[^0]0|(.)\1 regex iterálásával, ebben a három alternatíva diszjunkt lehetőségeket fed le, így az első találat után a következő kérésekor failelni fognak és lineáris időben kiderül, hogy illeszkedik-e a stringünk vagy sem.

Possessive iterálás¶

A Java motor támogatja a possessive quantifiereket: a ?, {..}, + és * helyett a ?+, {..}+, ++, *+ operátorokkal az alap greedy viselkedés helyett

az első találatot pontosan ugyanúgy adják fel, mint az eredeti ?, {..}, + és * operátorok,
viszont ha kérnek tőlük következőt, akkor nem adnak, hanem failelnek.

Ez azt is jelenti, hogy egészen megváltozik, mikre fog illeszkedni a regex! Használjuk körültekintően, kizárólag akkor, ha biztosak vagyunk benne, hogy az iterált rész legelső találata ha nem megfelelő, akkor nincs is jó lehetőség.

A fenti pókeres példára visszatérve, a ^(?:0.|.0|(.)\1)++$ regex sem okoz catastrophic backtrackinget: a 0. 0. 0. .. 0. első találat feladása után mivel a még egy nulla nem az input vége, a motor kéri tőle a következő találatot, erre pedig egyből failelni fog. (Lépésszámot tekintve gyorsabban, mint ha a ^(?:0[^0]|[^0]0|(.)\1)+$ regexet illesztenénk, hiszen az kipróbálja a belső alternatívákat is, mind failel, visszalépked és egyesével adja fel az egyre rövidebb prefixeket, és csak mikor feladja az utolsót és egyik se lett az input vége, akkor failel el. Persze azért puding próbája az evés, mérjük le az idejét Javában a két regex illesztésének!)

Lazy iterálás¶

Greedy helyett egy másik opció a lazy quantifier: a ?, {..}, + és * helyett a ??, {..}?, +?, *? operátorokkal az alap greedy viselkedés helyett

az R? előbb adja fel az üres stringet találatnak, és csak ezután halad végig az R találatain
az R* előbb adja fel az üres stringet, majd (jelölje Ri az R kifejezés i-edik találatát, hogy jobban látsszon) a sorrend:
R1
R1 R1
R1 R1 R1 (amíg van még R-illeszkedés, csak egyesével veszi fel őket)
R1 R1 R2
R1 R1 R3 (mondjuk most ez volt az utolsó alternatíva)
R1 R2 (itt is először csak egyet illeszt, nem iterál tovább akkor se ha lehet)
R1 R2 R1 (csak a következő lépésben)
R1 R2 R1 R1 (ha mondjuk ennyiszer lehet így iterálni)
R1 R2 R1 R2 (mondjuk itt ez az utolsó)
R1 R2 R2 (mondjuk itt ez az utolsó)
R1 R3 (stb)
az R+ ettől annyiban tér el, hogy nem dobja fel az elején az üres stringet
az intervallum-ismétlések pedig minél kevesebbet próbálnak iterálni és csak akkor rátenni még egy R-t ha kérik tőlük a következőt

Mint láthatjuk, a lazy iterálás viszont feldobja ugyanazokat a lehetőségeket, mint a greedy, tehát

az illeszkedő stringek köre ugyanaz marad
a konkrét visszaadott illeszkedés lehet más
ha az input string nem illeszkedik a reguláris kifejezésre, ez is ugyanúgy végigpróbál minden lehetőséget, tehát sebességre nem lesz jobb ilyenkor
viszont illeszkedő string esetén lehet, hogy más konkrét csoportokat ad vissza, mint greedy változatban, és lehet, hogy nem ugyanannyi lépésben találja meg, mint greedy változatban.

Például ha egy xml-ben meg akarjuk keresni az <a> tagek belsejében lévő tartalmakat, korábban egy lehetőség, ami eszünkbe juthatott, az <a>(.*)</a> regex lehetett, azonban ez az <a>egy</a>kettő<a>három</a> input esetén a . greedy iterálása miatt találatában az első csoportba az egy</a>kettő<a>három stringet teszi, ami nem az, amit szeretnénk! (Ellenőrizzük.) Ehelyett a lehető legkevesebb karaktert akarjuk ismételni és rögtön az első záró tagnál kiszállni: <a>(.*?)</a> már előbb az egy, majd újra findolva a három stringet találja meg, ahogy szeretnénk.

Atomi csoportok¶

Javában támogatottak a (possessive quantifierekhez nagyon hasonló) atomi csoportok is, melynek jele az (?>..) zárójelpáros; egy (?>R) reguláris kifejezés illesztésekor egy pozíciótól

a motor elkéri R első illeszkedését ezen a pozíción,
ha nincs, akkor failel,
ha van, feladja ezt az első illeszkedést, és ha kérnek tőle még egyet, akkor failel.

Tehát ha nézzük az R*+ possessive iterálást, ez ugyanaz, mint az (?>R*) atomi csoportban greedy iterálás: mindkettő a greedy R* legelső találatát adja fel és mást nem. Ha véletlenül olyan környezetben vagyunk, mely atomi csoportot támogat, de possessive iterálást nem, így oldhatjuk meg. A párok felismerésére pl. egy szintén jó reguláris kifejezés lett volna az (?>0.|.0|(.)\1) atomi csoport, hiszen mivel minden találat kétbetűs, így biztos, hogy ha még egyszer megkérdezik tőlünk ugyanazon a pozíción, hogy van-e még illeszkedés, ha adunk is, úgyis ugyanazt adnánk, mint adtunk korábban, ezt pedig nem akarjuk, hiszen az egész hátralévő illesztési mechanizmus megismétlődne még egyszer fölöslegesen.

Utolsó frissítés: 2021-10-23 18:39:09