Interna der Solr-Rechtschreibprüfung (jetzt mit Tests!)
Lassen Sie uns über Rechtschreibprüfungen sprechen. Eine Rechtschreibprüfung ist, wie Sie vielleicht wissen, ein Gerät, das Ihnen sagt, ob Sie…
Lassen Sie uns über Rechtschreibprüfungen sprechen. Eine Rechtschreibprüfung ist, wie Sie vielleicht wissen, ein Gerät, das Ihnen sagt, ob Sie ein Wort falsch geschrieben haben oder nicht, und das Ihnen einige Vorschläge macht. Eine der ersten Rechtschreibprüfungen, die ich gesehen habe, war die MS Word-Rechtschreibprüfung. Man könnte sagen, dass MS Word die „Standardschnittstelle“ für die Rechtschreibprüfung von Textverarbeitungsprogrammen definiert hat: Wenn Sie ein Wort falsch geschrieben haben, wurde es mit einer zickzackförmigen roten Linie unterstrichen, und wenn Sie mit der rechten Maustaste darauf klicken, erscheint eine Liste mit Wortvorschlägen. Ich habe diese Schnittstelle schon in vielen anderen Programmen gesehen, zum Beispiel in Google Docs.
Ein anderes, moderneres Beispiel ist das berühmte „Meinten Sie“ von Google. Sie geben ein Wort wie „britny spears“ ein und Google schlägt „Britney Spears“ vor. Es scheint, dass viele Menschen Probleme mit der Rechtschreibung von Britney Spears haben. Aber Google ist anders. Wie üblich verwendet das Unternehmen Algorithmen der künstlichen Intelligenz, um falsch geschriebene Wörter vorzuschlagen. Die Algorithmen von Google kommen der Magie in der Computertechnik am nächsten.
Aber heute werde ich über Solr SpellChecker sprechen. Im Gegensatz zu Google ist die Solr-Rechtschreibprüfung nicht viel mehr als ein Algorithmus zur Musterähnlichkeit. Sie geben ihm ein Wort vor und er findet ähnliche Wörter. Aber was wird von Solr als „ähnlich“ interpretiert? Die Wörter werden einfach als eine Reihe von Zeichen interpretiert, so dass zwei Wörter ähnlich sind, wenn sie viele Übereinstimmungen in ihren Zeichenfolgen haben. Das mag offensichtlich klingen, aber in natürlichen Sprachen haben die Bytes (Buchstaben) wenig Bedeutung. Es ist das gesamte Wort, das eine Bedeutung hat. Die Solr-Algorithmen werden also nicht einmal wissen, dass Sie ihnen Wörter geben. Diese Byte-Folgen könnten Zahlenfolgen oder Farbfolgen sein. Solr findet die Zahlenfolgen, die sich geringfügig von der Eingabe unterscheiden, oder die Farbfolgen usw. Übrigens ist dies nicht der Ansatz, den Google verfolgt. Google kennt die häufigen Wörter, die häufig falsch geschriebenen Wörter und die Art und Weise, wie Menschen häufig Fehler machen. Ich habe vor, diese interessanten Themen in einem nächsten Beitrag zu behandeln, aber lassen Sie uns jetzt erst einmal im Detail untersuchen, wie die Solr-Rechtschreibprüfung funktioniert, und dann einige Tests durchführen.
Die Solr-Rechtschreibprüfung verfolgt die gleiche Strategie wie viele andere Rechtschreibprüfungen. Sie verfügt über ein Wörterbuch mit korrekt geschriebenen Begriffen (per Definition korrekt, d.h. wenn ein falsch geschriebenes Wort im Wörterbuch steht, wird es als korrektes Wort gewertet). Wenn jemand nach Vorschlägen für ein Wort fragt, erhält die Solr-Rechtschreibprüfung zunächst eine Liste von Wortkandidaten und ordnet diese dann nach bestimmten Kriterien ein. Der erste Schritt wird durch Ngramme bewerkstelligt. Ein Ngramm ist eine Teilzeichenkette in einer Zeichenkette. Wenn Sie zum Beispiel das Wort ‚Haus‘ haben, wären einige Ngramme ‚hou‘, ‚ous‘, ’se‘ (es gibt viele andere Ngramme unterschiedlicher Länge, ich habe Ihnen nur drei davon gezeigt). Zwei ähnliche Wörter werden viele übereinstimmende Ngramme haben: ‚Maus‘ hat auch ‚ous‘ und ’se‘, aber nicht ‚hou‘. Solr erstellt einen Lucene-Index der Wörter im Wörterbuch und filtert sie mit Ngramm-Filtern. Wenn Sie also nach Vorschlägen für „Haus“ fragen, sucht Solr nach ‚ho‘ ODER ‚ou‘ ODER ‚us‘ ODER ’se‘ ODER ‚hou‘ ODER ‚ous‘ ODER ‚use‘ ODER ‚hous‘ ODER ‚ouse‘. Da Solr boolesche Abfragen nach dem Dokument mit den meisten Übereinstimmungen ordnet, erhalten Sie eine Liste mit ähnlichen Wörtern aus unserem Wörterbuch.
Wie ordnet Solr die Wörter anschließend ein? Es gibt eine so genannte Editierdistanz, die uns sagt, wie viele Operationen wir durchführen müssen, um ein Wort in ein anderes umzuwandeln. Unter Operationen verstehen wir Einfügungen, Löschungen oder Änderungen einzelner Zeichen. Es gibt viele Algorithmen, um die Editierdistanz zu ermitteln, einer davon ist Levenshtein (das ist der in Solr verwendete Standardalgorithmus). Diese Algorithmen sind rechenaufwändig, und das ist der Grund, warum Solr sie nicht als erste Wahl bei der Auswahl der Vorschläge aus allen Wörtern des Wörterbuchs verwendet. Das Wörterbuch wird reduziert und dann wird dieser „schwierige“ Ranking-Prozess durchgeführt.
Vielleicht verstehen Sie jetzt, was ich mit „Solr-Rechtschreibprüfung findet nur ähnliche Byte-Arrays“ meinte. Sie führen niemals Informationen über unsere natürliche Sprache in den Algorithmus ein und das einzige, was Sie zur Verfügung stellen, ist „eine Reihe von Byte-Sekuenzen“ (d.h. ein Wörterbuch).
So weit, so gut. Funktioniert dieser Ansatz? Ja. Könnte er noch besser funktionieren? Ja, natürlich! Und es gibt eine Menge Dinge, die wir tun können, um den Algorithmus zu verbessern. Aber lassen Sie uns zunächst versuchen, das Ganze wissenschaftlich aussehen zu lassen (wenn Sie sich erinnern, das war ja die Idee des Internets überhaupt…) Wir brauchen Tests, um zu sehen, wo wir stehen. Ich finde es langweilig, von der theoretischen Seite zur experimentellen Seite überzugehen. Aber das ist ein Muss in diesem Bereich, den wir Forschung nennen. Im Folgenden stelle ich Ihnen eine Reihe verschiedener Tests vor, die ich mit einer Solr-Instanz (die wir zu Versuchszwecken haben) der Wikipedia durchgeführt habe (ich empfehle allen, die versuchen, riesige Textmengen zu indizieren, diesen Beitrag darüber zu lesen, wie wir die Wikipedia indiziert haben).
Ich habe ein Wörterbuch mit den Wörtern aus der Wikipedia erstellt und dann eine Reihe verschiedener falsch geschriebener Wörter unterschiedlicher Herkunft getestet.
Für jeden Testfall habe ich ein kleines Python-Skript erstellt, das einfach jedes einzelne falsch geschriebene Wort in Solr abfragt und zählt, an welcher Stelle das richtig geschriebene Wort zurückkommt. Der Testfall enthält das richtige erwartete Wort. Sie können den Quellcode hier herunterladen.
Der erste Satz ist eine synthetische Liste falsch geschriebener Wörter, die ich aus einem Wörterbuch aus dem Internet erstellt habe (es handelt sich um ein Wörterbuch von Ispell) und auf die Wörter Modifikationen von „Edit Distance 1“ angewendet habe. Ich habe einen Teil des Algorithmus von Peter Norvig aus seinem ausgezeichneten Artikel über Rechtschreibprüfungen verwendet
Verarbeitete Wörter insgesamt: 19708
In den ersten 1 Positionen gefunden: 53%
In den ersten 2 Positionen gefunden: 58%
In den ersten 3 Positionen gefunden: 60%
In den ersten 10 Positionen gefunden: 61%
Das bedeutet, dass 53% der Wörter beim ersten Vorschlag richtig korrigiert wurden, 58% bei den ersten beiden und so weiter. Ziemlich miese Ergebnisse, selbst bei einem einfachen Datensatz. Aber lassen Sie uns etwas Schwierigeres versuchen.
Aspell ist die GNU-Rechtschreibprüfungsbibliothek von GNU. Sie stellen einen Datensatz zur Verfügung, den sie zum Testen ihrer Bibliothek verwenden. Die Ergebnisse sind sehr gut, aber sie verwenden eine andere Methode.
Ich habe diese Bibliothek mit unserer Testumgebung getestet und das ist das Ergebnis
Verarbeitete Wörter insgesamt: 547
In den ersten 1 Positionen gefunden: 27%
In den ersten 2 Positionen gefunden: 33%
In den ersten 3 Positionen gefunden: 37%
In den ersten 10 Positionen gefunden: 45%
Noch schlimmer. Sie geben nicht an, woher diese Wörter stammen. Ein guter Test wäre es, echte Fehler von echten Menschen zu verwenden. Diese wurden aus einer frei verfügbaren Datei entnommen. Ich habe eine Liste mit häufig falsch geschriebenen Wörtern von Collage-Studenten, eine Liste mit Tippfehlern und eine Liste mit bekannten Rechtschreibfehlern in der englischen Sprache getestet (all das können Sie in der Readme-Datei sehen, die dem Download beiliegt, ich möchte das hier nicht ausweiten). Das Format einiger dieser Dateien musste konvertiert werden. In dem vorherigen Code-Download habe ich die Skripte dafür enthalten.
MASTERS Rechtschreibfehler bei etwa 260 Wörtern in Rechtschreibtests von 600 Schülern in Iowa in den 1920er Jahren – 200 Achtklässler, 200 High-School-Senioren und 200 College-Senioren
Verarbeitete Wörter insgesamt: 13020
In den ersten 1 Positionen gefunden: 27 %
In den ersten 2 Positionen gefunden: 35 %
In den ersten 3 Positionen gefunden: 38 %
In den ersten 10 Positionen gefunden: 44 %
SHEFFIELD Eine Liste von etwa 380 Rechtschreibfehlern, meist Tippfehler, die von Mitarbeitern und Studenten der Abteilung für Informationsstudien der Universität Sheffield im Rahmen eines Projekts von Angell, Freund und Willett gesammelt wurden.
Forschung zur Rechtschreibkorrektur.
Verarbeitete Wörter insgesamt: 384
In den ersten 1 Positionen gefunden: 57 %
In den ersten 2 Positionen gefunden: 62 %
In den ersten 3 Positionen gefunden: 65 %
In den ersten 10 Positionen gefunden: 70 %
FAWTHROP Eine Zusammenstellung von vier Sammlungen amerikanischer Rechtschreibfehler, die bereits veröffentlicht wurden.
Verarbeitete Wörter insgesamt: 809
In den ersten 1 Positionen gefunden: 44 %
In den ersten 2 Positionen gefunden: 50 %
In den ersten 3 Positionen gefunden: 52 %
In den ersten 9 Positionen gefunden: 55 %
Das beste Ergebnis und sehr ähnlich zu meinem ersten Test ist das der Tippfehler. Das liegt daran, dass Tippfehler in der Regel Wörter sind, die eine Editierdistanz von 1 zu echten Wörtern haben (man macht normalerweise nicht zwei Tippfehler im selben Wort). Die anderen sind ziemlich schlecht. Dieses Szenario ist das gleiche, das jeder machen würde, der einen großen Dokumentenkorpus indiziert (wie z.B. Wikipedia) und damit einen Index erstellt, und das ist die Effektivität, die er in der Rechtschreibprüfung erreichen wird.
Was könnte der Grund für diese Ergebnisse sein? Wahrscheinlich sind die Ergebnisse schlecht, weil die Solr-Rechtschreibprüfung nichts über die natürliche Sprache, die wir Englisch nennen, weiß.
Wie können Sie diese Ergebnisse verbessern? Durch einen anderen Ansatz bei der Rechtschreibprüfung. Es gibt Algorithmen, die Wörter finden, die ähnlich klingen, um Vorschläge zu machen. Wie ein Wort klingt, gibt dem System viele Informationen über die natürliche Sprache (und die Psychologie von Fehlern)! (Dies ist der Ansatz, den GNU Aspell verfolgt). Andere Algorithmen verwenden die von Shannon entwickelte Informationstheorie und berücksichtigen, dass wir Menschen verrauschte Kanäle sind, die Rauschen (Rechtschreibfehler) in Wörter einbringen. Wenn Sie die Informationen natürlicher Sprachen über Statistiken einbringen, können Sie bessere Ergebnisse erzielen (wie in dem Artikel von Peter Norvig)
In zukünftigen Beiträgen werden wir einige dieser Algorithmen implementieren und (der wissenschaftlichen Tradition folgend) testen.
Wir sehen uns in der Zukunft!!!
Dieser Beitrag stammt aus meinem persönlichen Blog http://emmaespina.wordpress.com