Quantifizierung der "Unterschiedlichkeit" von Wörtern

Hallo zusammen!

Zum Kontext:
Bei dem Projekt, bei dem ich arbeite, müssen wir eine Suchfunktion programmieren, die ein lateinisches Textcorpus durchsucht. Da dieses Textcorpus nicht hunderprozentig perfekt sein, sondern sicher den ein oder anderen Fehler enthalten wird, sollte diese Suchfunktion nicht nur wörtlich genau den eigegebenen Begriff suchen, sondern "unscharf" sein, also auch Wörter finden, die sich durch eine gewisse Anzahl an Zeichen vom eingegebenen Wort unterscheiden. Die Frage ist, wie groß diese Anzahl sinnvoll sein darf, damit nicht zu viele Ergebnisse gefunden werden, und damit auch, wie hoch unsere Textqualität sein muss.

Jetzt die Frage:
Diese "Unschärfe" der Suche kann man natürlich mathematisch quantifizieren, indem man z.B. einen Wert a definiert, der mit jedem Zeichen, das sich vom Ausgangswort unterscheidet, um 1 höher wird, z.B.

Ausgangswort: solum a=0

dolum a=1 (nur s durch d ersetzt)
secum a=2 (ec statt ol)
multum a=3 (mu statt so, t hinzugefügt)
usw.

Dann könnte man etwa der Suche sagen "alles bis zu einem Unterschied von 3 ist in Ordnung". 

Man könnte daraus als grobe Orientierung z.B. auch einen Durchschnitt berechnen, etwa indem man sich ein bestimmtes Lexikon vornimmt und dieses komplett mit einem Grundwort vergleicht und daraus eine durchschnittliche Abweichung des Lexikons von diesem Grundwort errechnet. Evtl. könnte man dann wiederum über alle Wörter im Lexikon einen Durchschnitt berechnen und so aussagen, dass die Einträge dieses Lexikons sich im Schnitt durch soundsoviele Zeichen unterscheiden. 

Ich hab das jetzt natürlich noch nicht durchexerziert, kann sein, dass diese konkrete Methode wenig aussagekräftig oder totaler Schwachsinn ist. Aber ich bin mir recht sicher, dass man auf irgendeine Weise sinnvoll eine "durchschnittliche Unterschiedlichkeit" der Wörter eines vorgegebenen Lexikons berechnen kann, und dass dieser Wert für verschiedene Sprachen verschieden ausfällt.

Weiß vielleicht jemand von euch, ob so etwas schon mal in irgendeiner Form gemacht wurde? Im Idealfall natürlich sogar für Latein, aber auch wenn es für eine andere Sprache gemacht wurde, würde mich die Methode interessieren.

Vielen Dank schonmal!

Das Verfahren, das du beschreibst, klingt für mich nach der Levenshtein-Distanz. Diese ist definiert als die minimale Anzahl von Operationen, die man braucht, um sozusagen die Ausgangszeichenkette in die Zielzeichen "umzubauen". In der Standardversion sind die Operationen Zeichen ersetzen, Zeichen anfügen und Zeichen entfernen. Darauf aufbauend gibt es dann Varianten, die das Vertauschen zweier Zeichen berücksichtigen oder auf verschiedene Art mit Gewichtungen arbeiten und teilweise eigenständige Namen haben (z. B. Levenshtein-Damerau-Distanz). In der (Computerl)inguistik kommt das Verfahren an diversen Stellen zum Einsatz (z. B. in der Dialektometrie oder bei der Berechnung von Phylogenetischen Bäumen für Sprachfamilien.) ^[1]

Die Verwendung für unscharfes Suchen, nachdem der gefragt hattest, im Informational Retrieval ist eine weitere gängige Anwendung dafür. Dafür gibt es fertige Software, die das kann, je nach Anwendungsfall (z. B. Apache Lucene und das darauf aufbauende Solr, welche für professionelle Suchanwendungen sehr weit verbreitet sind). Diese verwenden intern stark optimierte Versionen der Levenshtein-Distanz; der Standard-Algorithmus, den man auf Wikipedia und in Lehrbüchern findet ist nicht sonderlich performant bei großen Mengen.

Ich finde deine Idee mit der durchschnittlichen Abweichung für einzelne Wörter sehr interessant. Ich habe das gerade mal für eine Swadesh-Liste gegen eine 100.000 Wörter Wortliste (~85.000  geeignete Wörter) ausprobiert (s.u). Die Ergebnisse sind interessant, aber ich weiß nicht, ob sie für die angedachte Anwendung angesichts der Höhe der Abweichung sinnvoll wären. Mit einer besser ausgewählten Liste kommt man vielleicht zu stabileren und aussagekräftigeren Werten. Spannend sind insb. auch die Schwankungen bei Wörtern derselben Länge sowie die Unterschiede zwischen den Wortlängen. Für Latein hatte ich gerade keine Daten greifbar.

Persönlich würde ich für die praktische Anwendung aber auf die o.g. Software oder Vergleichbares ausweichen. Ich würde schätzen, dass diese auch für deine Anwendung gut funktionieren kann, auch wenn sie nicht darauf optimiert ist. Die Arbeit mit vordefinierten Distanzen oder Prozenten im Rahmen einer selbst implementierten Lösung klappt meiner Erfahrung nach nur so mittel gut und steht ggf. nicht um Verhältnis zum notwendigen Aufwand.

Als Randnotiz noch: Außer der genannten Levenshtein-Distanz auf Grundlage einzelner Zeichen gibt es auch noch andere Verfahren, sowie den Ansatz auf N-Grammen zu arbeiten. Da kann man dann zum Beispiel mit dem Dice-Koeffizienten oder dem Jaccard-Index arbeiten.
 

---

Fußnoten:

1. Als kleine Spielerei hatte ich das z.B. in einem alten Post verwendet, um orthographische Minimalpaare zu berechnen.

Das klingt auf jeden Fall schon mal nach etwas, was meiner Idee entspricht, danke dir!

Ich denke, durch ein eingeengtes Vergleichscorpus ließe sich diese Methode auf jeden Fall optimieren, wenn man etwa davon ausgeht, dass die allermeisten Fehler in unseren Texten ein Wort nicht um wahnsinnig viele Zeichen länger machen werden, sondern eher in der Verwechslung von Buchstaben, ihrer Löschung und vielleicht der ein oder anderen Hinzufügung bestehen. Dann könnte man das Vergleichscorpus auf Wörter von "in etwa der gleichen Länge" beschränken.

Ich kam die Tage auf den Gedanken, als ich mir mal beispielhaft überlegt habe, was unsere Suche finden würde, wenn man "solum" (Teekesselchen für "Boden", "alleine" und "nur", also recht häufiges Wort) sucht und die unscharfe Suche die Erlaubnis hat, sich vom gesuchte Wort maximal zwei Operationen (Buchstaben durch anderen ersetzen, Buchstaben hinzufügen, Buchstaben weglassen, wobei "Buchstabe" das Leerzeichen einschließt) zu entfernen.

Ich bin das händisch durchgegangen und habe auf Anhieb ca. 20 andere Wörter gefunden, größtenteils durchaus gängige, die die Suche in diesem Fall mitausspucken würde. Man bekäme also bei einem entsprechenden Suchcorpus Hunderte Treffer, die nicht relevant wären, und zwei Operationen erscheint mir wirklich nicht viel, die Suche hat den Namen "unscharf" doch kaum verdient. Deswegen habe ich mich gefragt, ob dieses Wort ein Einzelfall ist, oder ob vielleicht auch Latein in dieser Hinsicht problematischer oder weniger problematisch ist als andere Sprachen.

Letztlich muss das Problem unsere informatische Abteilung lösen, aber da ich auch ein Mathematikstudium hinter mir habe, fasziniert es mich natürlich ebenso :D

Eine Frage am Rande, die Deine Arbeit vermutlich nicht beeinflussen wird. Was verstehtst Du genau unter 'Lexikon'? Du hast ja selbst Homographe angesprochen. Wie handhabt ihr die bei Eurer Idee, Unschärfen zuzulassen? Die formbasierte Zeichenkette kann ja mehrere Bedeutungen haben und gerade bei Fehlern in der Form oder Änderungen der Form durch Wandelphänomene kann jede Bedeutung unterschiedliche Abweichungen haben. Ein Beispiel: Im Deutschen kann nur die Präposition 'zu' mit dem folgenden Artikel zu 'zum' oder 'zur' verschmelzen, nicht aber die Verbpartikel.

Um die genaue technische Umsetzung müssen sich Informatiker kümmern und die stehen damit auch noch ganz am Anfang, von daher kann ich dazu wenig sagen. Das Schöne am Lateinischen ist immerhin, dass es zu etwas wie Zusammenziehungen voneinander unabhängiger Wörter eigentlich nicht gibt, das ist zumindest etwas. Homographe gibt es dafür natürlich immer noch genug und dieses Problem werden wir auch nicht lösen können.

Zum Kontext: Wir haben ca. 30 000 Seiten an Lateinischem und Griechischem Text in Bildform, die durchsuchbar gemacht werden sollen, indem der Text per OCR erkannt wird. Wir haben dafür drei Jahre Zeit, in denen wir aber auch noch eine Menge anderer Dinge zu tun haben. Wir werden also definitiv nicht die Zeit haben, sämtliche auftretenden Homographe durchzugehen und zu kennzeichnen, welche Wortart/Bedeutung in diesem Zusammenhang vorliegt, wir werden es wahrscheinlich nicht mal schaffen, jede dieser Seiten auch nur flüchtig durchzulesen. 

Das Ziel ist daher in erster Linie, den Text für Computer erkennbar zu machen, sodass der Benutzer dann nach einer bestimmten Zeichenkette suchen kann. Welche Funktion die Zeichenkette dann im ausgegebenen Fall erfüllt und ob das tatsächlich das Wort ist, das er sucht, oder nur ein Homograph, muss der Benutzer selbst entscheiden. Insofern verstehe ich unter "Lexikon" hier etwas, was man vielleicht besser einfach als "Wortliste" bezeichnet, eine Liste von in dem Korpus vorkommenden Zeichenketten, wobei durchaus eine Zeichenkette mehrere homographe Wörter bezeichnen kann (wie solum = Boden; alleine; nur).

Danke für die Präzisierung!