Sinds een jaartje heb ik de website http://itypemachine.azurewebsites.net, een website waar je gratis je klaviervaardigheid kan inoefenen. Voorlopig is er maar één type oefening nl. je krijgt een tekst te zien en je moet die overtikken. Foute aanslagen worden gedecteerd en je kan niet verder gaan tot je de juiste aanslagen hebt uitgevoerd. Ik wil daar nu enkele types oefeningen aan toevoegen. Eén is dat men een tekst kan overtikken en dat die tekst ACHTERAF gecorrigeerd wordt.
Ik ben op zoek naar een algoritme om dit efficiënt te doen. Opgelet … fouten kan erg divers zijn. Gaande van “een K ingetikt ipv een L, enkele karakters teveel ingetikt, enkele karakters te weinig ingetikt, een woord dubbel ingetikt, enz …”. Wie heeft tips, ideeën, bedenkingen, …? dieter@depuydt.eu
Ik denk meteen aan een datastructuur waarbij je een mapping maakt voor elk woord uit het groene boekje, bv. map[A][P][P][E][L] = true, voor elk woord uit het groene boekje. Dit moet je echter maar eenmalig doen, opslaan, en kun je vervolgens vanuit je programma ophalen wanneer nodig.
Vervolgens maak je een mapping met voor elke toets op het toetsenbord, de meest dichtbijzijnde toetsen. bv: key[D] = { {EFCS},{ZRVX},{AQWTGB} , … }
Als je je tekst doorloopt, controleer je voor elk woord dat niet begint met hoofdletter (= naam plaats stad of land) of map[C1][C2][C3][C4]… true is, en in het groene boekje voorkomt zeg maar. Als dit niet het geval is, controleer je voor elk karakter C1 … CN of een vervanging met één van de dichtsbijzijnde key[C1] karakters (dichtste karakters op het toetsenbord) wél voorkomt in het groene boekje.
Zo krijg je een lijst met mogelijke correcties. Je kunt hier verder in gaan, door bijvoorbeeld de zin uit de tekst te nemen en te proberen zoeken via google. Indien de exacte tekst meer dan 1 maal in de broncode van de zoekpagina voorkomt, wilt dat zeggen dat iemand anders ooit deze tekst ook heeft getypt en online heeft geplaatst. Dit verhoogt de kans dat de zin steek houdt.
Vervolgens krijg je een lijst met de correcties die steek houden. Als je verder wilt gaan zul je artificiële intelligentie moeten gebruiken om het onderwerp van de tekst te herkennen en zo de juiste mogelijkheid in zijn context te kiezen.
Qua grammaticale fouten, zou ik ook in de richting van google zoeken. Zoek de zin op, kijk welke referentie het hoogst staat, waarin alle woorden voorkomen die je opzocht, en vervang jouw zin door de gesuggereerde zin.
Dit is hoe ik het in een eerste opzicht zou aanpakken 🙂
Dag Dieter,
Ik heb jaren geleden een dergelijk algoritme ontwikkeld. Het werd toegepast in de populaire Typ-Top-software van Uitgeverij De Boeck (voorheen Standaard Educatieve Uitgeverij), dat in heel wat scholen in Vlaanderen gebruikt werd en nog steeds wordt. Zoals je wellicht al begrepen hebt is het niet eenvoudig om zo’n algoritme te maken, omdat er heel wat verschillende soorten fouten gemaakt kunnen worden. Achteraf fouten opsporen is heel andere koek dan een foute aanslag detecteren terwijl de gebruiker (leerling) aan het typen is. Mogelijke fouten zijn bijvoorbeeld twee letters omwisselen, letters vergeten of extra letters toevoegen, maar ook woorden of zelfs een hele regel overslaan of dubbel typen, hoofletters typen in plaats van kleine letters of omgekeerd, twee woorden aan elkaar plakken of extra spaties typen waar het niet moet, etc.
Een algoritme maken dat al die gevallen (en alle mogelijke combinaties ervan) feilloos kan herkennen en nooit faalt, is een bijzonder grote uitdaging. Het spreekt dan ook vanzelf dat ik het algoritme dat in de Typ-Top-software zit, niet zomaar mag prijsgeven. Dat zouden ze bij de uitgeverij van Typ-Top niet kunnen appreciëren.
Maar ik kan je wel enkele tips geven voor het geval je zelf zoiets zou willen programmeren. Eerst en vooral moet je goed nadenken over wat alle mogelijke fouten zijn die kunnen voorkomen en die je wilt kunnen detecteren. Hierboven heb ik ze al grotendeels opgesomd. Je weet wellicht ook dat er een standaard-algoritme bestaat om twee teksten met elkaar te vergelijken: het zogenaamde diff-algoritme (zie o.a. https://en.wikipedia.org/wiki/Diff_utility). Je kunt diff gebruiken om de originele opgave te vergelijken met de tekst die de gebruiker getypt heeft. Maar met een simpele diff ben je er nog lang niet. Je zult de output van diff met een eigen algoritme moeten toetsen aan alle hogergenoemde foutscenario’s. Diff vertelt je waar er tekst is weggelaten of toegevoegd, maar zult zelf moeten zien uit te vissen waar zo’n weglating of toevoeging eigenlijk neerkomt om bijvoorbeeld een omwisseling van letters of woorden, een verkeerd gebruik van de hooflettertoets, het aaneenplakken van woorden etc.
Ik betwijfel dat je een kant-en-klaar algoritme op het internet zult vinden. Ik wens je dus alvast veel succes toe met het programmeren. Wanneer je ermee klaar bent, zal ik het graag eens aan een kritische test onderwerpen…