3. gyakorlat

A gyakorlat anyaga

A Java és C++ built-in regex libek. Lookahead.

A C++ <regex> header

Az itteni regex motor is támogatja többek közt ezeket a műveleteket:

  • illeszkedik-e egy teljes input szöveg egy regexre (match bool)
  • illeszkedés esetén capturing groupok tartalmának kigyűjtésére (match groups)
  • input szövegben az input regexre első illeszkedő substring megkereresése (search)
  • input szövegben az input regexre illeszkedő substringek, vagy közülük csak az első cseréje valamire (replaceAll, replace)

A lenti példák egyben itt vannak.

match

Lássunk egy egyszerű "illik-e vagy sem" kódot: megkeressük (ggmarkk után szabadon), hogy az input stringünkben vajon szerepel-e (külön szóként) a "telefon" szó.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
#include <regex>               //std::regex osztály, std::regex_match függvény, C++11 óta része
#include <string>              //std::string
#include <iostream>            //std::cout, std::endl
//using namespace std;         //ízlés dolga, hogy ki szereti behúzni az egész névteret
//using std::string;           //vagy csak egy-egy osztályt belőle
                               //vagy kiírja mindig, hogy std::string, string helyett
...

std::regex  theRegex(".*\\btelefon\\b.*");         // arra a stringekre illik, melyek tartalmazzák a "telefon" szót
std::string theText = "alma körte telefon barack"; // c++ alapból használjunk std::stringet, ha lehet   
if( std::regex_match(                              // regex_match: bool, illik-e
      theText,                                     // erre a std::string vagy char* szövegre 
      theRegex ) )                                 // ez a std::regex
{
  std::cout << "a regex illik a szövegre" << std::endl;
}else{
  std::cout << "a regex NEM illik a szövegre" << std::endl;
}

groups

Ha az illesztést úgy szeretnénk elvégezni, hogy utána a capturing groupokkal is szeretnénk kezdeni valamit, adnunk kell egy std::regex_match referenciát a regex_matchnek, második argumentumként. Ez egy template osztály, ugyanazzal a karaktertípussal kell példányosítsuk, mint ami az input text stringnek a karaktertípusa -- de két példányosztály aliasolva van nekünk előre: ha char * a textünk, akkor az std::cmatch osztályt, ha pedig string, akkor az std::smatch osztályt használhatjuk.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
regex  theRegex("\\s*((?:\\S+(?:\\s+\\S+)*)?)\\s*");
string theText = "   a whitespace duplaplusz nemjó   ";
std::smatch results;                                                    //ebbe fognak kerülni a csoportok
if( regex_match(theText, results, theRegex )) {                         //text, match, regex a sorrend, ha illik, akkor feltölti a match-be a csoportokat
  cout << "we have a match! Groups count: " << results.size() << endl;  //kb. mint egy vector: van neki mérete
  for( int i = 0; i < results.size(); i++ ) {
    cout << "Group " << i << " is *" << results[i] << "*" << endl;      //és tömbelem-kiválasztás operátora is
  }
}else{
  cerr << "Sumthin is wrong"; //should never happen, ez a regex mindenre illeszkedik
}

Ennek a fenti hívásnak az eredményeképp megkapjuk, hogy két csoport van, a nulladikba került a teljes string, az elsőbe pedig a a whitespace duplaplusz nemjó string.

Ha pedig valamiért char* az input:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
regex  theRegex("\\s*((?:\\S+(?:\\s+\\S+)*)?)\\s*");
char* theText = "   a whitespace duplaplusz nemjó   ";                 //most char* a text
std::cmatch results;                                                   //ezért cmatch-ot használunk
if( regex_match(theText, results, theRegex )) {
  cout << "we have a match! Groups count: " << results.size() << endl;
  for( int i = 0; i < results.size(); i++ ) {
    cout << "Group " << i << " is *" << results[i] << "*" << endl;
  }
}else{
  cerr << "Sumthin is wrong"; //should never happen, ez a regex mindenre illeszkedik
}

Az output persze ugyanaz, mint volt az előbb is.

Ha regex_match helyett a regex_search függvényt hívjuk, ez szintén egy boolt ad vissza, hogy van-e az input textben az input regexre illeszkedő substring; ha igen, akkor az első illeszkedő substringgel frissíti a paraméterként kapott match_resultot, ha kapott olyat:

1
2
3
4
5
6
regex theRegex("[+-]?\\d+"); //számjegy-sorozat, esetleg előjellel
string theText("Ebben a szövegben 3 szám és 12 szó van, vagy még több");
std::smatch results;
if( std::regex_search(theText, results, theRegex) ) {
  cout << "Egy szám: " << results[0] << endl;            //prints '3'
}

Ha szeretnénk olyan funkcionalitást, amilyen pl. a grepnek van és megkeresni az összes illeszkedő stringet, akkor pl. iterálhatjuk a regex_searchet úgy, hogy minden lépésben az input stringnek a match utáni részére hívjuk. Ezt a stringet állítja nekünk elő a match_results osztály suffix() függvénye:

1
2
3
4
5
6
7
8
regex theRegex("[+-]?\\d+"); //számjegy-sorozat, esetleg előjellel
string theText("Ebben a szövegben 3 szám és 12 szó van, vagy -1 több");
std::smatch results;
string tempString = theText; //ne rontsuk szét az eredeti szöveget
while( std::regex_search(tempString, results, theRegex) ) {
  cout << "Egy szám: " << results[0] << endl;            //prints '3', then prints '12', then prints -1
  tempString = results.suffix();
}

Érdemes lehet tudni, hogy a fenti kód nem készít új másolatot a suffix() metódus hívásakor, az így készült tempString ugyanannak stringnek a memóriaterületére fog mutatni. Maga a suffix() metódus nem is egy stringet ad vissza, hanem egy referenciát egy olyan objektumra, melyből pl. az értékadás operátorral egy string objektumot tud készíteni, de másolás nélkül.

replace

A csomag sed-like regex alapú search&replace allt is támogat a std::regex_replace függvényen keresztül. Ennek értelemszerű használatára egy példa:

1
2
3
4
regex theRegex("[+-]?\\d+"); //megint számjegyek, possibly előjellel
string theText = "Ebben a szövegben a 27 és a -42 fordulnak elő számként.";
string replaced = std::regex_replace(theText, theRegex, "SZÁM");
cout << replaced << endl; //prints Ebben a szövegben a SZÁM és a SZÁM fordulnak elő számként.

Ha nem pont ez a szándékunk, akkor flagekkel módosítható a működés: pl. a format_first_only flag beállításával csak az első előfordulást cseréljük:

1
2
3
4
regex theRegex("[+-]?\\d+"); //megint számjegyek, possibly előjellel, két csoportban
string theText = "Ebben a szövegben a 27 és a -42 fordulnak elő számként.";
string replaced = std::regex_replace(theText, theRegex, "SZÁM", std::regex_constants::format_first_only);
cout << replaced << endl; //prints Ebben a szövegben a SZÁM és a -42 fordulnak elő számként.

A string, melyre cserélünk, tartalmazhatja még a következőket:

  • a $& jelzi magát a matchelt substringet
  • a $` jelzi a stringnek a match előtti részét (note: replaceAll hívásakor ez az előző match és az aktuális match közti rész lesz)
  • a $' a stringnek a match utáni részét
  • a $0, $1, stb. pedig a nulladik, első stb. capturing group tartalmát.

Így pl. ez a kód zárójelbe teszi az input szövegben a számok előjel utáni részét:

1
2
3
4
regex theRegex("([+-]?)(\\d+)"); //megint számjegyek, possibly előjellel
string theText = "Ebben a szövegben a 27 és a -42 fordulnak elő számként.";
string replaced = std::regex_replace(theText, theRegex, "$1($2)");
cout << replaced << endl; //prints Ebben a szövegben a (27) és a -(42) fordulnak elő számként.

A Java java.util.regex package

Ennek a csomagnak a működését már láttuk az előző alkalommal röviden. A java.util.regex csomag mindent támogat nagyon hasonlóan a C++ headerjéhez:

  • a Pattern osztály, melyet a compile statikus factory metódussal tudunk példányosítani egy regex stringből, kb a std::regex-nek felel meg
  • a Matcher osztály, melyet a legyártott pattern matcher( String text ) metódusával példányosítjuk, kb a std::regex_match-nek felel meg
  • bool értékek helyett a visszakapott objektumok megfelelő függvényeit (pl. a Matcher objektum matches() függvényét) kell hívnunk

A C++-ra fentebbi példakódokkal ekvivalens Java megoldások (egyben itt):

match

1
2
3
4
5
6
7
8
Pattern theRegex = Pattern.compile(".*\\btelefon\\b.*");  //elkészül a Pattern a regex stringből
String  theText = "alma körte telefon barack";            //ez lesz az input szöveg
Matcher theMatcher = theRegex.matcher( theText );         //elkészítjük a Matchert
if( theMatcher.matches() ) {                              //true, ha a szöveg illik a regexre
  System.out.println("a regex illik a szövegre");
}else{
  System.out.println("a regex NEM illik a szövegre");
}

groups

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
Pattern theRegex = Pattern.compile("\\s*((?:\\S+(?:\\s+\\S+)*)?)\\s*");
String theText = "   a whitespace duplaplusz nemjó   ";
Matcher results = theRegex.matcher(theText);
if( results.matches() ) {
  System.out.println("we have a match! Groups count: " + results.groupCount() );
  for( int i = 0; i <= results.groupCount(); i++ ) {                             //NOTE 0-tól groupCount()-ig vannak a csoportok!
    System.out.println("Group " + i + " is *" + results.group(i) + "*");
  }
}else{
  System.err.println( "Sumthin is wrong" );
}

search

1
2
3
4
5
6
7
Pattern theRegex = Pattern.compile("[+-]?\\d+"); //számjegy-sorozat, esetleg előjellel
String theText = "Ebben a szövegben 3 szám és 12 szó van, vagy még több";
Matcher results = theRegex.matcher(theText);
if( results.find() ){                                  //a find() metódus matchelő substringet keres
  System.out.println("Egy szám: " + results.group() ); //a group() ugyanaz, mint a group(0) : a match
  //prints Egy szám: 3
}

Ha mindent meg akarunk keresni, kicsit más módon tehetjük meg, mint C++-ban:

  • A Matcher objektum létrehozásakor a teljes input texthez kötöttük. A find(int from) metódusának meg tudjuk adni, hogy hanyadik pozíciótól kezdve keressen találatot.
  • Ha pedig a Matcher talált egy matchet, akkor az end() metódusával kaphatjuk meg azt a pozíciót, ami a vége (és már nincs benne a matchben).

Ezt a kettőt összekombinálva találhatunk egy grep-like searchAll-t:

1
2
3
4
5
6
7
8
Pattern theRegex = Pattern.compile("[+-]?\\d+"); //számjegy-sorozat, esetleg előjellel
String theText = "Ebben a szövegben 3 szám és 12 szó van, vagy -1 több";
Matcher results = theRegex.matcher(theText);
int lastPos = 0;                                        //lastPos-ban tároljuk, hogy honnan kezdje keresni a következőt
while( results.find(lastPos) ) {
  System.out.println("Egy szám: " + results.group());   //prints '3', then prints '12', then prints -1
  lastPos = results.end();                              //a következő keresést a mostani match végétől kezdje el
}

replace

Flagek helyett Javában a Matcher osztálynak van külön egy replaceAll és egy replaceFirst metódusa, mindkettő megkapja argumentumként, hogy mire cserélje ki a találato(ka)t:

1
2
3
4
5
Pattern theRegex = Pattern.compile("[+-]?\\d+"); //megint számjegyek, possibly előjellel
String theText = "Ebben a szövegben a 27 és a -42 fordulnak elő számként.";
Matcher results = theRegex.matcher(theText);
String replaced = results.replaceAll("SZÁM");
System.out.println(replaced); //prints Ebben a szövegben a SZÁM és a SZÁM fordulnak elő számként.
1
2
3
4
5
Pattern theRegex = Pattern.compile("[+-]?\\d+"); //megint számjegyek, possibly előjellel
String theText = "Ebben a szövegben a 27 és a -42 fordulnak elő számként.";
Matcher results = theRegex.matcher(theText);
String replaced = results.replaceFirst("SZÁM");
System.out.println(replaced); //prints Ebben a szövegben a SZÁM és a -42 fordulnak elő számként.

Kényelmes módon a replacement stringben pontosan ugyanúgy használhatóak a $0, $1 stb. meták is (a prefixre és a suffixre viszont nem működik a dollár-aposztróf és dollár-backtick kombó), melyek helyére a megfelelő captured groupok kerülnek be, mint C++ban:

1
2
3
4
5
Pattern theRegex = Pattern.compile("([+-]?)(\\d+)"); //megint számjegyek, possibly előjellel
String theText = "Ebben a szövegben a 27 és a -42 fordulnak elő számként.";
Matcher results = theRegex.matcher(theText);
String replaced = results.replaceAll("$1($2)");
System.out.println(replaced); //prints Ebben a szövegben a (27) és a -(42) fordulnak elő számként.

Note: a non-capturing zárójelek használata pl. azért is fontos lehet, mert itt a dollár metában csak 0 és 9 közti indexeket parsol fel, tehát maximum kilenc captured grouppal tudunk dolgozni!

A kétféle szemlélet: automata vagy backtrack

Láttuk előadáson, hogy egy (klasszikus, vagy egy olyannal ekvivalens) regexből könnyen lehet (nemdeterminisztikus) véges automatát építeni, ami ugyanazt a nyelvet ismeri fel, aminek szavaira a regex illeszkedik. Azt is tudjuk, hogy (nyilvántartva, hogy aktuálisan hol lehetünk az automatában) nemdeterminisztikus véges automatával, azaz NFA-val gyorsan tudunk regexet illeszteni.

Csakhogy mivel az első open-source regex motor implementáció nem ezt csinálta, hanem backtrack illesztett, ebből lett a "szabvány" is: az ún. PCRE szabvány (Perl Compatible Regular Expression) az alapján készült, hogy egy backtrack motor melyik találatot adja vissza a lehetségesek közül. Mint kiderült, amit a backtrack motor preferál, az nem visszaadható automatával - még akkor is, ha a regex "klasszikus" regex, az automatás illesztés módszere ugyan vissza tud adni egy illeszkedést, sőt a captured groupokat is, de ugyanazt visszaadni, amit a szabvánnyá lett PCRE illesztés megkövetel, nem igazán lehet másképp (jelen tudásunk szerint), mint ténylegesen végigtolva a backtracket.

Tehát egy mai regex illesztő motornak kb. a következő két választása van:

  • PCRE-kompatibilisen visszaadni a találatokat. Ekkor muszáj backtrackelnie és ezért lesznek olyan regexek (klasszikusak is), melyeken exp ideig fut.
  • (nemdeterminisztikus) automatát használni illesztésre, ha lehet. Ekkor (legalábbis a klasszikus regexeken) garantáltan gyors lesz, de nem lesz PCRE-kompatibilis.

Az egrep alapvetően pl. a második utat járja, a Java és a C++ pedig az elsőt. Persze a backtracking motorok közt is van különbség aszerint, hogy melyik ágakról "látják előre", hogy ott úgysem lesz illeszkedés, ily módon egy-egy backtrack motor jobb lehet, mint egy másik (erre egy példa, hogy a Java 8-ban még ha egy 32 db a-ból álló textre próbáltuk matchelni az (a+)+b (nyilvánvalóan nem illeszkedő) regexet, akkor ez timeoutolt, adta az exp idejű viselkedést, ez Java 11-ben már le van kezelve és szinte instant visszajön, hogy nem illeszkedik - pedig a Java továbbra is backtracket használ ugyanúgy, mint a C++ vagy a javascript az eddig látottak közül.

Legutóbb láttuk, hogy mi történik, ha Java 11-ben az egyre több a betűből álló anb stringre próbáljuk illeszteni az (?:a+)+ regexet és hogy mi történik ehhez képest Java 8-ban, de idemásolom, ami nálam történik (kód itt):

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
Length: 20 Elapsed time: 239us
Length: 21 Elapsed time: 147us
Length: 22 Elapsed time: 185us
Length: 23 Elapsed time: 167us
Length: 24 Elapsed time: 133us
Length: 25 Elapsed time: 115us
Length: 26 Elapsed time: 84us
Length: 27 Elapsed time: 116us
Length: 28 Elapsed time: 102us
Length: 29 Elapsed time: 81us
Length: 30 Elapsed time: 77us
Length: 31 Elapsed time: 77us
Length: 32 Elapsed time: 87us
Length: 33 Elapsed time: 90us
Length: 34 Elapsed time: 104us
Length: 35 Elapsed time: 115us
Length: 36 Elapsed time: 107us
Length: 37 Elapsed time: 113us
Length: 38 Elapsed time: 110us
Length: 39 Elapsed time: 117us
Length: 40 Elapsed time: 122us

Az, hogy egyre rövidebb idő alatt jött rá a motor az elején, hogy nem illeszkedik, az vélhetően annak köszönhető, ahogy a Java HotSpot a program futása közben elemezve, hogy mihez milyen gyakran férünk hozzá, dinamikusan elkezdett arról rendelkezni, hogy mi kerüljön ezek alapján a cache-be és mi nek. Néha időmérés közben pedig elképzelhető, hogy egy éppen beinduló garbage collector rontja el az időmérést.. Javában elég nehéz időt mérni.

Java 8-ban ugyanez a kód ezt adja nálam:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
Length: 20 Elapsed time: 126573us
Length: 21 Elapsed time: 57751us
Length: 22 Elapsed time: 112223us
Length: 23 Elapsed time: 226588us
Length: 24 Elapsed time: 449249us
Length: 25 Elapsed time: 937316us
Length: 26 Elapsed time: 1893573us
Length: 27 Elapsed time: 3762752us
Length: 28 Elapsed time: 7599350us
Length: 29 Elapsed time: 15238873us

(nem vártam végig, kilőttem) Ez annyira szépen adja a 2n időigényt, hogy annál keresve se találnék jobbat: eggyel növelve az n értékét, szinte teljesen pontosan duplázódik az időigény. Az legalábbis biztos, hogy valami upgrade történt Java 8 és 11 között illesztéskor (note: a us az mikroszekundum, milliomod másodperc, a 29 darab a és egy b, összesen 30 hosszú inputra tehát kb fél percig illesztett a "régi" Java motor).

Lássuk, mit lép erre a C++ (kód itt):

1
2
3
4
5
6
7
Length: 20 Elapsed time: 272322us
Length: 21 Elapsed time: 542538us
Length: 22 Elapsed time: 1080090us
Length: 23 Elapsed time: 2166841us
Length: 24 Elapsed time: 4325287us
Length: 25 Elapsed time: 8636044us
Length: 26 Elapsed time: 17254479us

Ha átrakom a fordítót release módba debugból:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
Length: 20 Elapsed time: 46073us
Length: 21 Elapsed time: 90612us
Length: 22 Elapsed time: 182764us
Length: 23 Elapsed time: 367602us
Length: 24 Elapsed time: 732752us
Length: 25 Elapsed time: 1454524us
Length: 26 Elapsed time: 2908245us
Length: 27 Elapsed time: 5832874us
Length: 28 Elapsed time: 11658973us
Length: 29 Elapsed time: 23727141us

Oh well, még így is lassabb, mint a Java 8 :D

Now ha 20-tól 40-ig odaadom ugyanazeket a stringeket az egrepnek egy file-ban, ezt kapom:

1
2
3
4
5
$time egrep '^(a+)+$' grep_input_aplusplus.txt

real    0m0,002s
user    0m0,002s
sys 0m0,000s

Két millisec (összesen 2000us) alatt végighúzta az összes inputon (az óra is ms pontosságú tho), szóval ezt a kört az egrep és a Java 11 nyerték, a C++ és a Java 8 vesztették.

Most érdemes tudnunk arról is, hogy az egrep ugyan egy időben többet tudott a grepnél (ezért hívták Extended grepnek), de ma már deprecated, és a grep -E parancs ekvivalens vele. Abszolút hasonló időt is produkál:

1
2
3
4
5
$time grep -E '^(a+)+$' grep_input_aplusplus.txt

real    0m0,004s
user    0m0,001s
sys 0m0,003s

Viszont, a grep -E, azaz az egrep, nem mindig pont a PCRE szabványnak megfelelő captured groupokat ad vissza. Van egy -P opciója a grepnek, amivel lehet forcolni, hogy márpedig PCRE-kompatibilis legyen. Ekkor pedig:

1
2
3
4
5
6
$time grep -P '^(a+)+$' grep_input_aplusplus.txt
grep: exceeded PCRE's backtracking limit

real    0m0,089s
user    0m0,085s
sys 0m0,004s

A PCRE kompatibilitás a grepnél is azt jelenti, hogy backtrackelni fog és ha túl sokat backtrackel (többet, mint egy előre beégetett konstans), akkor kilövi az egészet és kirakja a standard errorra, hogy túllépte a backtracking korlátot.

Egy másik "nehéz" regex a backtracking motoroknak a a?a?a?...a?aaa...a illesztése az aaa...a inputra, ahol is a?-ből is, a-ból is mindenhol valami n darab van. Nyilván illeszkedést kéne kapjunk, hiszen az összes a?-et ha üres stringre tesszük, akkor a hátsó n darab a illeszkedni fog az inputra, ami szintén n darab a. Ez már megfekteti a Java 11-et is (pedig klasszikus regex):

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
Length: 20 Elapsed time: 65653us
Length: 21 Elapsed time: 65353us
Length: 22 Elapsed time: 119844us
Length: 23 Elapsed time: 264733us
Length: 24 Elapsed time: 511237us
Length: 25 Elapsed time: 1083926us
Length: 26 Elapsed time: 2090143us
Length: 27 Elapsed time: 4521295us
Length: 28 Elapsed time: 8746713us
Length: 29 Elapsed time: 19187271us
Length: 30 Elapsed time: 36869034us

A release-be fordított C++ se okoz meglepetést az előzőhöz képest:

1
2
3
4
5
6
7
8
9
Length: 20 Elapsed time: 83623us
Length: 21 Elapsed time: 169654us
Length: 22 Elapsed time: 355323us
Length: 23 Elapsed time: 747202us
Length: 24 Elapsed time: 1561360us
Length: 25 Elapsed time: 3271949us
Length: 26 Elapsed time: 6907469us
Length: 27 Elapsed time: 14747987us
Length: 28 Elapsed time: 30235478us

Let's see the grep 40 karakterre:

1
2
3
4
$echo aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa|time grep -E --color '^a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa$'
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
0.00user 0.00system 0:00.00elapsed 80%CPU (0avgtext+0avgdata 3420maxresident)k
0inputs+0outputs (0major+205minor)pagefaults 0swaps

Ezt a kört a grep nyerte, ami automatát épít, amikor csak tud.

Hát, azt beszéltük a múltkor, hogy a backreference az kivezet a reguláris nyelvek osztályából, adja magát, hogy mi lenne, ha mondjuk beadnánk egy (.)\1(a+)+ regexet a grepnek h eméssze egy kicsit mondjuk az n darab a-t követő egy darab b betűn (nyilván nem illeszkedik, de van benne backreference, tehát nem tud automatát építeni hozzá):

1
2
3
4
5
$ time grep -E '^(.)\1(a+)+$' 03-grep_input_aplusplus.txt

real    0m0,004s
user    0m0,001s
sys 0m0,003s

OK, ez nem segített, a grep ezt továbbra is megeszi simán.

1
2
3
4
5
$ time grep -E '^(a+)+(.)\2$' 03-grep_input_aplusplus.txt

real    0m0,015s
user    0m0,010s
sys 0m0,005s

Mintha kicsit lassabb lenne, de nem tűnik számottevőnek. (Java, C++ természetesen exp lelassul mindkét regexen.)

Mivel tudjuk, hogy backreference-ek használatával nem ismert, hogy elkerülhető lenne egyáltalán az exp viselkedés, azért lehet találni olyan regexet is, ami a grepből is kihozza ezt a viselkedést:

1
2
3
4
5
$ time grep -E '^(.+)(a+)+\1\1b$' 03-grep_input_aplusplus.txt
//..itt ugye minden 20..40 hosszú string illeszkedik az inputból, ezeket kiírja
real    0m18,473s
user    0m18,455s
sys 0m0,004s

Itt már az utolsó, 40 hosszú stringgel elszöszölt kb tíz másodpercet, mielőtt rájött, hogy illeszkedik. De in general az egrep, avagy grep -E, gyorsabb illesztő motor, mint a többi, amennyiben nem ragaszkodunk a PCRE kompatibilitáshoz.

A PCRE

SOON

Regexek vagyolása, éselése, negálása

A "páros sok a van benne" kérdésre előállhatunk mondjuk a következő regexszel: [^a]*(?:a[^a]*a[^a]*)*. Persze az egymásba ágyazott csillagok miatt akár aggódhatunk is, hogy ez most akkor okoz-e bármi exp viselkedést, de ez épp nem fog; erre még később visszatérünk, hogy miért is nem. Most C++-ban fogunk időmérni, de csak mert ott megbízhatóbban tudunk, mint Javában. (Kód itt.)

Először is generálunk egy string vektort, benne 10.000 darab, egyenként 100 hosszú stringgel, random feltöltve a,b,c betűkkel. (Igen, ezt a részt lehetne hatékonyabban is, ha nem stringet használnánk, amíg összerakjuk.)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
vector<string> inputs;                                          //ebbe a vektorba tesszük a generált stringeket
std::default_random_engine generator;                           //veszünk egy random generátort
void fillVector(int count, int length){
    inputs.clear();                                             //üresre inicializáljuk az inputok vektorát
    std::uniform_int_distribution<int> distribution(0,2);       //0-tól 2-ig dobunk egyforma eséllyel inteket
    for( int i = 0; i < count; i++ ){
        std::string randomString = "";
        for(int j = 0; j < length; j++){
            char d3 = (char)('a'+distribution(generator));      //'a', 'b' vagy 'c' lesz, akit hozzáfűzünk
            randomString += d3;
        }
        inputs.push_back(randomString);                         //betesszük a vektorba
    }
}

Megírunk egy függvényt, mely kiszámolja "kézzel", hogy a generált stringvektorban mennyi olyan van, akiben páros sok az a betű:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
inline bool evenChars( string input, char c ){
    bool even = true;
    for( int i = 0; i < input.length(); i++ ){
        if(input[i] == c) even = !even;
    }
    return even;
}

size_t countEvenChars( char c ){
    int count = 0;
    for( string input : inputs ){
        if( evenChars(input, c)) count++;
    }
    return count;
};

és egy olyat, ami ugyanezt regex illesztéssel teszi meg:

1
2
3
4
5
6
7
8
regex theRegex("[^a]*(?:a[^a]*a[^a]*)*");
size_t countEvenAsRegex() {
    size_t count;
    for( string input: inputs ) {
        if( regex_match(input, theRegex)) count++;
    }
    return count;
}

Feltöltjük a vektorunkat azzal a megígért 10.000 darab 100 hosszú random a,b,c fölötti stringgel, és lemérjük mindkét megközelítést:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
fillVector(10000,100);

auto start = high_resolution_clock::now();
size_t count = countEvenChars('a');
auto end   = high_resolution_clock::now();
cout << "Direct count: " << count << " Time: " << std::chrono::duration_cast<std::chrono::microseconds>(end-start).count() << endl;

start = high_resolution_clock::now();
count = countEvenAsRegex();
end   = high_resolution_clock::now();
cout << "Regex  count: " << count << " Time: " << std::chrono::duration_cast<std::chrono::microseconds>(end-start).count() << endl;

Hát..

1
2
Direct count: 4987 Time: 1293
Regex  count: 4987 Time: 33372

Nagyságrendileg ugyanez marad az időigény, ha 1000 darab 1000 hosszú stringet, vagy 100 darab 10.000 hosszú stringet generálunk, tehát a regex illesztés nem exp idejű, hanem szép lineáris, csak na, lassú azért a direkt módszerhez képest.

Javában sincs ez másképp (kód):

1
2
Direct count: 4992 Time: 13616
Direct count: 4992 Time: 64658

viszont javában, ha 100 darab 10.000 hosszú stringet generálunk:

1
2
Exception in thread "main" java.lang.StackOverflowError
    at java.base/java.util.regex.Pattern$GroupHead.match(Pattern.java:4804)

és egyébként ha 1 darab 100.000 hosszú stringen próbáljuk a C++ regex illesztést elvégezni, akkor ott is

1
Process finished with exit code 139 (interrupted by signal 11: SIGSEGV)

érkezik -- ez az egymásba ágyazott csillagok következménye miatt létrehozott rengeteg backtrack breakpoint következménye mindkét esetben.

Ha pedig pl. az ezzel "ekvivalens" (?:[^a]|(?:a[^a]*a[^a]*))* regexet nézzük (10.000 darab 100 hosszú stringre), akkor a C++ ezen exp viselkedést produkál, a Java meg egy kicsit meglassul (kb kétszer-háromszor annyi idő alatt fut végig, mint az eredeti regexünkkel). Ez meg valahol az alternálás megcsillagozása miatt történik, többé-kevésbé.

Hogy erre mit lehet lépni a leírások szerint (és hogy ezek mennyire működnek), visszatérünk még a lazy és possessive quantifierek részben.

Egyébként a grepnek odaadva fileban a inputot (tehát még azt is meg kellett nyissa, beolvassa, stb) ha a -c kapcsolójával csak az illeszkedő sorok számát kérjük le és nem íratjuk ki vele:

1
2
3
4
5
6
$time grep -E -c '^[^a]*(a[^a]*a[^a]*)*$' abc_10000_times_100.txt
4965

real    0m0,173s
user    0m0,167s
sys 0m0,004s

ez kb 167000us-nek felel meg az előzőekkel összemérve, de vannak benne file műveletek. Igaz, maga a file I/O annyira nagyon sok időbe nem telhet, hiszen:

1
2
3
4
5
6
$ time grep -E -c '^.*$' abc_10000_times_100.txt
10000

real    0m0,020s
user    0m0,019s
sys 0m0,001s

egy egyszerű regexet illesztve 19000us alatt végez a file I/O-val. Nézzük a másik regexünket:

1
2
3
4
5
6
$ time grep -E -c '^([^a]|a[^a]*a[^a]*)*$' abc_10000_times_100.txt
4965

real    0m0,191s
user    0m0,187s
sys 0m0,004s

a grep robusztusságát nem igazán zavarja az alternálás csillagozása sem.

1
2
3
4
5
6
$ time grep -E -c '^([^a]|a[^a]*a[^a]*)*$' abc_10_times_100000.txt
6

real    0m2,083s
user    0m2,077s
sys 0m0,004s

sem pedig az, ha 100.000 hosszú stringeket kap. (Legalábbis annyira nem, mint a Javát meg a C++-t.)

vagyolás

A vagyolás adja magát mint reguláris művelet: ha "páros sok a vagy páros sok b" kell nekünk, akkor csak alternáljunk egyet. Grep time ugyanerre a file-ra:

1
2
3
4
5
6
$ time grep -E -c '^[^a]*(a[^a]*a[^a]*)*$|^[^b]*(b[^b]*b[^b]*)*$' abc_10000_times_100.txt
7516

real    0m0,236s
user    0m0,235s
sys 0m0,001s

C++ időmérés két különböző direkt módszerrel:

1
2
3
Direct count: 7485 Time: 1814
Direct count2: 7485 Time: 1366
Regex  count: 7485 Time: 48077

Java:

1
2
Direct count: 7509 Time: 14870
Regex count:  7509 Time: 95463

A kb. másfélszeres idők nagyjából világosak: a regex első fele ilyen tételben kb az esetek felében illeszkedik, ekkor a második felét a vagyolásnak ki se értékeli a motor, a maradék felében viszont igen (és az meg szintén kb 50% eséllyel fog illeszkedni), így jön ki, hogy az eredeti időigénynek még a fele jön rá pluszban kb (és kb a random inputok 75%-ára illeszkedik a vagyolás).

Negálás, éselés

  • Jövő hétre otthoni feladat: hasonlóan mérjünk ki különböző regexeket (és a direkt módszereket) a "páros sok a ÉS páros sok b" nyelvre -- először gondoljuk át, hogy az eddigi tapsztalataink alapján vajon melyik motor mennyire lesz gyors az illesztésben! Itt valójában ha már regexeket használunk, akkor vélhetően jobb megoldás lesz külön-külön illeszteni a két regexet és éselni az eredményt, mint egy nagy regexbe gyúrni az egész kifejezést.
  • Ha a külső regexet negáljuk, akkor C++ és Java esetében nincs nagy különbség: csak a matches() függvényt mikor vizsgáljuk, a másik szálán kell menjünk tovább az ifnek. A grepnek pedig a -v kapcsolója fogja kilistázni pontosan azokat a sorokat, melyekben nincs illeszkedés a kért regexre. De mi van akkor, ha egy belső kifejezést szeretnénk negálni/komplementálni?

Lookahead

Van, amikor jól jön, ha egy-egy pozícióján a stringnek szeretnénk tesztelni, hogy a pozíció utáni rész(nek egy prefixe) illik-e egy mintára, és ha illik, akkor nem feldolgozni azt a részt, hanem onnan folytatni az illesztést, ahol tartottunk, mintha csak "előrenéznénk" az inputot feldolgozás nélkül. Ezt lookaheadnek hívják és a jele C++-ban is és Javában is a (?= nyitó- és ) zárójel. Tehát amikor egy (?=R)T regexet illesztünk egy pozíción, akkor

  • először a motor megnézi, hogy ezen a pozíción kezdődik-e olyan substringje a teljes inputnak, ami illeszkedik R-re;
  • ha nem, akkor itt nincs illeszkedés, ha viszont igen, akkor megpróbálja ugyanerről a pozícióról illeszteni T-t (az már fel fogja dolgozni a karaktereket, ahogy szokta is, amikre illeszkedik).

(note: a sed nem támogatja a lookaheadet -- amennyire hinni lehet az internetnek, a körbenéző operátorokat, mint a lookahead is, csak a PCRE backtracking motorok támogatják)

Van még:

  • negatív lookahead: egy pozíción akkor illeszkedik a (?!R) regex, ha a pozíció utáni stringnek nincs olyan prefixe, melyre illeszkedik R.
  • (pozitív) lookbehind: egy pozíción akkor illeszkedik a (?<=R) regex, ha a pozíció előtti stringnek van olyan suffixe, amire illeszkedik R.
  • negatív lookbehind: egy pozíción akkor illeszkedik a (?<!R) regex, ha a pozíció előtti stringnek nincs olyan suffixe, amire illeszkedik R.

Messze nem minden motor támogatja ezeket a lookaround műveleteket: a cpp::regex pl. nem támogatja a lookbehindot.

A negatív lookahead hasznos lehet, ha pl. olyan feltételünk van, ami azt mondja, hogy a mintánkat nem követi pl. valamilyen karakter: a q[^u] mintára findolva megkapjuk az összes olyan q betűt az input stringben, ami után jön egy karakter, és az nem u, de egyrészt ez lenyeli ezt a második karaktert is (tehát pl. ha qqx van a stringünkben, akkor csak az első q-ra jelez találatot), másrészt a szó végén lévő q-ra nem illik (mert a [^u]-nak kell egy karakter, ami nem u, de akkor is kell neki egy karakter). Ehelyett a q(?!u) regexet illesztve minden olyan q karaktert megtalálunk a stringben, ami után nem jön u betű, akár a string végén van, akár nem.

Feladatok

  • Írjunk függvényt C++-ban vagy Javában, mely az inputként kapott stringből készít egy olyan stringet, ami az eredeti string minden számjában hármasával pontokat helyez el a szokásos módon! Pl. a van 1001 kiskutyám és 1234567 hópihém, nem csak 4000 stringből készítse el a van 1.001 kiskutyám és 1.234.567 hópihém, nem csak 4.000 stringet.

Utolsó frissítés: 2020-09-27 22:48:51