manera más eficiente de agrupar resultados de búsqueda por similitud de cadena

Question

Estoy trabajando en un servidor sql 2008 DB y asp.net mvc web E-commerce app.

Tengo diferentes usuarios que alimentan sus productos a la base de datos, y quiero comparar los precios de 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 manera más eficiente de agrupar los resultados de búsqueda? ¿Debo comparar cada uno de los registros recursivamente usando el algoritmo Levenshtien Distance? ¿Debo hacerlo en la base de datos o en el código? ¿Hay alguna manera de implementar la agrupación difusa SSIS en tiempo real para esta tarea? ¿Existe una forma eficiente de hacerlo utilizando la búsqueda de texto libre del servidor Sql 2008?

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

¿Qué opinas?

Answer 1

Si puede obtener un diccionario/ontología adecuado que básicamente proporcione la mejor agrupación posible, dado que las palabras son hojas en un árbol conceptual, la distancia en el árbol es la distancia entre palabras en un sentido semántico. Así, el gato y el perro no son tan cercanos como tabby y 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.).

Tener en cuenta los pequeños errores de ortografía (al buscar palabras deletreadas similares que están en el diccionario de sinónimos de palabras que no lo son) podría aumentar la solidez, pero también podría generar resultados inesperados como resultado de homónimos.

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

Answer 2

Este es un problema de agrupamiento y por lo tanto computacionalmente difícil, pero hay un gran número de algoritmos conocidos para resolver tales problemas, tanto con exactitud y aproximadamente. Tenga un lok en la página de wikipedia en Cluster Analysis y this answer.

Una vez que haya implementado un algoritmo de agrupación en clúster, podrí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 sea mejor ejecutar el algoritmo de agrupación una vez por hora o una vez al día.