effizienteste Möglichkeit, Suchergebnisse nach String-Ähnlichkeit zu gruppieren

Question

Ich arbeite auf einem SQL-Server 2008 DB und asp.net mvc Web E-Commerce-App.

Ich habe verschiedene Benutzer, die ihre Produkte der DB zuführen, und ich möchte die Preise von Produkten mit ähnlichen Namen vergleichen. Ich weiß, dass String-Matching Domain-spezifisch ist, aber ich brauche immer noch die beste generische Lösung.

Wie gruppieren Sie die Suchergebnisse am effizientesten? Sollte ich jeden der Datensätze rekursiv mit dem Levenshtien-Distanzalgorithmus vergleichen? Sollte ich es in der DB oder im Code tun? Gibt es eine Möglichkeit, SSIS Fuzzy Grouping in Echtzeit für diese Aufgabe zu implementieren? Gibt es eine effiziente Möglichkeit, dies mit der Sql Server 2008 Freitextsuche zu tun?

Bearbeiten 1: Was ist mit Netzwerk-Grafik-Analyse. Wenn ich eine Matrix mit dem Levenshtien-Distanz-Algorithmus definiere, könnte ich einen Clustering-Algorithmus (zum Beispiel: clauset newman moore) und separate Gruppen verwenden, die keinen phonologischen Pfad zwischen ihnen haben. Ich habe Nick Johnson (siehe Kommentar) als Katzenhund zum Beispiel angehängt (die roten Linien sind die Cluster) - und mit der Klausel newman moore erstelle ich 2 verschiedene Cluster und trenne Katzen von Hunden.

Was denkst du?

Answer 1

Wenn Sie einen geeigneten Thesaurus/Ontologie erhalten können, der im Grunde die bestmögliche Clusterbildung bietet - da Wörter Blätter in einem Konzeptbaum sind, ist Entfernung im Baum die Entfernung zwischen Wörtern in einem semantischen Sinn. So sind Katze und Hund nicht annähernd so nah wie Tabby und Kaliko (Katze), aber sie sind wesentlich näher als Katze und Banane, die selbst näher sind als Katze (n.) Und springen (v.).

Die Berücksichtigung von kleinen Rechtschreibfehlern (durch die Suche nach ähnlich geschriebenen Wörtern, die im Thesaurus für nicht vorhandene Wörter enthalten sind) könnte die Robustheit erhöhen, aber auch durch Homonyme zu unerwarteten Ergebnissen führen.

Um es in der Datenbank oder im Code zu tun, tun Sie es in Code. In dem Ausmaß, in dem Sie cachen können, wird das schneller.

Answer 2

Dies ist ein Clustering-Problem und damit rechnerisch schwierig, aber es gibt eine große Anzahl von Algorithmen zur Lösung solcher Probleme bekannt, die beide genau und ungefähr. Haben Sie einen Ort auf der Wikipedia Seite auf Cluster Analysis und this answer.

Sobald Sie einen Clustering-Algorithmus implementiert haben, könnten Sie die Cluster in der Datenbank speichern, aber ich vermute, dass es zu teuer wäre, die Cluster für jedes hinzugefügte Element neu zu berechnen. Es wäre wahrscheinlich am besten, den Clustering-Algorithmus einmal pro Stunde oder einmal am Tag auszuführen.