Materjalid koostas ja kursuse viib läbi
Tartu Ülikooli arvutiteaduse instituudi programmeerimise õpetamise töörühm
| < eelmine | 6. OSA sisukord | järgmine > |
6.1 Regulaaravaldis
Eelnevates osades oleme vaadanud teemasid, meetodeid ja konstruktsioone, mida iga programmeerija oma igapäevases töös kasutab. Selles osas käsitleme vahendeid, mis ei pruugi olla igale programmeerijale kohustuslikud, kuid on siiski väga huvitavad ja kasulikud ka igapäevaelus.
Päris paljud programmeerijatel ette tulevad ülesanded on seotud sõnade ja teksti analüüsiga. Seesugusest analüüsist on sageli abi ka ülesannete juures, kus seda esmapilgul ehk ei ootakski.
ÕIGEKEELSUSSÕNARAAMAT. METAMÄRK
Kui soovime teada saada mingi eestikeelse sõna õigekirja või tähendust, siis võime abi otsida “Eesti õigekeelsussõnaraamatust ÕS 2013”. Näiteks kui tahame teada, kuidas käändub sõna “aadress”, siis sisestame veebilehel http://www.eki.ee/dict/qs/ olevasse päringuvormi selle sõna ja saamegi tema kohta info kätte.
Mis saab aga siis, kui me ei tea täpselt, kuidas otsitavat sõna kirjutada? Selle peale on mõeldud! Probleemsete tähtede asemele saame panna küsimärgi. Näiteks kui me ei tea, kas õige on “kandidaat” või “kanditaat”, võime sisestada “kandi?aat”. Küsimärki nimetatakse selles kontekstis metamärgiks ehk metasümboliks. Metamärk ei tähista iseennast, vaid viitab mingile reeglile, mille põhjal saame meie (ja ka arvuti) aru, kuidas antud kohta sõnas mõista. Seega metamärgina tähistab küsimärk ühte suvalist sümbolit. Otsingusõna “kandi?aat” puhul leitakse selliseid sõnu sõnaraamatust ainult üks. Sobivaid vasteid võib-olla ka rohkem, näiteks "?ell" puhul on neid lausa kuus. Kui asendada sõna esimene täht (või mitu tähte) küsimärgiga, siis see annab juba päris hea meetodi, kuidas riimuvaid sõnu otsida!
Otsingute puhul on teiseks levinud metamärgiks tärn *, mis tähistab suvalist arvu mingeid märke (seejuures ka märkide puudumist). Näiteks päring "meh*aanika" leiab kõik sõnad, mis algavad tähtedega "meh" ja lõppevad tähtedega "aanika". Nüüd võib sobivate vastete hulgas olla ka lühemaid ja pikemaid sõnu, sest tärni asemel võib olla null, üks või rohkem märki. Nii saame "ka*ak" korral vasteteks teiste hulgas "kaak", "kajak" kui ka "kaelkirjak".
Otsingus võib korraga olla mitu metamärki, nt *us?epp. Otsingusõna võib koosneda ka ainult metamärkidest, näiteks "???????????????????????".
Ülesanne
Proovige veebilehel http://www.eki.ee/dict/qs/ erinevaid päringuid, näiteks neid:
- kandi?aat
- *sepp
- *us?epp
- ???????????????????????
REGULAARAVALDIS
Metamärkide süsteeme on mitmeid ja olenevalt süsteemist võivad metamärkide tähendused ka erineda. Järgnevalt vaatleme süsteemi, mis on paljudes programmeerimiskeeltes levinud. Selles süsteemis ongi märkide ? ja * tähendused teistsugused kui ülaltoodud sõnastiku päringutes.
Käesolevas tekstis on kasutatud termineid "sõna" ja "sõne". "Sõna" on siin tavalises tähenduses, näiteks "armastus" ja "lapsepõlv" on sõnad. Mõiste "sõne" on laiem, sest sõne võib sisaldada ka tühikuid, kirjavahemärke, isegi reavahetusi jms. Sõnest võib mõelda kui suvalisest sümbolijadast. Mingi sõne alamsõneks nimetatakse sõnet, mis sisaldub esialgses sõnes. Kui sõne on näiteks “Ma tahaksin kodus olla”, siis selle alamsõned on teiste hulgas näiteks "Ma", "kodu", "sin ko" ja " ".
Eeltoodud ÕSi päringute puhulgi anti vastuseks need sõnad, mis vastasid päringus määratud mustrile. Mitmetes programmeerimiskeeltes saab mustrit kirjeldada regulaaravaldise abil. Iga konkreetse sõne puhul saab siis öelda, kas see sõne vastab antud regulaaravaldisele või mitte. Regulaaravaldistes on tähtis roll metamärkidel, millest siin materjalis piirdume ainult mõne olulisemaga. Need on toodud järgnevas tabelis.
| Metamärk | Kirjeldus | Näide |
|---|---|---|
| . | üks suvaline sümbol | "a.i" |
| Sümboli "a" järel on suvaline sümbol ja seejärel "i". | ||
| Näiteks "abi", aga mitte "appi". | ||
| ? | 0 või 1 kord eelnevat sümbolit või regulaaravaldist | "ai?" |
| Sümboli "a" järel on 0 või 1 sümbolit "i". | ||
| Ainsad näited on "a", "ai". | ||
| * | suvaline arv kordi (ka 0 korda) eelnevat sümbolit või regulaaravaldist | "ai*" |
| Sümboli "a" järel on suvaline arv korda sümbolit "i". | ||
| Näiteks "a", "ai", "aii", "aiiii". | ||
| {n} | n korda eelnevat sümbolit või regulaaravaldist | "ai{2}" |
| Sümboli "a" järel 2 sümbolit "i". | ||
| Ainus näide on "aii". | ||
| [ ] | võimalike sümbolite hulga märkimine | "a[ij]" |
| Sümboli "a" järel on sümbol "i" või sümbol "j". | ||
| Ainsad näited on "ai", "aj". | ||
| [ - ] | võimalike sümbolite vahemiku märkimine | "a[0-9]" |
| Sümboli "a" järel on suvaline number. | ||
| Näiteks "a0", "a5". | ||
| ( ) | rühmitamine | "a(ij)*" |
| Sümboli "a" järel on suvaline arv korda sümbolipaari "ij". | ||
| Näiteks "a", "aij", "aijij", "aijijij", aga mitte "aji". | ||
| ^ | sõne algus | "^ai" |
| Sõned, mis algavad sümbolipaariga "ai". | ||
| Näiteks "ai", "aine", "aiandus". | ||
| $ | sõne lõpp | "ai$" |
| Sõned, mis lõpevad sümbolipaariga "ai". | ||
| Näiteks "ai", "hai", "samurai". |
Metamärkide abil saame koostada lihtsamaid ja keerulisemaid regulaaravaldisi. Ühes regulaaravaldises võib olla ka mitu metamärki. Näiteks ".a*" tähistab, et suvalisele sümbolile järgneb suvaline arv korda sümbol "a". Kuna suvaline arv võib ka 0 olla, siis "a" võib ka puududa.
Sõne vastavust regulaaravaldisele saab Pythonis kontrollida funktsioonidega re.match ja re.search. Kõigepealt tuleb importida moodul re. Nimi re tuleb ingliskeelsest mõistest regular expression, mis tähendabki tõlkes regulaaravaldist. Seega kirjutame programmi algusesse import re.
FUNKTSIOON re.match
Vaatleme esialgu funktsiooni re.match, millega saab kontrollida, kas sõne algus vastab regulaaravaldisele. Esimeseks argumendiks tuleb sellele funktsioonile anda regulaaravaldis, teiseks argumendiks sõne. Funktsiooni re.match saame kasutada valikulauses.
Järgnev programm kontrollib, kas sõne "abi" algab regulaaravaldisele "a.i" vastavalt. Punkt (".") tähistab üht suvalist sümbolit ning antud hetkel sobib suvalise sümboli rolli täht "b".
import re
if re.match("a.i", "abi"):
print("vastab")
else:
print("ei vasta")
Funktsioon re.match otsib vastavust sõne algusest. Seega re.match("a.i", "Nabi") puhul vastavust pole. Küll aga ei pea regulaaravaldisele vastava osaga sõne ära lõppema, nt re.match("a.i", "abiks") näitab vastavust.
Mitme metamärgiga regulaaravaldised avavad uusi (ka keerulisi) võimalusi. Näiteks ".*" tähendab, et suvalisi sümboleid on suvaline arv kordi (võib olla ka null korda). Regulaaravaldisega ".*a.i" on seega vastavuses “Nabi”, “esmaabi”, “aabits”, “aminohape on oluline” ja veel lõpmatu arv teisi sõnesid. Metamärgiga $ on võimalik kontrollida, kas regulaaravaldisele vastav alamsõne lõpetab sõne. Näiteks regulaaravaldisega “a.i$” on vastavuses “abi”, aga “abiks” ei ole.
Ülesanne
Selle ja mitmete edasiste ülesannete puhul antakse Kontrolli-nuppu vajutades reaktsioon iga vastusevariandi jaoks eraldi. Reaktsioon oleneb sellest, kas vastusevariant on õigesti märgitud/märkimata või mitte.
Järgmises ülesandes on regulaaravaldistes kasutusel mitmed erinevad metamärgid.
Ülesanne
FUNKTSIOON re.search
Funktsiooni re.match kõrval kasutatakse ka üsna sarnaselt toimivat funktsiooni re.search, mis otsib vastavust mitte ainult sõne algusest, vaid üle kogu sõne. Nii saame näiteks leida, kas sõnes leidub kolm kõrvuti olevat numbrit. Seda, kas tegemist on numbriga saab kontrollida "[0-9]" abil (vt metamärkide tabelit). Loogelistes sulgudes saame ette anda, mitu korda eelnevat sümbolit või avaldist peab olema.
import re
if re.search("[0-9]{3}", "Auto registreerimisnumbriga 007PYT lähenes"):
print("sisaldub")
else:
print("ei sisaldu")
Tegelikult võiksime "[0-9]" asemel kirjutada "[0123456789]", sest seda me ju otsime: kas sõnes leidub selline koht, kus on järjest kirjutatud kolm numbrit ehk sümbolit, millest igaüks võib olla kas 0, 1, 2, 3, 4, 5, 6, 7, 8 või 9.
Ülesanne
Järgmises näites püüame leida, kas teates sisaldub korvpalli seis. Esialgu eeldame lihtsustatult, et kummalgi võistkonnal on kahekohaline skoor.
import re
korvpalli_seis = "[0-9]{2}:[0-9]{2}"
teade = "Esimene korvpallimäng olümpiamängudel toimus 1. augustil 1936. aastal. Eesti võitis Prantsusmaa 34:29."
if re.search(korvpalli_seis, teade):
print("sisaldab ilmselt korvpalliseisu")
else:
print("ei sisalda ilmselt korvpalliseisu")
Tegelikult võib korvpallis skoor olla ka kolmekohaline ja mängu algusjärgus muidugi ka ühekohaline. Seda kirjeldab paremini regulaaravaldis "[0-9][0-9]?[0-9]?:[0-9][0-9]?[0-9]?".
VEEL (JA PÄRIS ELULISI) VARIANTE
Nüüd vaatame elulist, kuid pisut keerulisemat näidet geneetika valdkonnast. See on eelkõige mõeldud just huvitavaks ja harivaks lugemiseks - ülesannetes neid teadmisi ei nõuta.
DNA koosneb nukleotiididest adeniin (A), guaniin (G), tsütosiin (C) ja tümiin (T). Lühendite abil saame DNA ahela lõigu kirja panna näiteks sõnena, mis koosneb tähtedest A, G, C ja T. DNA ahelas paiknevad geenid, millest transkripteeritakse RNA molekule ning millest omakorda moodustatakse aminohapetest koosnevaid proteiine, mis on vajalikud meie elutegevuseks ja panevad paika, kuidas meie keha töötab. Mitte kogu DNA ahel ei koosne geenidest, vaid geenid asuvad teatud positsioonidel DNA ahelas. Selleks, et teada saada, millal mõni geen algab või lõppeb, on olemas algus- ja lõpukoodonid - kindlad järjestused, mis annavad teada, et selle koha pealt tuleb geeni lugema hakata või lugemine lõpetada. Alguskoodoniks on järjestus ATG ning lõpukoodoneid on lausa mitu: TGA, TAG ja TAA.
Kui tahame näiteks leida, kas mõnel DNA lõigul asub potentsiaalne geen, peaksime kontrollima, kas leidub selline järjestus, mis algab kolmikuga ATG ning lõppeb kolmikuga TGA, TAG või TAA. Lisaks peab nende kahe kolmiku vahele jääma kolmega jaguv arv nukleotiide. Kolmega jaguvust on vaja kontrollida seetõttu, et ühele aminohappele vastab nukleotiidide kolmik ning kui nukleotiidide arv ei jagu kolmega, siis ei saa sellisest järjestusest teha proteiini. Järgmine näide demonstreerib, kuidas teha kindlaks, kas antud DNA lõigus on mõni potentsiaalne geen:
import re
dna_lõik = "AAGGCTAGACTGGCTTAGCCTCCCAGCCTACATCTTTCTCCCATGCTGGATGCTTCCTGCCCTCAAACATCAGGCTCCATGTTTTTCAGCTTTGGGACTCACAGTGGCTTCCTTGCTCCTCAGTTTACAGACAGCCTATTGTGGGACCTTGTGATTGTGTGAGTTAATACTACTTAATAAACTCCCATATGTAGGTGTGTGTATATGTCTTATTAGTTCTATCCCTCTAGAGAACCCTGACTGATACACCTGCTCTAACAGGCTGTTGAATGCCCATGGCTTTTCCAGGTGCAGGGCATAAGCTGCCAGTGGATATACTATTATTGGGTCTACAAGGTGATGGCCCACTTCTCACAGCTCCATTAGGCAGTGTTCCGGTGAAGGCTCTGTGTGGGGACTTGAACCCTTCATTTTCCCTTGATACTACCCTAGAAGTTATCTGTGGGGGTTCTGTTTCTGAAGTAGGCTTCTGCCTGGACACCCAGGCTTTTCATACATCCTTGGAAATCTACGCAGAAGGTGCCAAGACTTATTCATTCTTACACTCTGTGCACTTGCAGGCTTAACAGTACATAGAAGACACCAAGGCTTATGGCAGTTTGTACTTTCCTGAGCAGCAACATGAAGAGTATGTGGGAGGTTTTGAGCCAAGGCTGGAGCCGGAGTTGCCTAGACGTGGGGAACAGTATTTCAAGACTACACAGGGCAGCAAAGCCCTGGGCCTGGCCATGGAAACCATTGTTTCCTACTAGGCCTCAGGACTTGTCATGGAAGGGGCTGCCATGAAGTCTCTGAAATGCTTTCCAAGCATCCTCCTCATTGTCTTGGCTATCAGCACTTGGCTCCCTTTTTAGTCATGCATACTTCTCTAGCAAGTCGTTTCTTCACAGCCTGCCTGAATTCCTCTCCCCAGAAAGGTTTTTTTCTTCCTCTGCCACATGGCCAGGCTGCAAATTTTGAAAACTTTTGTTGTCTGCTTCCCTTTTAAATATAGGTTCTAACTTTAAGTCATTCCTTTGTTCCTAAATCTGAGCATAGGTTGTTAGAAGCTGCCAGGCCACATTTTGAATGCTTTTCTGCTTAGAAATTTCCTCCACCAGGTACCCTAAATCATCCCCATGAAGTTCAAACTTCCAAAGATCCTCAGGGCATGAACAGAATGCATCCAGGGTTTTTACTAAGGTATAACACACATGACTTTTGCTCCAGCTCTCAATAAGTTATTTCTATCTGAGACCTCAGCAGCCTGGAATTCGGTCTCCGTATCACTATAAGTATTTTGATCACAACCATTTAACCAGTCTCTAAGACATTTCTAACTTTTCCTCATCTTCCTGTCTTCTTCAAAGCTCTCCAAACTCTTTCAAACATAGCTCATTACCCAGTTCCAAAGCTGCTTCCACATTTTCAGATATCTTTATAGCAAAGGCTCGATCCTCAATACCAATTTTCTTTACTAGACTGCTCTTGTATTTCTATGAAGAAATATCTGAGAGAGGGTAATTTATAAAGAAAAGAGGTTTAATTGGCTCCCAGTACTGCAGGATTTACAGAAATAATGATACTGGCATCTGCCTGGCTTCTTGGGAGGTCTCAGGCAACTTACAATCACGGTAGAAGGTGAAGAGAGAGCAGGCATGCCACTTGGTGAAAGCAGGAGCGTGAGAGAGACAGTGGGTG"
leidub = re.search("ATG(...)+T((GA)|(AG)|(AA))", dna_lõik)
if leidub:
print("Antud DNA lõigus asub vähemalt üks potentsiaalne geen.")
else:
print("Antud DNA lõigus ei asu ühtegi potentsiaalset geeni.")
Regulaaravaldiste abil saab näiteks üles leida kõik potentsiaalsed geenid ja nende asukohad DNA ahelal ning edasi saavad geenitehnoloogid ja bioinformaatikud uurida, millise funktsiooni eest erinevad geenid vastutavad.
Püüame nüüd ka kasutatud regulaaravaldisest ATG(...)+T((GA)|(AG)|(AA)) detailsemalt aru saada.
- "ATG" regulaaravaldise alguses näitab, et otsitakse alamsõne, mis algab tähtedega "ATG".
- (...) tähistab kolme suvalist märki. Pluss ("+") pärast seda ütleb, et eelnevat (antud juhul siis kolme märki) peab olema 1 või rohkem korda. See tagab, et algus- ja lõpukoodoni vahele jääb kolmega jaguv arv nukleotiide.
- Otsitav alamsõne peab lõppema kolmikuga "TGA", "TAG" või "TAA". See tagatakse regulaaravaldise lõpuga
T((GA)|(AG)|(AA)), kus märk | tähendab "või". Seega võib lõpukoodon olla kas "TGA", "TAG" või "TAA".
Ülesanne
Lõpetuseks võib veel öelda seda, et regulaaravaldist algkursustes tavaliselt ei käsitleta, aga loodetavasti olete nõus, et tegemist on huvitava ja kasuliku teemaga.
| < eelmine | 6. OSA sisukord | järgmine > |