Jeder Benutzer hatte jemals Tippfehler beim Schreiben von Suchanfragen. Das Fehlen von Mechanismen zur Korrektur von Tippfehlern führt zur Ausgabe irrelevanter Ergebnisse oder sogar zu deren Fehlen. Um die Suchmaschine benutzerorientierter zu gestalten, sind daher Fehlerkorrekturmechanismen integriert.

Die Korrektur von Tippfehlern erscheint auf den ersten Blick eher unkompliziert. Wenn Sie jedoch von einer Vielzahl von Fehlern ausgehen, kann die Implementierung einer Lösung schwierig sein. Im Allgemeinen wird die Tippfehlerkorrektur in kontextunabhängig und kontextsensitiv unterteilt (wobei die Wörterbuchumgebung berücksichtigt wird) . Im ersten Fall werden Fehler für jedes Wort separat korrigiert, im zweiten Fall - unter Berücksichtigung des Kontexts (zum Beispiel erfolgt für den Ausdruck "sie ging nach Hause" im kontextunabhängigen Fall eine Korrektur für jedes Wort separat, wobei wir "sie ging nach Hause" erhalten können). und im zweiten Fall ergibt die korrekte Korrektur "sie ist nach Hause gegangen").

In den Suchanfragen des russischsprachigen Benutzers können vier Hauptfehlergruppen nur zur kontextunabhängigen Korrektur unterschieden werden [ 1 ]:
1) Fehler in den Wörtern selbst (sagen Sie mr → hi), diese Kategorie umfasst alle Arten von Auslassungen, Einfügungen und Permutationen von Buchstaben - 63,7%,
2) kontinuierliche Rechtschreibung von Wörtern - 16,9%,
3) verzerrtes Layout (ghbdtn → hi) - 9,7%,
4) Transliteration (Liguster → hi) - 1,3%,
5) gemischte Fehler - 8,3%.

Benutzer machen in ungefähr 10-15% der Fälle Tippfehler. Gleichzeitig haben 83,6% der Anfragen einen Fehler, 11,7% - zwei, 4,8% - mehr als drei. Der Kontext ist in 26% der Fälle wichtig.

Diese Statistiken wurden auf der Grundlage einer Zufallsstichprobe aus dem täglichen Yandex-Protokoll von 2013 auf der Grundlage von 10.000 Anfragen erstellt. Im öffentlichen Bereich gibt es eine viel frühere Präsentation von Yandex für 2008, die eine ähnliche Verteilung der Statistiken zeigt [ 2 ]. Daraus können wir schließen, dass sich die Verteilung der verschiedenen Arten von Fehlern für Suchanfragen im Durchschnitt im Laufe der Zeit nicht ändert.

Im Allgemeinen basiert der Tippfehlerkorrekturmechanismus auf zwei Modellen: dem Fehlermodell und dem Sprachmodell. Darüber hinaus wird für eine kontextunabhängige Korrektur nur das Fehlermodell verwendet, und bei einer kontextabhängigen Korrektur werden zwei gleichzeitig verwendet. Das Fehlermodell ist normalerweise entweder die redaktionelle Distanz (Levenshtein, Damerau-Levenshtein-Distanz, verschiedene Gewichtungsfaktoren, Methoden ähnlich wie Soundex usw. können hier ebenfalls hinzugefügt werden - in diesem Fall wird die Distanz als gewichtet bezeichnet) oder das Bril-Moore-Modell, das arbeitet an den Wahrscheinlichkeiten von Übergängen von einer Zeile zur anderen. Bril und Moore positionieren ihr Modell als perfekter. Bei einem der jüngsten SpellRuEval-Wettbewerbe zeigte der Damerau-Levenshtein-Ansatz jedoch ein besseres Ergebnis [ 3 ], obwohl der Damerau-Levenshtein-Abstand (Klarstellung ist ungewichtet) keine A-priori-Informationen über die unvorhergesehenen Statistiken verwendet . Diese Beobachtung ist besonders aussagekräftig, wenn dieselben Trainingstexte für unterschiedliche Implementierungen von Autokorrekturen in der DeepPavlov-Bibliothek verwendet wurden.

Offensichtlich erschwert die Möglichkeit einer kontextsensitiven Korrektur den Aufbau des Autokorrektors, da zusätzlich zum Fehlermodell die Notwendigkeit eines Sprachmodells hinzugefügt wird. Wenn Sie jedoch auf die Statistik der Tippfehler achten, können ¾ alle falsch geschriebenen Suchanfragen ohne Kontext korrigiert werden. Dies legt nahe, dass der Nutzen mindestens eines kontextunabhängigen Autokorrektors sehr bedeutend sein kann.

Außerdem ist eine kontextsensitive Korrektur zum Korrigieren von Tippfehlern in Anforderungen sehr ressourcenintensiv. Zum Beispiel unterschied sich in einer von Yandex 'Reden die Liste der Paare zur Korrektur von Tippfehlern (Bigramme) von Wörtern zehnmal im Vergleich zur Anzahl der Wörter (Unigramme) . Was ist dann mit Trigrammen? Dies hängt natürlich wesentlich von der Variabilität der Abfragen ab. Es sieht ein wenig seltsam aus, wenn die Autokorrektur die Hälfte des Speichers des vorgeschlagenen Firmenprodukts einnimmt, dessen Zweck nicht auf die Lösung des Rechtschreibproblems gerichtet ist. Das Problem der Implementierung kontextsensitiver Korrekturen in Suchmaschinen von Softwareprodukten kann daher sehr kontrovers sein.

Auf den ersten Blick hat man den Eindruck, dass es für jede Programmiersprache viele vorgefertigte Lösungen gibt, die verwendet werden können, ohne viel in die Details der Funktionsweise von Algorithmen einzutauchen, auch in kommerziellen Systemen. In der Praxis wird die Entwicklung ihrer Lösungen jedoch fortgesetzt. Zum Beispiel hat Joom vor relativ kurzer Zeit seine eigene Entscheidung getroffen, Tippfehler mithilfe von Sprachmodellen für Suchanfragen zu korrigieren [ 4 ]. Ist die Situation mit der Verfügbarkeit schlüsselfertiger Lösungen wirklich schwierig? Zu diesem Zweck wurde so weit wie möglich ein umfassender Überblick über bestehende Lösungen gegeben. Bevor wir mit der Überprüfung beginnen, werden wir entscheiden, wie die Qualität des Autokorrektors überprüft wird.

Qualitätskontrolle

Das Problem der Überprüfung der Qualität des Autokorrektors ist sehr umstritten. Ein einfacher Ansatz zur Validierung ist Precision and Recall. In Übereinstimmung mit der ISO-Norm werden Genauigkeit und Vollständigkeit durch Korrektheit (auf Englisch „Korrektheit“) ergänzt.

Die Vollständigkeit (Rückruf) wird wie folgt berechnet: Eine Liste der korrekten Wörter wird an die Autokorrektur (Total_list_true) gesendet, und die Anzahl der Wörter, die die Autokorrektur als korrekt erachtet (Spellchecker_true) geteilt durch die Gesamtzahl der korrekten Wörter (Total_list_true), wird als Vollständigkeit betrachtet.

R e c a l l = R e c h t s c h r e i b p r ü f u n g_{t} r u e o v e r T o t a l_{l} i s t_{t} r u e

$Recall = {Rechtschreibprüfung \ _true \ over Total \ _list \ _true}$

Um die Genauigkeit (Präzision) zu bestimmen, wird eine Liste falscher Wörter (Total_list_false) an die Eingabe des Autokorrektors gesendet, und die Anzahl der Wörter, die der Autokorrektor als falsch erachtet (Spell_checker_false), geteilt durch die Gesamtzahl falscher Wörter (Total_list_false), wird als Genauigkeit definiert.

P r e c i s i o n = R e c h t s c h r e i b p r ü f u n g_{f} a l s e o v e r T o t a l_{l} i s t_{f} a l s e

$Precision = {Rechtschreibprüfung \ _false \ over Total \ _list \ _false}$

Wie allgemein diese Metriken informativ sind und wie nützlich sie sein können, wird jeweils unabhängig voneinander bestimmt. Schließlich besteht das Wesentliche dieses Tests darin, dass das Wort im Trainingswörterbuch überprüft wird. Die Korrektheit kann als eine offensichtlichere Metrik angesehen werden, nach der die Autokorrektur für jedes Wort aus dem Testsatz falscher Wörter eine Liste von Ersatzkandidaten bildet, für die dieses falsche Wort korrigiert werden kann (denken Sie daran, dass es möglicherweise Wörter gibt, die nicht im Trainingswörterbuch enthalten sind). . Angenommen, die Größe einer solchen Liste von Ersatzkandidaten beträgt 5. Basierend auf der Tatsache, dass die Größe der Liste 5 beträgt, werden 6 Gruppen gebildet, in die wir jedes unserer ursprünglichen falschen Wörter nach dem folgenden Prinzip einfügen: in der 1. Gruppe - wenn in Die Liste der Ersatzkandidaten, das richtige Wort, in dem wir uns befinden sollen, ist das erste, das zweite, wenn es das zweite ist usw., und in der letzten Gruppe, wenn das angeblich richtige Wort nicht in der Liste der Ersatzkandidaten enthalten ist. Natürlich funktioniert die Autokorrektur umso besser, je mehr Wörter in die 1. Gruppe und je weniger in die 6. Gruppe fallen.

Die Autoren betrachteten den in Artikel [ 5 ] berücksichtigten Ansatz, bei dem kontextunabhängige Autokorrekturen mit einer Abweichung vom ISO-Standard verglichen wurden. Es enthält auch Links zu anderen Methoden zur Qualitätsbewertung.

Einerseits basiert dieser Ansatz nicht auf Bruttostatistiken, die auf dem Brill-Moore-Fehlermodell [ 6 ] oder dem Damerau-Levenshtein-gewichteten Distanzfehlermodell basieren können.

Um die Qualität der Arbeit des kontextunabhängigen Autokorrektors zu überprüfen, haben wir einen eigenen Tippfehlergenerator erstellt, der Tippfehler mit falschem Layout und Rechtschreibfehler basierend auf den von Yandex eingereichten Statistiken zu Tippfehlern generiert. Für Rechtschreibfehler wurden zufällige Einfügungen, Ersetzungen, Löschungen und Umordnungen generiert, und die Anzahl der Fehler variierte ebenfalls gemäß diesen Statistiken. Bei Fehlern im verzerrten Layout wurde das richtige Wort zeichenweise vollständig gemäß der Zeichenübersetzungstabelle geändert.

Dann wurde eine Reihe von Experimenten für die gesamte Liste der Wörter im Trainingswörterbuch durchgeführt (die Wörter des Trainingswörterbuchs wurden entsprechend der Wahrscheinlichkeit eines bestimmten Tippfehlers auf falsche korrigiert) . Im Durchschnitt korrigiert die Autokorrektur Wörter in 75% der Fälle korrekt. Ohne Zweifel wird diese Anzahl reduziert, wenn das Lernwörterbuch mit Wörtern in redaktioneller Entfernung, einer Vielzahl von Wortformen, aufgefüllt wird. Dieses Problem kann durch Ergänzung mit Sprachmodellen gelöst werden. Es sollte jedoch berücksichtigt werden, dass die Menge der erforderlichen Ressourcen erheblich zunehmen wird.

Fertige Lösungen

Die Prüfung vorgefertigter Lösungen wurde mit dem Schwerpunkt auf dem eigenen Gebrauch durchgeführt, und Autokorrekturen, die drei Kriterien erfüllen, wurde Vorrang eingeräumt:
1) Implementierungssprache,
2) Art der Lizenz,
3) Aktualisierbarkeit.

In der Produktentwicklung gilt Java als eines der beliebtesten. Daher wurde Java bei der Suche nach Bibliotheken Vorrang eingeräumt. Von den relevanten Lizenzen: MIT, Public, Apache, BSD. Aktualisierbarkeit - nicht mehr als 2 Jahre nach dem letzten Update. Während der Suche wurden zusätzliche Informationen aufgezeichnet, z. B. über die unterstützte Plattform, die erforderlichen zusätzlichen Programme, Anwendungsfunktionen, mögliche Schwierigkeiten bei der ersten Verwendung usw. Links zu grundlegenden und nützlichen Ressourcen zu den Quellen finden Sie am Ende des Artikels. Wenn nicht auf die oben genannten Kriterien beschränkt, ist die Anzahl der vorhandenen Lösungen im Allgemeinen groß. Lassen Sie uns einen kurzen Blick auf die wichtigsten werfen und nur einigen mehr Aufmerksamkeit schenken.

Historisch gesehen ist Ispell (International Spell) einer der ältesten Autokorrekturen. Er wurde 1971 in Assembler geschrieben, später nach C übertragen und verwendet die redaktionelle Distanz Damerau-Levenshtein als Modell für Fehler. Für ihn gibt es sogar ein Wörterbuch auf Russisch. Anschließend wurde er durch zwei Autokorrekturen HunSpell (ehemals MySpell ) und Aspell ersetzt . Beide sind in C ++ implementiert und werden unter GPL-Lizenzen vertrieben. HunSpell wird auch von der GPL / MPL abgedeckt und zum Korrigieren von Tippfehlern in OpenOffice, LibreOffice, Google Chrome und anderen Tools verwendet.

Es gibt viele JS-Lösungen für das Internet und Browser (dazu gehören: NodeJun-Sätze , Nspell , Node-Markdown-Rechtschreibprüfung , Korrekturleser , Rechtschreibprüfung-API - eine Gruppe von Lösungen, die auf dem Hunspell- Autokorrektur-Code basieren; Grunz-Zauber - für NodeJS; Yaspeller- ci - Wrapper für Yandex.Speller Autokorrektur, vertrieben unter MIT; rousseau - Leichter Korrektor in JS - zur Rechtschreibung verwendet).

Die Kategorie der kostenpflichtigen Lösungen umfasst: Spellex ; Quellcode-Rechtschreibprüfung - als Desktop-Anwendung; für JS: Nanospell ; für Java: Keyoti RapidSpell Rechtschreibprüfung , JSpell SDK , WinterTree (WinterTree kann sogar Quellcode für 5000 US-Dollar kaufen).

Die Autokorrektur von Peter Norwig ist weit verbreitet. Der Python-Code ist im Artikel „ Wie schreibe ich eine Rechtschreibkorrektur? “ [ 7 ] öffentlich verfügbar. Basierend auf dieser einfachen Lösung wurden Autokorrektoren in anderen Sprachen erstellt, zum Beispiel: Norvig-Rechtschreibprüfung , Scala-Norvig-Rechtschreibprüfung (auf Scala), Spielzeug-Rechtschreibkorrektur - Golang Rechtschreibprüfung (auf GO), Pyspellchecker (auf Python) . Natürlich geht es hier nicht um Sprachmodelle und kontextsensitive Korrekturen.

Für Texteditoren, insbesondere für von VIM erstellten Vim-Dialekt , vim-ditto - unter einer öffentlichen Lizenz vertrieben; für Notepad ++, entwickelt von DspellCheck in C ++, GPL-Lizenz; Emacs verfügt über ein Tool zum automatischen Erkennen von Sprachen beim Drucken, das als Vermutungssprache bezeichnet wird und unter einer öffentlichen Lizenz verteilt wird.

Es gibt separate Dienste von Suchriesen: Yandex.Speller - von Yandex, über den oben erwähnten Wrapper, google-api-spelling-java (bzw. von Google).

Kostenlose Bibliotheken für Java: Sprachecool (lizenziert unter LGPL), integriert sich in die Lucene-Textsuchbibliothek und ermöglicht die Verwendung von Sprachmodellen. Java Version 8 ist erforderlich. Jazzy (ein Analogon von Aspell ) ist unter LGPLv2 lizenziert und wurde seit 2005 nicht mehr aktualisiert. 2013 wurde es auf GitHub portiert. In Anlehnung an diesen Autokorrektor wurde eine separate Lösung gefunden [ 8 ]; Jortho (Java Orthography) wird unter der GPL vertrieben und erlaubt die kostenlose Nutzung ausschließlich für nichtkommerzielle Zwecke, für kommerzielle Zwecke - gegen eine zusätzliche Gebühr; Jaspell (lizenziert unter BSD und seit 2005 nicht mehr aktualisiert); Open Source Java Suggester - wurde seit 2013 nicht aktualisiert, von SoftCorporation LLC vertrieben und ermöglicht die kommerzielle Nutzung; LuceneSpellChecker ist ein Lucene-Autokorrektor, der in Java geschrieben und unter der Apache-Lizenz vertrieben wird.

Wolf Garbe beschäftigte sich lange Zeit mit Tippfehlern und schlug die Algorithmen SymSpell (unter der MIT-Lizenz) und LinSpell (unter der LGPL) mit C # -Implementierungen [ 9 ] vor, die den Damerau-Levenshtein-Abstand für das Fehlermodell verwenden. Die Besonderheit ihrer Implementierung besteht darin, dass in der Phase der Erzeugung möglicher Fehler für das Eingabewort nur Löschungen anstelle aller Arten von Löschungen, Einfügungen, Ersetzungen und Permutationen verwendet werden. Im Vergleich zur Implementierung des Autokorrektors von Peter Norwig arbeiten beide Algorithmen dadurch schneller, während die Geschwindigkeitssteigerung erheblich zunimmt, wenn der Abstand Damerau-Levenshtein mehr als zwei beträgt. Aufgrund der Tatsache, dass nur Löschungen verwendet werden, wird auch die Wörterbuchbildungszeit reduziert. Der Unterschied zwischen den beiden Algorithmen besteht darin, dass LinSpell sparsamer im Speicher und langsamer in der Suchgeschwindigkeit ist , SymSpell - umgekehrt. In einer späteren Version behebt SymSpell Rechtschreibfehler. Sprachmodelle werden nicht verwendet.

Zu den neuesten und vielversprechendsten für die Verwendung von Autokorrekturen, die mit Sprachmodellen arbeiten und kontextsensitive Tippfehler korrigieren, gehören Yandex.Speller , JamSpell [ 10 ], DeepPavlov [ 11 ]. Die letzten 2 sind frei verteilt: JamSpell (MIT), DeepPavlov (unter Apache).

Yandex.Speller verwendet den CatBoost-Algorithmus, arbeitet mit mehreren Sprachen und korrigiert alle Arten von Fehlern, auch unter Berücksichtigung des Kontexts. Die einzige gefundene Lösung korrigiert falsche Layoutfehler und Transliteration. Die Lösung ist vielseitig einsetzbar. Der Nachteil ist, dass es sich um einen Remote-Dienst handelt. Informationen zu Einschränkungen und Nutzungsbedingungen finden Sie hier [ 12 ]. Der Dienst arbeitet mit einer begrenzten Anzahl von Sprachen. Sie können keine Wörter selbst hinzufügen und den Korrekturprozess verwalten. In Übereinstimmung mit der Ressource [ 3 ] zeigte dieser Autokorrektor gemäß den Ergebnissen des RuSpellEval-Wettbewerbs die höchste Qualität der Korrekturen. JamSpell ist der schnellste bekannte Autokorrektor (C ++ - Implementierung), es gibt fertige Ordner für andere Sprachen. Korrigiert Fehler nur in den Wörtern selbst und arbeitet mit einer bestimmten Sprache. Sie können die Lösung nicht auf der Ebene von Unigrammen und Bigrammen verwenden. Um eine akzeptable Qualität zu erzielen, ist ein großer Schulungstext erforderlich.
DeepPavlov verfügt über einige bewährte Methoden. Die Integration dieser Lösungen und die anschließende Unterstützung in das eigene Produkt können jedoch zu Schwierigkeiten führen, da für die Arbeit mit ihnen eine virtuelle Umgebung verbunden und eine frühere Version von Python 3.6 verwendet werden muss. DeepPavlov bietet eine Auswahl von drei vorgefertigten Implementierungen von Autokorrekturen, von denen zwei die Bril-Moore- Fehlermodelle und zwei Sprachmodelle verwenden. Es werden nur Rechtschreibfehler korrigiert, und die Option mit einem Fehlermodell, das auf dem Abstand Damerau-Levenshtein basiert, kann Fehler beim kontinuierlichen Schreiben korrigieren.

Ich werde einen anderen modernen Ansatz zur Korrektur von Tippfehlern erwähnen, der auf der Verwendung von Vektordarstellungen von Wörtern (Word Embeddings) basiert. Sein Vorteil ist, dass damit eine Autokorrektur erstellt werden kann, um Wörter basierend auf dem Kontext zu korrigieren. Weitere Details zu diesem Ansatz finden Sie hier [ 13 ]. Um Tippfehler von Suchanfragen zu korrigieren, müssen Sie jedoch ein großes Protokoll von Suchanfragen erstellen. Darüber hinaus kann das Modell selbst hinsichtlich des Speicherverbrauchs sehr umfangreich sein, was sich auf die Komplexität der Integration in das Produkt auswirkt.

Naumen Wahl

Aus den vorgefertigten Lösungen für Java wurde eine Autokorrektur von Lucene ausgewählt (vertrieben unter einer Lizenz von Apache). Ermöglicht das Korrigieren von Tippfehlern in Worten. Der Lernprozess ist schnell: Beispielsweise betrug die Bildung einer speziellen Wörterbuchdatenstruktur - eines Index für 3 Millionen Zeilen - 30 Sekunden auf einem Intel Core i5-8500 3,00-GHz-Prozessor, 32 GB RAM, Lucene 8.0.0. In früheren Versionen kann die Zeit zweimal länger sein. Die Größe des Trainingswörterbuchs beträgt 3 Millionen Zeilen (~ 73 MB txt-Datei), die Indexstruktur beträgt ~ 235 MB. Für das Fehlermodell können Sie die Entfernung von Jaro-Winkler, Levenshtein, Damerau-Levenshtein, N-Gram wählen, bei Bedarf können Sie Ihre eigene hinzufügen. Bei Bedarf kann ein Sprachmodell angeschlossen werden [ 14 ]. Modelle sind seit 2001 bekannt, aber ihr Vergleich mit bekannten modernen Lösungen im öffentlichen Bereich wurde nicht gefunden. Der nächste Schritt ist die Überprüfung ihrer Arbeit.

Die resultierende Lucene-basierte Lösung korrigiert nur Fehler in den Wörtern selbst. Es ist nicht schwierig, eine Korrektur eines verzerrten Tastaturlayouts zu einer solchen Lösung mittels einer geeigneten Übersetzungstabelle hinzuzufügen, wodurch die Möglichkeit einer irrelevanten Ausgabe auf 10% reduziert wird (gemäß Tippfehlerstatistik). Darüber hinaus ist es einfach, das separate Schreiben von verschmolzenen 2 Wörtern und die Transliteration hinzuzufügen.

Die Hauptnachteile der Lösung sind die Notwendigkeit von Java-Kenntnissen, das Fehlen detaillierter Anwendungsfälle und detaillierter Dokumentation, was sich in einer Verringerung der Entwicklungsgeschwindigkeit von Lösungen für Data-Science-Spezialisten niederschlägt. Außerdem werden Tippfehler mit einem Damerau-Levenshtein-Abstand von mehr als 2 nicht korrigiert. Wenn wir von der Statistik der falschen Darstellung ausgehen, treten mehr als 2 Fehler in einem Wort seltener auf als in 5% der Fälle. Ist die Notwendigkeit, den Algorithmus zu komplizieren, insbesondere eine Erhöhung des Speicherverbrauchs, gerechtfertigt? Es kommt schon auf den Fall des Kunden an. Wenn es zusätzliche Ressourcen gibt, warum nicht?

Wichtige Ressourcen für erschwingliche Autokorrekturen :

Referenzen

Übersicht über Open Typo Correction Solutions

Qualitätskontrolle

Fertige Lösungen

Naumen Wahl

More articles: