Enkele jaren na de publicatie van Schateiland¹ (Engels: Treasure Island, 1883) kwam Robert Louis Stevenson² tot de schokkende ontdekking dat een groot deel van zijn verhaal klakkeloos was overgenomen uit het boek Tales of a Traveller³ (1824) van Washington Irving⁴, waarvan hij volledig vergeten was dat hij het vele jaren daarvoor had gelezen.

Afbeelding uit het boek Schateiland (Engels: Treasure Island) van Robert Louis Stevenson (1883).

Hij schreef daarover later het volgende:

Ik geloof dat er zelden een erger geval van plagiaat geweest is. Het boek kwam plotsklaps terug in me op en sloeg me recht in mijn gezicht: Billy Bones, zijn schatkist, het gezelschap in de salon, de hele innerlijke geest, en een groot deel van de materiële details uit mijn eerste hoofdstukken — ze stonden er allemaal, ze waren allemaal ontsproten aan de verbeelding van Washington Irving. Maar ik had er toen geen idee van — terwijl ik bij de open haard zat te schrijven — in wat leek op het springtij van inspiratie die op kousevoeten rondhuppelde. Ook niet dag na dag, na de lunch, terwijl ik het werk van die ochtend aan mijn gezin voorlas.

Dit is een voorbeeld van cryptomnesie⁵. Het verwarren van een vergeten herinnering met een origineel idee. Stevenson beschuldigde zichzelf van plagiaat, maar had oprecht geloofd dat hij een nieuw verhaal aan het schrijven was.

Het voelde zo origineel als maar kon zijn. Het leek van mij te zijn zoals mijn rechteroog.

Bij het lezen van Nietzsches Also Sprach Zarathustra⁶ was Carl Jung verrast om bijna woordelijk het relaas te ontdekken van een incident dat in 1686 werd vermeld in een scheepslogboek. Jung herkende daarin meteen de passage uit een boek dat rond 1835 was gepubliceerd, ongeveer 50 jaar voordat Nietzsche zijn werk schreef. Hij nam contact op met de zus van de filosoof, die bevestigde dat beiden het boek hadden gelezen toen Nietzsche 11 jaar oud was.

Opgave

Werk een eenvoudige manier uit om de similariteit — de mate van overeenkomst — tussen twee teksten te bepalen. Hiervoor introduceren we eerst het concept filter: een functie waaraan een tekst (str) moet doorgegeven worden en die een aangepaste versie van de gegeven tekst (str) teruggeeft. Begin alvast met het schrijven van de volgende eenvoudige filters:

Een functie hoofdletters die alle letters in de gegeven tekst omzet naar hoofdletters.
Een functie verwijder_witruimte die alle witruimte (spaties, tabs en newlines) uit de gegeven tekst verwijdert.

Als volgende stap moeten we teksten kunnen opdelen in overlappende substrings met vaste lengte $$k$$. Definieer hiervoor een klasse Tekst waaraan een tekst (str) moet doorgegeven worden. Deze klasse moet een methode fragmenten ondersteunen waaraan een getal $$k \in \mathbb{N}_0$$ moet doorgegeven worden. Voor een tekst van lengte $$n$$ moet de methode een lijst (list) teruggeven met de $$n - k + 1$$ overlappende substrings (str) met vaste lengte $$k$$, in de volgorde waarin ze in de tekst voorkomen. Optioneel kunnen aan de methode fragmenten ook meerdere filters doorgegeven worden. Vooraleer de tekst wordt opgedeeld in fragmenten van lengte $$k$$, moeten die filters eerst één na één toegepast worden op de gegeven tekst, in de volgorde waarin ze als argument doorgegeven worden.

Het volgende concept dat we nodig hebben, is dat van een multiset — een veralgemening van het concept verzameling. Een element van een multiset kan meer dan één keer in de multiset voorkomen. Dit in tegenstelling tot een verzameling waarin elk element precies één keer voorkomt. Het aantal keer dat eenzelfde element $$e$$ voorkomt in een multiset $$X$$, wordt de multipliciteit van dat element genoemd (genoteerd als $$m_X(e)$$). In de multiset $$X = \{a, a, b, b, c, b\}$$ hebben de elementen bijvoorbeeld als multipliciteit $$m_X(a) = 2$$, $$m_X(b) = 3$$ en $$m_X(c) = 1$$. De multipliciteit van een element $$d$$ dat niet tot de multiset behoort, is per definitie gelijk aan 0. Het totale aantal elementen in een multiset $$X$$ is de som van de multipliciteiten van de elementen en wordt de kardinaliteit van de multiset genoemd (genoteerd als $$|X|$$). De multiset $$X = \{a, a, b, b, c, b\}$$ heeft bijvoorbeeld kardinaliteit $$|X| = 6$$.

Definieer een klasse Multiset waarmee multisets kunnen voorgesteld worden. Bij het aanmaken van een multiset (Multiset) moet een reeks (list of tuple) met de elementen (str) van de multiset doorgegeven worden. Elk element komt even vaak in de reeks voor als zijn multipliciteit in de multiset. Voor multisets $$X, Y$$ (Multiset) moet gelden dat

ze een methode als_dict moeten hebben (zonder argumenten) die een dictionary (dict) teruggeeft die elk element van de multiset afbeeldt op de multipliciteit van dat element; deze dictionary bevat nooit sleutels met multipliciteit 0
len($$X$$) de kardinaliteit van $$X$$ teruggeeft (ingebouwde functie len)
$$X$$ & $$Y$$ de doorsnede van $$X$$ en $$Y$$ oplevert (genoteerd als $$X \cap Y$$): een multiset $$Z$$ (Multiset) met als multipliciteit \[ m_Z(e) = \min(m_X(e), m_Y(e)) \]
$$X$$ | $$Y$$ de unie van $$X$$ en $$Y$$ oplevert (genoteerd als $$X \cup Y$$): een multiset $$Z$$ (Multiset) met als multipliciteit \[ m_Z(e) = \max(m_X(e), m_Y(e)) \]

Een similariteitsmaat $$\mathcal{S}$$ is een functie waaraan twee multisets $$X$$ en $$Y$$ (Multiset) moeten doorgegeven worden en die de mate van overeenkomst tussen $$X$$ en $$Y$$ uitdrukt als een waarde uit het interval $$[0, 1]$$ (float). Als $$\mathcal{S}(X, Y) = 0$$ dan zijn $$X$$ en $$Y$$ volledig verschillend van elkaar. Als $$\mathcal{S}(X, Y) = 1$$ dan zijn $$X$$ en $$Y$$ volledig gelijk aan elkaar. Definieer de volgende twee similariteitsmaten:

jaccard \[ \mathcal{S}(X, Y) = \frac{|X \cap Y|}{|X \cup Y|} = \frac{|X \cap Y|}{|X| + |Y| - |X \cap Y|} \]
dice \[ \mathcal{S}(X, Y) = \frac{2|X \cap Y|}{|X| + |Y|} \]

Definieer ten slotte ook nog een functie similariteit waarmee de similariteit van twee teksten $$x$$ en $$y$$ kan bepaald worden. Aan de functie moeten vier argumenten doorgegeven worden: i) een similariteitsmaat $$\mathcal{S}$$, ii) een tekst $$x$$ (str), iii) een tekst $$y$$ (str) en iv) een getal $$k \in \mathbb{N}_0$$. Optioneel kunnen aan de functie ook meerdere filters doorgegeven worden. De functie moet de waarde $$s$$ (float) teruggeven die als volgt bepaald wordt:

pas één na één de gegeven filters toe op $$x$$ en $$y$$
bepaal de overlappende substrings van vaste lengte $$k$$ van de resulterende teksten
bepaal de multisets die corresponderen met de reeksen overlappende substrings
$$\mathcal{S}$$ toegepast op deze multisets levert $$s$$ op

Voorbeeld

        >>> hoofdletters("een twee  drie   vier   ")
'EEN TWEE  DRIE   VIER   '
>>> verwijder_witruimte("een twee  drie   vier   ")
'eentweedrievier'
>>> tekst = Tekst('een\\n twee\\n  drie\\n')
>>> tekst.fragmenten(4)
['een\\n', 'en\\n ', 'n\\n t', '\\n tw', ' twe', 'twee', 'wee\\n', 'ee\\n ', 'e\\n  ', '\\n  d', '  dr', ' dri', 'drie', 'rie\\n']
>>> tekst.fragmenten(6, verwijder_witruimte)
['eentwe', 'entwee', 'ntweed', 'tweedr', 'weedri', 'eedrie']
>>> tekst.fragmenten(8, verwijder_witruimte, hoofdletters)
['EENTWEED', 'ENTWEEDR', 'NTWEEDRI', 'TWEEDRIE']
>>> multiset = Multiset(tekst.fragmenten(2, hoofdletters, verwijder_witruimte))
>>> multiset.als_dict()
{'EE': 2, 'EN': 1, 'NT': 1, 'TW': 1, 'WE': 1, 'ED': 1, 'DR': 1, 'RI': 1, 'IE': 1}
>>> len(multiset)
10

>>> tekst1 = Tekst('Mississippi')
>>> multiset1 = Multiset(tekst1.fragmenten(2, hoofdletters, verwijder_witruimte))
>>> len(multiset1)
10
>>> multiset1.als_dict()
{'MI': 1, 'IS': 2, 'SS': 2, 'SI': 2, 'IP': 1, 'PP': 1, 'PI': 1}
>>> tekst2 = Tekst('permissiveness')
>>> multiset2 = Multiset(tekst2.fragmenten(2, hoofdletters, verwijder_witruimte))
>>> len(multiset2)
13
>>> multiset2.als_dict()
{'PE': 1, 'ER': 1, 'RM': 1, 'MI': 1, 'IS': 1, 'SS': 2, 'SI': 1, 'IV': 1, 'VE': 1, 'EN': 1, 'NE': 1, 'ES': 1}
>>> (multiset1 & multiset2).als_dict()
{'MI': 1, 'IS': 1, 'SS': 2, 'SI': 1}
>>> (multiset1 | multiset2).als_dict()
{'MI': 1, 'IS': 2, 'SS': 2, 'SI': 2, 'IP': 1, 'PP': 1, 'PI': 1, 'PE': 1, 'ER': 1, 'RM': 1, 'IV': 1, 'VE': 1, 'EN': 1, 'NE': 1, 'ES': 1}
>>> jaccard(multiset1, multiset2)
0.2777777777777778
>>> dice(multiset1, multiset2)
0.43478260869565216
>>> similariteit(jaccard, 'Mississippi', 'permissiveness', 2, hoofdletters, verwijder_witruimte)
0.2777777777777778
>>> similariteit(jaccard, 'Mississippi', 'mississippi', 2, hoofdletters, verwijder_witruimte)
1.0
>>> similariteit(dice, 'Mississippi', 'permissiveness', 2, hoofdletters, verwijder_witruimte)
0.43478260869565216
>>> similariteit(dice, 'Mississippi', 'mississippi', 2, hoofdletters, verwijder_witruimte)
1.0