Estoy tratando de utilizar k-vecinos más cercanos para el problema de similitud de cadena, es decir, dada una cadena y una base de conocimiento, quiero producir k cadenas que son similares a mi cadena dada. ¿Hay algún tutorial que explique cómo utilizar kd-trees para hacer de manera eficiente esta búsqueda de vecinos k-next para cadenas? La longitud de la cadena no excederá más de 20 caracteres.¿Cómo uso kd-trees para determinar la similitud de cadenas?
Probablemente una de las publicaciones de blog más candentes que había leído hace un año o más: Levenstein Automata. Eche un vistazo a ese artículo. Proporciona no solo una descripción del algoritmo sino también el código a seguir. Técnicamente, no es un árbol kd, pero está bastante relacionado con la coincidencia de cadenas y los algoritmos de corrección del diccionario que uno puede encontrar/usar en el mundo real.
También tiene otra publicación en el blog acerca de BK-trees que son mucho mejores en la coincidencia difusa para cadenas y búsquedas de cadenas donde hay errores ortográficos. Aquí hay otro recurso que contiene el código fuente de un BK-tree (este no puedo verificar la precisión o la implementación correcta).
+1 para transductores Levenshtein. –
El Levenshtein Automata es impresionante, sin embargo, habiéndolo implementado, solo puedo decir que la versión precalculada explota rápidamente (en términos de nodos) cuando la distancia crece. En la práctica, es muy rápido buscar en un Trie, pero el autómata comienza a ser realmente grande a una distancia de 4 en adelante. –
@Matthieu M. ¿qué recomendarías en su lugar? – wheaties
¿Cuál es su similitud entre 2 cadenas? [scipy.spatial.cKDtree] (http://docs.scipy.org/doc/scipy/reference/generated/scipy.spatial.cKDTree.html) es rápido y sólido, válido para 20d, pero solo tiene métricas de Lp. – denis