Gruppierung Strings nach Ähnlichkeit

Question

Ich habe eine Reihe von Strings, nicht viele (vielleicht ein paar hundert), aber oft lang (ein paar hundert Zeichen).

Die Zeichenfolge, in der Regel, Unsinn und anderes von den anderen .. aber in einer Gruppe jener Schnur, vielleicht 5 von 300, gibt es eine große Ähnlichkeit. In der Tat sind sie die gleiche Zeichenfolge, was unterscheidet formatiert, Zeichensetzung und ein paar Worte ..

Wie ich diese Gruppe von String arbeiten kann?

By the way, ich bin in Ruby zu schreiben, aber wenn nichts anderes wäre ein Algorithmus in Pseudo-Code in Ordnung sein.

dank

Answer 1

Es gibt viele Möglichkeiten Strings Ähnlichkeit zu vergleichen.

Here is a site with various similarity metrics Sie verwenden können.

Here is a Wikipedia article with various similarity metrics Sie verwenden können.

Answer 2

Es könnte Overkill und möglicherweise und nicht genau passend zu dem, was Sie erreichen wollen, aber Sie könnten in der Lage sein, "Ferret" zu helfen (die Ruby-Version von Lucene - Volltextindex/Such-API) zu Sortiere aus der Interpunktion und Formatierung - auch wenn sich die Sätze durch gebräuchliche Stoppwörter unterscheiden (die, und, ist ...) können diese gefiltert werden.

Ihren Suchanfragen werden dann Gewichtungen zugewiesen: Dies gibt eine Vorstellung von Ähnlichkeit.

http://www.davebalmain.com/ http://www.amazon.co.uk/Ferret-David-Balmain/dp/0596519400/ref=sr_1_2?ie=UTF8&s=books&qid=1264751909&sr=8-2

Answer 3

können Sie den Levenshtein Algorithmus für diese. Here's eine Implementierung in Ruby.

Answer 4

Unter der Annahme, dass Sie über Rechtschreibfehler oder andere Fehler in jedem Wort nicht besorgt sind, können Sie Folgendes tun:

einen invertierten Index bauen, die durch Wort verkeilte im Grunde ein Hash ist, indem er auf eine Liste von Zeigern auf die Zeichenfolgen, die dieses Wort enthalten (wie du mit doppelten Vorkommen umgehst, bleibt dir überlassen). Um Zeichenfolgen zu ermitteln, die einer bestimmten Abfragezeichenfolge ähneln, suchen Sie jedes Abfragewort im Index und zählen für jede Quellenzeichenfolge in den Ergebnislisten, wie oft die Quellenzeichenfolge in jeder Liste angezeigt wird. Die Zeichenfolgen mit den höchsten Zahlen sind die besten Kandidaten für Ähnlichkeit, da sie die meisten Wörter enthalten.

Dann können Sie die Edit-Distanz zwischen den beiden Strings berechnen, oder was auch immer andere Metrik, die Sie wollen. Auf diese Weise vermeiden Sie die O (n^2) -Komplexität des Vergleichens jeder Zeichenfolge mit jeder anderen Zeichenfolge.