Maschinelle Suche nach Grundform von Wörtern

Question

Gibt es eine Online-Resource oder ein Programm, das ich unter Linux installieren kann, das folgendes leistet?

Ich habe einen kurzen deutschen Text (typischerweise nur ein bis drei einfache Aussagesätze) und möchte von jedem Wort in dem Text die jeweilige Grundform (das lexikographische Lemma) wissen. Komposita sollen dabei wenn möglich in ihre Bestandteile zerlegt werden.

Zum Beispiel soll aus dem folgende Satz

Singlefrauen haben meist aufgeräumtere Wohnungen als Junggesellen.

das werden:

Single Frau, haben, meist, aufräumen, Wohnung, als, Junggeselle

Dabei ist mir relativ egal, ob im Fall von »aufgeräumtere« das Adjektiv »aufgeräumt« oder das Verb »aufräumen« ausgeben wird, solange die Eingabe von »aufgeräumt« genau dasselbe Ergebnis liefert.

Mir ist auch egal, ob ich ganze Sätze oder nur einzelne Wörter eingeben kann.

Etwas ähnliches wurde bereits hier gefragt: Lemma, Grundform-Lexikon deutscher Sprache Allerdings hatte der Fragesteller genau die umgekehrte Aufgabe im Visier (»Liefere mir alle Wortformen, die sich von einem gegebenem Lemma ableiten lassen«).

In einer Antwort auf die eben zitierte Frage wurde canoonet genannt. Ich glaube, canoonet wäre zwar prinzipiell sehr gut in der Lage, mein Problem zu lösen, allerdings ist der Output für menschliche Nutzer aufbereitet und ungeeignet um von einem Programm verarbeitet zu werden.

Dasselbe Problem scheint Wiktionary zu haben. Auch hier hat der Output kein Format, das eine einfache maschinelle Verarbeitung ermöglicht. Vielleicht habe ich aber auch nur Hinweise auf eine Programmierschnittstelle (API) übersehen, in diesem Fall bitte ich, mich mit der Nase darauf zu stoßen.

Ich benötige die Ausgabe der Grundformsuche in einer Form, die ohne hohen Aufwand von einem Computerprogramm verarbeitet werden kann.

---

Kontext

Wofür brauche ich das?

Dieser Abschnitt gehört eigentlich nicht mehr zur Frage, soll aber helfen den Fokus meiner Frage klarer herauszuarbeiten.

Seit nunmehr 14 Jahren betreibe ich die Datenbank des nutzlosen Wissens, die bereits mehr als 5000 veröffentlichte und rund 1000 noch unveröffentlichte Einträge beinhaltet. Es ist mittlerweile aussichtslos, bei dieser riesigen Menge an Fakten Duplikate durch manuelles Sichten ausfindig zu machen. Daher habe ich schon vor Jahren Programme geschrieben, die das automatisch erledigen sollen. Ich bin nun dabei diese Programme zu überarbeiten.

Die Duplikaterkennung soll z.B. erkennen, dass diese beiden Beiträge (fast) denselben Inhalt haben, obwohl sie unterschiedlich lang sind nur nur ein einziges Wort gemeinsam haben, das noch dazu auf semantischer Eben kaum Informationen enthält (»bis«):

1. Wenn man Küchenschaben den Kopf abschneidet, leben sie noch bis zu 14 Tage lang weiter, dann verhungern sie.
2. Geköpfte Kakerlaken sterben erst nach zwei bis drei Wochen.

Intern macht das Programm aus den beiden Eingaben das:

1. Küche Schabe Insekt Kopf schneiden abschneiden leben 14 Tage Zeit verhungern Hunger
2. köpfen Kopf Kakerlake Schabe Insekt sterben leben 2 3 Woche Zeit

Dass die beiden Beiträge Kandidaten für ein Duplikatspaar sind, wird anhand der fett hervorgehobenen Wörter erkannt.

Damit das gelingt, muss mein Programm Synonyme (Küchenschabe - Kakerlake) und Antonyme (leben - sterben) erkennen, es muss verwandte Begriffe erkennen (köpfen - Kopf), und es muss Überbegriffe wissen (Schabe = Insekt, Tag = Zeit).

Die eben beschriebenen Arbeiten sind alles Analysen auf semantischer Ebene, aber davor muss die Lemmatisierung stehen, also ein Umwandlungsprozess, der Wort-Variationen, die meist durch die Grammatik verursacht sind, vereinheitlicht. Das Vorhandensein von standardisierten Grundformen ist eine wichtige Voraussetzung, um nach Synonymen usw. zu suchen.

Der ganze Prozess soll automatisiert ablaufen. Das Programm soll der Reihe nach jeden einzelnen der rund 6000 Beiträge entweder als Ganzes, oder Wort für Wort an einen Lemmatisierungs-Automaten schicken, der dann entweder eine Liste der gefundenen Grundformen, oder eben die jeweilige Grundform zurückgibt. Unbekannte Wörter (Eigennamen, Rechtschreibfehler) sollen idealerweise zur Ausgabe einer kurzen Fehlermeldung führen, ohne dass dadurch die Verarbeitung bekannter Begriffe beeinträchtigt wird.

Das Ermitteln der Grundformen muss also ganz ohne menschliches Zutun erfolgen können.

Answer 1

Das ist jetzt recht technisch und etwas allgemeiner, aber... was du suchst ist wahrscheinlich ein Stemmer oder Lemmatizer. Gibts zB. als Go-Library (habe ich nur auf die Schnelle ergoogelt, aber mit den Begriffen findest du sicher auch Anderes).

Das Ganze lässt sich dann in eine NLP-Pipline einbauen: Tokenizer => Stemmer => Stop-word-removal => Synonymauflösung => Similarity.

Mit "Similarity" meine ich hier irgendein gebräuchliches Maß wie Cosine-Similarity auf tf-idf. Da es dir um semantische Ähnlichkeiten geht, könnte man natürlich auch etwas sophistizierteres wie LSA benutzen.

Googlebare Begriffe, um einen Überblick dazu zu bekommen, sind "Natural language processing" und "Document retrieval". Hier sind auch noch die Folien einer Vorlesung zu Data Mining, die ich besucht habe, und in der NLP-Anwendungen immer wieder als praktische Beispiele vorkommen. Wenn du in eine Bibliothek gehen (oder Geld ausgeben) willst, empfehlen sich die Klassiker von Manning und Jurafsky.

_{(Die Links verweisen mit Absicht auf die englische Wikipedia -- dort sind die Artikel ausführlicher.)}

Answer 2

Lemmatisierung:

Meine Empfehlung wäre der snowball stemmer. Es gibt u.a. ein Python interface. Auf der alten Seite von snowball findet man Beispiele für die deutsche Sprache inkl. Vokabular.

Synonyme:

dict.cc hat gute deutsche Unterstützung. Es enthält auch Synonyme. Man kann den gesamten Datensatz haben, es steht aber nicht, ob der auch Synonyme enthalten würde. Außerdem ist die Verwendung an bestimmte Klauseln geknüpft, man muss eine Anfrage stellen.

Weiters findet sich auf openthesaurus ein deutsches Synonymwörterbuch für 100.000 Wörter. Dazu würde diese Seite auch ein API zur Abfrage anbieten.

BeoLingus der TU Chemitz bietet ebenfalls eine Wörterdatenbank zum Download an.

Zu Machine Learning kann ich leider nicht so viel sagen.

Der wichtigste Punkt: ein fertiges Programm wirst Du nicht finden, Du müsstest das selber programmieren. Empfehlen würde sich hier Python. Es hat mit scrapy eine Library um Daten aus Webseiten abzufragen, und es gibt mit NLTK eine Lib zur Sprachverarbeitung, sowie zahlreiche weitere Libs.

Hier findet sich schließlich eine nette Einführung in nltk auf deutsch.

Viel Spaß bei der Umsetzung!

Answer 3

Ich glaube schon, dass Dein Ansatz aus bereits zur Verfügung stehenden Wortlisten, z.B. aus Open Source Bereichen, funktionieren sollte, und im ersten Schritt einfacher ist als der grammatische Weg aus NLP bzw. sich mit diesem ergänzen lässt.

1. leo.org (Deutsch-Englisch-Deutsch)

   Beispiele:
   http://dict.leo.org/englisch-deutsch/aufger%C3%A4umt
   http://dict.leo.org/englisch-deutsch/K%C3%B6pfe
   http://dict.leo.org/englisch-deutsch/Junggesellen

   Die Suche auf leo.org ergab für folgende von Dir genannten Worte auf Anhieb die richtigen Wortstämme unter dem Text "Mögliche Grundformen für das Wort"

   • aufgeräumtere => aufgeräumt
   • aufgeräumtere=> aufgeräumt
   • aufgeräumt => aufräumen (!!)
     (leider kein direkter Verweis auf Raum, da würde aber dict.cc, s.u. gute leisten)
   • Köpfe => der Kopf
   • Junggesellen => der Junggeselle
   • Wohnungen => die Wohnung
   • Singlefrau (leider NICHTS)

- Leo.org könnte man auch mal kontaktieren oder gucken, ob man etwas offline geladen kriegt.

-

2. Ich würde mal auf dict.cc den Paul Hemmelsberger anmailen:

   http://www.dict.cc/?s=about%3A

   Ich verändere die Adresse mal, sie steht aber im Link oben direkt: paul ät dict punkd cc "(Vor Kontaktaufnahme bitte FAQ lesen!)" Er wird auf Grund seiner Erfahrung im Bereich kostenlose Wörterbücher sicher Vieles kennen, was wir mit Googeln nicht so einfach finden.

3. Die dict.cc Einträge selbst z.B. aus Englisch-Deutsch würde ich einschätzen, dass man die schon als Grundform per Programm als Heuristik verwenden könnte: Aber vielleicht ist dict.cc eher für die Such nach Synonymen, dem Hauptwort zu einem Verb oder Adjektiv nützlicher. Auf jeden Fall mal:

   erste Regel: Suche "der/die/das", Beispiel:

   Übersetzung(en) tabellarisch anzeigen | immer
   Übersetzungen mit gleichem Wortanfang
   KOP | Kopf | Kopfe | Köpfe
   NOUN der Kopf | die Köpfe
   Köpfe {pl}
   heads
   pates [archaic or hum.] [heads]

   zweite Regel: Suche Wort mit hohere Ähnlichkeit, welches kürzer ist

   ADJ aufgeräumt | aufgeräumter | am aufgeräumtesten
   VERB aufräumen | räumte auf/aufräumte | aufgeräumt
   SYNO aufgeräumt | bereinigt | geordnet ... aufgeräumt [ordentlich]

4. Meine Vermutung wäre gewesen, dass Du mit einem einfachen Algorithmus, welches die Levenshtein-Distanz berechnet, verschiedenste Ansätze ganz gut unterstützen, bzw. Bewertungen vorgeschlagener (syntaktischer) Stämme vornehmen kannst. Aber vermutlich machst Du das schon

Answer 4

Ich beantworte meine eigene Frage, weil ich ja selbst auch nach einer Antwort suche, und einen aktuellen Stand meiner Nachforschungen bekanntgeben will, damit andere, die versuchen die Frage zu beantworten, sich auch daran orientieren können.

Zweiter Grund: Sobald das Problem gelöst ist, möchte ich hier meine Lösung präsentieren, damit andere, die vielleicht etwas ähnliches machen wollen, sich hier Anregungen holen können.

---

Ich halte derzeit zwei Ansätze für vielversprechend:

1. The Durm German Lemmatizer

   Das ist ein fix und fertiger Lemmatisierer, den ich aber nicht so wie er ist verwenden würde, sondern ich würde ganz einfach sein frei verwendbares Lexikon (mit 84320 Einträgen, 8,6 MB groß) in eine Datenbanktabelle stopfen und mit einem selbstgeschriebenen Programm abfragen.

   Dieses Lexikon enthält zwar z.B. »Singlefrauen« aber weder »aufgeräumtere« noch »aufgeräumter«, nicht einmal »aufräumen« sondern nur das Nomen »Aufräumen«.

2. ParZu - The Zurich Dependency Parser for German

   Das ist zwar weder ein Stemmer noch ein Lemmatisierer, sondern ein Parser, und damit eigentlich übers Ziel hinaus geschossen, aber wie man auf der Demo-Seite gut nachvollziehen kann, spuckt dieses Programm auch Grundformen aus.

   Sehr vorteilhaft erscheint mir hier die Eigenschaft, dass das Programm z.B. in dem Satz

   Er sagt, sein Bruder würde bald hier sein.

   erkennt, dass die beiden Instanzen von »sein« verschiedene Wörter mit verschiedenen Grundformen sind.

   Das Programm liefert auch Grundformen für Singlefrauen und aufgeräumtere.

   Außerdem eröffnet die Ausgabe der grammatischen Funktionen Möglichkeiten, die mir vielleicht helfen können, die zugrundeliegende Aufgabe (Erkennen von Aussagen mit gleicher Bedeutung) besser zu bewältigen.

   Dieser Parser kann unter der GNU General Public License frei verwendet werden und läuft unter Linux. Zur Zeit ist dieser Parser die von mir favorisierte Lösung.

---

Nachtrag:

Wie oben schon angedeutet, habe ich mich für den Zurich Dependency Parser entschieden (Link: siehe oben)

Da es sich hier um einen Parser handelt, werden ganze Sätze analysiert. Das hat den Vorteil, dass grammatische Beziehungen zwischen den Wörtern erkannt werden, was eben unter anderem dazu führt, dass zu jedem Wort die tatsächliche Grundform gefunden wird.

Vorteil Nr. 2: Der Parser liefert auch alle notwendigen Daten, um abgetrennte Präfixe trennbarer Verben sehr einfach den Kernen der Verben zuzuordnen. Damit können die korrekten Grundformen von trennbaren Verben gefunden werden.

Vorteil Nr. 3: Der Parser erkennt auch Mehrwortlexeme (»San Francisco«, »Vincent Van Gogh«) und liefert Daten, mit deren Hilfe die Bestandteile dieser Mehrwortlexeme zuverlässig zu einem Begriff zusammengefügt werden können.

Insgesamt liefert dieser Parser also eine Lemmatisierung von äußerst hoher Qualität.

Der Parser hat aber auch einen Nachteil:

Jedesmal wenn er aufgerufen wird, um einen Text zu analysieren, braucht er mehrere Sekunden, um irgendwelche internen Vorarbeiten durchzuführen. Erst dann wird der Text tatsächlich analysiert.

Wenn man also knapp 6000 relativ kurze Texte analysiert haben will, würde das mehrere Tage dauern, wenn man jeden Text einzeln an den Parser übergibt. Daher muss man die Texte zuerst zu einem langen Text zusammenfügen und als eine große Textdatei dem Parser zuführen. In meinem Fall war das Parsen dann in weniger als 10 Minuten erledigt.

---

Nachtrag 2

Weitere Ressourcen, die bei der Bewältigung der in der Frage beschriebenen Aufgabe helfen, kann man hier herunterladen: https://www.openthesaurus.de/about/download

Dort gibt es z.B. ein sehr hochwertiges Synonymlexikon (einen Thesaurus), das sogar als MySQL-Dump verfügbar ist. Man muss es nur herunterladen und kann daraus sofort eine MySQL-Datenbank erzeugen. Allerdings ist die Beschreibung der Tabellen und Spalten dürftig bis mangelhaft. Wenn man sich die Tabellen genauer ansieht, kann man aber gut erkennen, wie sie zusammenhängen und wie man sie verwenden kann.

Den Thesaurus gibt es auch als reine Textdatei, ich habe mir diese Datei aber nicht angesehen und kann dazu nichts sagen.

Auf der verlinkten Seite gibt es auch einen Link zu einer Programmierschnittstelle (API). Man kann sie nutzen, um zu einzelnen Wörtern Synonyme zu finden. Wer aber, so wie ich, Massenabfragen an den Server stellen würde, ist besser beraten, sich gleich den ganzen Bestand herunterzuladen.

Alle beschriebenen Versionen des Thesaurus sind unter der GNU Lesser General Public License frei verfügbar.

Morphologie-Lexikon

Auf derselben Seite gibt es auch einen Link, wo man sich ein Vollformen-Wörterbuch herunterladen kann. (Also etwas, was genau meine Frage beantworten würde). Dieses Wörterbuch enthält angeblich zu jedem deutschen Wort alle nur denkbaren grammatischen Formen.

Dieses Morphologie-Lexikon hat aber einen Haken: Es liegt als binär codierte Datei vor. Um es nutzen zu können, muss man ein Programm namens LanguageTool herunterladen und installieren. Dieses Programm kann angeblich die binäre Datei in eine strukturierte Textdatei umwandeln. Aber dieses Programm ist in Java geschrieben. Damit man es zum Laufen bekommt, müsste man also zusätzlich auch noch eine Java-Runtime herunterladen und installieren.

Weil jede Software eine potentielle Sicherheitslücke ist, habe ich weder Java noch LanguageTool auf meinem Server installiert (ich brauche beide Programme eigentlich überhaupt nicht), und kann daher nicht sagen, ob man wirklich wie versprochen am Ende ein verwendbares Morphologie-Lexikon rausbekommt.

Dieses Lexikon ist ebenfalls frei verfügbar, allerdings unter einer anderen Lizenz (CC BY-SA 4.0).