Wie vergleiche ich Sätze für Ähnlichkeit?

Question

Wenn Sie eine Frage eingeben, zeigt stackoverflow eine Liste von Fragen an, die wahrscheinlich dasselbe Thema behandeln. Ich habe ähnliche Funktionen auch auf anderen Seiten oder in anderen Programmen gesehen (zB Hilfedateisysteme), aber ich habe selbst noch nie so etwas programmiert. Jetzt bin ich neugierig zu wissen, welche Art von Algorithmus man dafür verwenden würde.

Der erste Ansatz, der mir in den Sinn kommt, besteht darin, die Phrase in Wörter aufzuteilen und nach Phrasen zu suchen, die diese Wörter enthalten. Bevor Sie das tun, möchten Sie wahrscheinlich unbedeutende Wörter (wie 'das', 'a', 'tut' usw.) wegwerfen, und dann werden Sie die Ergebnisse ordnen wollen.

Hey, warten Sie - lassen Sie uns, dass Web-Seiten für die tun, und dann können wir eine haben ... Watchamacallit ... - eine „Suchmaschine“, und dann können wir Anzeigen verkaufen, und dann ...

Nein, im Ernst, was sind die üblichen Wege, um dieses Problem zu lösen?

Answer 1

Ein Ansatz ist das sogenannte Bag-of-Word-Modell.

Wie Sie schon erraten haben, zählen Sie zuerst, wie oft Wörter im Text vorkommen (im NLP-Jargon normalerweise Dokument genannt). Dann wirfst du die so genannten Stoppwörter wie "das", "ein", "oder" und so weiter weg.

Sie sind mit Wörtern und Wortzählungen verlassen. Tun Sie dies für eine Weile und Sie erhalten eine umfassende Reihe von Wörtern, die in Ihren Dokumenten erscheinen. Sie können dann einen Index für diese Wörter erstellen: "Aardvark" ist 1, "Apfel" ist 2, ..., "Z-Index" ist 70092.

Jetzt können Sie Ihre Wort Taschen nehmen und sie in Vektoren. Zum Beispiel, wenn Ihr Dokument zwei Referenzen für Erdferkel und nichts enthält sonst würde es so aussehen:

[2 0 0 ... 70k zeroes ... 0]. 

Danach können Sie den „Winkel“ zwischen den beiden Vektoren mit a dot product zählen. Je kleiner der Winkel, desto näher sind die Dokumente.

Dies ist eine einfache Version und andere fortgeschrittene Techniken. Möge die Wikipedia be with you.

Answer 2

Von meiner (eher kleinen) Erfahrung entwickelnden Volltext-Suchmaschinen: Ich würde Fragen nachschlagen, die einige Wörter aus der Abfrage enthalten (in Ihrem Fall ist die Abfrage Ihre Frage). Sicher, Noise-Wörter sollten ignoriert werden und wir könnten die Abfrage nach 'starken' Wörtern wie 'ASP.Net' überprüfen, um den Suchbereich einzuschränken. http://en.wikipedia.org/wiki/Index_(search_engine)#Inverted_indices'>Invertierte Indizes werden häufig verwendet, um Fragen mit Wörtern zu finden, an denen wir interessiert sind.

Nach dem Finden von Fragen mit Wörtern aus der Abfrage, könnten wir wollen wir die Distanz zwischen Wörtern berechnen, an denen wir uns in Fragen interessieren, so steht die Frage mit dem Text "Phrasenähnlichkeit" höher als die Frage mit "Ähnlichkeiten diskutieren, Sie hören folgende Sätze ...".

Answer 3

@Hanno sollten Sie den Levenshtein-Distanzalgorithmus ausprobieren. Bei einem gegebenen Eingangskette s und eine Liste von Zeichenketten t Iterierte für jede Saite u in t und gibt die einen mit dem minimalen Abstand Levenshtein.

http://en.wikipedia.org/wiki/Levenshtein_distance

ein Java-Implementierung Beispiel in http://www.javalobby.org/java/forums/t15908.html

Answer 4

Um die bag-of-Worte Idee zu erweitern Siehe:

Es gibt ein paar Möglichkeiten, wie Sie auch einige Aufmerksamkeit auf n-Gramm zahlen können, Strings aus zwei oder mehr Wörtern in der richtigen Reihenfolge. Vielleicht möchten Sie dies tun, weil eine Suche nach "Raumkomplexität" viel mehr ist als eine Suche nach Dingen mit "Raum" UND "Komplexität", da die Bedeutung dieser Phrase mehr ist als die Summe ihrer Teile; Das heißt, wenn Sie ein Ergebnis erhalten, das von der Komplexität des Weltraums und des Universums spricht, ist dies wahrscheinlich nicht das, was die Suche nach "Raumkomplexität" wirklich bedeutet. Eine Schlüsselidee der Verarbeitung natürlicher Sprache ist hier die mutual information, mit der Sie (algorithmisch) beurteilen können, ob eine Phrase wirklich eine bestimmte Phrase ist (wie zum Beispiel "Raumkomplexität") oder nur Wörter, die zufällig benachbart sind . Mathematisch gesehen besteht die Hauptidee darin, probabilistisch zu fragen, ob diese Wörter häufiger nebeneinander erscheinen, als Sie anhand ihrer Häufigkeiten vermuten würden. Wenn Sie in Ihrer Suchanfrage (oder während der Indexierung) eine Wortgruppe mit einem hohen gegenseitigen Informationsgehalt sehen, können Sie bessere Ergebnisse erzielen, wenn Sie versuchen, diese Wörter in der richtigen Reihenfolge zu halten.