Regulaaravaldised

Allikas: Keeleleek

Tihti nimetatud ka regexpidena või regexidena, inglise keeles regular expression. Populaarseks muutusid regulaaravaldised 1960ndate programmeerimiskeeles SNOBOL, kuigi regulaaravaldised ja rekursiivteooria rajas Stephen Cole Kleene juba 1930.--1940. aastail. Kleene' järgi on nimetatud ka regulaaravaldiste tuntuim operaator * ehk tärn Kleene'i tärniks (Kleene star). Oleks huvitav uurida N. Chomsky ja rekursiivteooria vahekorda. Chomsky lõi kontekstivabade ja kontekstitundlikke keelte klassid ja sellega vahetegemise nende vahel.

Regulaaravaldiste kasutus erineb otsimootorite programmeerimiskeelte valdkondades, siinne tekst ei ole veel valdkonniti jaotatud, ent põhirõhk peaks olema otsimootorite poole.


Lihtne õpetus

Mitte-programmeerijad kohtavad regulaaravaldisi mh korpuste otsingutes, kus nood võimaldavad otsida "mitut-asja-korraga" või "umbes-sellist-asja" tüüpi otsinguid.

  • Püstkriips töötab loogilise või-na, st võimaldab otsida "seda või toda". Näiteks leiab järgmine avaldis nii sõnavormi 'seda' kui ka sõnavormi 'toda'
 seda|toda      # leiab 'seda', 'toda'
  • Rühmitamine töötab sama moodi nagu matemaatikas; 1+2*3=7 aga (1+2)*3=9; Grupeerimine ei ole aga alati hea loetavuse jaoks. Järgmist koodi loetakse järgmiselt "alamgrupist ühitada kas 'se' või 'to', millele järgneb 'da'
 (se|to)da      # leiab 'seda', 'toda'
  • Kvantor "üks või rohkem" märgitakse plussmärgiga, millega tähistatakse "eelnev täht või grupp peab esinema vähemalt üks kord, aga võib ka rohkem".
 (ko)+kutamine  # leiab 'kokutamine', 'kokokutamine' jne
  • Kvantor "null või rohkem" märgitakse tärniga (ehk Kleene'i tärniga), mis tähendab et eelnevat tähte või rühma võib esineda kui mitu korda tahes, või üldse mitte esineda
 koku(ta)*mine  # leiab 'kokumine', 'kokutamine', 'kokutatamine' jne
  • Kvantor "olla või mitte olla" märgitakse küsimärgiga, ja tähendab et eelnev täht või grupp kas esineb või ei esine
 pea(ae)?gu     # leiab 'peagu' ja 'peaaegu'
  • "Mistahene" märgitakse punktiga, ja üks punkt leiab ühe mis tahes tähe (arvutis on ka nt tühik 'täht'). Mistahes-punkti saab muidugi modifitseerida nt kvantoriga.
 kas.         # leiab nt 'kass', 'kast', 'kas ' jne
 kas.*        # leiab kõik mis algab 'kas'-ga; nt 'kastani tn', 'kas sa saad?' jne
  • "valikulised" määravad rühma, millest üks liige peab leiduma. Liikmed defineeritakse nurksulgude vahel.
 [kK]as.*       # sama mis eelmine, aga leiab ka suure algustähe
 [aoeuiyäõöü]+  # leiab kõik sõnad, mis koosnevad vaid täishäälikutest
  • rühmi saab ka eitada, ehk vastandväärtust andma, siis leiab see kõike seda mida rühmas ei ole määratud. Eitus käib ^ märgiga kohe pärast sulgu
 [^aoeuiyäõöü]+  # leiab kõik konsonantklustrid
  • kui on vaja leida just sellist tähte mis töötab operaatorina, siis peab kasutama paomärki (kurakaldkriipsu) selle ees, või paigutama nurksulgudesse
 \.      # leiab punkti
 [.]     # leiab samuti punkti
 \?      # leiab küsimärgi
 [?]     # leiab samuti küsimärgi
 \\      # leiab kurakriipsu
 
 [*.^?]  # leiab kas tärni, punkti, katuse või küsimärgi
 [^*.?]  # NB! kui katus on esimene liige, siis töötab see eitajana
         # niisiis leiab see avaldis kõike muud peale tärni, punkti ja küsimärgi
 [^]     # üksinda vastab see ikkagi katusmärgile (mis on tegelikult loogiline)
 \^      # sama mis eelmine
 \]\[    # leiab märgijada ][
 \[.\]   # leiab mis tahes asja nurksulgude sees, nt [a] või [1] või [ ]
 # kõik järgmised märgid tuleb paomärgiga otsida
 . ^ $ * + ? { [ ] \ | ( )
  • Sõna algust ja sõna lõppu saab ka märkida (mida sõnaalgus tähendab (sest tegelikult tähendab see hoopis midagi muud) loe edasijõudnute osast)


Edasijõudnule, ehk "kõik mis sa õppisid on vale"

Nagu maailmas mujalgi, on ka siinses õpetuses asjad tinglikud. Tegelikkus on alati mitmekesisem kui teooria või mudel.

Mudeli käitumine sõltub tihti aga asjadest, mis tavakasutajale ei ole nähtavad. Näiteks võib otsimootor automaatselt lisada päringujadale rea alguse ja rea lõpu sümbolid. Need lisada või mitte lisada sõltub korpusest ja sellest mida otsitakse. Korpused kust saab otsida sõnu, tihti piiritlevad otsitava niimoodi, korpused kus aga saab otsida lauseid, vastupidi ei piiritle otsitavat. Otsimootori disain püüab ennetada seda, et otsija ei pea iga otsingu puhul lisama ^piire$ või lisama .*mitte-piire.*. Näiteks eesti keele spontaanse kõne foneetilise korpuse otsimootor arvab, et otsitakse sõna (st lisab). Tasakaalus kirjakeele korpus neid ei lisa, ja otsija peab ise seadma sõnapiirid paika. Disain sõltub ka korpuse segmenteerimisest (kas segmendiks on sõna, lause või terviktekst).


Proovime siis selgemaks teha


 [aäoõeöuüi]+   # tegelikult ei leia 'vaid vokaalidest koosnevaid sõnu'
                # vaid leiab lihtsalt kõik vokaalid

leiab järgmise eelmine avaldis leiaks kõik selle, mis on selles lauses alljoonestatud. See on tegelikult loogiline, sest avaldises on kirjeldatud vaid "üks või rohkem vokaali", ja seda ta leiabki. Mida me tahame leida on 'kõik sõnad, mis koosnevad ühest või rohkemast vokaalist', aga kuidas me defineerime sõna?

Arendame avaldist edasi naiivse definitsiooniga, et sõna on üks tähtede jada, mis on mõlemalt poolt tühikutega ümbritsetud.

 [aäoõeöuüi]+      # nüüd on lisatud tühikud ette ja taha ja nüüd leiab
                   # avaldis 'vokaalidest koosnevad sõnad'. kuna tühikud
                   # ei paista väga silma, on parem kasutada märki \b
 \b[aäoõeöuüi]+\b  # \b märgib sõnapiiri, st hariliku tähe ja mitte-tähe
                  # vahelist piiri (tühik ja punktuatsioon on mitte-tähed)

See avaldis ei leia rohkem kui ühe sõna sellest lausest. See sobib, aga kui kriitiline olla, siis ei ole kõik sõnad tühikutega piiritletud, nt esimese sõna ees lause alguses ei pruugi olla tühikut. Ka ei ole ^ ja $ operaatoritest kasu, juhul kui korpus on segmenteeritud lauseteks (sellises korpuses-kontekstis tähendaks meie avaldis ^[aäoõeöuüi]+$ "kõik laused mis sisaldavad vaid täishäälikuid"). See mida me leiame, sõltub sellest, millest me seda otsime -- see on otsija mure arvestada kontekstiga, mitte regulaarse keele.


Näiteid

Loetavuse heaks on \b tihti ärajäetud.

 [^ ]+             # jada, mis saab koosneda kõigest muust kui tühikutest,
                   # korpuste kontekstis tähendab see tihti lihtsalt sõnavormi.
                 
 <[^>]+>           # jada, mis jääb < ja > vahele, nt <märgisiltide vahel olev tekst>
 \([^)]+\)         # sama tehnikat võib ka teiste märkide puhul rakendada, nt ( ja )
                   # NB! sildimärgid < ja > jäävad leitud jada külge alles
 <a[^>]*>[^<]*</a> # leiab HTML koodist kõik <a href="www...">aadressid</a> ja nende tekstid
 \bkas [^ ]+       # sõna mis järgneb sõnale 'kas' ja tühikule
 \bkas [^?]+\?     # lause, mis algab sõnaga kas, ja lõppeb küsimärgiga
 \b[Kk]as [^?]+    # terve kas-küsilause-fraas küsimärgini
 \b[Kk]as [^?]+\?  # terve kas-küsilause-fraas koos küsimärgiga
 garaaž[gk]i       # kumb neist õige oligi?
 tee[nd]           # leiab 'teen' ja 'teed'
 tee(n|d|me|te)    # leiab 'teen', 'teed', 'teeme' ja 'teete'
 tegema|teha       # leiab 'tegema' ja 'teha'
 te(gema|ha)       # kas on sama arusaadav mis eelmine?
 [Nn]ä(ge(ma|mine|v)|gi([nd]|[mt]e)?|h(a(kse)?|es|k[ue]|tud)|e([nd]|[mt]e)?|inud)
                   # nägema sõna mõned pindstruktuurid :)


Formaalsem definitsioon

Regulaaravaldis on iseenesest ühe regulaarse keele kirjeldus ehk grammatika. Regulaarne keel on Chomsky hierarhias neljandal ja seega viimasel kohal, järgmine on kontekstivabad grammatikad (ehk programmeerimiskeeled).

Internetiallikaid

Python programmeerimiskeele Regular Expression HOWTO on hea ülevaatlik ja hästi organiseeritud õpetus, Ctrl+F-iga otsida leiab kiiresti üles väiksed detailid mis unarusse jäävad. Soovitan ka mitte-programmeerijatele.