Wie effizient berechnen die Cosinus-Ähnlichkeit zwischen Millionen von Strings

Question

Ich muss die Kosinusähnlichkeit zwischen Strings in einer Liste berechnen. Zum Beispiel habe ich eine Liste von mehr als 10 Millionen Strings, jeder String muss die Ähnlichkeit zwischen sich selbst und jedem anderen String in der Liste bestimmen. Was ist der beste Algorithmus, mit dem ich solche Aufgaben effizient und schnell erledigen kann? Ist der Divide and Conquer-Algorithmus anwendbar?

EDIT

ich mit der Ähnlichkeit zugeordnet, die Saiten sind am ähnlichsten einer bestimmten Zeichenfolge und in der Lage zu bestimmen, wollen eine Maßnahme/Score. Ich denke, was ich tun möchte, steht im Einklang mit Clustering, wo die Anzahl der Cluster zunächst nicht bekannt ist.

Answer 1

Mit der transponierten Matrix arbeiten. Das macht Mahout auf Hadoop, um diese Art von Aufgabe schnell zu erledigen (oder einfach Mahout zu benutzen).

Im Wesentlichen ist die Berechnung der Kosinusähnlichkeit der naive Weg schlecht. Weil Sie am Ende viel 0 * etwas berechnen. Stattdessen arbeiten Sie besser in Spalten und lassen Sie alle 0s dort.

Answer 2

Sie könnten versuchen SimString.

Es ist eine C++ - Bibliothek (mit Python- oder Ruby-Bindungen) für ungefähre Zeichenfolgenabgleich.

Es behauptet, Strings mit hoher Kosinusähnlichkeit in weniger als 1 Millisekunde für eine Datenbank von 13 Millionen Strings zu finden.

Der verwendete Algorithmus ist here basierend auf der Beschneidung von invertierten Listen beschrieben.