La forma más eficiente de agrupar los resultados de búsqueda por similitud de cadena: algoritmo, búsqueda, comercio electrónico, agrupación, búsqueda difusa

Estoy trabajando en un servidor SQL 2008 DB y una aplicación web de comercio electrónico de asp.net mvc.

Tengo diferentes usuarios alimentando sus productos ael DB, y quiero comparar los precios de los productos con nombres similares. Sé que la coincidencia de cadenas es específica del dominio, pero aún necesito la mejor solución genérica.

¿Cuál es la forma más eficiente de agrupar¿Resultados de la búsqueda? ¿Debo comparar cada uno de los registros de forma recursiva utilizando el algoritmo de distancia de Levenshtien? ¿Debo hacerlo en la base de datos, o en el código? ¿Hay alguna manera de implementar SSIS Fuzzy Grouping en tiempo real para esta tarea? ¿Existe una forma eficiente de hacerlo utilizando la búsqueda de texto libre del servidor Sql 2008?

Edición 1: ¿Qué pasa con el análisis de red-gráfico. Si definiré una matriz utilizando el algoritmo de distancia Levenshtien, podría usar un algoritmo de agrupamiento (por ejemplo: clauset newman moore) y grupos separados que no tengan una ruta fonológica entre ellos. He adjuntado a Nick Johnson (ver comentario) cat-dog, por ejemplo (las líneas rojas son los grupos), y al usar el clauset newman moore estoy creando 2 grupos diferentes y separando a los gatos de los perros.

¿Qué piensas?

Respuestas

Si puedes conseguir un adecuadoTesauro / ontología que básicamente proporciona la mejor agrupación posible, ya que las palabras son hojas en un árbol conceptual, la distancia en el árbol es la distancia entre palabras en sentido semántico. Por lo tanto, el gato y el perro no están tan cerca como el gato atigrado y el calicó (gato), pero están sustancialmente más cerca que el gato y el plátano, que a su vez están más cerca que el gato (n.) Y el salto (v.).

Permitiendo pequeños errores de ortografía (mirandopara palabras deletreadas de manera similar que están en el diccionario de sinónimos para palabras que no están "t" podría aumentar la solidez, pero también podría crear resultados inesperados como resultado de homónimos.

En cuanto a hacerlo en la base de datos o en código, hágalo en código. En la medida en que puedas cachear, eso será más rápido.

Este es un problema de agrupamiento y por lo tantocomputacionalmente difícil, pero hay una gran cantidad de algoritmos conocidos para resolver tales problemas, tanto de manera exacta como aproximada. Tener un lok en la página de wikipedia en Análisis de conglomerados y esta respuesta.

Una vez que haya implementado un algoritmo de clusteringpodría almacenar los clústeres en la base de datos, pero sospecho que sería demasiado caro volver a calcular los clústeres en cada elemento agregado. Probablemente sería mejor ejecutar el algoritmo de agrupamiento una vez por hora o una vez por día.