Hoewel het woord computer letterlijk rekenaar betekent, wordt de computer tegenwoordig meer en meer gebruikt voor toepassingen die met teksten te maken hebben. Iedereen is wel bekend met tekstverwerking. Een andere belangrijke toepassing, waar we het deze keer over willen hebben, is het zoeken in teksten.

De computer is hier bijzonder bedreven in. Zonder moeite kunnen duizenden bladzijdes tekst (in elektronische vorm) doorzocht worden. Soms ben je daarbij geinteresseerd in het vinden van bepaalde woorden, maar meestal in iets algemenere patronen.

Voorbeeld: herken je eigen naam

Een simpel voorbeeld betreft de mogelijkheid om naar je eigen naam te zoeken. Mijn naam is Gertjan van Noord. Sommige mensen schrijven echter Gert-Jan. Ook worden niet altijd hoofdletters gebruikt. Een reguliere expressie kun je gebruiken om een patroon te definieren. Hier is een voorbeeld:

[g,e,r,t,j,a,n]

Spreek uit: een g gevolgd door een e, gevolgd door een r, gevolgd door een t, gevolgd door een j, gevolgd door een a, gevolgd door een n. Deze expressie matcht slechts met gertjan. In plaats van de g kunnen we ook een G toestaan. In zo'n geval schrijven we {g,G} (spreek uit: g of G). Ook de j kan als hoofdletter worden geschreven. We krijgen dus:

[{G,g},e,r,t,{j,J},a,n]

Deze expressie matcht dus met vier verschillende vormen: gertjan, gertJan, Gertjan en GertJan. Tenslotte kunnen we aangeven dat na de r eventueel een tussenstreepje mogelijk is. Om aan te geven dat het streepje wel mogelijk is, maar niet verplicht, gebruiken we de ^.

[{G,g},e,r,t,'-'^,{j,J},a,n]

Met hoeveel verschillende vormen matcht deze expressie? Het streepje zelf moet tussen aanhalingstekens worden geplaatst. Dit is noodzakelijk omdat in zo'n reguliere expressie sommige letters een speciale betekenis hebben. Om nu duidelijk te maken dat je een letter letterlijk bedoelt, kun je de aanhalingstekens gebruiken. Als je bijvoorbeeld een spatie wilt invoeren als onderdeel van een patroon, dan zijn zulke aanhalingstekens ook nodig:

[{G,g},e,r,t,{'-',' '}^,{j,J},a,n]

Wat staat hier nu? Een G of een g, gevolgd door een e, gevolgd door een r, gevolgd door een t, eventueel gevolgd door een spatie of een streepje, gevolgd door een j of een J, gevolgd door een a, gevolgd door een n. Dit match nu bijvoorbeeld ook met gert jan.

Wanneer de computer zo'n reguliere expressie leest, dan wordt een klein computerprogrammaatje gebouwd. Zo'n programmaatje kunnen we als volgt weergeven in de vorm van een plaatje. Zo'n plaatje wordt vaak een transitiediagram genoemd.

De computer start steeds in de groene begintoestand. Om te checken of een gegeven input aan het patroon voldoet moet de eerstvolgende letter van de input overeenkomen met de letter die bij een pijl hoort. In dat geval kom je in een volgende toestand terecht. Zo werkt de computer de input door. Wanneer de input leeg is, en de computer is in een rode eindtoestand terecht gekomen, dan voldeed de input aan het patroon. Zodra je in een toestand terecht bent gekomen waaruit geen pijlen vertrekken die met je input overeenkomen, dan voldeed je input niet.

De practicumopdrachten bij dit college maken gebruik van een programma dat automatisch reguliere expressies omzet in transitiediagrammen. Bovendien wordt van een aantal verschillende inputs vastgesteld of ze wel of niet aan het patroon voldoen.

Opdracht 1

Schrijf een reguliere expressie voor je eigen voornaam en enkele voor-de-hand-liggende spellingvarianten van je voornaam. Breid het voorbeeld uit met je achternaam. Laat ook toe dat alleen je voorletter(s) gebruikt worden.

Voorbeeld: herken postcodes

Een ander voorbeeld betreft het herkennen van postcodes. Je kunt je voorstellen dat de PTT belangstelling heeft om postcodes automatisch te herkennen. Postcodes bestaan uit vier cijfers, gevolgd door twee hoofdletters. Bij dit voorbeeld kunnen we gebruik maken van een handigheidje. In plaats van

{0,1,2,3,4,5,6,7,8,9}

kunnen we de notatie 0..9 gebruiken. Op dezelfde manier kunnen we schrijven a..z om aan te geven dat op een positie een (kleine) letter voorkomt. En A..Z zijn dan natuurlijk de hoofdletters. Een postcode kan nu worden gedefinieerd als:

[0..9,0..9,0..9,0..9,' ',A..Z,A..Z]

Deze definitie is een beeje streng. Wanneer iemand wat meer ruimte openlaat tussen de cijfers en de letters dan wordt de postcode niet geaccepteerd. Om aan te geven dat iets 1 keer of vaker mag voorkomen, bestaat de + notatie:

[0..9,0..9,0..9,0..9,' '+,{A..Z,a..z},{A..Z,a..z}]

Hier staat dus: vier cijfers, gevolgd door één of meer spaties, gevolgd door een kleine letter of een hoofdletter gevolgd door een kleine letter of een hoofdletter. Naast de + notatie bestaat ook nog de * notatie om aan te geven dat iets 0 keer of vaker mag voorkomen.

Opdracht 2

Schrijf een reguliere expressie voor (Nederlandse) nummerborden.

Regels die patronen bevatten

Heel vaak ben je natuurlijk geinteresseerd in regels (of documenten) die een bepaald patroon bevatten. In die gevallen kunnen we de reguliere expressie zo definieren dat alle inputs geaccepteerd worden die dat patroon bevatten. De $ notatie kan hiervoor gebruikt worden:

$ [{G,g},e,r,t,{'-',' '}^,{j,J},a,n]

Deze expressie laat alle inputs toe waarin ergens mijn naam voorkomt!

Voorbeeld: afkortingen

Het is soms ook belangrijk om in een tekst de gebruikte afkortingen te kunnen herkennen. Een tekst naar spraak systeem is een systeem dat in staat is geschreven teksten automatisch uit te spreken. Hierbij is het herkennen van afkortingen cruciaal, omdat die vaak heel anders moeten worden uitgesproken. Bijvoorbeeld, indien in de tekst het woord EEG voorkomt, dan moet de uitspraak luiden ee - ee - gee, en natuurlijk niet eeg. Hetzelfde geldt voor een afkorting zoals t.a.v. dat in zo'n systeem wellicht het liefst wordt uitgesproken als ten aanzien van, en in ieder geval niet op zo'n manier dat het rijmt op daf. Reguliere expressies blijken ook hier cruciaal te zijn. Je kunt met reguliere expressies immers precies definieren welke lettercombinaties tot de afkortingen gerekend dienen te worden. In een eerste poging zou je als volgt te werk kunnen gaan. Een afkorting is een woord dat geheel uit hoofdletters bestaat:

A..Z+

of een punt bevat:

$ '.'

De twee mogelijkheden samen leveren dan:

{ A..Z+ , $ '.' }

Opdracht 3

Definieer een reguliere expressie om afkortingen te herkennen. Probeer ervoor te zorgen dat voorbeelden zoals de volgende wel geaccepteerd worden:

t.a.v.                       KPN
NAVO                         CIA
KGB                          mr.
jl.                          C.I.D.
o.a.                         PSP'er
NOSstudio                    NAVO-generaals
N.O.-I                       N.H.M.-tarieven
SALT-perscentrum             oud-ASVA-voorzitter
N.S.B.ers                    S.S.'ers

Maar tegelijkertijd is het de bedoeling dat voorbeelden zoals deze niet geaccepteerd worden:

Gertjan                      boterhammenzakje
15.30                        4.49.6
...                          U

Extra Opdrachten

1. Bij de volgende opdrachten geldt steeds dat een reguliere expressie word gevraagd die alleen inputs herkent waarvoor geldt dat ze gebruik maken van de letters a en b, en waarvoor bovendien geldt:
   1. dat het totaal aantal letters even zijn.
   2. dat het aantal a's even is.
   3. dat het aantal a's even is, en ook het aantal b's even is.
   4. dat precies éénmaal drie a's achter elkaar optreden.
   5. elke a wordt voorafgegaan door een b
   6. elke a wordt voorafgegaan door een a of een b
   7. dat aantal a's modulo 3 is gelijk aan aantal b's modulo 3 (moeilijk).
2. De & notatie kan worden gebruikt om twee reguliere expressies te combineren. Een input voldoet pas aan de reguliere expressie E₁ & E₂ wanneer de input zowel aan expressie E₁ als aan E₂ voldoet. Voorbeeld:

   [a,a]* & [a,a,a]*
   

   Links van het & symbool worden alle inputs geaccepteerd met een aantal a's dat deelbaar is door twee. Rechts worden ook inputs geaccepteerd, maar alleen als het aantal deelbaar is door drie. Gecombineerd met de intersectie operator worden alleen inputs bestaande uit a's geaccepteerd als het aantal a's deelbaar is door zes.

   Welke patronen worden herkend door de reguliere expressies van:

   1. het voorbeeld Gevorderd 1
   2. het voorbeeld Gevorderd 2
3. De laatste opdracht luidt: definieer een reguliere expressie die (Nederlandse) namen herkent. Dit is in het algemeen een bijzonder lastig probleem. Probeer eens te kijken hoever je kunt komen. De volgende lijst is een lijst namen die ik met de hand uit een aantal teletekstberichten van de afgelopen week heb verzameld. Deze kun je gebruiken om je expressie te testen:

   Borst                        Mendes de Leon
   Zalm                         Job Cohen
   Cohen                        Mordaunt
   Hans van Dam                 Scholten van Aschat
   Saskia Temmink               DICK JASPERS 
   Polychronopoulos             GERWIN VALENTIJN 
   R. Ceulemans                 LOUIS HAVERMANS
   John v.d.Wiel                Van Happen
   Peter Paul de Vrind          Ton van Happen
   De Vrind                     Marc-Kevin Göllner
   

   Het probleem is natuurlijk om er voor te zorgen dan alleen deze inputs te accepteren. Hoeveel regels van het volgende Teletekst bericht bevatten namen volgens jouw reguliere expressie?

   Debat Veiligheidsraad over Kosovo
   
   VERENIGDE NATIES De VN-Veiligheidsraad 
   komt vandaag in spoedzitting bijeen ter
   bespreking van de situatie in Kosovo. De
   aanleiding is een bloedbad dat Serviers
   dit weekeinde hebben aangericht onder
   burgers in het dorp Gornje Obrinje. 
   
   Verslaggevers hebben daar 18 verminkte 
   lijken aangetroffen. Het bloedbad lijkt 
   een vergelding voor de dood van zeven
   Servische politiemannen,die vorige week
   in het gebied bij een bomaanslag om het
   leven kwamen.
   
   De NAVO beslist begin volgende week 
   over een mogelijk militair optreden 
   tegen Joegoslavie. Rusland heeft daar al
   op voorhand tegen gewaarschuwd.
   

   Een voorbeeld dat het nuttig kan zijn om namen in teksten te herkennen is automatische vertaling. Niet alleen is het niet nodig om namen te vertalen, het is bovendien fout. Kortgeleden liet ik (voor de aardigheid) mijn homepage van het Engels naar het Portugees vertalen, met behulp van een automatisch vertaalsysteem. Mijn naam werd in het Portugees Gertjan camionete Noord, omdat van immers het Engelse woord voor vrachtwagen is!

---

Informatiekunde aan de RuG

Informatiekunde onderzoekt de communicatie- en informatieprocessen bij organisaties en individuen, en de rol die ICT daarin speelt.

De informatiekunde op de RuG legt een bijzondere nadruk op talige informatie. Het onderzoek en onderwijs richt zich daarom vooral op ICT in combinatie met taal, tekst en communicatie. De Groninger informatiekunde bevindt zich daarmee op het snijvlak tussen de traditionele letterenstudies (taal, cultuur en geschiedenis) en de informatie- en communicatietechnologie.

ICT heeft de wereld van communicatie diep veranderd. De productie, redactie, publicatie, revisie, vertaling, distributie en receptie van teksten geschiedt in toenemende mate door middel van ICT. Deze processen vergen allemaal de analyse van taal en teksten, om te weten hoe men in teksten naar informatie kan zoeken, hoe men teksten kan representeren, sorteren, comprimeren, versturen, en opslaan. Verder maakt ICT het steeds makkelijker om naast tekstuele boodschappen ook grafisch, symbolisch, geanimeerd, en akoestisch materiaal te gebruiken en met elkaar te combineren.

Omdat de informatiekunde in Groningen gericht is op talige informatie, en de automatische verwerking daarvan, is de computationele taalkunde een voorname wetenschappelijke basis voor het onderzoek. De computationele taalkunde ambieert om inzichten uit de taalkunde en de informatica te combineren, om inzicht te krijgen in de mogelijkheden om natuurlijke taal automatisch te verwerken. De communicatiekunde leert ons hoe communicatie (succesvol) verloopt, en biedt wetenschappelijke hulpmiddelen om communicatieve systemen te ontwerpen, implementeren en evalueren. De manier waarop het onderzoek en onderwijs in de informatiekunde in Groningen gestalte krijgt kenmerkt zich door de combinatie van wetenschappelijke interesse in algemene onderzoeksvragen met de interesse voor de implementatie van (deel-)oplossingen voor concrete praktische problemen. Dit leidt ertoe dat behoorlijke eisen worden gesteld aan programeervaardigheden en kennis van de methodologische aspecten van experimenteel onderzoek.

Postbus 716, 9700 AS Groningen; (050) 3635974; www.let.rug.nl/alfa; bosveld@let.rug.nl