Je leest:

26 letters onder 9 toetsen

26 letters onder 9 toetsen

Auteur:

Sms-software, waarmee je voor elke letter maar één toets hoeft in te drukken op je mobiel, is waarschijnlijk de meest gebruikte toepassing van taaltechnologie. Naar schatting 4 miljard telefoons maken gebruik van T9 en vergelijkbare software. Hoe werkt het eigenlijk precies? En kan het niet nóg makkelijker?

Je staat er misschien niet bij stil, maar elke keer als je een sms’je verstuurt, maak je gebruik van taaltechnologie. Als je bijvoorbeeld ‘aardig’ wilt sms’en, typ je feitelijk alleen ‘227344’. Toch weet je telefoon dat je ‘aardig’ bedoelt, en niet ‘barfig’ of ‘acpehi’. Halverwege de jaren 90 moest je nog met de zogenaamde multi-tap methode elke knop op je telefoon net zo vaak indrukken totdat de juiste letter in het schermpje stond. Nu is één knop per letter voldoende en weet de software in je telefoon meestal precies wat je bedoelt.

Trie

Dit staaltje taaltechnologie werkt op de meeste telefoons onder de naam T9, wat staat voor text on 9 keys. Antal van den Bosch, hoogleraar Geheugen, Taal en Betekenis aan de Universiteit van Tilburg, legt uit dat de sms-software beschikt over een soort woordenlijst, een lexicon genaamd. “In zo’n lexicon staan de woorden die het meest voorkomen in een taal. Dit aantal kan oplopen tot zo’n 300 duizend.” Met dit lexicon kan de software razendsnel opzoeken welk woord bij een bepaalde toetsencombinatie hoort.

Small
Donald Knuth heeft de trie-structuur uitgebreid beschreven in zijn serie boeken ‘The Art of Computer Programming’. Voor veel computerprogrammeurs geldt deze serie als een soort bijbel.

Hoe gaat de software hierbij te werk? Simpelweg de hele lijst met woorden langslopen zou niet bepaald efficiënt zijn. Als je mazzel hebt staat het woord aan het begin van de lijst, maar als je pech hebt staat het woord achteraan en moet je eerst de hele lijst door. Dat kost te veel tijd. “Eigenlijk moet je helemaal niet denken in woorden, maar in cijfersequenties. Dat is immers wat je binnenkrijgt, ” aldus Van den Bosch. Het T9-algoritme werkt dan ook met een trie, een datastructuur in een boomvorm.

Voordelen

In de bovenste knoop van de trie staan nog alle woorden uit het lexicon op actief. Vanaf daar lopen 9 takken naar beneden: voor elke letterknop op de telefoon ééntje. Stel dat je de 2 intypt, dan blijven alleen de woorden die beginnen met een a, een b of een c actief. Vanaf die tak lopen vervolgens weer 9 takken naar beneden, waarmee ook de opties voor de tweede letter worden teruggebracht naar 3 of 4. Dit proces gaat net zo lang door tot het hele woord is ingetypt óf tot de software al eerder zeker weet welk woord het moet zijn. Hij doet dan een suggestie, die de gebruiker waarschijnlijk weer een paar klikken bespaart.

Large
Een trie-structuur biedt razendsnelle toegang tot het volledige lexicon van enkele honderdduizenden woorden. Met elke nieuwe key press vallen weer een hoop mogelijke woorden af. Hierboven zie je alleen nog de mogelijke eerste twee letters van een woord. De trie-structuur is niet alleen sneller, maar ook efficiënter: het opslaan van het hele lexicon in een trie kost al snel 95% minder ruimte dan in een woordenlijst.

“Het T9-algoritme biedt dus twee voordelen ten opzichte van het originele sms’en”, aldus Van den Bosch. “Ten eerste bespaar je al key presses met T9 ten opzichte van de multi-tap methode en vervolgens ook nog eens doordat het uniciteitspunt bereikt wordt.” Dat uniciteitspunt is het moment dat de software suggereert hoe het woord kan worden afgemaakt. Met één druk op de knop worden dan automatisch alle resterende letters ingevuld.

Small

Hoe sms’t een Chinees?

Wij hebben het nog relatief eenvoudig met onze 26 letters. Chinezen moeten met de 9 knopjes op hun mobiel duizenden karakters kunnen maken. Hoe gaat dat? Chinezen sms’en meestal in het pinyin, een schrijfmethode waarbij de klanken van de Chinese karakters in ons Latijnse alfabet worden weergegeven. Op het beeldschermpje van de telefoon verschijnen, via een T9-algoritme, wel gewoon de karakters. De sms’er kan kiezen welke hij bedoelt.

Context

Zoals je zelf waarschijnlijk ook al gemerkt hebt, werkt T9 niet altijd even goed. Hoe komt dit? Ten eerste kan dat liggen aan de samenstelling van het lexicon. “Die lexicons zijn gebaseerd op woordfrequentielijsten van een taal”, legt Van den Bosch uit. “Deze lijsten zijn vaak gebaseerd op formeel taalgebruik, waardoor ze eigenlijk heel slecht zijn voor de taal die in sms’jes vaak gebruikt wordt. Typische informele woorden staan er vaak niet in.” De laatste jaren is dit flink verbeterd, maar het blijft de vraag hoe zo’n lexicon er nu het beste uit kan zien. “Er zijn daarom ook varianten op T9 die gepersonaliseerd kunnen worden, of dit uit zichzelf doen. Zo’n systeem neemt alle woorden die de gebruiker typt op in zijn lexicon. Ook namen van vrienden en familieleden zal hij dan kunnen suggereren.”

Small
h3. T9-verwarring Het T9-algoritme kan er soms flink naast zitten. De onbedoelde woorden kunnen voor veel narigheid, maar ook voor veel plezier zorgen. Onze Taal verzamelt voorbeelden van T9-verwarring op haar website.

Een andere oorzaak van verkeerde voorspellingen van T9 is het ontbreken van enige taalkennis bij het systeem. “Na elke spatie begint het T9-algoritme opnieuw bovenaan in de boomstructuur”, legt Van Den Bosch uit. “Dat hoeft natuurlijk niet, want vaak is al op basis van het voorgaande woord met enige zekerheid te voorspellen wat het volgende woord zal zijn. Het team van Van den Bosch heeft dan ook een systeem ontwikkeld dat niet na elke spatie de voorgaande boom wist, maar er juist op voortborduurt.

Twitter

Het nieuwe systeem neemt de voorgaande context mee bij het bepalen van het vervolg van de lettersequentie. Het werkt daarom niet meer met een lexicon, maar met een corpus, een groot bestand aan lopende taal. Dit specifieke corpus bestaat uit afgevangen twitter-feeds; dat lijkt erg veel op sms-taal. “Ons systeem kijkt zo ver mogelijk terug om zo zeker mogelijk te zijn van het vervolg”, aldus Van den Bosch. “We zoeken naar de langste lettersequentie die ook in het corpus voorkomt: hoe langer, hoe beter en sneller de voorspelling."

Het systeem dat Van den Bosch ontwikkelde komt sneller met de juiste suggestie dan het T9-algoritme: je hebt minder key presses nodig dan T9 voor precies dezelfde tekst. Waarom werken onze mobieltjes dan nog niet met dit nieuwe systeem? “We hebben ons algoritme geprobeerd te patenteren, maar er blijken al verschillende vergelijkbare patenten te bestaan voor algoritmes die de voorgaande lettersequentie meenemen”, legt Van den Bosch uit. “Bijna alle telefoonmakers bezitten dergelijke patenten. Ze zijn er dus duidelijk mee bezig om deze techniek in hun mobiele telefoon in te bouwen.”

Small

iPhone toetsenbord

De iPhone heeft een speciaal toetsenbordinterface voor zijn touchscreen. De toetsjes op dit toetsenbord zijn echter zo klein dat je er makkelijk naast zit. Apple werkt daarom met een vergelijkbare methode als het T9-algoritme. Als je bijvoorbeeld ‘halli’ typt, maakt hij er vanzelf ‘hallo’ van. Zoals T9-software weet dat een ‘5’ voor een ‘j’, een ‘k’ of een ‘l’ kan staan, zo weet de iPhone dat een ‘i’ ook een ‘o’, een ‘k’ of een ‘u’ kan zijn. Het enige nadeel hiervan is (net als bij T9) dat hij elk onbekend woord zal proberen om te vormen tot een woord uit zijn lexicon. Ook als je dat helemaal niet wilt.

Geheugen

De enige belemmerende factor lijkt vooralsnog de geheugencapaciteit van mobieltjes. “Als de boom maar blijft vertakken kost dat veel meer geheugen. Met de huidige mogelijkheden past het nieuwe algoritme simpelweg nog niet in het geheugen dat in mobiele telefoons zit”, aldus Van den Bosch. Op de nieuwste laptops en desktops –die beschikken over een groter werkgeheugen dan een mobiele telefoon- vindt je soms wel al context-gevoelige spellingscorrectie. Het lijkt er dus op dat we geduldig zullen moeten wachten tot de geheugencapaciteit van mobieltjes groot genoeg is voor we Van den Bosch’ algoritme kunnen gebruiken. Tot die tijd: altijd goed je sms’je nalezen voor je op ‘versturen’ klikt.

Lees ook:

Oeps: Onbekende tag `feed’ met attributen {"url"=>"http://www.kennislink.nl/kernwoorden/stevin.atom", “max”=>"3", “detail”=>"normaal"}

Dit artikel is een publicatie van NEMO Kennislink.
© NEMO Kennislink, sommige rechten voorbehouden
Dit artikel publiceerde NEMO Kennislink op 19 mei 2010

Discussieer mee

Vragen, opmerkingen of bijdragen over dit artikel of het onderwerp? Neem deel aan de discussie.

LEES EN DRAAG BIJ AAN DE DISCUSSIE