Papers we love: Regular Expression Search Algorithm

 
15 februari 2017

Regular expressions zijn gaaf. Het zijn op het eerste gezicht obscure tekenreeksen die worden gebruikt om een patroon te definiëren wat gematcht kan worden aan een reeks tekst. Nu denk je misschien: het zoeken in tekst is toch niet zo’n ingewikkeld probleem? Helaas, dat is het wel.

Probeer het eens uit te redeneren: je hebt een lange, maar eindige reeks tekst (bijvoorbeeld een boek). Stel dat je hier nu bepaalde naam (zeg ‘Belgarath’) in wilt vinden, bijvoorbeeld die van een hoofdpersoon. Een naïve implementatie is om de gehele tekst karakter voor karakter door te lopen en deze te vergelijken met de opgegeven naam.

Maar wat gebeurt er nu als je ‘Belgarath’ of ‘belagarath’ wilt hebben? Dus met-, of zonder hoofdletter? Naïef kunnen we dit ook weer teken voor teken langslopen, en op beide manieren controleren. Zoals je al aanvoelt wordt dit een lastig en intensief probleem naarmate de expressies complexer worden.

Nu hebben alle talen een grammatica, en zijn deze talen weer hiërarchisch onder te verdelen in verschillende types. De ‘laagste’, meest gebonden variant is een zogenaamde reguliere taal, in de Chomsky hiërarchie geclassificeerd als een type 3 taal. Ik ga hier nu niet op in, maar belangrijk is dat deze talen altijd uit te drukken zijn in een finite state machine.

Een finite state machine is conceptueel een grote flowchart, waarbij er verschillende ‘states’ zijn met daaraan gebonden overgangen. Een simpel voorbeeld is een stoplicht: deze heeft drie states: rood, oranje en groen. In de basis is deze ‘rood’, wat de default start state is. Vervolgens wordt er afhankelijk van de input van sensoren en/of een timer een transitie gedaan naar groen, vervolgens nogmaals van oranje weer terug naar rood. Je kunt dus niet direct van rood naar oranje, die transitie is onmogelijk.

Inmiddels denk je misschien: stoplichten, taalclassificaties, reguliere expressies? Waar gaat dit heen? In de jaren vijftig is er al een paper geschreven die een formele definitie gaf over regular sets, wat de fundamentele basis legt voor deze finite state machines. Dit idee is uiteindelijk op een aantal manieren uitgewerkt, waarbij de meest bekende van Ken Thomspon is. Hij heeft het probleem ‘zoeken naar tekst’ uitgedrukt in het genereren van een finite state machine die wordt gebruikt om door tekst heen te zoeken. Plat gezegd: tekst wordt in de state machine ingevoerd, en er komt een lijst met ‘hits’ uit van waar deze gevonden zijn.

De bijdrage van deze paper is dan ook tweeledig: als eerste beschrijft het in een paar pagina’s een hele elegante manier om een reguliere expressie om te zetten naar een finite state machine (in IBM 7094 machine code). Deze methode is vanuit technisch en architectureel perspectief leuk om eens te lezen. Er is op een hele natuurlijke wijze een flexibele, uitbreidbare architectuur ontstaan. Het tweede sleutelaspect is wat mij betreft de integratie van de aangegeven functionaliteit in een teksteditor. Hierdoor is het ‘aan het grote publiek’ kenbaar gemaakt en heel populair geworden. Inmiddels kent bijna iedereen reguliere expressies en wordt het ontzettend veel gebruikt, zij het in een bredere maar minder pure variant dan het type besproken in de paper van deze maand.

Ik kan iedereen aanraden de paper eens te lezen. Hij is heel laagdrempelig, kort en de helft zijn ook nog visualisaties van de state machines die worden gegenereerd. De complexiteit is laag, maar de implicaties zijn groot. Deze toepassing valt onder de categorie ‘dit had je bijna zelf kunnen bedenken’, zolang je zelf ook maar de achterliggende concepten al kent. De stap van the finite state machine paper naar de reguliere expressie toepassing van Ken Thompson is daarmee een logische, maar erg belangrijke stap.

Mocht je in dit onderwerp geïnteresseerd zijn: er is ook nog een fantastisch O’Reilly boek over dit onderwerp geschreven. Die kan ik je van harte aanraden.


Over deze papers we love: binnen Sogyo hebben we de traditie dat we maandelijks een nieuwsbrief rondsturen. De nieuwsbrief gaat veel over interne feitjes, echter sinds februari 2015 verzorgd Kevin van der Vlist het topic: papers we love. Hij deelt met ons papers die interessant zijn om te lezen en ons kunnen inspireren. De topic is uitgegroeid tot een mooie verzameling die we ook graag hier willen delen.


Werken met ?
Kijk dan bij onze mogelijkheden voor zowel starters als ervaren engineers.


Categorieën: Gave Technologie