Algorithmus zum Vergleichen von Wörtern (nicht alphabetisch)

Question

Ich muss eine Lösung für eine bestimmte Anforderung codieren, und ich wollte wissen, ob jemand entweder vertraut mit einer Bibliothek ist, die es erreichen kann, oder kann mich anleiten die beste Praxis Beschreibung:

Der Benutzer gibt ein Wort ein, das eine von mehreren festen Optionen sein soll (ich halte die Optionen in einer Liste). Ich weiß, dass die Eingabe in einem Mitglied in der Liste sein muss, aber da es Benutzereingaben sind, hat er möglicherweise einen Fehler gemacht. Ich suche nach einem Algorithmus, der mir sagt, was das wahrscheinlichste Wort ist, das der Benutzer meinte. Ich habe keinen Kontext und ich kann den Benutzer nicht zwingen, aus einer Liste zu wählen (d. H. Er muss das Wort frei und manuell eingeben können).

Zum Beispiel sagen die Liste enthält die Worte "Wasser", "Viertel", "Bier", "Rüben", "Hölle", "Hallo" und "Aardvark".

Die Lösung für verschiedene Arten von „normal“ Fehler Konto muss:

• Geschwindigkeit Tippfehler (zB Zeichen verdoppelt, Zeichen usw. dropping)
• Keyboard benachbarten Zeichen Fehler (zB „qater“ für „Wasser „)
• Non-native Englisch Tippfehler (zB "quater" für‚Viertel‘)
• Und so weiter ...

Die naheliegende Lösung besteht darin, Buchstabe für Buchstabe zu vergleichen und jedem einzelnen Buchstaben, jedem zusätzlichen Buchstaben und jedem fehlenden Buchstaben "Strafgewichte" zu geben. Aber diese Lösung ignoriert Tausende von "Standard" -Fehlern, von denen ich sicher bin, dass sie irgendwo aufgelistet sind. Ich bin mir sicher, dass es Heuristiken gibt, die sich mit allen spezifischen und allgemeinen Fällen befassen, wahrscheinlich mit einer großen Datenbank von Standard-Mismatches (ich bin offen für datenintensive Lösungen).

Ich bin in Python Codierung, aber ich halte diese Frage sprachunabhängig.

Irgendwelche Empfehlungen/Gedanken?

Answer 1

Sie lesen möchten, wie Google tut dies: http://norvig.com/spell-correct.html

Edit: Einige Leute haben erwähnt, Algorithmen, die eine Metrik zwischen einem Benutzer gegebenen Wort und einem Kandidatenwort (levenshtein, soundex) definieren. Dies ist jedoch keine vollständige Lösung des Problems, da man auch eine Datenstruktur benötigt, um eine Suche nach einem nicht euklidischen nächsten Nachbarn effizient durchzuführen. Dies kann z.B. mit dem Cover Tree: http://hunch.net/~jl/projects/cover_tree/cover_tree.html

Answer 2

Haben Sie Algorithmen in Betracht gezogen, die durch phonetische Laute vergleichen, wie soundex? Es sollte nicht zu schwer sein, Soundex-Repräsentationen Ihrer Wörterliste zu erstellen, sie zu speichern und dann einen Soundex der Benutzereingabe zu erhalten und die nächste Übereinstimmung dort zu finden.

Answer 3

Eine gängige Lösung ist die Levenshtein distance zwischen der Eingabe und Ihren festen Texten zu berechnen. Die Levenshtein-Distanz zweier Strings ist nur die Anzahl der einfachen Operationen - Einfügen, Löschen und Ersetzen eines einzelnen Zeichens -, die benötigt werden, um einen der Strings in den anderen zu verwandeln.

Answer 4

Obwohl es möglicherweise nicht das gesamte Problem löst, sollten Sie in Betracht ziehen, den soundex-Algorithmus als Teil der Lösung zu verwenden. Eine schnelle Google-Suche nach "soundex" und "python" zeigte einige Python-Implementierungen des Algorithmus.

Answer 5

Versuchen Sie, nach "Levenshtein distance" oder "edit distance" zu suchen.Er zählt die Anzahl der Bearbeitungsvorgänge (Löschen, Einfügen, Ändern des Buchstabens), die Sie benötigen, um ein Wort in ein anderes umzuwandeln. Es ist ein gebräuchlicher Algorithmus, aber abhängig von dem Problem benötigen Sie möglicherweise etwas Spezielles mit unterschiedlichen Gewichten für die verschiedenen Arten von Tippfehlern.

Answer 6

Suchen Sie nach dem Bitap-Algorithmus. Es eignet sich gut für das, was Sie tun möchten, und kommt sogar mit einem Quellcode-Beispiel in Wikipedia.

Answer 7

Wenn Ihr Datensatz wirklich klein ist, sollte der Vergleich der Levenshtein-Distanz für alle Elemente unabhängig sein. Wenn es jedoch größer ist, müssen Sie ein BK-Tree oder ein ähnliches Indizierungssystem verwenden. Der Artikel, mit dem ich verlinkt habe, beschreibt, wie man Übereinstimmungen innerhalb einer gegebenen Levenshtein-Entfernung findet, aber es ist relativ einfach, sich anzupassen, um die nächsten Nachbarn zu suchen (und als Übung für den Leser übrig gelassen wird;).