In 1951 werd James Thurber¹ door zijn vriend Joseph Mitchell² uitgedaagd om een Engels woord te vinden dat de vier opeenvolgende letters SGRA bevat. Die nacht in bed bedacht Thurber de volgende woorden:

• kissgranny: een man die gezelschap zoekt bij oudere vrouwen, voornamelijk oudere vrouwen met geld; een intrigerende man, een fortuinjager

• blessgravy: een predikant of geestelijke; een gezinshoofd; iemand die genade schenkt

• hossgrace: aangeboren of natuurlijke waardigheid, vergelijkbaar met die van een volbloedpaard

• bussgranite: letterlijk: een steenkusser; een man die tevergeefs blijft proberen om de gunst of aandacht te winnen van koude, onverschillige of wispelturige vrouwen

• tossgravel. een man die — meestal 's nachts — steentjes gooit tegen het raam van een vrouw, meestal die van een jonge maagd; vandaar ook gebruikt voor een (mannelijke) geliefde, een schatje, een vrouwenloper

Helaas staat geen enkel van deze woorden in het woordenboek. Aan welk woord dacht Mitchell dan wel?

Opgave

Een $$n$$-gram is een string (str) met $$n$$ letters. In een $$n$$-gram mogen enkel de 26 letters van het alfabet (a–z) voorkomen, dus geen spaties, leestekens of letters met diakritische tekens⁷. Gevraagd wordt:

• Schrijf een functie ngrammen waaraan twee argumenten moeten doorgegeven worden: i) een string $$s$$ (str) en ii) een getal $$n \in \mathbb{N}_0$$ (int). De functie moet een lijst (list) teruggeven met alle $$n$$-grammen van opeenvolgende letters die in $$s$$ voorkomen, opgelijst in de volgorde waarin ze in $$s$$ voorkomen.

• Schrijf een functie woordenboek waaraan twee argumenten moeten doorgegeven worden: i) de locatie van een tekstbestand (str) en ii) een getal $$n \in \mathbb{N}_0$$ (int). Het gegeven tekstbestand moet een woordenlijst bevatten waarvan elk woord op een afzonderlijke regel staat. De functie moet een dictionary (dict) teruggeven die elk $$n$$-gram dat in minstens één woord uit de woordenlijst voorkomt, afbeeldt op de verzameling (set) van woorden (str) waarin het $$n$$-gram voorkomt. Er mag geen onderscheid gemaakt worden tussen hoofdletters en kleine letters bij het bepalen of een $$n$$-gram in een woord voorkomt. De dictionary die door de functie teruggegeven wordt, moet sleutels hebben die in hoofdletters staan.

• Schrijf een functie aantal_ngrammen waaraan een dictionary (dict) moet doorgegeven worden die opgebouwd is zoals de dictionaries die worden teruggegeven door de functie woordenboek. De gegeven dictionary beeldt dus elk $$n$$-gram (in hoofdletters) dat in een woordenlijst $$\mathcal{W}$$ voorkomt af op de verzameling woorden waarin het $$n$$-gram voorkomt, en dit voor een bepaalde $$n \in \mathbb{N}_0$$. De functie aantal_ngrammen heeft ook nog een tweede optionele parameter waaraan een getal $$m \in \mathbb{N}_0$$ (int) kan doorgegeven worden. Als niet expliciet een waarde wordt doorgegeven aan de optionele parameter, dan moet de functie het aantal verschillende $$n$$-grammen teruggeven dat in de woordenlijst $$\mathcal{W}$$ voorkomt. Anders moet de functie het aantal verschillende $$n$$-grammen teruggeven die in exact $$m$$ woorden uit de woordenlijst $$\mathcal{W}$$ voorkomen. Zo moet de functie bijvoorbeeld voor $$m = 1$$ het aantal $$n$$-grammen teruggeven waarvoor er juist één woord is waarin het $$n$$-gram voorkomt, en voor $$m = 2$$ het aantal $$n$$-grammen waarvoor er juist twee woorden zijn waarin het $$n$$-gram voorkomt.

• Schrijf een functie uniek_ngram waaraan eenzelfde dictionary (dict) moet doorgegeven worden als bij de functie aantal_ngrammen. De functie moet een tuple (tuple) met twee strings (str) teruggeven, waarvan het eerste element een willekeurig geselecteerd $$n$$-gram is dat in slechts één woord uit de woordenlijst $$\mathcal{W}$$ voorkomt, en het tweede element het geselecteerde woord is waarin dat $$n$$-gram voorkomt.

De functies aantal_ngrammen en uniek_ngram mogen de gegeven dictionary nooit wijzigen. De tekstbestanden die aan de functie woordenboek doorgegeven worden, gebruiken de UTF-8⁸ tekencodering. Bij het openen van een tekstbestand kan je de gebruikte tekencodering meegeven aan de parameter encoding van de ingebouwde functie open:

>>> open('bestand.txt', 'r', encoding='utf-8')

Voorbeeld

In onderstaande voorbeeldsessie gaan we ervan uit dat de tekstbestanden woordenboek.en.txt¹¹ en woordenboek.nl.txt¹² zich in de huidige directory bevinden.

>>> ngrammen('Disgrace', 4)
['Disg', 'isgr', 'sgra', 'grac', 'race']
>>> ngrammen('vergeet-mij-nietje', 3)
['ver', 'erg', 'rge', 'gee', 'eet', 'mij', 'nie', 'iet', 'etj', 'tje']
>>> ngrammen('façade', 2)
['fa', 'ad', 'de']
>>> ngrammen('A4-formaat', 2)
['fo', 'or', 'rm', 'ma', 'aa', 'at']

>>> engels = woordenboek('woordenboek.en.txt13', 4)
>>> engels['SGRA']
{'disgrading', 'disgrade', 'disgracers', 'misgrafts', 'palsgrave', 'hansgrave', 'disgracement', 'misgraded', 'misgrading', 'disgracer', 'disgraced', 'grosgrain', 'misgracious', 'disgracive', 'disgrace', 'predisgrace', 'palsgraf', 'disgracing', 'dysgraphia', 'misgrafting', 'disgraded', 'disgracefulness', 'misgraft', 'misgrave', 'misgraffed', 'misgrade', 'grosgrained', 'disgraceful', 'disgracia', 'disgracefully', 'disgracious', 'grosgrains', 'disgradation', 'disgraces', 'sgraffiti', 'crossgrainedness', 'misgraff', 'sgraffiato', 'undisgraced', 'disgradulate', 'misgrafted', 'sgraffito', 'palsgravine'}
>>> aantal_ngrammen(engels)
63546
>>> aantal_ngrammen(engels, 1)
13711
>>> aantal_ngrammen(engels, 2)
7408
>>> aantal_ngrammen(engels, 3)
4613
>>> uniek_ngram(engels)
('RLBU', 'pearlbush')
>>> uniek_ngram(engels)
('FIFR', 'kefifrel')
>>> uniek_ngram(engels)
('PPAT', 'wappato')

>>> engels = woordenboek('woordenboek.en.txt14', 3)
>>> engels['GNT']
{'sovereignties', 'pgntt', 'supersovereignty', 'pgnttrp', 'sovereignty', 'cosovereignty', 'semisovereignty'}
>>> aantal_ngrammen(engels)
9025
>>> aantal_ngrammen(engels, 1)
1125
>>> aantal_ngrammen(engels, 2)
561
>>> aantal_ngrammen(engels, 3)
332
>>> uniek_ngram(engels)
('HMP', 'rhythmproof')
>>> uniek_ngram(engels)
('IPZ', 'leipzig')
>>> uniek_ngram(engels)
('LZH', 'alzheimer')

>>> nederlands = woordenboek('woordenboek.nl.txt15', 4)
>>> nederlands['SGRA']
{'visgraatje', 'bezettingsgraad', 'hardheidsgraad', 'asgrauwe', 'jongensgrappen', 'verzuringsgraad', 'doctorsgraden', 'alfabetiseringsgraad', 'werkgelegenheidsgraad', 'schansgravers', 'orpheusgrasmussen', 'visgraatmotief', 'moeilijkheidsgraad', 'werkloosheidsgraad', 'stadsgrachten', 'zeemansgraf', 'tewerkstellingsgraad', 'basisgrammatica', 'varkensgras', 'werkloosheidsgraden', 'werkingsgraad', 'leesgrage', 'scholingsgraad', 'ontwikkelingsgraad', 'vullingsgraad', 'glansgraad', 'Bosgra', 'koersgrafieken', 'vervuilingsgraad', 'activiteitsgraad', 'traangasgranaten', 'visgraatpatronen', 'gifgasgranaten', 'paltsgraven', 'visgraatdessins', 'kostendekkingsgraden', 'bewustzijnsgraad', 'visgraat', 'beladingsgraad', 'oorlogsgraf', 'zelfvoorzieningsgraad', 'oorlogsgraven', 'hellingsgraad', 'paltsgraaf', 'liesgras', 'koningsgraf', 'dekkingsgraden', 'moeilijkheidsgraden', 'visgraatdiagram', 'gasgranaten', 'vrijheidsgraad', 'beschavingsgraad', 'vrijheidsgraden', 'gasgranaat', 'doctorsgraad', 'asgrauw', 'besmettingsgraad', 'dekkingsgraad', 'luchtvochtigheidsgraad', 'beursgraadmeters', 'automatiseringsgraad', 'bezettingsgraden', 'leesgraag', 'Palsgraaf', 'koersgrafiek', 'stadsgracht', 'bedekkingsgraad', 'opleidingsgraad', 'olifantsgras', 'vochtigheidsgraad', 'beschermingsgraad', 'molenaarsgraaf', 'benuttingsgraad', 'zeemansgraven', 'hardheidsgraden', 'paltsgravin', 'bewolkingsgraad', 'struisgras', 'beursgraadmeter', 'koningsgraven', 'kostendekkingsgraad', 'visgraten', 'uitbuitingsgraad', 'paltsgraafschap', 'visgraatjes', 'jongensgrap', 'traangasgranaat', 'werkzaamheidsgraad', 'zuiverheidsgraad'}
>>> aantal_ngrammen(nederlands)
57210
>>> aantal_ngrammen(nederlands, 1)
8224
>>> aantal_ngrammen(nederlands, 2)
7360
>>> aantal_ngrammen(nederlands, 3)
3856
>>> uniek_ngram(nederlands)
('LAMR', 'glamrock')
>>> uniek_ngram(nederlands)
('ACGL', 'cognacglazen')
>>> uniek_ngram(nederlands)
('ALOL', 'afvalolie')