Chomsky normálforma polinomidőben

Egy környezetfüggetlen nyelvtan (továbbiakban CF nyelvtan, vagy csak CFG) Chomsky alakú, ha kétféle szabály van benne:

• A → BC (egy változót cserélhetünk két változóra)
• A → a (egy változót cserélhetünk egy betűre)

Mármost ha csak ilyen szabályokat engednénk meg, akkor az üres szót (most legyen ennek jele ε) nem lehetne levezetni a kezdőszimbólum S-ből, mert nem tudna rövidülni a munkastringünk. Ezért kivételként megengedjük az S → ε szabályt, de csak akkor, ha S amúgy nem szerepel jobb oldalon sehol (ha szerepelne, akkor az megfektetene néhány elemző algoritmust, amik CF nyelvtanokra működnek).

Minden CF nyelvtant lehet Chomsky alakra hozni, ehhez négy alaplépés van:

1. Az ε jobboldalú szabályoktól megszabadulunk, ezt nevezzük ε-mentesítésnek.
2. Az A → B (egy változót egy változóra átíró) ún. láncszabályoktól is megszabadulunk, ezt hívjuk láncszabálymentesítésnek.
3. Ha van olyan jobb oldal, ami legalább három hosszú, azt több részbe daraboljuk, nevezhetjük ezt mondjuk darabolásnak.
4. Ha marad A → aB, Ba, aa alakú szabály, tehát ami ugyan kettő hosszú, de van benne terminális, akkor ahhoz a terminálishoz bevezetünk egy új változót, azt írjuk az ilyen jobboldalakba, és abból az új változóból csak ezt a terminálist lehessen levezetni. Legyen mondjuk a neve ennek nagybetűsítés :D

A legtöbb egyetemen a világon ezt konkrétan ebben a sorrendben is tanítják, hogy így kell csinálni

de ez egyszerűen plain wrong

mert exponenciálisan is nagyobb nyelvtant eredményezhet, teljesen feleslegesen, ahogy mindjárt látni is fogjuk.

Nézzük az átalakításokat egyenként.

ε-mentesítés.

• Először meghatározzuk egy sima fixpontiterációval, hogy kikből lehet egyáltalán ε-t levezetni, egy vagy több lépésben. Tehát egy N halmazba tesszük az ilyen szimbólumokat:
• inicializálás: azokat az A-kat tesszük N-be, akikre van A → ε szabály.
• iteráció: ha találunk olyan A változót, amire van olyan A → X1X2...Xk szabály, amiről az összes Xi már benne van N-ben, akkor tegyük bele A-t is N-be. (világos: ha minden Xi-t ki tudok nullázni, akkor az A-t is úgy, hogy előbb X1..Xk-ra átírom, aztán kinullázom az összes Xi-t)
• fixpontiterációt csinálunk, azaz addig toljuk az iterációs lépést, amíg a halmazunk már nem változik tovább.
• Ezek után pedig átalakítjuk a nyelvtant: az új nyelvtan szabálya úgy készülnek, hogy 
• ahányféleképpen el lehet hagyni nullázható (N-beli) változót jobb oldalról, annyiféleképp elhagyjuk,
• de persze A → ε szabályt nem veszünk fel (ami eredetileg is ilyen volt, vagy ha úgy kapnánk, hogy mindent elhagyunk).
• Ha ezt csináljuk, akkor még ellenőrizni kell, hogy S, a kezdőszimbólum nullázható-e. Ha az, akkor fel kell vegyünk egy új S0 kezdőszimbólumot, és S0 → S | ε szabályokat. (Emiatt az új kezdőszimbólumból egyrészt le tudunk vezetni üres szót is, másrészt mivel új, biztos nem volt jobb oldalon.) De még egyszer: ezt csak akkor, ha S N-beli, nullázható változó.

Nézzünk példát:

S → AB | AAaB | CBA

A → BB | aBBa | a

B → ε | aSB

C → aA | BC

Ekkor eredetileg N = { B }, mert van B → ε szabály.

Eztán iterációban találunk egy A → BB szabályt, aminek a jobb oldalát ki tudjuk nullázni (mind a két B benne van N-ben), tehát A-t is nullázhatjuk: N = { A, B }.

Eztán S → AB miatt, mert A és B is benne van N-ben, S is nullázható: N = { A, B, S }.

C nem kerül bele, mert aA-ban a, BC-ben pedig C nem nullázható. Tehát az N = { A, B, S } halmaz az összes nullázható változó halmaza.

Következő lépésben ahányféleképp lehet, elhagyunk N-beli elemeket a jobb oldalakról, figyelve arra, hogy ε ne maradjon:

S → AB | A | B lesz az S → AB-ből: elhagyhatjuk A-t is, B-t is, vagy egyiket se; mindkettőt azért nem, mert akkor nem maradna semmi;

S → AAaB-ből lesz S → AAaB | AaB | aB | AAa | Aa | a,

A → BB -ből A → BB | B,

és így tovább, a majdnem végeredmény:

S → AB | A | B | AAaB | AaB | aB | AAa | Aa | a | CBA | CB | CA | C

A → BB | B | aBBa | aBa | aa | a

B → aSB | aS | aB | a

C → aA | a | BC | C

utolsó lépésben ugye C nem nullázható, azért nem hagytuk el egyszer sem.

A végeredmény pedig mivel S is nullázható: ugyanez, plusz
S0 → S | ε

Láncszabálymentesítés.

• Először minden A változóra meghatározzuk azt a CA halmazt, amiben pontosan az összes olyan változó van, amiket A-ból láncszabályokkal el lehet érni. Nulla darab láncszabállyal is, tehát A mindig bekerül CA-ba. Ha ezt is fixpontiterációval csináljuk, akkor CA = { A } -val inicializálunk, aztán ha találunk olyan láncszabályt, aminek bal oldala CA-beli, jobb oldala meg nem, akkor betesszük a jobb oldalt is CA-ba.
• Egyébként ezt gráfosan is meg lehet csinálni: készítünk egy gráfot, csúcsai a változók, A-ból B-be akkor megy él, ha van A → B láncszabály, ekkor CA-ba pont az A-ból elérhető csúcsok kerülnek bele.
• Miután megvan az összes CA halmaz, az A változó új jobboldalai az összes CA-beli változó eredeti jobb oldalai lesznek, kivéve a láncszabályokat.

Folytatva az előző példát, CS = { S } inicializálás, van S → A és S → B szabály, sőt S → C is, ezért A, B és C is bekerülnek CS-be: CS = { S, A, B, C }.

CA = { A }, inicializálás, van A → B láncszabály, bekerül B, de se A-ból, se B-ből nem indul több láncszabály, ezért marad CA = { A, B }.

CB = { B }, nincs B-ből láncszabály, ez így marad.

CC = { C }, van ugyan C → C, de egyrészt minek, másrészt C már benne van CC-ben, így marad.

Akiről elfeledkeztem: CS0 = { S0, S, A, B, C }, először S0 került bele, majd S0 → S miatt S is, majd S → A | B | C miatt a másik három.

Hogy ezek a halmazok megvannak, pl. S új jobboldalai mindenki lesz, aki eredetileg akár S, akár A, B vagy C jobb oldalán szerepelt, kivéve a láncszabályokat, stb. eredmény:

S0 → ε | AB | AAaB | AaB | aB | AAa | Aa | a | CBA | CB | CA | BB | aBBa | aBa | aa | a | aSB | aS | aB | a | aA | a | BC

S → AB | AAaB | AaB | aB | AAa | Aa | a | CBA | CB | CA | BB | aBBa | aBa | aa | a | aSB | aS | aB | a | aA | a | BC

A → BB | aBBa | aBa | aa | a | aSB | aS | aB | a

B → aSB | aS | aB | a

C → aA | a | BC

Aki cizellálni akarja, persze kiszűrheti az ismétlődéseket például, S-nek és S0-nak "a" az legalább háromszor van a jobb oldalán, de kit zavar :D ez a vége a láncszabály-mentesítésnek,

Darabolás.

Itt mindössze annyi a dolgunk, hogy ha túl hosszú (értsd, legalább három hosszú) a jobb oldal, akkor az első betűjét megtartjuk, a maradék rész helyett pedig egy egészen új változót vezetünk be, amiből ezt a részt levezethetjük egy lépésben. Ha túl hosszú így is, akkor ezt tovább folytatjuk. Pl. a fenti S0 → AAaB szabályból lesz S0 → AX, X → AY, Y → aB, ahol X és Y teljesen új változók.

Mondjuk írásban én úgy szoktam ajánlani, hogy pl. egy AaB stringből egy [AaB] nevű változót készítsünk, akkor jobban követhető, hogy mi történik: S0 → A[AaB], [AaB] → A[aB], [aB] → aB szerintem jobban látszik, ha debugolni kell valamiért, hogy mi történt.

Nagybetűsítés.

Ahogy korábban is mondtam, ha mondjuk van egy C → aA szabályunk, ez azért nem Chomsky, mert az a-nak is változónak kéne lennie. Hogy az legyen, minden a betűhöz felveszünk egy egészen új Xa változót, egy Xa → a szabályt és a jobb oldalakban levő a-kat Xa-kra cseréljük. Lesz ebből pl. C → XaA, Xa → a.

Az eredeti nyelvtant tovább ütve az utolsó két lépéssel azt kapjuk, hogy

S0 → ε | AB | A[AaB] | A[aB] | XaB | A[Aa] | AXa | a | C[BA] | CB | CA | BB | Xa[BBa] | a[Ba] | XaXa | Xa[SB] | XaS | XaB | XaA | BC

S → AB | A[AaB] | A[aB] | [aB] | A[Aa] | AXa | a | C[BA] | CB | CA | BB | Xa[BBa] | Xa[Ba] | XaXa | Xa[SB] | XaS | XaB | XaA | BC

A → BB | Xa[BBa] | Xa[Ba] | XaXa | a | Xa[SB] | XaS | XaB

B → Xa[SB] | XaS | XaB | a

C → XaA | a | BC

[AaB] → A[aB]

[aB] → XaB

[Aa] → AXa

[BA] → BA

[BBa] → B[Ba]

[Ba] → BXa

[SB] → SB

Xa → a

meseszép. (nem.) (de legalább Chomsky alakú.)

Elemezve a méretet, amit kapunk, azt látjuk, hogy az ε-mentesítésnél durván elszállhat a dolog, pl. ha a nyelvtan

S → X1X2...Xn

X1 → a1 | ε

X2 → a2 | ε

...

Xn → an | ε

akkor minden Xi és S is nullázható lesz az ε-mentesítéskor, ezért az S új jobboldalán $2^{n-1}$ különböző string születik és ekkora lesz a Chomsky-alak is.

that's plain wrong.

Nyilván az igaz, hogy az ε-mentesítés behozhat láncszabályokat, tehát előbb kell ε-mentesíteni, és csak aztán láncszabályozni. A nagybetűsítést tkp bármikor megcsinálhatjuk, az nem növeli lényegesen a nyelvtan méretét. A láncszabály-mentesítés, mivel csak jobboldalakat másolunk, nem fog behozni se hosszú jobboldalt, se ε-szabályt, ha már eleve nem volt. A darabolás se hoz be se láncszabályt, se ε-szabályt, az is igaz. De ha a költségeket nézzük:

• ε-mentesítés: $k$ hosszú szabályból $O(2^k)$ hosszú szabály születhet;
• láncszabály-mentesítés: négyzetesen lehet nagyobb a nyelvtan mérete tőle;
• darabolás: konstansszor lesz nagyobb a nyelvtan;
• nagybetűsítés: elhanyagolható, kisbetűnként egy új szabály.

Ezek miatt ha a sorrendet arra vesszük, hogy

1. darabolás
2. ε-mentesítés
3. láncszabály-mentesítés
4. nagybetűsítés

akkor az egész trafó max négyzetes méretű nyelvtant ad

mert a darabolás után minden jobb oldal max kettő hosszú, ezt a nullázással már csak háromszor akkorává tudjuk duzzasztani (eddig tehát hatszor akkora a nyelvtanunk, mint volt, tops), erre jön a négyzetes láncszabály-mentesítés, majd a nagybetűsítés, az egész csak négyzetes marad.

Ha ebben a sorrendben megyünk végig az eredeti inputon:

S → AB | AAaB | CBA

A → BB | aBBa | a

B → ε | aSB

C → aA | BC

darabolás:

S → AB | A[AaB] | C[BA]

[AaB] → A[aB]

[aB] → aB

[BA] → BA

A → BB | a[BBa] | a

[BBa] → B[Ba]

[Ba] → Ba

B → ε | a[SB]

[SB] → SB

C → aA | BC

ε-mentesítés: nullázni lehet {B, A, S, [BA], [SB]} változókat, ezeket elhagyogatva:

S0 → S | ε

S → AB | A | B | A[AaB] | [AaB] | C[BA] | C

[AaB] → A[aB] | [aB]

[aB] → aB

[BA] → BA | B | A

A → BB | B | a[BBa] | a

[BBa] → B[Ba] | [Ba]

[Ba] → Ba

B → a[SB]

[SB] → SB | S | B

C → aA | BC | C

láncszabály-mentesítés: S0-ból {S0, S, A, B, C } érhető el láncszabályokkal, S-ből {S, A, B, C}, [AaB]-ből {[AaB], [aB] }, [aB]-ből csak önmaga, [BA]-ből {[BA], B, A}, A-ból {A, B}, [BBa]-ból és [Ba]-ból csak önmaguk, B-ből és C-ből is, [SB]-ből pedig {[SB], S, B, A, C}. Akkor ez rögtön nagybetűsítve is:

S0 → ε | AB | A[AaB] | [AaB] | C[BA] | BB | Xa[BBa] | a | Xa[SB] | XaA | BC

S → AB | A[AaB] | [AaB] | C[BA] | BB | Xa[BBa] | a | Xa[SB] | XaA | BC

[AaB] → A[aB] | XaB

[aB] → XaB

[BA] → BA | BB | Xa[BBa] | a | Xa[SB]

A → BB | Xa[BBa] | a | Xa[SB]

[BBa] → B[Ba]

[Ba] → Ba

B → Xa[SB]

[SB] → SB | AB | A[AaB] | [AaB] | C[BA] | BB | Xa[BBa] | a | Xa[SB] | XaA | BC

C → XaA | BC

Xa → a

négyzetes az egész, frankó.

csakhogy.

Nem tudjuk (és engem érdekel), hogy a láncszabály-mentesítéshez (az a bottleneck, minden más lineáris a történetben) tényleg kell-e az a négyzetes algoritmus, vagy van ennél jobb is. Ami tudomásom szerint ismert, az az, hogy legalábbis $\Omega(n^{3/2})$ költsége biztos van a láncszabály-mentesítésnek, de hogy ez elég lenne, vagy négyzetes kell mindig, nem tudjuk.

Evil regexek

...szóval, mikor is baj az a backtrack.

Az egrep (és talán a tcl) regex motorja rendes, véges automatás elvű, az $O(n\cdot m)$ időigényét nem lehet semmilyen regexszel (eek) és/vagy inputtal legyalázni, kb minden más programozási környezetét (kivéve a hírek szerint a C++11 <regex> könyvtárát, amit még nem volt érkezésem kipróbálni - ha a hírek igazak, az a ma létező legjobb cucc. Részletek később) viszont igen, mert azok backtracket használnak.

A backtracking illesztés nem csak azt mondja meg, hogy az input regexre illeszkedik-e a text, de azt is, hogy hol van az illeszkedés. Dióhéjban:

1. A specifikáció szerint a legelső illeszthető pozíción kell kezdődjön a visszaadott illeszkedés. Ezért a regex motorok lényegében egy forciklussal végigpróbálgatják szépen először az első, majd a második, stb. karakternél kezdve illeszteni az egész regexet.
2. Alternatívákat balról jobbra próbál végig. Így például az $(a|aa|b)$ regexnél előbb az $a$, majd az $aa$, ha az $a$-val nem sikerült, végül ha azzal sem, a $b$ alternatívát próbálja.
3. Az $*$ iteráció és a $?$ opcionális operátorok mohók. Ha tehát aktuálisan a jelenlegi pozíciótól egy $R?$ subregexet akarunk illeszteni, akkor oda először is megpróbálja illeszteni az $R$ regexet (azt is olyan hosszan, ahogy csak lehet), ha sikerül, akkor megy tovább az engine. Ha ezek után az egész regex maradék része nem illeszkedik a maradék textre, akkor az $R$ regexet rövidebb substringre akarja illeszteni, ha úgy sem, még rövidebbre, végül ha sehogy nem áll össze, akkor az $R?$-nek az opcionális, kihagyó ágára fut rá, és úgy próbálja befejezni az illesztést. Ha így se sikerül, akkor ebből az állapotból is visszalépés a keresésben.

Ezt a hármas pontot egy-két példával szemléltetném inkább: van mondjuk az $ab?b$ regexet, és illesszük az $aab$ textre.

• Először az $ab?b$-t az első $a$-ra próbálja illeszteni. Az $a$ stimmel. Most $b?b$-t illeszti a fennmaradó $ab$-re. A $b?$ részt ilesztve az $ab$-re először $b$-t illeszt $ab$-re, nem illeszkedik, mert $a$-val kezd. Akkor a $b?$ subregexet üres stringgel oldja meg (tehát kihagyja), és már csak a regex végén lévő $b$-t illeszti az $ab$-re. Nem sikerül. Visszalépés.
• Most az $ab?b$-t a második $a$-nál kezdve próbálja illeszteni. Az $a$ oké, $b?b$-t akar illeszteni a fenmaradó $b$-re, akkor először kipróbálja, hogy ha a $b?$-beli $b$-t illeszti, mi történik. Sikerül, a regex maradék $b$-jét kell a.. elfogyott a text. Akkor ez így nem jó, visszalép. Most a $b?$-et skippeléssel illeszti, és a regex maradék $b$-jét a text maradékára, $b$-re próbálja illeszteni, sikerül, mindenki boldog, illeszkedik a regex: a második pozíción kezdve, mégpedig úgy, hogy a $b?$ skippeli az opcionálist.

Mindenki boldog, kivéve, hogy mikor a Jeffrey Friedl könyvében ezt olvastam, az arcomon egy apró ideg elkezdett rángatózni... aztán kisétáltam az udvarra, felástam egy részét, és nem volt ezzel gondom.

Ahogy mondtam, a csillag is mohó operátor, annyiszor próbál illeszteni, ahányszor csak tud, azon belül pedig minden egyes iterációban amilyen hosszút csak tud. Ha rájön, hogy túl hosszan illesztett, akkor az utolsó iterációt rövidíti, majd elengedi, stb.

Ez még nem hangzik olyan veszélyesnek, igaz?

plain wrong

dehogynem.

Illesszük mondjuk az.. $(a^*)^*b$ regexet az $a^n$ textre, valamilyen $n$-re! Érzi remélem mindenki, hogy nem kéne illeszkedjen? Pastebin itt. Ideone.com output:

On a, .find run in 2451933 nanoseconds.
On aa, .find run in 69710 nanoseconds.
On aaa, .find run in 75366 nanoseconds.
On aaaa, .find run in 121180 nanoseconds.
On aaaaa, .find run in 419257 nanoseconds.
On aaaaaa, .find run in 421194 nanoseconds.
On aaaaaaa, .find run in 1158488 nanoseconds.
On aaaaaaaa, .find run in 2692903 nanoseconds.
On aaaaaaaaa, .find run in 1265485 nanoseconds.
On aaaaaaaaaa, .find run in 377794 nanoseconds.
On aaaaaaaaaaa, .find run in 672745 nanoseconds.
On aaaaaaaaaaaa, .find run in 1399777 nanoseconds.
On aaaaaaaaaaaaa, .find run in 2746695 nanoseconds.
On aaaaaaaaaaaaaa, .find run in 5498918 nanoseconds.
On aaaaaaaaaaaaaaa, .find run in 10948008 nanoseconds.
On aaaaaaaaaaaaaaaa, .find run in 21770596 nanoseconds.
On aaaaaaaaaaaaaaaaa, .find run in 43556607 nanoseconds.
On aaaaaaaaaaaaaaaaaa, .find run in 86682752 nanoseconds.
On aaaaaaaaaaaaaaaaaaa, .find run in 172915112 nanoseconds.
On aaaaaaaaaaaaaaaaaaaa, .find run in 345402683 nanoseconds.
On aaaaaaaaaaaaaaaaaaaaa, .find run in 653601295 nanoseconds.
On aaaaaaaaaaaaaaaaaaaaaa, .find run in 1266362512 nanoseconds.

és a szokásos timeout. Megint $a^{10}$ környékére ficcent be a hotspot, utána szépen duplázódott az időigény, $a^{22}$-re még sikerült illessze, aztán elszállt.

Miért is?

Az első menetben $a^{20}$-ra (mondjuk nézzük ezt) illeszti $(a^*)^*b$-t. Ehhez először $(a^*)^*$-ot illeszt a legelső karaktertől. Ahhoz $a^*$-ot illeszt a legelső karaktertől. Itt iterációban szépen megpróbál annyi $a$-t benyelni, amennyit csak lehet: az $a^*$ rész megeszi az egész inputot. Elfogyott az input, most ide próbálná illeszteni a $b$-t, nem sikerül, visszalép.

Most az az eset jön, mikor a belső $a^*$ már szerényebben csak $a^{19}$-et nyel le. Ezután az $(a^*)^*$-on futó motor azt mondja, hogy oké, akkor egy iterációban a belső rész lenyelt $19$ darab $a$-t, próbáljunk meg még egy iterációt! Illeszti az $a^*$-ra a maradék $a$-t, betalál, elfogyott az input, jé, megint nincs a végén $b$. Akkor ezt a második iterációt elfelejtjük, és a text utolsó $a$-jára illesztjük a regexet záró $b$-t. Hm, nem sikerült. Akkor az első iterációs $a^*$ még szerényebb, már csak $18$ karaktert nyel le, marad $aa$ a textből, amin a motor továbbra is az $(a^*)^*b$-t próbálja illeszteni. Először a belső $a^*$-gal lenyeleti az egész textet, elfogy, nem passzol a $b$, oké, akkor a belső $a^*$-gal csak az első $a$-t nyeleti be, és a maradék $a$-ra illeszti tovább az $(a^*)^*b$-t, a belső $a^*$-gal először lenyeleti az egész $a$-t, elfogy, nem passzol a $b$, akkor skippeli az $a^*$-ot, rájön, hogy a $b$ nem illeszkedik az $a$-ra, visszalép, akkor az $aa$-ra illeszti $(a^*)^*b$-t úgy, hogy az egész csillag üres stringre illjen, jé, a $b$ nem illeszkedik az $aa$-ra se, visszalépek, az első iterációs $a^*$ már csak $17$ karaktert szeretne, akkor $(a^*)^*b$-t illesztjük $aaa$-ra úgy, hogy először $3$, majd $2+1$, majd $2$, majd $1+2$, majd $1+1+1$, majd $1+1$, majd $1$, végül $0$ darab $a$-t akarunk lenyeletni, de persze az a $b$ egyszer se lesz ott...

...ha kiszámoljuk, ez azt jelenti, hogy a regex illesztő backtracking motor $(a^*)^*b$-t $a^n$-re illesztéskor $\Theta(2^n)$ idő alatt jön rá, hogy ez bizony nem illeszkedik. (És ahogy a fenti ideone logot láthatjuk, ez Javában is így megy...)

Mikor ezt olvastam a Jeffrey Friedl könyvében, becsuktam a könyvet, kimentem a fejszémért, kivágtam egy (kiszáradt) fát, ittam egy sört, visszamentem olvasni és megállapítottam, hogy valaki elég kókány munkát végzett valamikor.

A fenti "catastrophic backtracking" (mikor sikerül kicsalni egy exponenciális futásidőt egy alkalmasan megválasztott texten való futtatással) viselkedést mutatni képes regexeket (mint amilyen az $(a^*)^*b$ is) Evil (vagy malicious) Regexnek hívják :) ha ne adj'Isten egy webszerveren a user inputot egy evil regexre illesztik, az egy remek kiindulópontja a ReDoS (regular expression denial of service) támadásnak (ld még itt): a usernek más dolga nincs is, csak egy megfelelően craftolt stringet beírni a form megfelelő input fieldjébe, amit ha a szerver elkezd illeszteni, azzal garantáltan elfoglalkozik egy darabig :D

Az előző post $(a?)^na^n$ regexe az nem ilyen volt, mert az exponenciális viselkedéshez a regexet is egyre hosszabbra kellett venni. Ha szervert támadsz, akkor az azon levő adott regexhez kell megfelelő textet gyártani. De ha a regexedben van olyan $R^*$ vagy $R^+$ alakú rész, hogy az $R$ illeszkedik valami $u$ (nemüres) szóra és annak egy hatványára is (pl. $a$-ra is és $aa$-ra is, vagy $aba$-ra és $abaabaaba$-ra is stb), akkor ezt a regexet egy olyan text, amiben sok áll egymás után ebből az $u$-ból ezen a helyen (és melyre a regex nem illeszkedik, hogy végig kelljen tekernie a backtracket), catastrophic backtrackingbe fogja küldeni. They are all evil, period.

Egyszerű példák evil regexekre:

• $(a^*)^*$ - ez egy iteráció, aminek a belseje illeszkedik $a$-ra is és $aa$-ra is, és ahogy láttuk, $a^{30}$ már elszállítja ideone.on
• $(a|aa)^*$ - ugyanez
• $([a-zA-Z]^+)^*$ - "karaktersorozatok egymás után", szeparátor nélkül? nem jó, szintén $a$ és $aa$ is illeszkedik belül
• $(.^*,?)^+$ - vesszőkkel elválasztott szavak, gondolom ilyesmi akart volna lenni, utolsó vessző elhagyható, ezért opcionális. Ez több sebből is vérzik, de eleve a $.^*$ regexet jó ötlet kerülni, amennyire csak lehet. Belül így illeszkedik pl. $a$-ra és $aa$-ra is, de ha a vessző nem is lenne opcionális, még akkor is a $,$ és $,,$ szavakra is illeszkedik... A $.^*$ regex pedig a korábbiak szerint ha idefut a backtrack, először is szépen benyeli az input teljes maradék részét, utána egyet, még egyet, ... visszaad a regex további részének. Ez elég időigényes tud lenni (bár "csak" egy $N$-es szorzó, a text hosszával szorzódik, de az se kevés)
• $(a|a?)^+$ - ez evil, de nem a fenti ökölszabály miatt. A backtracking motor először az $a$-t próbálja illeszteni, ha az nem sikerül, akkor az $a?$-et, melyet is először úgy, hogy $a$-t, majd úgy, hogy üres stringet illeszt. Ezt a három lehetőséget aztán végigpörgeti az összes további $a$-ra is...
• Guglizva emailcím regexre meg lehet kapni akár ezt. Ennek a közepén van egy ilyen: $(([-.]|[\_])^?[a-zA-Z0-9]^+)^*$, azaz mínusz, pont vagy underscore ESETLEG ($?$), utána alfanumerikus nemüres string, ezt ismételjük. Itt ugye a gond a $?$, amiatt az első csoport akár üresre is illeszthető és az iterált rész matchel bármilyen alfanumerikussal. Pl $a$, $aa$... ne írjunk soha ilyesmit: $(R_1?R_2^*R_3?)^*$, mert ebbe belefér az $(R_2^*)^*$ is akár, amiről tudjuk, hogy rossz ötlet
• Itt van ez, hogy mi egy Java osztály neve: $([a-z]^+.)^+[A-Z][a-z]^+$, azaz (kisbetűk, akármi)párszor, nagybetű, megint kisbetűből néhány.  A "kisbetűk, akármi" részre illeszkedik $aa$ is és $aaaa$ is...

Szerencsére általában ezeket a regexeket (már ha észrevesszük, hogy a regexünk nem éppen hatékony ;) ) át lehet transzformálni olyan alakúra, amin a backtracking motor nem tölt el annyira sok időt, mint ezeken az evil formokon tölthet.

Ahogy az idő telt, egyre több és több szintaktikus elem került be a legtöbb regex motorba, amivel a backtracket irányíthatjuk (ha már automatánk nincs ugye..), legközelebb ezekről beszélek majd.

És arról is, hogy mi lehet az oka annak, hogy én magam se automatával, hanem backtrackkel próbálnék mai regexet illeszteni.

folytköv

mekkora cliffhanger

remélem, erre senki nem számított

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)

Bonyelm gyakjegyzet 2014, 2. gyak

A félév túlnyomó részében egymáshoz fogunk problémákat viszonyítani, és szeretnénk olyat mondani, hogy pl az $A$ probléma "könnyebb", mint a $B$ probléma (vagy legalábbis, "legfeljebb olyan nehéz" - ez megint a $<$ vs. $\leq$ különbségre emlékeztet. Maradunk a "legfeljebb olyan nehéz"-nél, mert sokszor a problémák "egyforma" nehezek lesznek majd.).

Adja magát, hogy pl. akkor mondanánk az $A$-t könnyebbnek, mint a $B$-t, ha az optimális algoritmus $A$-ra gyorsabb, mint $B$-re. Ezzel csak egy a baj: néhány triviális esettől eltekintve nem szoktuk azt tudni, hogy ami algoritmusunk nekünk van, az tényleg az optimális-e vagy sem. Emiatt ez nem egy járható út.

Ami a másik szóbajövő lehetőség: ha $B$-t meg tudnánk oldani, akkor az őt megoldó algoritmus segítségével az $A$-t is. Ezt a megközelítést használja a visszavezethetőség fogalma: azt mondjuk, hogy az $A$ probléma visszavezethető $B$-re, ha van olyan $f$ inputkonverzió (ez lesz maga a visszavezetés), mely

• $A$ inputjaiból $B$ inputjait készíti;
• tartja a választ, azaz $A(x)=B(f(x))$ tetszőleges $x$ inputjára $A$-nak (azaz $A$ "igen" példányaiból $B$ "igen" példányait készíti, "nem" példányokból pedig "nem" példányokat);
• és hatékony, azaz polinomidőben kiszámítható.

A definíció oké abból a szempontból, hogy ha $f$ egy visszavezetés $A$-ból $B$-re és $B$-re van megoldó algoritmusunk, akkor onnan kezdve $A$-ra is van: az input $x$-et át kell konvertálni $f$-fel $B$ egy $f(x)$ inputjára, erre meghívni a $B$-t megoldó algoritmust és a választ visszaadni, az megválaszolja, hogy az $x$ input az $A$ problémának "igen" példánya-e vagy sem.

Például, a SAT probléma a következő: input egy CNF (konjunktív normálforma), output, hogy kielégíthető-e. A FORMSAT pedig ugyanez, csak inputja tetszőleges Boole-formula lehet, nem feltétlen CNF-ben.

Az világos, hogy a SAT legfeljebb olyan nehéz, mint a FORMSAT: ehhez egy visszavezetést kell találjunk SAT-ról FORMSAT-ra. Azaz egy olyan $f$ konverziót, ami

• SAT inputjából (azaz egy CNF-ből) készíti
• FORMSAT egy inputját (azaz egy akármilyen Boole-formulát) úgy, hogy
• ha az input $F$ kielégíthető, akkor a generált $f(F)$ is kielégíthető lesz és csak akkor, továbbá
• $f$ polinomidőben (azaz gyorsan) kiszámítható legyen.

Ebbe az irányba az $f$ lehet az identikus függvény is, azaz nem bántjuk az inputot, csak visszaadjuk, hogy tess, ez a konvertálás eredménye. Jó lesz: egy CNF formula is egyben, a kielégíthetősége nem változik (nyilván), kész. (Ez a módszer mindig alkalmazható, ha az $A$ probléma inputja speciális esete a $B$ problémáénak és a kérdés ugyanaz.)

Visszafelé is igaz, hogy a FORMSAT legfeljebb olyan nehéz, mint a SAT, azaz FORMSAT $\leq$ SAT. Itt vigyázunk kell egy kicsit, it's a trap! Kell adni egy olyan $f$ konverziót, ami

• input tetszőleges formulából készít
• CNF-et úgy, hogy
• ha az input $F$ formula kielégíthető, akkor a generált $f(F)$ CNF is az lesz, és csak akkor, továbbá
• $f$ polinomidőben kiszámítható.

Az első ép ötlet, ami az ember eszébe jut, hogy hát hozzuk CNF-re az input formulát és kész is vagyunk! A szokásos módszer ugye a $\to,\leftrightarrow$ nyilak eliminálása, majd a deMorgan-azonosságok alkalmazása, aztán a disztributivitással megjavítani az $\vee,\wedge$ sorrendjét. Ez persze egy ekvivalens formulát készít, tehát a kielégíthetőséget nem bántja, az output CNF, szóval...

mégis rossz az egész

meeert ez a CNF-re hozó algoritmus bizony nem polinomidejű, sőt.

Több sebből vérzik a dolog, például ha az input formula

$(x_1\wedge y_1)\vee(x_2\wedge y_2)\vee\ldots\vee(x_n\wedge y_n)$

(igen, ez egy DNF), akkor az ezzel ekvivalens CNF, amit disztributivitással kapunk, kb ilyen:

$(x_1\vee x_2\vee\ldots\vee x_n)\wedge(x_1\vee\ldots\vee x_{n-1}\vee y_n)\wedge\ldots\wedge(x_1\vee y_2\vee x_3\vee y_4\vee\ldots\vee x_n)\wedge\ldots\wedge(y_1\vee y_2\vee\ldots y_n)$.

Olyan hosszú, hogy nem fér ki. Ez minimum gyanús. Tehát egy klózban $x_i$-k vannak és $y_i$-k, minden $i$-re pontosan az egyik a kettő közül; ilyen klóz $2^n$-féle van, mindegyik $n$ hosszú, emiatt a teljes generált CNF $n\cdot 2^n$ hosszú lesz. Exponenciális hosszú outputot pedig nem lehet polinomidőben generálni, emiatt

a standard CNF-re hozó algoritmus nem polinomidejű.

sőt.

nincs is polinomidejű CNF-re hozó algoritmus.

Ettől persze még vissza akarjuk vezetni a FORMSAT-ot a SAT-ra, egy afféle apróság, hogy nem lehet tetszőleges formulából ekvivalens CNF-et készíteni polinomidőben, nem szabad, hogy kedvünket szegje. Megnézve a specifikációt, arról egy szó nincs, hogy ekvivalens is legyen a két formula, csak annyi a kérés, hogy kielégíthetőből kielégíthetőt, kielégíthetetlenből pedig kielégíthetetlent készítsünk (ezt hívtuk logikából $s$-ekvivalens formuláknak, $s$ mint satisfiability).

A módszer pedig az lesz, hogy minden egyes $F$ részformulához társítunk egy új $x_F$ változót és annak az értékét egy-egy $\leftrightarrow$ ekvivalenciával kényszerítjük, hogy vegye fel azt az értéket, mint amit az $F$ venne, az eredeti változók tetszőleges kiértékelése mellett. Azaz, a következő rekurzív átírást csináljuk:

$x \mapsto x$, $(F\vee G) \mapsto x_{(F\vee G)}\leftrightarrow(x_F\vee x_G)$, $(F\wedge G)\mapsto x_{(F\wedge G)}\leftrightarrow (x_F\wedge x_G)$, stb. Egy példán keresztül, ha az input formula $y\wedge\neg (z\vee \neg w)$, akkor a $\neg w$ részformula helyett bevezetünk egy $x_{\neg w}$ fedőnevű változót, és azt mondjuk, hogy $x_{\neg w}\leftrightarrow \neg w$, a $(z\vee \neg w)$ részformula helyett bevezetünk egy $x_{z\vee\neg w}$ nevű változót, és azt mondjuk, hogy $x_{z\vee\neg w}\leftrightarrow(z\vee x_{\neg w})$, aztán a $\neg (z\vee\neg w)$ részformula helyett bejön egy $x_{\neg(z\vee\neg w)}$ változó, amiről azt mondjuk, hogy $x_{\neg(z\vee\neg w)}\leftrightarrow(\neg x_{z\vee\neg w})$, és az egész formula helyett bevezetünk egy $x_{y\wedge\neg(z\vee\neg w)}$ (eek) nevű változót, amiről pedig azt mondjuk, hogy $x_{y\wedge\neg(z\vee\neg w)}\leftrightarrow(y\wedge x_{\neg(z\vee\neg w)})$. Ezzel megoldottuk, hogy minden részformulának az értékét "letároljuk" egy változóban, már csak azt kell mondjuk, hogy a formula még ráadásul igaz is, ezt pedig úgy tesszük, hogy hozzáéseljük az $x_{y\wedge\neg(z\vee\neg w)}$ változót is a fenti összes "értékadás" éseléséhez.

Az eredményként kapott formulánk ez lenne:

$(x_{\neg w}\leftrightarrow \neg w)\wedge$

$(x_{z\vee\neg w}\leftrightarrow(z\vee x_{\neg w}))\wedge$

$(x_{\neg(z\vee\neg w)}\leftrightarrow(\neg x_{z\vee\neg w}))\wedge$

$(x_{y\wedge\neg(z\vee\neg w)}\leftrightarrow(y\wedge x_{\neg(z\vee\neg w)}))\wedge$

$x_{y\wedge\neg(z\vee\neg w)}$.

Hiába látszik hosszúnak ez a formula, ez csak azért van, mert a változók neve hosszú, bevezethettem volna $x_0$, $x_1$, stb változókat is $x_{z\vee\neg w}$ stb. nevek helyett.

Egy jogos észrevétel, hogy ez még nem is CNF, de könnyen azzá tehető, ekvivalenciánként, a végeredmény pedig:

$(\neg x_{\neg w}\vee\neg w)\wedge(x_{\neg w}\vee w)\wedge$

$(\neg x_{z\vee\neg w}\vee z\vee x_{\neg w})\wedge(x_{z\vee\neg w}\vee\neg z)\wedge(x_{z\vee\neg w}\vee\neg x_{\neg w})\wedge$

$(\neg x_{\neg(z\vee\neg w)}\vee\neg x_{z\vee\neg w})\wedge(x_{\neg(z\vee\neg w)}\vee x_{z\vee\neg w})\wedge$

$(\neg x_{y\wedge\neg(z\vee\neg w)}\vee y)\wedge (\neg x_{y\wedge\neg(z\vee\neg w)}\vee x_{\neg(z\vee\neg w)})\wedge(x_{y\wedge\neg(z\vee\neg w)}\vee\neg y\vee\neg x_{\neg(z\vee\neg w)})\wedge$

$x_{y\wedge\neg(z\vee\neg w)}$.

Így általánosan formulából tudunk készíteni lineáris időben (egyszer kell csak bepreorderjárni a formulát mint fát) egy max kb. nyolcszor olyan hosszú CNF-et, ami ha nem is ekvivalens, de $s$-ekvivalens az eredetivel.

Amúgy ha pl. ennél a példánál a formulát kielégíti az $y=1, z=0, w=1$ kiértékelés, akkor a plusz változókat a "megfelelő" értékre, tehát $x_{\neg w}=0$, $x_{z\vee\neg w}=0$, $x_{\neg(z\vee\neg w)=1}$ és $x_{y\wedge\neg(z\vee\neg w)}=1$, a fenti CNF is igaz lesz, tessék ellenőrizni.

A tanulság egyelőre annyi, hogy a polinomidő az néha komolyabb kritérium a konvertálás felé, mint első blikkre látszik.

Egy másik példát is néztünk: legyen $ILP$, az Integer Linear Programming a következő probléma: input egy $A\boldsymbol{x}\geq \boldsymbol{b}$ alakú egyenlőtlenség-rendszer, ahol $A$ és $\boldsymbol{b}$ egész számokból álló együtthatómátrix ill. vektor; output: lehet-e úgy egész értékeket rendelni az $\boldsymbol{x}$ változókhoz, hogy teljesüljenek az egyenlőtlenségek? (Van-e egészértékű megoldás?) Mármost ez opkutból ismerős történet, "tudjuk", hogy ha az egészértékű kikötés nem lenne az $\boldsymbol{x}$-re, akkor mondjuk a szimplex módszerrel hipp és hopp ezt megtudnánk (standardizálás, LKAF stb.) Oké, a szimplex módszer nem polinomidejű, de belsőpontossal vagy ellipszoiddal is meg lehet oldani, ami viszont polinomidejű is.

Hanem (ahogy opkutkettőből tudjuk) ebből kerekítéssel nem jön feltétlen össze egészértékű megoldás.. mindenesetre, azt azért megcsináltuk, hogy

$SAT\ \leq\ ILP$,

ez mit jelent? Egy olyan $f$ konverziót kell adnunk, ami

• CNF-ből készít
• egyenlőtlenség-rendszert úgy, hogy
• ha a CNF kielégíthető, akkor az egyenlőtlenség-rendszernek van megoldása, és csak akkor,
• mindezt polinomidőben.

Ilyenkor ki kell találni, hogy az input melyik részeiből az output melyik részei lesznek. Ha például úgy döntünk, hogy

• az input változóiból az outputnak szintén változói lesznek, azaz egy $x$ logikai változóból a SAT-ban készítünk egy $x$ egészértékű változót az ILP-be,
• azt szeretnénk jó informatikushoz méltóan, hogy az ILP-ben úgy jelenjen meg az $x$ értéke, hogy $0$ a hamis, $1$ az igaz,
• akkor fel kell vennünk minden $x$-hez egy $0\leq x\leq 1$ feltételt (hogy megfeleljen a fenti formának, ez két egyenlőtlenség: $x\geq 0$ és $-x\geq -1$), ezzel már el is értük, hogy a változók az ILP-ben binárisak lesznek;
• akkor egy pozitív $x$ literálból simán $x$-et csináljuk, a negatív $\neg x$ literál meg így elsőre úgy fog oldalhelyesen $0$-t vagy $1$-et felvenni, ha belőle $(1-x)$-et készítünk;
• végül, egy klózból egy egyenlőtlenség lesz. A klóz akkor igaz, ha van benne igaz literál (aminek az ILP alakban $1$ az értéke), és akkor hamis, ha minden literál hamis benne (azaz $0$). Tehát ha a klózban a literálok(nak megfeleltetett $x$-ek és $(1-x)$-ek) összege $0$, akkor hamis, amúgy pedig igaz lesz. Tehát az $\ell_1\vee\ldots\vee\ell_k$ klózból egy $\sum_{i=1}^{k}\ell_i\geq 1$ egyenlőtlenség pont megfelelő lesz, és ez minden, amit a visszavezetésnek tennie kell.

Egy példán keresztül: ha az input CNF az $(x_1\vee\neg x_2\vee x_3)\wedge(x_2\vee\neg x_3)$, abból a következő egyenlőtlenség-rendszer lesz:

$0\leq x_1,x_2,x_3\leq 1$,

$x_1+(1-x_2)+x_3\geq 1$,

$x_2+(1-x_3)\geq 1$.

Ha valakit zavar, hogy ez nem pont a mátrix alakban van, akkor némi (polinomidejű :D ) átrendezés után:

$x_1\geq 0$, $x_2\geq 0$, $x_3\geq 0$, $-x_1\geq -1$, $-x_2\geq -1$, $-x_3\geq -1$,

$x_1 - x_2 + x_3 \geq 0$,

$x_2-x_3\geq 0$

a generált egyenlőtlenség-rendszerünk. Ennek pont akkor van megoldása, ha az input SAT kielégíthető volt. (Például $x_1=1,x_2=1,x_3=0$ kielégíti az input formulát is és az egyenlőtlenség-rendszerünket is.)

A bonyelm kurzuson a visszavezetésekből olyan tanulságokat fogunk levonni, hogy egy probléma nehéz. Konkrétan, ha $A\leq B$ és $A$-ról már tudjuk, hogy nehéz, akkor $B$ is nehéz kell legyen. Így van ez a fenti példában is: nemsokára látjuk előadáson, hogy a SAT egy "nehéz" probléma (hogy ez mit jelent, egyelőre szakmai titok), és emiatt az ILP is nehéz kell legyen, mert a SAT visszavezethető rá. Erről még később.

folytköv nextweek

Bonyelm gyakjegyzet 2014, 1. gyak

re,

kicsit off voltam nyáron. Nemsokára folytatom a regexes threadet is (remélem), addig is elkezdek itt egy bonyelm gyakjegyzetet loggolni :-)

Első jóhír, hogy jótanácsot követve belőttem a MathJaxet, úgyhogy most már talán ki fognak nézni valahogy a matekos jelek is.

Első gyakorlaton (követelményismertetés után ofc) felidéztük, hogy futásidőket és tárigényeket akarunk majd összehasonlítani és számolgatni, ezeket pedig elég lesz csak nagyságrendben ismernünk, nem a pontos függvényeket. Ha $f$, $g$ függvények (mondjuk természetes számokat valós számokra képezőek, de lehet az értelmezési tartomány is a pozitív valós, vagy az értékkészlet a természetes, mindegy), akkor azt mondjuk, hogy $f=O(g)$ (ami kb. a "$g$ legalább olyan gyorsan nő, mint $f$"-nek felel meg), ha van olyan $c>0$ konstans, amire $f\leq c\cdot g(n)$ majdnem minden $n$-re (ami matekul ugyanaz, mint hogy "van olyan $N$ küszöbszám, hogy ha $n>N$, akkor már igaz).

• Például, $3n=O(\frac{n^2}{100})$, mert ha $c=100$ és $N=3$, akkor tényleg fennáll, hogy ha $n>3$, akkor $3n \leq 100\cdot\frac{n^2}{100}=n^2$ (egyszerűsítünk $n$-nel, kész).

Az $O$ (e. ordó) kapcsolatnál szigorúbb az $o$ (kisordó) kapcsolat: $f=o(g)$, ha tetszőleges $c>0$-ra $f(n)\leq c\cdot g(n)$ majdnem minden $n$-re. (Ez kb. a "$g$ gyorsabban nő, mint $f$"-nek felel meg.) Ilyenkor már nem mondani kell egy $c$-t és egy $N$-t, hanem tetszőleges $c>0$-ra mondani kell egy $N$-t, amitől kezdve igaz az összefüggés.

• Például, $3n=o(\frac{n^2}{100})$ is igaz, hiszen ha $c>0$, akkor átrendezve kapjuk, hogy ha $\frac{300}{c}\leq n$, akkor $3n\leq c\cdot\frac{n^2}{100}$.

Ezután megláttuk a $\log^2 n=o(n)$ feladatot.. hát erre input $c>0$ küszöbszámra mondani megfelelő $N$-t már nem nekünk való feladvány (megjegyzés: a $\log$ mindig kettes alapú logaritmust jelent, mi mást, a $\log^2 n$ pedig a $(\log n)^2$-nek egy átláthatóbb formája. Nem pedig pl. a $\log\log n$-nek). Szerencsére "tudjuk", hogy ha $\lim_{n\to\infty}\frac{f(n)}{g(n)}=0$, akkor $f=o(g)$. Ha pedig a limesz legalábbis kisebb, mint végtelen (tehát például 7, 0 vagy $\pi$), akkor $f=O(g)$ lesz.

Ezután már könnyű volt, mert $\lim_{n\to\infty}\frac{\log^2 n}{n}$ a L'Hopital-szabály szerint ugyanannyi, mint $\lim_{n\to\infty}\frac{2\cdot\ln 2\cdot\log n}{n}$, ami megint ugyanemiatt a szabály miatt $\lim_{n\to\infty}\frac{2\cdot\ln 2\cdot\ln 2}{n}$, ami tényleg $0$, tehát $\log^2 n=o(n)$. Persze akármilyen $k>0$ konstanst is mondunk, ezek szerint $\log^k(n)=o(n)$ is igaz lesz - ez nálunk annyit tesz, hogy akár futásidőről, akár tárigényről lesz szó, a $\log^k(n)$ alakú erőforrás-igényt jobbnak fogjuk tartani, mint a lineárist. (A $\log^k(n)$ alakú függvényeket egyébként polilogaritmikus függvénynek hívjuk.) Persze ha szekvenciális algoritmusról beszélünk, annak nem lehet $o(n)$ (amit szublineárisnak is mondunk) az időigénye, hiszen ennyi lépésben nem tudja végigolvasni se az inputot. Amikor elő fognak jönni szublineáris függvények:

• tárigénynél;
• párhuzamos számítás időigényénél.

Példaképp felhoztam, hogy az ${Elérhetőség}$ probléma (input: irányított gráf, csúcsai $1$-től $n$-ig a számok, output: van-e út $1$-ből $n$-be?) az egy könnyű probléma, lineáris időigényű algoritmus van rá, pl. a mélységi keresés. Vagy a szélességi. Viszont ezek az algoritmusok mind $n$ tárat használnak (mert jelölgetik a csúcsokat). Házi jellegű feladatra kértem, hogy próbáljunk készíteni szublineáris tárigényű algoritmust, ami szintén eldönti az ${Elérhetőség}$ problémát.

Megnéztük még azt is, hogy $n^2=o(2^n)$, hiszen két L'Hopital szabály után kapjuk, hogy $\lim\frac{n^2}{2^n}=\lim\frac{2n}{\ln 2\cdot 2^n}=\lim\frac{2}{\ln 2\ln 2\cdot 2^n}=0$. Általában is igaz, hogy ha $p$ polinom, $e$ pedig exponenciális függvény, akkor $p=o(e)$, legyen akármekkora a polinom fokszáma és akármilyen pici is az $e$ alapja. Általában futásidőről ha szó lesz, akkor a polinomnak fogunk örülni, azt tekintjük hatékony algoritmusnak, ami polinom időigényű (legrosszabb esetben is), és egy problémát hatékonyan megoldhatónak akkor hívjuk, ha van rá polinom időigényű algoritmus. (Ez a Cobham-Edmonds tézis.)

Házi jelleggel megnézhetjük, hogy az exponenciális lassabban nő, mint $n!$, ami pedig lassabb, mint a $2^{n^2}$.

Voltam konferencián

...augusztusban, kétszer is. Előbb a DCFS 2014 volt Turkuban (ahol beszéltem is eredményekről), majd az MFCS 2014 Pesten (pontosabban Budán). Aki szakmai "élménybeszámolóra" kíváncsi, elérheti itt az előbbiét, itt az utóbbiét.

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