Inleiding

Of je nu je aan het schrijven bent aan je laatste nieuwe bestseller, een zoekopdracht intypt in een zoekrobot, of een mailtje verstuurt naar je favoriete (zaken?)partner, heel vaak is er de bijna goddelijke aanwezigheid van de spellingcontrole die alles ziet en ons wijst op onze fouten. Maar net zoals bij zoveel andere technologieën waar we dagelijks gebruik van maken, weten slechts weinigen hoe spellingcontrole werkt. In dit artikel gaan we in op de basisprincipes.

Een eenvoudige spellingcontrole heeft een lijst met correct gespelde woorden ter beschikking. Voor elk woord in de lijst wordt de afstand berekend met het fout gespelde woord en vervolgens de waarschijnlijkheid dat dit het bedoelde woord is. Met de meest waarschijnlijke correcties kan vervolgens verder gewerkt worden. De twee stappen, het bepalen van de afstand en het bepalen van de waarschijnlijkheid, worden hieronder wat uitgebreider toegelicht.

Afstand tussen woorden

Wanneer een mens twee al dan niet correct gespelde woorden leest in een taal die hij beheerst, voelt hij/zij ogenblikkelijk aan hoe sterk deze woorden vormelijk op elkaar lijken. “leven” lijkt beter op “lever” dan op “galblaas” , en “kompjoeter” kunnen we vrij probleemloos koppelen aan “computer”. Maar hoe kan een computeralgoritme dergelijke afstanden tussen woorden berekenen? Dit is namelijk een esentieel onderdeel bij spellingcontrole.

De spellingcontrole gaat namelijk in een lijst met correct gespelde woorden na hoe goed elk woord in de lijst lijkt op het fout gespelde woord d.m.v. het berekenen van afstanden tussen woorden. Deze lijst bevat naast de lemma’s (infinitieven, enkelvouden, etc.) ook alle afgeleide vormen zoals vervoegingen (vb. 1e persoon enkelvoud en voltooid deelwoord) en verbuigingen (vb. meervouden). Voor talen met veel geslachten en naamvallen zal deze lijst dus aanzienlijk langer worden.

Om de afstand tussen twee woorden te berekenen wordt gebruik gemaakt van een metriek. Veelal het Levenshtein algoritme, dat in 1965 door de Rus Vladimir Levenshtein voorgesteld werd. Dit algoritme telt in zijn meest eenvoudige vorm het aantal karaktermanipulaties (insert, delete en/of substitute) dat nodig is om een gegeven woord om te vormen tot een ander gegeven woord. Om het woord “kast” in het woord “kaars” om te zetten zijn bijvoorbeeld twee substituties (‘s’ -> ‘a’ en ‘t’ -> ‘r’) en één insert (+‘s’) nodig. Elk van de drie manipulatietypes kan een ander gewicht krijgen. Hoe groter het totaal gewicht van de benodigde manipulaties, hoe groter de afstand tussen de woorden zal zijn.

Verfijningen van LevenshteinEen vaak gemaakte typfout is het verwisselen van twee aaneengrenzende letters (vb. “schrjiven” i.p.v. “schrijven”). Met het standaard Levenshtein algoritme zijn twee bewerkingen nodig om een dergelijke fout te corrigeren (2 substitutes). Het Damerou–Levenshtein algoritme is een uitbreiding op Levenshtein en voegt deze verwisseling toe als vierde manipulatie, die, logischerwijs, een gewicht moet krijgen dat lager is dan dat van twee substituties. Het Levenshtein algoritme kan verder verfijnd worden zodat het verschil tussen bepaalde letters minder zwaar bestraft wordt dan andere. Ter illustratie kan een substitutie van “e” naar “ê” zeer beperkt of zelfs helemaal niet bestraft worden, een substitutie van “k” naar “c” al wat meer en een “e” naar “m” nog wat meer. Voor een franstalige ligt “clé” inderdaad dichter bij “cle” dan bij clc. Met dat laatste kan immers evengoed “clac” bedoeld worden. Wanneer we nog verder verfijnen, kunnen ook combinaties van twee (of eventueel meer) letters in rekening gebracht worden. In het Duits worden “ö”, “ä”, ü, ß veelal geschreven als “oe”, “ae”, “ue” en “ss”, en ook in het Nederlands zien we wel eens dat “y” en “ij” verwisseld en “ei” en “ij” verward worden. “Wijn” lijkt inderdaad meer op “wyn” dan op “wtjn”. Analoog worden letters vaak verdubbeld of ontdubbeld (vb. “sollicitatie” vs. “solicitatie”).

Door steeds verder te verfijnen, zoals in het grijze kader, kan een steeds accuratere heuristiek voor afstanden tussen woorden bekomen worden, wat dan weer een accuratere spellingcontrole mogelijk maakt. Daartegenover staat de toegenomen complexiteit. Als een tekst 1000 woorden bevat en een woordenlijst 100.000, dan moet het algoritme al 100.000.000 keer uitgevoerd worden, en dit bij voorkeur ongemerkt en in real-time.

Een tweede aspect bij een verfijndere metriek is het belang van een nauwkeurige bepaling van de gewichten. Dit kan gedaan worden door een set van teksten die fouten bevatten manueel te corrigeren en daarna de frequentie van verschillende types fouten automatisch te berekenen en vervolgens daaruit de gewichten af te leiden.

Waarschijnlijkheid dat woord bedoeld werd

Stel dat we een het woord “grott” vinden in een tekst. Dit woord zal niet in de lijst met correcte woorden voorkomen. De afstand met de woorden “grote”, “groot”, “grot” en “groet” kan gelijk zijn. Welk woord wordt er dus het best gekozen? Om hierover uitsluitsel te geven kan de initiële woordenlijst uitgebreid worden zodat voor elk woord ook zijn relatieve frequentie gegeven is. Daarmee bedoelen we hoe vaak het woord voorkomt in een gemiddelde (voor ons Nederlandse) tekst.

Een klein beetje statistiek voor de geïnteresseerden…We willen de waarschijnlijheid kennen dat met een fout gespeld woord w het correct gespelde woord c bedoeld werd. Dit kunnen we schrijven als P(c|w), wat volgens het theorema van Bayes gelijk is aan P(w|c)P(c)/P(w). Gezien P(w) voor elk woord c in de lijst hetzelfde is, kunnen we dit weglaten als we de meest waarschijnlijke correcties willen weten. We kijgen dus P(w|c)P(c) waarbij P(c) de relatieve frequentie van c is, en P(w|c) de waarschijnlijkheid dat w geschreven werd, terwijl c was bedoeld. P(w|c) wordt ook wel het error model genoemd en P(c) het language model. Voor P(w|c) kan de eerder geschetste (Levenshtein) afstand als benadering gebruikt worden.

De afstand tussen het correcte woord en het fout gespelde woord vermenigvuldigd met de relatieve frequentie van het correcte woord geeft de waarschijnlijheid van de correctie, zoals in het grijze kader geschetst wordt. Dit betekent dat voor een fout geschreven woord het woord met de kortste afstand niet per se het meest waarschijnlijke is.

De resterende vraag is hoe die relatieve frequentie gevonden kan worden. Hiervoor wordt een verzameling teksten ingelezen en wordt per woord geteld hoe vaak het voorkomt. Maar hoe weten we zonder onze spellingcontrole of de teksten die de spellingcontrole als invoer krijgt effectief foutloos zijn? Een mogelijke aanpak om hiermee op te gaan is het nemen van een voldoende grote en voldoende betrouwbare set van teksten als invoer en enkel die woorden te aanvaarden die meer dan X keer voorkomen. Bovendien bestaan er lijsten van veel voorkomende spelfouten (vb. “zowiezo” i.p.v. “sowieso”). De woorden in deze lijst worden uit onze lijst verwijderd.

Om de spellingcontrole nauwkeuriger te maken kan de woordfrequentielijst domeinspecifiek gemaakt worden. In de geneeskunde hanteert men inderdaad een vocabularium dat nogal verschilt van het vocabularium dat in de fotografie of ingenieurswetenschappen gebruikt wordt.

Uitbreidingen

Natuurlijk kan er nog veel meer intelligentie aan een spellingcontrole toegevoegd worden. We vermelden enkele mogelijkheden.

• Er kan rekening gehouden worden met collocaties (woordcombinaties). Moet “ziekenfors” bijvoorbeeld gecorrigeerd worden naar “ziekenzorg” of “ziekenfonds”? Indien we voor het foutgespelde woord “christelijk” vinden, zal allicht “ziekenfonds” bedoeld worden in de context van de sociale zekerheid.
• Part-of-speech tagging geeft per woord de woordsoort en kenmerken (vb. werkwoord in voltooid deelwoord). Een gekende POS tagger is Tree Tagger. Via het taggen van woorden in de omgeving van het foutgespelde woord en kennis van zinsbouw heeft de spellingcontrole meer informatie over de verwachte woordsoort. Als bijvoorbeeld een werkwoord verwacht wordt, vallen alle adjectieven en substantieven af als mogelijke kandidaten.

Conclusie

Uiteraard kan er steeds verder gegaan worden in het intelligenter maken van spellingcontrole waarbij rekening gehouden wordt met zinsontleding en contextinformatie, maar naast accuraatheid zijn ook kostenefficiëntie en performantie factoren die in rekening gebracht moeten worden. Spellingcontrole is dus niet zo eenvoudig als het misschien op het eerste zicht lijkt.

P.S. En nu maar hopen dat er niet te veel schrijffouten in dit artikel staan, want de Nederlandse spellingcorrectie werkte niet mee…