Volltextsuche - "Meinten Sie..." - Feature wie bei Google

[Herzlicher]

Hallo,
jeder kennt die nette Funktion von Google, bei der bei einem Vertipper ("fusball") automatisch ein korrigiertes Suchwort angeboten wird ("Meinten Sie: fußball").

Mich würde interessieren darüber zu debattieren, wie eine Implementierung einer solch nutzerfreundlichen Funktion aussieht:

Führt Google eine Liste aller von Nutzer eingegeben Suchwörter (Vertipper) und verknüpft sie mit einem anderen ähnlichen Suchwort, das direkt im Anschluss eingegeben wurde? (Annahme: der Nutzer hat seinen Vertipper erkannt und gibt das Wort in einem zweiten Anlauf korrekt ein).

Oder werden die Verknüpfungen (Vertipper --> richtiges Wort) schlicht mit der Hand vorgenommen?

Ich bin gespannt über Eure Ideen.

Herzlichst

[Rouven]

Hello,

was Google genau macht weiß ich nicht. Eine Möglichkeit wäre die Kombination eines Ähnlichkeitsalgorithmus wie Levenshtein Distanz oder phonetischer Algorithmen mit der Häufigkeit im Index, d.h. kommt ein ähnliches Wort nicht sehr viel häufiger vor.

MfG
Rouven

[Reiner]

Hello,

was Google genau macht weiß ich nicht. Eine Möglichkeit wäre die Kombination eines Ähnlichkeitsalgorithmus wie Levenshtein Distanz oder phonetischer Algorithmen mit der Häufigkeit im Index, d.h. kommt ein ähnliches Wort nicht sehr viel häufiger vor.

eins setzen! ;-)

Gruß
Reiner

[Jonny 5]

Hi,

Mich würde interessieren darüber zu debattieren, wie eine Implementierung einer solch nutzerfreundlichen Funktion aussieht:

Ich habe einmal so eine ähnliche Funktion für eine kleine Suchmaschine geschrieben. Dabei ging ich folgendermaßen vor.

Es existert ein Keyword-Table, ua mit folgenden Spalten:
-------------------
keyword = das Wort
page_count = Vorkommen des jweiligen Wortes auf Seiten
search_count = Wie oft haben User nach dem Wort gesucht
-------------------
Zusätlich existert eine Tabelle mit häufigen Phrasen

1.) Jedes Wort wird geprüft, ob es einen entsprechenden Schwellenwert aus search_count/page_count überschritten hat.

• Wenn nicht, wird versucht, eine ähnliche Phrase zu finden
  (dazu hab ich etwas aus LIKE und REGEXP zusammgeflickt, das aus ähnlichem Anfang und Ende oder einem Buchstabenvorrat, der um häufige Tippfehler (ß <-> ss, ai <-> ei <-> ay, kk <-> ck, ch <-> sch usw) ergänzt wurde, ähnliche Treffer mit hohem Vorkommen liefert.

2.) Wird keine Phrase gefunden, wird für jedes - mit hoher Wahrscheinlichkeit falschgeschriebene Wort - nach dem selben Schema ein passendes Ersatzwort geliefert.

3.) Aus Wortähnlichkeit und Häufigkeit/Beliebtheit wird ein Faktor berechnet, der eine entsprechende Schwelle überschreiten muss.

Ob es Google ähnlich macht, weiß ich nicht, es könnte aber sein, daß sie für häufige Verschreiber bereits Worte / Phrasen auf Lager haben, ohne große Vergleiche berechnen zu müssen (performance).

Das größte Problem besteht meines Erachtens darin, zu erkennen, wann etwas falsch geschrieben ist. Wenn ich Suchmaschine wäre und bei einem ähnlichen Wort / Phrase sehr viel mehr anbieten könnte, würde ich nicht ruhig bleiben: Meintest du ... ;)

herzliche Grüße,
Jonny 5

[EisFuX]

(Hallo|Hi(ho)|Tag) Herzlicher,

jeder kennt die nette Funktion von Google, bei der bei einem Vertipper ("fusball") automatisch ein korrigiertes Suchwort angeboten wird ("Meinten Sie: fußball").

Mich würde interessieren darüber zu debattieren, wie eine Implementierung einer solch nutzerfreundlichen Funktion aussieht:
...
Ich bin gespannt über Eure Ideen.

Ich hab keine Ideen, ich hab erst die Wikipedia befragt und die lieferte mir folgenden Link:
http://answers.google.com/answers/threadview?id=526503

MffG
EisFuX

[Tim Tepaße]

Hallo,

Mich würde interessieren darüber zu debattieren, wie eine Implementierung einer solch nutzerfreundlichen Funktion aussieht:

Peter Norvig, der Direktor für Forschung, vorher Direktor für Suchqualität bei Google wurde das auch mehrmals gefragt. Praktischerweise hat er durchaus Spaß daran, Wissen weiter zu geben oder zu lehren (er hat ein sehr gutes Buch über AI geschrieben) und hat gleich ein Tutorial über einen kleines Rechtschreibkorrekturskript veröffentlicht.

Führt Google eine Liste aller von Nutzer eingegeben Suchwörter (Vertipper) und verknüpft sie mit einem anderen ähnlichen Suchwort, das direkt im Anschluss eingegeben wurde?

Auch wenn das vorgestellte Skript natürlich sehr viel simpler als Googles tatsächliche Lösung sein wird, glaube ich schon, dass da ein größerer Kern Wahrheit drin sein wird. Mit der von Rouven erwähnten Levenshtein-Distanz (und anderen Editierdistanzen) hat man ja ein gutes Modell, um den Unterschied von Strings zueinander in Zahlen zu verwandeln; ein Modell, das sich besonders gut für Vertipper eignet. Es gibt also ein Funktion, die zu einem gegebenen Wort dessen Vertipper ausspuckt. Und funktioniert auch umgekehrt. Man hat einen Vertipper und kriegt automatisiert auch dessen Varianten (Vertipper der Vertipper) heraus, unter denen sich dann auch richtige Wörter befinden können. Das ist also leicht.

Was etwas komplizierter ist, ist das Auswählen der richtigen Korrektur und damit beschäftigt sich Norvig in seinem Tutorial mehr. Da kann man ein Schema erkennen. Google als reine Suchmaschine ist ja auch deswegen so erfolgreich geworden, weil sie einen Algorithmus dafür fanden, Links so zu bewerten, so dass die ersten Links anscheinend für die meisten der Suchenden am erfolgreichesten waren, anstatt dass diese Links erst auf Seite 567 auftauchten. Einfach unsortiert Ergebnisse ausspucken kann ja jeder.

Norvig benutzt in seinem Skript die Wahrscheinlichkeit dafür, dass ein zu korrigierenes Word k gesucht wird, wenn der Vertipper v auftaucht und gruppiert die möglichen Lösungsworter k, k', k" ... danach. Das schreibt sich dann P(k|v). Nun kennt niemand die Wahrscheinlichkeit ausser vielleicht der Vertippende selber. Deswegen benutzt er aus der Mathematik der Wahrscheinlichkeiten den Satz von Bayes um die unbekannte Wahrscheinlichkeit in bekanntere und vor allem berechenbarere Wahrscheinlichkeiten umzuformen. Klingt absurd, funktioniert aber. Dir ist es vielleicht aus der Spambekämpfung bekannt, seit einem Versuch von Paul Graham hat sich das in den letzten Jahren rasant durchgesetzt. Alexander Brock hat das mal in einem Artikel für Selfaktuell genauer auseinanderklamüsert.

Durch diesen Kunstgriff braucht er dann nur noch mit zwei leichter zu berechnenden Wahrscheinlichkeiten zu arbeiten. Einmal der Wahrscheinlichkeit P(k), die darüber aussagt, ob das gesuchte Wort k auch wirklich ein richtiges Wort ist. Er macht das einfach durch den Vergleich mit der Häufigkeit bekannter Wörter.
Zum anderen die bedingte Wahrscheinlichkeit P(v|k), die aussagen soll, wie wahrscheinlich ein Vertipper v ist, wenn k getippt werden sollte. Da hat er keine Theorie, sondern nutzt einfach nur seine Intuition, das Vertipper mit einer geringeren Editier-Distanz viel wahrscheinlicher sind als die mit einer höheren Distanz. Funktioniert aber meistens.

Der Algorithmus ist dann einfach zu einem gegebenen Vertipper v die besten (geringste Distanz) existierenden Korrekturen k nach seinem intuitiven Modell P(v|k) zu berechnen und diese dann nach ihrer Häufigkeit P(k) zu gruppieren. Das kann man, insbesondere mit den Ressourcen von Google, noch stark verbessern.

Erstmal dürfte Google den größten Textkorpus der Welt besitzen, das gesamte von Google indizierte Internet. Damit hat Google schon mal eine großartige Grundlage für die Häufigkeitsverteilung hinter P(k).

Dann sammelt Google vermutlich die Korrekturen des jeweiligen sich vertippenden Nutzers, um Feedback zu bekommen. Das kann zweierlei benutzt werden. Zum einen für einen individuellen P(v|k), die Wahrcsheinlichkeit, also wie oft sich der Nutzer Tim in der Vergangeneheit bei dem Wort „Wahrscheinlichkeit“ vertippt und es korrigiert hat. Es kann aber auch in einer generellen, für alle geltenden P(v|k) einfliessen, einfach in dem geguckt wird, wie oft manche Korrekturen bei entsprechenden Vertippern auftauchen können.

Norvig schlägt noch Kontext vor. Da kann zum einen der aufgeführte Kontext des gesamten Suchbegriffes sein. Im Kontext der umgebenden Wörter kann eine bestimmte Korrektur k' für einen Vertipper sinnvoller sein als eine Korrektur k''. Solche Phrasen kriegt Google natürlich wieder aus seinem Datenbestand heraus; sie veröffentlichten ja schon einen Korpus von Phrasen bis zu 5 Wörtern. Noch geschickter wäre es aber auch, die bereits bekannten Suchterme einzubeziehen und denen eine höhere Relevanz zu geben als irgendwelchen dahergelaufenen Satzfetzen aus dem Internet.

Kontext kann aber auch Information über geographischen Aufenthaltsort (IP-Geolocation) oder die eingestellte Sprache des Nutzers (Cookie) sein. Dadurch erhält man einen Hinweis auf die Sprache und kann das dann nutzen. Der Tee zum Trinken der Deutschen dürfte häufiger vorkommen als das tee der amerikanischen Golf-Spieler, das aber häufiger vorkommt als das Tee der deutschen Golf-Spieler, einfach weil von den Ersteren sehr viel mehr da sind.

Und natürlich auch Tagesaktualität, d.h. inwieweit eine mögliche Korrektur weit hoch auf der Hitliste gesuchter Suchbegriffe steht oder wie oft sie bei Google News, Google Reader und ähnlichem auftauchen, oder ob Paris Hilton wieder mal irgendwas gemacht hat.

Das sind natürlich alles mehr Variablen die besser nicht in die oben benutzten Wahrscheinlichkeiten einfliessen. Aber eine bedingte Wahrscheinlichkeit (wie das P(k|v) am Anfang) kann auch von mehreren Bedingungen abhängen. Diese schlimme, unberechenbare Wahrscheinlichkeit müsste dann wieder mit Bayes in halbwegs bestimmbare Wahrscheinlichkeiten aufgelöst werden.

Und noch nebenbei: Ich gehe davon aus, dass Google einen Haufen Optimierungen benutzt. Zum Beispiel wird bei Norvig die durch die Editierdistanzen erzeugten Varianten immer neu bestimmt; das dauert und ist eigentlich unnötig und nicht sehr elegant. Ich habe mal gelesen, dass eine Google Anwendung binnen 10 Millisekunden antworten sollte, damit sie in die Große Suche eingebettet wird. Da kann ich mir gut vorstellen, dass für alle bekannten Wörter, oder aber wenigstens die populärsten (Häufigkeitsverteilung des Korpus, Häufigkeitsverteilung der Suchbegriffe) Editierdistanzen und vielleicht auch einige Wahrscheinlichkeiten vorausberechnet werden. Immerhin wird jeder Suchterm gesplittet und jedes Wort auf mögliche Korrekturen überprüft. Das ist ... viel. ;)

Tim