Wie meint Google "Meinten Sie?" Algorithmusarbeit?

436

Ich habe eine interne Website für ein Portfolio-Management-Tool entwickelt. Es gibt viele Textdaten, Firmennamen usw. Ich war wirklich beeindruckt von der Fähigkeit einiger Suchmaschinen, sehr schnell auf Anfragen mit "Meinten Sie: xxxx" zu antworten.

Ich muss in der Lage sein, eine Benutzeranfrage intelligent zu beantworten und nicht nur mit rohen Suchergebnissen zu antworten, sondern auch mit einem "Meinten Sie?" Antwort, wenn es eine sehr wahrscheinliche alternative Antwort gibt usw.

[Ich entwickle in ASP.NET (VB - halte es nicht gegen mich!)]

UPDATE: OK, wie kann ich dies ohne die Millionen von "unbezahlten Benutzern" nachahmen?

  • Tippfehler für jeden "bekannten" oder "richtigen" Begriff generieren und Suchvorgänge durchführen?
  • Eine andere elegantere Methode?
Andrew Harry
quelle
1
Hier ist die VB.NET-Version des Norvig Spelling Corrector. Sie können dies nützlich finden, wenn es nicht zu spät ist!
Ralph Wiggum
7
mögliches Duplikat von Wie implementieren Sie ein "Meinten Sie"?
Kurt McKee
Ich tippe auf einer Tastatur ohne QWERTY (Colemak) und die Funktion ist nicht halb so clever. Es lernt sicherlich aus aufgezeichneten Fehlerkorrekturpaaren und ist daher auf QWERTY eingestellt. Gewöhnliche Rechtschreibprüfungen funktionieren für meine Tastatur wie erwartet einwandfrei - der Abstand zum Bearbeiten von Zeichenfolgen ist layoutinvariant.
Colonel Panic

Antworten:

366

Hier ist die Erklärung direkt aus der Quelle (fast)

Suche 101!

um min 22:03

Sehenswert!

Grundsätzlich und laut Douglas Merrill, ehemaliger CTO von Google, ist es so:

1) Sie schreiben ein (falsch geschriebenes) Wort in Google

2) Sie finden nicht, was Sie wollten (klicken Sie nicht auf Ergebnisse)

3) Sie stellen fest, dass Sie das Wort falsch geschrieben haben, sodass Sie das Wort im Suchfeld neu schreiben.

4) Sie finden, was Sie wollen (Sie klicken in die ersten Links)

Dieses millionenfach vervielfachte Muster zeigt, was die häufigsten Rechtschreibfehler und was die "häufigsten" Korrekturen sind.

Auf diese Weise kann Google fast augenblicklich eine Rechtschreibkorrektur in jeder Sprache anbieten.

Dies bedeutet auch, wenn über Nacht jeder anfängt, die Nacht zu buchstabieren, da "nigth" Google stattdessen dieses Wort vorschlagen würde.

BEARBEITEN

@ ThomasRutter: Douglas beschreibt es als "statistisches maschinelles Lernen".

Sie wissen, wer die Abfrage korrigiert, weil sie wissen, welche Abfrage von welchem ​​Benutzer stammt (mithilfe von Cookies).

Wenn die Benutzer eine Abfrage durchführen und nur 10% der Benutzer auf ein Ergebnis klicken und 90% zurückgehen und eine andere Abfrage (mit dem korrigierten Wort) eingeben und diesmal 90% auf ein Ergebnis klicken, wissen sie, dass sie es gefunden haben eine Korrektur.

Sie können auch wissen, ob es sich um "verwandte" Abfragen von zwei verschiedenen handelt, da sie Informationen zu allen angezeigten Links haben.

Außerdem nehmen sie jetzt den Kontext in die Rechtschreibprüfung auf, sodass sie je nach Kontext sogar unterschiedliche Wörter vorschlagen können.

Sehen Sie sich diese Demo von Google Wave (@ 44m 06s) an, die zeigt, wie der Kontext berücksichtigt wird, um die Rechtschreibung automatisch zu korrigieren.

Hier wird erklärt, wie diese Verarbeitung natürlicher Sprache funktioniert.

Und schließlich ist hier eine großartige Demo dessen, was getan werden kann, indem der Mischung eine automatische maschinelle Übersetzung (@ 1h 12m 47s) hinzugefügt wird .

Ich habe den Videos Anker von Minuten und Sekunden hinzugefügt, um direkt zum Inhalt zu springen. Wenn sie nicht funktionieren, versuchen Sie, die Seite neu zu laden oder von Hand zur Marke zu scrollen.

OscarRyz
quelle
Wie funktioniert der Algorithmus? Wie geht Google von "Wir erhalten Milliarden von Suchanfragen mit verschiedenen Begriffen, und dies sind diese Suchanfragen" zu "Dieser Begriff muss daher ein häufiger Rechtschreibfehler dieses Begriffs sein"? Sie haben dieses Problem gelöst, aber ich bin daran interessiert, wie. Wie stellen sie fest, dass zwei Suchanfragen vom selben Benutzer stammen und welches Wort eine "Korrektur" eines anderen ist, und wie aggregieren sie dies über Milliarden von Suchanfragen?
Thomasrutter
51
Wenn alle anfingen, "Nacht" falsch zu schreiben ... Ich glaube, sie sind bereits auf Leute gestoßen, die nach "Flickr" suchten.
Max Lybbert
42
Das Problem, dass jeder etwas falsch geschrieben hat, ist bereits in einem viel schwerwiegenderen Sinne aufgetreten: Geben Sie "fuscia" in Google ein. Google sagt "Meinten Sie Fuschia?" Die korrekte Schreibweise ist in der Tat "Fuchsia", aber niemand kann sie aus irgendeinem Grund richtig buchstabieren. Das Problem ist auf Dictionary.com noch schlimmer. Wenn Sie "fuschia" in die Suche eingeben, erhalten Sie "Keine Ergebnisse für fuschia. Meinten Sie" fuschia "?" (dh meinten Sie, was Sie gerade getippt haben?)
Daisy Sophia Hollman
8
Ich glaube nicht, dass sie nur Rechtschreibfehler verwenden - es gibt definitiv eine Levenshtein-Distanz oder ähnliches -, nach 'Plack' (und einem oder mehreren anderen Wörtern) suchen und es wird immer zu 'Schwarz' korrigiert, was eine sehr unwahrscheinliche Rechtschreibfehler sind / Tippfehler
plusplus
4
@ Jakub Ich denke, sie haben das Problem behoben, seit ich diesen Kommentar vor mehr als 4 Jahren abgegeben habe. In der Tat hat Google auch das Problem behoben. Eine Suche nach Fuschia enthält automatisch Ergebnisse für Fuchsia.
Daisy Sophia Hollman
104

Ich habe diesen Artikel vor einiger Zeit gefunden: Wie man einen Rechtschreibkorrektor schreibt , geschrieben von Peter Norvig (Forschungsdirektor bei Google Inc.).

Es ist eine interessante Lektüre zum Thema "Rechtschreibkorrektur". Die Beispiele sind in Python, aber es ist klar und einfach zu verstehen, und ich denke, dass der Algorithmus leicht in andere Sprachen übersetzt werden kann.

Nachfolgend folgt eine kurze Beschreibung des Algorithmus. Der Algorithmus besteht aus zwei Schritten: Vorbereitung und Wortprüfung.

Schritt 1: Vorbereitung - Einrichten der Wortdatenbank

Am besten ist es, wenn Sie tatsächliche Suchwörter und deren Vorkommen verwenden können. Wenn Sie das nicht haben, kann stattdessen eine große Menge Text verwendet werden. Zählen Sie das Vorkommen (die Popularität) jedes Wortes.

Schritt 2. Wortprüfung - Suchen von Wörtern, die dem geprüften ähnlich sind

Ähnlich bedeutet, dass der Bearbeitungsabstand gering ist (normalerweise 0-1 oder 0-2). Der Bearbeitungsabstand ist die Mindestanzahl von Einfügungen / Löschungen / Änderungen / Swaps, die erforderlich sind, um ein Wort in ein anderes umzuwandeln.

Wählen Sie das beliebteste Wort aus dem vorherigen Schritt und schlagen Sie es als Korrektur vor (falls nicht das Wort selbst).

Davide Gualano
quelle
6
@Davide: "" Die Beispiele sind in Python, aber es ist klar und einfach zu verstehen. "": Ich verstehe Ihre Verwendung von "aber" nicht. Ich würde sagen, angesichts des Schreibstils von Python + Norvig "klar und" einfach zu verstehen "ist das erwartete Ergebnis.
John Machin
20
Das "aber" war da, weil Harry in seiner Frage sagte, dass er ein VB.NET-Entwickler ist, also nahm ich an, dass er mit der Python-Sprache nicht vertraut war.
Davide Gualano
56

Informationen zur Theorie des Algorithmus "Meinten Sie" finden Sie in Kapitel 3 der Einführung in das Abrufen von Informationen. Es ist kostenlos online verfügbar . Abschnitt 3.3 (Seite 52) beantwortet Ihre Frage genau. Und um Ihr Update speziell zu beantworten, benötigen Sie nur ein Wörterbuch mit Wörtern und nichts anderes (einschließlich Millionen von Benutzern).

Szere Dyeri
quelle
10

Hmm ... Ich dachte, dass Google seinen riesigen Datenbestand (das Internet) verwendet hat, um ernsthafte NLP (Natural Language Processing) durchzuführen.

Zum Beispiel haben sie so viele Daten aus dem gesamten Internet, dass sie zählen können, wie oft eine Drei-Wort-Sequenz auftritt (bekannt als Trigramm) ). Wenn sie also einen Satz wie "Pink Frugr Konzert" sehen, können sie sehen, dass er nur wenige Treffer hat, und dann das wahrscheinlichste "Pink * Konzert" in ihrem Korpus finden.

Anscheinend machen sie nur eine Variation dessen, was Davide Gualano sagte, also lesen Sie diesen Link auf jeden Fall. Google verwendet natürlich alle Webseiten, die es als Korpus kennt, so dass sein Algorithmus besonders effektiv ist.

Claudiu
quelle
7

Ich vermute, dass sie eine Kombination aus einem Levenshtein-Distanzalgorithmus und den Datenmengen verwenden, die sie in Bezug auf die durchgeführten Suchvorgänge sammeln. Sie könnten eine Reihe von Suchvorgängen mit dem kürzesten Levenshtein-Abstand von der eingegebenen Suchzeichenfolge abrufen und dann die mit den meisten Ergebnissen auswählen.

Jim Burger
quelle
6
Angenommen, Sie haben insgesamt Wörter im Wert von Milliarden von Webseiten gespeichert. Es gibt keine einfache Möglichkeit, die Levenshtein-Entfernung zu indizieren, um nahe Übereinstimmungen schnell abzurufen, ohne die Levenshtein-Entfernung für jedes abgefragte Wort milliardenfach zu berechnen. Die Levenshtein-Entfernung ist daher in dieser Situation nicht von großem Nutzen, zumindest nicht in der ersten Phase, in der Google von Milliarden vorhandener Wörter auf diejenigen Wörter eingrenzen muss, bei denen es sich wahrscheinlich um Rechtschreibfehler des aktuellen Wortes handelt. Es kann Levenshtein definitiv als späteren Schritt anwenden, sobald es bereits wahrscheinliche Übereinstimmungen erzielt hat.
Thomasrutter
6

Normalerweise verwendet ein Produktions-Rechtschreibkorrektor mehrere Methoden, um einen Rechtschreibvorschlag zu liefern. Einige sind:

  • Entscheiden Sie, wie Sie feststellen möchten, ob eine Rechtschreibkorrektur erforderlich ist. Dies kann unzureichende Ergebnisse, Ergebnisse, die nicht spezifisch oder genau genug sind (je nach Maß) usw. umfassen. Dann:

  • Verwenden Sie einen großen Textkörper oder ein Wörterbuch, in dem alle oder die meisten bekanntermaßen richtig geschrieben sind. Diese sind online leicht zu finden, beispielsweise in LingPipe . Um den besten Vorschlag zu ermitteln, suchen Sie nach einem Wort, das auf der Grundlage mehrerer Kennzahlen am ehesten übereinstimmt. Das intuitivste sind ähnliche Zeichen. Durch Forschung und Experimente wurde gezeigt, dass zwei oder drei Zeichenfolge-Übereinstimmungen besser funktionieren. (Bigramme und Trigramme). Um die Ergebnisse weiter zu verbessern, wägen Sie eine höhere Punktzahl bei einem Spiel am Anfang oder Ende des Wortes ab. Indizieren Sie aus Leistungsgründen alle diese Wörter als Trigramme oder Bigramme, sodass Sie beim Durchführen einer Suche in n-Gramm konvertieren und über eine Hashtabelle oder einen Versuch suchen.

  • Verwenden Sie Heuristiken in Bezug auf mögliche Tastaturfehler basierend auf der Position des Zeichens. Also sollte "hwllo" "Hallo" sein, weil "w" in der Nähe von "e" liegt.

  • Verwenden Sie eine phonetische Taste (Soundex, Metaphone), um die Wörter zu indizieren und mögliche Korrekturen nachzuschlagen. In der Praxis liefert dies normalerweise schlechtere Ergebnisse als die Verwendung der n-Gramm-Indizierung, wie oben beschrieben.

  • In jedem Fall müssen Sie die beste Korrektur aus einer Liste auswählen. Dies kann eine Abstandsmetrik wie Levenshtein, die Tastaturmetrik usw. sein.

  • Bei einer Phrase mit mehreren Wörtern darf nur ein Wort falsch geschrieben sein. In diesem Fall können Sie die verbleibenden Wörter als Kontext verwenden, um die beste Übereinstimmung zu ermitteln.

eulerfx
quelle
6

Verwenden Sie den Levenshtein-Abstand und erstellen Sie dann einen metrischen Baum (oder schlanken Baum), um Wörter zu indizieren. Führen Sie dann eine 1-Nearest Neighbor-Abfrage aus, und Sie erhalten das Ergebnis.

Nicolas Dorier
quelle
4

Google schlägt anscheinend Abfragen mit den besten Ergebnissen vor, nicht mit solchen, die richtig geschrieben sind. Aber in diesem Fall wäre wahrscheinlich eine Rechtschreibkorrektur praktikabler. Natürlich könnten Sie für jede Abfrage einen Wert speichern, basierend auf einer Metrik, wie gute Ergebnisse zurückgegeben werden.

Damit,

  1. Sie benötigen ein Wörterbuch (Englisch oder basierend auf Ihren Daten)

  2. Generieren Sie ein Wortgitter und berechnen Sie die Wahrscheinlichkeiten für die Übergänge mithilfe Ihres Wörterbuchs.

  3. Fügen Sie einen Decoder hinzu, um die minimale Fehlerentfernung mit Ihrem Gitter zu berechnen. Natürlich sollten Sie bei der Berechnung der Entfernungen auf Einfügungen und Löschungen achten. Eine lustige Sache ist, dass die QWERTZ-Tastatur die Entfernung maximiert, wenn Sie Tasten nahe beieinander drücken. (Cae würde das Auto drehen, Cay würde die Katze drehen.)

  4. Geben Sie das Wort mit dem Mindestabstand zurück.

  5. Dann können Sie das mit Ihrer Abfragedatenbank vergleichen und prüfen, ob es bessere Ergebnisse für andere enge Übereinstimmungen gibt.

Geee
quelle
4

Hier ist die beste Antwort, die ich gefunden habe : Rechtschreibkorrektur implementiert und beschrieben von Googles Forschungsdirektor Peter Norvig.

Wenn Sie mehr über die Theorie dahinter lesen möchten, können Sie sein Buchkapitel lesen .

Die Idee dieses Algorithmus basiert auf statistischem maschinellem Lernen.

Aziz Alto
quelle
3

Ich habe vor ein paar Jahren etwas dazu gesehen, das sich vielleicht seitdem geändert hat, aber anscheinend haben sie damit begonnen, ihre Protokolle für dieselben Benutzer zu analysieren, die in kurzer Zeit sehr ähnliche Anfragen stellten, und maschinelles Lernen basierend auf der Art und Weise verwendet, wie Benutzer korrigiert hatten sich.

Seanb
quelle
3

Als Vermutung ... könnte es

  1. Suche nach Wörtern
  2. Wenn es nicht gefunden wird, verwenden Sie einen Algorithmus, um zu versuchen, das Wort zu "erraten".

Könnte etwas von der KI sein, wie das Hopfield-Netzwerk oder das Back-Propagation-Netzwerk, oder etwas anderes, das "Fingerabdrücke identifiziert", fehlerhafte Daten wiederherstellt oder Rechtschreibkorrekturen vornimmt, wie Davide bereits erwähnt hat ...

Paul Kapustin
quelle
2

Einfach. Sie haben Tonnen von Daten. Sie haben Statistiken für jeden möglichen Begriff, basierend darauf, wie oft er abgefragt wird und welche Variationen davon normalerweise zu Ergebnissen führen, auf die die Benutzer klicken. Wenn sie also sehen, dass Sie häufig einen Rechtschreibfehler für einen Suchbegriff eingegeben haben, schlagen sie vor die üblichere Antwort.

Wenn der Rechtschreibfehler tatsächlich der am häufigsten gesuchte Begriff ist, wird er vom Algorithmus als der richtige angesehen.

schonarth
quelle
1
Niemand hat daran gezweifelt, dass Google über alle erforderlichen Daten verfügt, aber die Frage lautete, wie Google einen Algorithmus entwickelt hat, um dies mit so vielen Daten in angemessener Zeit zu tun. Sie würden täglich unzählige Suchanfragen durchführen - wie können sie leicht erkennen, ob ein Suchbegriff eine "Rechtschreibkorrektur" eines anderen, neueren Begriffs ist? Welche Faktoren lassen Google entscheiden, dass ein Begriff ein Rechtschreibfehler eines anderen ist? Dies sind Implementierungsdetails, die von Interesse wären.
Thomasrutter
2

zu Ihrer Frage, wie Sie das Verhalten nachahmen können, ohne Tonnen von Daten zu haben - warum nicht Tonnen von Daten verwenden, die von Google gesammelt wurden? Laden Sie die Google Sarch-Ergebnisse für das falsch geschriebene Wort herunter und suchen Sie im HTML- Code nach " Meinten Sie:".

Ich denke, das nennt man heutzutage Mashup :-)

Tomas Petricek
quelle
Wie lange dauert es, bis Google Ihren Bot vom Scraping abhält? - oder würde Google es heutzutage gar nicht bemerken?
Andrew Harry
Ich glaube nicht, dass sie es bemerken werden, wenn die Anforderungen / Sek. Nicht zu hoch sind.
Mauricio Scheffer
2

Abgesehen von den obigen Antworten, hier ist ein Vorschlag, falls Sie etwas schnell selbst implementieren möchten -

Algorithmus

Die Implementierung und detaillierte Dokumentation dieses Algorithmus finden Sie auf GitHub .

  • Erstellen Sie eine Prioritätswarteschlange mit einem Komparator.
  • Erstellen Sie einen Ternay-Suchbaum und fügen Sie alle englischen Wörter (aus Norvigs Beitrag ) zusammen mit ihren Häufigkeiten ein.
  • Beginnen Sie mit dem Durchlaufen des TST und berechnen Sie für jedes in TST angetroffene Wort den Levenshtein-Abstand ( LD ) aus input_word
  • Wenn LD ≤ 3 ist, legen Sie es in eine Prioritätswarteschlange.
  • Zuletzt 10 Wörter aus der Prioritätswarteschlange extrahieren und anzeigen.
amarjeetAnand
quelle
1

Sie wollen Rechtschreibprüfung sagen? Wenn es sich eher um eine Rechtschreibprüfung als um eine ganze Phrase handelt, habe ich einen Link zur Rechtschreibprüfung, bei der der Algorithmus in Python entwickelt wird. Überprüfen Sie diesen Link

Mittlerweile arbeite ich auch an einem Projekt, bei dem Datenbanken mit Text durchsucht werden. Ich denke, das würde dein Problem lösen

Jimit Patel
quelle
1

Dies ist eine alte Frage, und ich bin überrascht, dass niemand das OP mit Apache Solr vorgeschlagen hat.

Apache Solr ist eine Volltextsuchmaschine, die neben vielen anderen Funktionen auch Rechtschreibprüfung oder Abfragevorschläge bietet. Aus der Dokumentation :

Standardmäßig sortieren die Lucene-Rechtschreibprüfer Vorschläge zuerst nach der Punktzahl aus der Berechnung des Zeichenfolgenabstands und zweitens nach der Häufigkeit (falls verfügbar) des Vorschlags im Index.

Josep Valls
quelle
0

Es gibt eine spezifische Datenstruktur - den ternären Suchbaum -, die natürlich Teilübereinstimmungen und Übereinstimmungen mit nahen Nachbarn unterstützt.


quelle
-1

Der einfachste Weg, dies herauszufinden, ist die dynamische Programmierung von Google.

Es ist ein Algorithmus, der von Information Retrieval entlehnt wurde und in der modernen Bioinformatik häufig verwendet wird, um zu sehen, wie ähnlich zwei Gensequenzen sind.

Die optimale Lösung verwendet dynamische Programmierung und Rekursion.

Dies ist ein sehr gelöstes Problem mit vielen Lösungen. Google einfach herum, bis du Open Source Code findest.

erwacht
quelle