Wie setzt man ein „Meinten Sie“ um?[Duplikat]

https://stackoverflow.com/questions/41424

09-06-2019
|

Frage

Mögliches Duplikat:
Wie bedeutet das Google "meinst du?" Algorithmusarbeit?

Angenommen, Sie verfügen bereits über ein Suchsystem auf Ihrer Website.Wie können Sie das „Meinten Sie:<spell_checked_word>" wie Google es in einigen Fällen tut Suchanfragen?

Lösung

Tatsächlich ist das, was Google tut, alles andere als trivial und auch zunächst kontraintuitiv.Sie führen keine Vergleichsprüfung mit einem Wörterbuch durch, sondern nutzen Statistiken, um „ähnliche“ Abfragen zu identifizieren, die mehr Ergebnisse als Ihre Abfrage lieferten. Der genaue Algorithmus ist natürlich nicht bekannt.

Hier müssen verschiedene Teilprobleme gelöst werden. Als grundlegende Grundlage für alle Statistiken zur Verarbeitung natürlicher Sprache gibt es ein Buch, das unbedingt vorhanden sein muss: Grundlage der statistischen Verarbeitung natürlicher Sprache.

Konkret habe ich mit der Verwendung gute Ergebnisse erzielt, um das Problem der Wort-/Abfrageähnlichkeit zu lösen Entfernung bearbeiten, ein mathematisches Maß für die Ähnlichkeit von Zeichenfolgen, das überraschend gut funktioniert.Früher habe ich Levenshtein verwendet, aber die anderen könnten einen Blick wert sein.

Soundex ist meiner Erfahrung nach Mist.

Tatsächlich ist das effiziente Speichern und Durchsuchen eines großen Wörterbuchs mit falsch geschriebenen Wörtern und der Abruf in weniger als einer Sekunde wiederum nicht trivial. Am besten nutzen Sie vorhandene Volltextindizierungs- und Abruf-Engines (d. h.nicht die Ihrer Datenbank), davon Lucene ist derzeit eines der besten und wurde zufällig auf viele, viele Plattformen portiert.

Andere Tipps

Dr. Norvig von Google hat erläutert, wie es funktioniert.er gibt sogar eine 20-Zeilen-Python-Implementierung:

http://googlesystem.blogspot.com/2007/04/simplified-version-of-googles-spell.html

http://www.norvig.com/spell-correct.html

Dr. Norvig erörtert auch das „Meinten Sie?“ in dieser hervorragende Vortrag.Dr. Norvig ist Leiter der Forschung bei Google – auf die Frage, wie „Meinten Sie?“ umgesetzt wird, lautet seine Antwort maßgeblich.

Es handelt sich also um eine Rechtschreibprüfung, vermutlich mit einem dynamischen Wörterbuch, das aus anderen Suchanfragen oder sogar tatsächlichen Internetphrasen usw. erstellt wurde.Aber das ist immer noch so Rechtschreibprüfung.

SOUNDEX und andere Vermutungen kommen nicht rein, Leute!

Überprüfen Das Artikel auf Wikipedia über die Levenshtein-Distanz.Schauen Sie sich unbedingt die möglichen Verbesserungen genau an.

Ich war angenehm überrascht, dass jemand gefragt hat, wie man ein hochmodernes Rechtschreibvorschlagssystem für Suchmaschinen erstellt.Ich arbeite seit mehr als einem Jahr für ein Suchmaschinenunternehmen an diesem Thema und kann auf öffentlich zugängliche Informationen zu diesem Thema verweisen.

Wie bereits in einem früheren Beitrag erwähnt, verwenden Google (sowie Microsoft und Yahoo!) kein vordefiniertes Wörterbuch und beschäftigen auch keine Horden von Linguisten, die über mögliche Rechtschreibfehler bei Suchanfragen nachdenken.Dies wäre aufgrund des Ausmaßes des Problems unmöglich, aber auch, weil nicht klar ist, ob die Leute tatsächlich richtig erkennen können, wann und ob eine Suchanfrage falsch geschrieben ist.

Stattdessen gibt es ein einfaches und durchaus wirksames Prinzip, das auch für alle europäischen Sprachen gilt.Erhalten Sie alle eindeutigen Abfragen in Ihren Suchprotokollen und berechnen Sie den Bearbeitungsabstand zwischen allen Abfragepaaren unter der Annahme, dass die Referenzabfrage diejenige mit der höchsten Anzahl ist.

Dieser einfache Algorithmus eignet sich hervorragend für viele Arten von Abfragen.Wenn Sie die nächste Stufe erreichen möchten, empfehle ich Ihnen, den Artikel von Microsoft Research zu diesem Thema zu lesen.Du kannst es finden Hier

Das Papier hat eine tolle Einleitung, aber danach müssen Sie sich mit Konzepten wie dem Hidden-Markov-Modell auskennen.

Ich würde vorschlagen, einen Blick darauf zu werfen SOUNDEX um ähnliche Wörter in Ihrer Datenbank zu finden.

Sie können auch auf das Google-eigene Wörterbuch zugreifen, indem Sie das verwenden Anfrage für einen Rechtschreibvorschlag für die Google API.

Vielleicht möchten Sie sich Peter Norvigs „So schreiben Sie einen Rechtschreibkorrektor" Artikel.

Ich glaube, dass Google alle Anfragen protokolliert und erkennt, wenn jemand eine Rechtschreibkorrektur vornimmt.Diese Korrektur kann dann vorgeschlagen werden, wenn andere die gleiche erste Anfrage stellen.Dies funktioniert für jede Sprache, tatsächlich für jede beliebige Zeichenfolge.

http://en.wikipedia.org/wiki/N-gram#Google_use_of_N-gram

Ich denke, das hängt davon ab, wie groß Ihre Website ist.In unserem lokalen Intranet, das von etwa 500 Mitarbeitern genutzt wird, schaue ich mir einfach die Suchphrasen an, die keine Ergebnisse lieferten, und gebe diese Suchphrase mit der neuen vorgeschlagenen Suchphrase in eine SQL-Tabelle ein.

Ich rufe diese Tabelle auf, wenn keine Suchergebnisse zurückgegeben wurden. Dies funktioniert jedoch nur, wenn die Website relativ klein ist, und ich mache es nur für Suchbegriffe, die am häufigsten vorkommen.

Vielleicht möchten Sie auch meine Antwort auf eine ähnliche Frage lesen:

„Ähnliche Beiträge“ wie Funktionalität mit MS SQL Server?

Wenn Sie branchenspezifische Übersetzungen haben, benötigen Sie wahrscheinlich einen Thesaurus.Ich habe zum Beispiel in der Schmuckindustrie gearbeitet und in unseren Beschreibungen gab es Abkürzungen wie kt – Karat, rd – rund, cwt – Karatgewicht …Endeca (die Suchmaschine für diesen Job) verfügt über einen Thesaurus, der häufige Rechtschreibfehler übersetzt, aber es erfordert manuelles Eingreifen.

Ich mache es mit Lucene'S Rechtschreibprüfung.

Soundex eignet sich gut für phonetische Übereinstimmungen, funktioniert aber am besten mit Personennamen (ursprünglich wurde es für Volkszählungsdaten entwickelt).

Schauen Sie sich auch die Volltextindizierung an. Die Syntax unterscheidet sich von der Google-Logik, ist aber sehr schnell und kann mit ähnlichen Sprachelementen umgehen.

Soundex und „Porter-Stemming“ (Soundex ist trivial, bei Porter-Stemming bin ich mir nicht sicher).

Es gibt etwas namens Aspell, das helfen könnte:http://blog.evanweaver.com/files/doc/fauna/raspell/classes/Aspell.html

Es gibt einen Rubinstein dafür, aber ich weiß nicht, wie ich von Python aus damit kommunizieren sollhttp://blog.evanweaver.com/files/doc/fauna/raspell/files/README.html

Hier ist ein Zitat aus der Ruby-Implementierung

Verwendung

Mit Aspell können Sie Wörter überprüfen und Korrekturen vorschlagen.Zum Beispiel:

  string = "my haert wil go on"

  string.gsub(/[\w\']+/) do |word|
    if !speller.check(word)
      # word is wrong
      puts "Possible correction for #{word}:"
      puts speller.suggest(word).first
    end
  end

Dies gibt aus:

Mögliche Korrektur für haert:Herz mögliche Korrektur für Wil:Wille

Die effektive Implementierung einer Rechtschreibkorrektur für Suchmaschinen ist nicht trivial (man kann nicht einfach den Edit/Levenshtein-Abstand zu jedem möglichen Wort berechnen).Eine auf k-Gramm-Indizes basierende Lösung ist in beschrieben Einführung in die Informationsbeschaffung (Volltext online verfügbar).

Sie könnten ngram für den Vergleich verwenden: http://en.wikipedia.org/wiki/N-gram

Verwenden des Python-Ngram-Moduls: http://packages.python.org/ngram/index.html

import ngram

G2 = ngram.NGram([  "iis7 configure ftp 7.5",
                    "ubunto configre 8.5",
                    "mac configure ftp"])

print "String", "\t", "Similarity"
for i in G2.search("iis7 configurftp 7.5", threshold=0.1):
    print i[1], "\t", i[0]

Du bekommst:

>>> 
String  Similarity
0.76    "iis7 configure ftp 7.5"    
0.24    "mac configure ftp"
0.19    "ubunto configre 8.5"

Warum nicht Googles verwenden, meinten Sie in Ihrem Code? Informationen dazu finden Sie hierhttp://narenonit.blogspot.com/2012/08/trick-for-using-googles-did-you-mean.html

Lizenziert unter: CC-BY-SA mit Zuschreibung

Nicht verbunden mit StackOverflow