il modo più efficiente per raggruppare i risultati di ricerca per similarità delle stringhe

Question

Sto lavorando su un DB sql server 2008 e su asp.net mvc web E-commerce.

Ho diversi utenti che alimentano i loro prodotti al DB e voglio confrontare i prezzi dei prodotti con nomi simili. So che la corrispondenza delle stringhe è specifica del dominio, ma ho ancora bisogno della migliore soluzione generica.

Qual è il modo più efficace per raggruppare i risultati della ricerca? Devo confrontare tutti i record in modo ricorsivo usando l'algoritmo Levenshtien Distance? Devo farlo nel DB o nel codice? Esiste un modo per implementare il raggruppamento Fuzzy SSIS in tempo reale per questa attività? Esiste un modo efficace per farlo usando la ricerca di testo libero Sql server 2008?

Modifica 1: E l'analisi del grafico di rete. Se definirò una matrice usando l'algoritmo Levenshtien Distance, potrei usare un algoritmo di clustering (ad esempio: clauset newman moore) e gruppi separati che non hanno un percorso fonologico tra di loro. Ho allegato Nick Johnson (vedi commento) cane gatto per esempio (le linee rosse sono i grappoli) - e usando il clauset newman moore sto creando 2 diversi cluster e gatti separati dai cani.

Cosa ne pensi?

Answer 1

Se riesci a trovare un thesaurus/ontologia adatto che fornisca il miglior raggruppamento possibile - poiché le parole sono foglie in un albero del concetto, la distanza nell'albero è la distanza tra le parole in un senso semantico. Così gatto e cane non sono così vicini come tabby e calico (gatto), ma sono sostanzialmente più vicini di gatto e banana, che sono più vicini di gatto (n.) E salto (v.).

Consentire errori di ortografia di piccole dimensioni (cercando parole simili pronunciate nel thesaurus per parole che non lo sono) potrebbe aumentare la robustezza, ma potrebbe anche creare risultati imprevisti a causa di omonimi.

Per quanto riguarda farlo nel database o nel codice, farlo nel codice. Nella misura in cui è possibile memorizzare nella cache, sarà più veloce.

Answer 2

Questo è un problema di clustering e quindi computazionalmente difficile, ma ci sono un gran numero di algoritmi noti per risolvere tali problemi, sia esattamente e circa. Avere un lok alla pagina di Wikipedia su Cluster Analysis e this answer.

Una volta implementato un algoritmo di clustering è possibile archiviare i cluster nel DB, ma sospetto che sarebbe troppo costoso ricalcolare i cluster su ogni articolo aggiunto. Probabilmente sarebbe meglio eseguire l'algoritmo di clustering una volta all'ora o una volta al giorno.