Wie funktioniert das Google "Meintest du?" Algorithmus arbeiten?
Ich habe die Entwicklung einer internen Webseite für ein portfolio-management-tool. Es gibt eine Menge von text, Daten, Firmen usw. Ich habe wirklich sehr beeindruckt von einigen Suchmaschinen die Möglichkeit, um sehr schnell reagieren zu Abfragen, die mit "meinten Sie: xxxx".
Ich muss in der Lage sein, intelligent zu nehmen, die ein Benutzer Abfragen und reagieren Sie nicht nur mit raw-Suchergebnisse, sondern auch mit einer "meinten Sie?" - Antwort, wenn es ist sehr wahrscheinlich alternative Antwort etc
[Ich bin in der Entwicklung in ASP.NET (VB - don ' T hold it against me! )]
UPDATE:
OK, wie kann ich imitieren, ohne die Millionen von " unbezahlte Nutzer?
- Tippfehler generiert für jedes 'bekannt' oder 'korrekte' Begriff und Suchvorgänge ausführen?
- Einige andere, elegantere Methode?
InformationsquelleAutor der Frage Andrew Harry | 2008-11-20
Du musst angemeldet sein, um einen Kommentar abzugeben.
Hier ist die Erklärung direkt von der Quelle ( fast )
Suche nach 101!
min 22:03
Sehenswert!
Grundsätzlich und nach Douglas Merrill ehemaliger CTO von Google ist es so:
1) schreiben Sie eine ( falsch geschriebene ) Wort in google
2) Sie nicht finden, was Sie möchten ( klicken Sie nicht auf alle Ergebnisse )
3) Sie erkennen, dass Sie falsch geschrieben das Wort, damit Sie umschreiben das Wort in das Suchfeld ein.
4) finden Sie, was Sie wollen ( Sie klicken in die erste links )
Dieses Muster multipliziert sich millionenfach, zeigt, was sind die häufigsten misspells und was sind die "üblichen" Korrekturen.
Diese Weise kann Google fast augenblicklich, bieten Rechtschreib-Korrektur in jeder Sprache.
Auch dies bedeutet, dass wenn über Nacht jeder beginnen, Zauber der Nacht, wie "Nachtruhe" google würde vorschlagen, das Wort statt.
BEARBEITEN
@ThomasRutter: Douglas beschreibt es als "statistische maschinelle lernen".
Wissen Sie, korrigieren Sie die Abfrage, weil Sie wissen, dass die Abfrage kommt, von dem Benutzer ( über cookies )
Wenn der Benutzer beim ausführen einer Abfrage, und nur 10% der Nutzer klicken auf ein Ergebnis, und 90% geht zurück, und geben Sie eine andere Abfrage ( das korrigierte Wort ) und dieses mal, dass 90% der Klicks auf ein Ergebnis, dann wissen Sie, dass Sie gefunden haben, eine Korrektur.
Können Sie auch wissen, ob diese "Verwandte" Suchanfragen von zwei verschiedenen, weil Sie Informationen von allen links, die Sie zeigen.
Darüber hinaus sind Sie jetzt auch den Kontext, in dem die Rechtschreibprüfung, so kann Sie auch empfehlen, ein anderes Wort, je nach Kontext.
Sehen diese demo von google wave ( @ 44m 06s ), die zeigt, wie der Kontext berücksichtigt wird, automatisch korrigieren Sie die Rechtschreibung.
Hier es wird erklärt, wie das mit der Verarbeitung natürlicher Sprache funktioniert.
Und schließlich, hier ist eine tolle demo, was getan werden kann hinzufügen automatische maschinelle übersetzung ( @ 1h 12m 47er ) auf die Mischung.
Ich habe Anker in Minuten und Sekunden, um die videos zu überspringen, direkt zum Inhalt, wenn Sie nicht arbeiten, versuchen Sie, die Seite neu zu laden oder scrollen von hand zu markieren.
InformationsquelleAutor der Antwort
Fand ich diesen Artikel vor einiger Zeit: How to Write a Rechtschreibung Korrektorgeschrieben von Peter Norvig (Forschungsdirektor bei Google Inc.).
Es ist eine interessante Lektüre über die "Rechtschreib-Korrektur" Thema. Die Beispiele sind in Python, aber es ist klar und einfach zu verstehen, und ich denke, dass der Algorithmus kann leicht
in andere Sprachen übersetzt.
Unten folgt eine kurze Beschreibung des Algorithmus.
Der Algorithmus besteht aus zwei Schritten, der Vorbereitung und word Prüfung.
Schritt 1: Vorbereitung - Aufbau des word-Datenbank
Beste ist, wenn Sie verwenden die tatsächlichen Suchbegriffe und deren auftreten.
Wenn du das nicht hast, eine große Menge von text verwendet werden können, statt.
Zählen der vorkommen (Beliebtheit) von jedem Wort.
Schritt 2. Word-überprüfen - Suche nach Wörtern, die ähnlich zu der aufgegebenen
Ähnlich bedeutet, dass die edit-Distanz gering ist (in der Regel 0-1 oder 0-2). Die edit-Distanz ist die minimale Anzahl von Einfügungen/Löschungen/änderungen/swaps transformieren mussten, ein Wort nach dem anderen.
Wählen Sie das beliebteste Wort, das aus dem vorherigen Schritt und schlage vor, es als eine Korrektur (wenn andere als das Wort selbst).
InformationsquelleAutor der Antwort Davide Gualano
Für die Theorie der "meinten Sie" - Algorithmus finden Sie in Kapitel 3 der Einführung in Information Retrieval. Es ist verfügbar online kostenlos. Abschnitt 3.3 (Seite 52) genau Ihre Frage beantwortet. Und konkret zu beantworten, das update brauchen Sie nur ein Wörterbuch der Wörter und sonst nichts (einschließlich Millionen von Nutzern).
InformationsquelleAutor der Antwort Szere Dyeri
Hmm... ich dachte, dass google verwendet Ihre riesigen Korpus von Daten (internet) zu tun einige ernsthafte NLP (Natural Language Processing).
Zum Beispiel, haben Sie so viele Daten aus der ganzen internet, die Sie können die Anzahl der Zeiten, die eine drei-Wort-Sequenz Auftritt (bekannt als Zeichen). Also, wenn Sie sehen, ein Satz wie: "rosa frugr Konzert", konnten Sie sehen, hat es einige erwischt, dann finden die meisten wahrscheinlich "pink * Konzert" in Ihrem Korpus.
Sind Sie scheinbar nur tun, eine variation von dem, was Davide Gualano war zu sagen, obwohl, so dass es auf jeden Fall Lesen, der link. Google hat natürlich die Nutzung aller web-Seiten, die es weiß, wie ein Korpus, also der Algorithmus, mit dem besonders effektiv.
InformationsquelleAutor der Antwort Claudiu
Meine Vermutung ist, dass Sie verwenden eine Kombination aus einem Die Levenshtein-Distanz Algorithmus und die Massen von Daten, die Sie sammeln in Bezug auf die sucht, die ausgeführt werden. Sie könnte ziehen eine Reihe von Suchanfragen, die haben die kürzeste Levenshtein-Distanz aus den eingegebenen Suchbegriff haben, dann Holen Sie die meisten Ergebnisse.
InformationsquelleAutor der Antwort Jim Burger
Normalerweise eine Produktion Rechtschreib-Korrektor nutzt mehrere Methoden, um eine Rechtschreib-Vorschlag. Einige sind:
Entscheiden, auf einem Weg, um zu bestimmen, ob die Korrektur der Rechtschreibung erforderlich ist. Diese können beinhalten, sind Unzureichende Ergebnisse, Ergebnisse, die nicht spezifisch oder genau genug (nach einigen Maßnahmen), etc. Dann:
Verwenden Sie eine große Menge von text oder ein Wörterbuch, wo alle, oder die meisten sind bekannt, werden richtig geschrieben. Diese sind leicht zu finden online, in Orten wie LingPipe. Dann, um zu bestimmen, den besten Vorschlag, Sie suchen ein Wort, das ist die nächste übereinstimmung, basierend auf mehrere Maßnahmen. Die intuitive eine ähnlich Zeichen. Was hat sich gezeigt, durch Forschung und Experimente ist, dass zwei oder drei-Zeichen-Sequenz entspricht, besser zu arbeiten. (bigrame und Trigramme). Zur weiteren Verbesserung der Ergebnisse, Wiegen Sie eine höhere Punktzahl auf eine übereinstimmung am Anfang oder Ende des Wortes. Aus Gründen der performance-index alle diese Worte als Trigramme oder bigrame, so dass, wenn Sie nachschlagen, konvertieren Sie zu n-Gramm-und lookup via hashtable-oder trie.
Verwenden Heuristiken in Bezug auf mögliche Tastatur-Fehler basierend auf dem Standort der Figur. So, die "hwllo" sollte "Hallo", weil 'w' in der Nähe '- e'.
Verwendung eines phonetischen Schlüssel (Soundex, Metaphone) index der Wörter und lookup mögliche Korrekturen. In der Praxis wird diese Regel gibt schlechtere Ergebnisse als die Verwendung von n-Gramm-Indizierung, wie oben beschrieben.
In jedem Fall müssen Sie wählen Sie die beste Korrektur aus einer Liste. Dies kann eine Distanz-Metrik wie dem levenshtein, der Tastatur, Metrisch, usw.
Für ein multi-Wort-Satz, nur ein Wort kann falsch geschrieben sein, in dem Fall können Sie die übrigen Wörter, die als Kontext bei der Bestimmung der besten übereinstimmung.
InformationsquelleAutor der Antwort eulerfx
Verwenden Die Levenshtein-Distanzdann erstellen Sie einen Metrik-Baum (oder Slim-Baum) - index-Wörter.
Führen Sie dann eine 1-Nearest Neighbour query, und du hast das Ergebnis.
InformationsquelleAutor der Antwort Nicolas Dorier
Google offenbar schlägt Abfragen mit den besten Ergebnissen, nicht mit denen, die korrekt geschrieben sind. Aber in diesem Fall, wahrscheinlich ein Zauber-Korrektor wäre mehr machbar, könnten Sie speichern einen Wert für jede Abfrage, basierend auf der Metrik, wie gut die Ergebnisse, die zurückgegeben werden.
So,
Benötigen Sie ein Wörterbuch (Englisch oder basierend auf Ihren Daten)
Generiert ein word-Gitter, und berechnen Sie die Wahrscheinlichkeiten für die übergänge mit Ihrem Wörterbuch.
Hinzufügen eines Decoders zu berechnen minimale Fehler aus der Entfernung mit Ihrem Spalier. Natürlich sollten Sie darauf achten, von Insertionen und Deletionen bei der Berechnung von Entfernungen. Lustige Sache ist, dass die QWERTZ-Tastatur maximiert den Abstand, wenn Sie drücken Sie die Tasten nahe beieinander.(cae drehen würde, Auto, cay drehen würde, Katze)
Zurück das Wort, das den minimalen Abstand.
Dann könnte man vergleichen, dass Ihre Datenbank-Abfrage und prüfen, ob es bessere Ergebnisse für andere enge Spiele.
InformationsquelleAutor der Antwort Geee
Hier ist die beste Antwort, die ich gefunden -, Rechtschreib-Korrektor implementiert und beschrieben durch Google-Forschungsdirektor Peter Norvig.
Wenn Sie möchten, um mehr über die Theorie hinter diesem ist, können Sie Lesen sein Buch Kapitel.
Die Idee dieses Algorithmus basiert auf der statistischen maschinellen Lernens.
InformationsquelleAutor der Antwort Aziz Alto
bezüglich Ihrer Frage, wie Sie imitieren das Verhalten, ohne Tonnen von Daten - warum nicht Tonnen von Daten, die von google? Laden Sie die google-such dir Ergebnisse für die falsch geschriebene Wort und suchen Sie nach "meinten Sie:" in den HTML-Code.
Ich denke, das nennt man mashup heute 🙂
InformationsquelleAutor der Antwort Tomas Petricek
Als eine Vermutung... könnte es
Könnte etwas aus AI wie Hopfield-Netzwerk oder das Backpropagation-Netzwerk, oder etwas anderes "erkennen von Fingerabdrücken", wiederherstellen gebrochen Daten, oder Rechtschreibkorrekturen als Davide bereits erwähnt ...
InformationsquelleAutor der Antwort badbadboy
Sah ich etwas auf diese ein paar Jahre zurück, so haben sich seitdem geändert, aber anscheinend haben Sie es begonnen, durch die Analyse Ihrer Protokolle für den gleichen Benutzern Abgabe sehr ähnliche Abfragen in kurzer Zeit, und verwendet maschinelles lernen, basierend auf, wie Benutzer korrigiert sich selbst.
InformationsquelleAutor der Antwort seanb
Einfach. Sie haben Tonnen von Daten. Haben Sie Statistiken für jeden möglichen Begriff, auf der Grundlage, wie oft es abgefragt wird, und welche Variationen es in der Regel zu Ergebnissen führen, die den Anwender auf... so, wenn Sie sehen, Sie haben einen häufigen Rechtschreibfehler, die für einen Suchbegriff, der Sie voran gehen und vorschlagen, die übliche Antwort.
Eigentlich, wenn der Rechtschreibfehler ist in der Tat der am häufigsten gesuchte Begriff, den algorythm wird es dauern, bis der richtige.
InformationsquelleAutor der Antwort schonarth
Du damit sagen, das die Rechtschreibprüfung? Wenn es eine Rechtschreibprüfung, anstatt einen ganzen Satz, dann habe ich eine link über die Rechtschreibprüfung in denen der Algorithmus wird in python entwickelt. Überprüfen Sie dieser link
Inzwischen, ich arbeite auch an einem Projekt, das beinhaltet die Suche nach Datenbanken mit text. Ich denke, das würde Ihr problem lösen
InformationsquelleAutor der Antwort Jimit Patel
Abgesehen von den oben genannten Antworten, in Fall, dass Sie wollen etwas umsetzen, indem Sie sich schnell, hier ist ein Vorschlag -
Algorithmus
Finden Sie die Umsetzung und die detaillierte Dokumentation dieser Algorithmus auf GitHub.
InformationsquelleAutor der Antwort amarjeetAnand
Einfachste Weg, um es herauszufinden, ist Google bei der dynamischen Programmierung.
Es ist ein Algorithmus, der war geliehen von Information Retrieval und wird intensiv genutzt, im modernen Bioinformatik zu sehen, wie ähnlich sich zwei gen-Sequenzen sind.
Optimale Lösung verwendet dynamische Programmierung und Rekursion.
Dies ist eine sehr gelöste problem mit vielen Lösungen. Google einfach herum, bis Sie finden einige open-source-code.
InformationsquelleAutor der Antwort ewakened
Gibt es eine bestimmte Datenstruktur - ternären Suchbaum - natürlich unterstützt teilweise übereinstimmungen und Nähe-Nachbarn entspricht.
InformationsquelleAutor der Antwort
Dies ist eine alte Frage, und ich bin überrascht, dass niemand vorgeschlagen, die OP mit Apache Solr.
Apache Solr ist eine Volltext-Suchmaschine, die neben vielen anderen Funktionen bietet auch die Rechtschreibprüfung oder Abfrage Anregungen. Aus der Dokumentation:
InformationsquelleAutor der Antwort Josep Valls