Asesoramiento sobre cómo mejorar una implementación de búsqueda difusa actual

Question

Actualmente estoy trabajando en la implementación de una búsqueda difusa de un servicio web de terminología y estoy buscando sugerencias sobre cómo podría mejorar la implementación actual. Es demasiado código para compartir, pero creo que una explicación puede ser suficiente para sugerir reflexiones. Me doy cuenta de que es mucho para leer, pero agradecería cualquier ayuda.

Primero, la terminología es básicamente solo una cantidad de nombres (o términos). Para cada palabra, la dividimos en tokens por espacio y luego iteramos a través de cada carácter para agregarlo al trie. En un nodo terminal (como cuando se alcanza el carácter y en strawberry) almacenamos en una lista un índice para la lista de términos principales. Por lo tanto, un nodo terminal puede tener múltiples índices (ya que el nodo terminal para fresa coincidirá con 'fresa' y 'alergia a fresa').

En cuanto a la búsqueda real, la consulta de búsqueda también se divide en tokens por espacio. El algoritmo de búsqueda se ejecuta para cada token. El primer carácter del token de búsqueda debe coincidir (por lo que traw nunca coincidirá con strawberry). Después de eso, pasamos por los niños de cada nodo sucesivo. Si hay un elemento secundario con un carácter que coincida, continuamos la búsqueda con el siguiente carácter del token de búsqueda. Si un niño no concuerda con el personaje dado, observamos a los niños usando el carácter actual del token de búsqueda (para no avanzar). Esta es la parte borrosa, por lo que 'stwb' coincidirá con 'fresa'.

Cuando lleguemos al final del token de búsqueda, buscaremos en el resto de la estructura trie en ese nodo para obtener todas las coincidencias posibles (ya que los índices de la lista de términos maestros están solo en los nodos del terminal). Llamamos a esto el roll up. Almacenamos los índices al establecer su valor en un BitSet. Entonces, simplemente y los BitSets de los resultados de cada resultado de token de búsqueda. Luego tomamos, digamos, los primeros 1000 o 5000 índices de los BitSets anidados y buscamos los términos reales a los que corresponden. Usamos Levenshtein para puntuar cada término y luego ordenarlo por puntaje para obtener nuestros resultados finales.

Esto funciona bastante bien y es bastante rápido. Hay más de 390k nodos en el árbol y más de 1,1 millones de nombres de términos reales. Sin embargo, hay problemas con esto tal como está.

Por ejemplo, la búsqueda de 'gato automóvil' devolverá el cateterismo, cuando no lo deseemos (dado que la consulta de búsqueda es de dos palabras, el resultado debe ser al menos dos). Eso sería fácil de verificar, pero no soluciona una situación como el Procedimiento de cateterismo, ya que son dos palabras. Idealmente, nos gustaría que coincida con algo como la cateterización cardíaca.

En función de la necesidad de corregir esto, se produjeron algunos cambios. Por un lado, pasamos por el trie en una búsqueda mixta de profundidad/amplitud. Esencialmente profundizamos primero siempre que un personaje coincida. Esos nodos secundarios que no coinciden se agregan a una cola de prioridad. La cola de prioridad se ordena por distancia de edición, que se puede calcular mientras se busca el trie (ya que si hay una coincidencia de caracteres, la distancia sigue siendo la misma y si no, se incrementa en 1). Al hacer esto, obtenemos la distancia de edición para cada palabra. Ya no estamos usando el BitSet. En cambio, es un mapa del índice de un objeto Terminfo. Este objeto almacena el índice de la frase de consulta y el término frase y puntaje. Por lo tanto, si la búsqueda es "gato de automóvil" y un término emparejado es "procedimiento de cateterización", el término "índices de frase" será 1, al igual que los índices de frase de consulta. Para "cateterismo cardíaco", el término índices de frase será 1,2, al igual que los índices de frase de consulta. Como puede ver, después es muy simple observar el recuento de los índices de frase terminológica y los índices de frase de consulta, y si no son al menos iguales al recuento de palabras de búsqueda, pueden descartarse.

Después de eso, sumamos las distancias de edición de las palabras, eliminamos las palabras del término que coinciden con el término índice de frase, y contamos las letras restantes para obtener la distancia de edición verdadera.Por ejemplo, si coincide con el término "alergia a las fresas" y su consulta de búsqueda fue "paja", obtendría un puntaje de 7 de las fresas, luego utilizaría el término índice de frase para descartar las fresas del término, y solo contaría "alergia a" (sin los espacios) para obtener el puntaje de 16.

Esto nos da los resultados precisos que esperamos. Sin embargo, es demasiado lento. Donde antes podíamos obtener 25-40 ms en una búsqueda de palabras, ahora podría ser tanto como medio segundo. Se trata en gran medida de cosas como instanciar objetos TermInfo, usando operaciones .add(), operaciones .put() y el hecho de que tenemos que devolver una gran cantidad de coincidencias. Podríamos limitar cada búsqueda para que solo devuelva 1000 coincidencias, pero no hay garantía de que los primeros 1000 resultados para "automóvil" coincidan con cualquiera de las primeras 1000 coincidencias para "gato" (recuerde, hay más de 1.1 millones de términos).

Incluso para una sola palabra de consulta, como cat, aún necesitamos una gran cantidad de coincidencias. Esto es porque si buscamos 'cat' la búsqueda va a coincidir con el auto y enrollaremos todos los nodos terminales debajo de él (que será mucho). Sin embargo, si limitáramos la cantidad de resultados, pondría demasiado énfasis en palabras que comiencen con la consulta y no en la distancia de edición. Por lo tanto, las palabras como el cateterismo tendrían más probabilidades de ser incluidas que algo como el pelaje.

Así que, básicamente, ¿hay alguna idea sobre cómo podríamos manejar los problemas que la segunda implementación solucionó, pero sin tanta velocidad de ralentización que introdujo? Puedo incluir algún código seleccionado si pudiera aclarar las cosas, pero no quería publicar una pared gigante de código.

Answer 1

Wow ... difícil.

¿Por qué no implementa Lucene? Es el mejor y más reciente estado del arte cuando se trata de problemas como el tuyo afaik.

Sin embargo, quiero compartir algunas ideas ...

Fuziness no es algo así como paja * es más bien la mecanografía de algunas palabras. Y cada personaje perdido/incorrecto agrega 1 a la distancia.

¡En general es muy, muy difícil tener coincidencias parciales (comodines) y borrosidad al mismo tiempo!

Tokenizar es generalmente una buena idea.

Todo depende en gran medida de los datos que obtenga. ¿Hay errores ortográficos en los archivos fuente o solo en las consultas de búsqueda?

He visto algunas implementaciones bastante agradables utilizando árboles de rango multidimensional.

Pero realmente creo que si quieres lograr todo lo anterior, necesitas una combinación bastante ordenada de un conjunto de gráficos y un buen algoritmo de indexación.

Podría, por ejemplo, usar una base de datos semántica como sésamo y al importar sus documentos, importe cada token y documento como un nodo. Luego, dependiendo de la posición en el documento, etc. puede agregar una relación ponderada.

Luego necesitas los tokens en alguna estructura donde puedes hacer coincidencias difusas eficientes como bk-trees. Creo que podría indexar los tokens en una base de datos mysql y realizar funciones de comparación de bits para obtener diferencias. Hay una función que devuelve todos los bits que coinciden, si translit sus cadenas a ascii y agrupa los bits puede lograr algo bastante rápido.

Sin embargo, si combinó los tokens con la cadena, puede construir una coincidencia hipotética perfecta y consultar su base de datos semántica para los vecinos más cercanos.

Tendría que separar las palabras en palabras parciales al realizar tokens para lograr coincidencias parciales.

Sin embargo, también puede hacer coincidencias de comodines (prefijo, sufijo o ambos) pero sin confusión.

También puede indexar la palabra completa o diferentes concatenaciones de tokens.

Sin embargo, puede haber implementaciones especiales de bk-tree que admitan esto, pero nunca he visto uno.

Answer 2

Hice una serie de iteraciones de un corrector ortográfico hace siglos, y aquí hay un recent description del método básico. Básicamente, el diccionario de palabras correctas está en trie, y la búsqueda es una simple bifurcación. Utilicé repetidas caminatas de profundidad primero, delimitadas por lev. distancia porque, dado que cada incremento adicional de distancia resulta en mucho más de lo que se camina, el costo, para la distancia pequeña, es básicamente exponencial en la distancia, por lo que ir a una búsqueda combinada de profundidad/amplitud no ahorra mucho pero lo hace mucho más complicado.

(Aparte: Usted se sorprendería de cuántas maneras los médicos pueden tratar de deletrear "ácido acetilsalicílico".)

Estoy sorprendido por el tamaño de su trie. Un diccionario básico de palabras aceptables es tal vez unos pocos miles. Luego hay prefijos y sufijos comunes. Como la estructura es un trie, puede conectar sub-intentos y ahorrar mucho espacio. Al igual que el trie de prefijos básicos puede conectarse al diccionario principal, y luego los nodos terminales del diccionario principal pueden conectarse a la trie de sufijos comunes (que de hecho pueden contener ciclos). En otras palabras, el trie se puede generalizar en una máquina de estados finitos. Eso te da mucha flexibilidad.

Independientemente de todo eso, tiene un problema de rendimiento. Lo bueno de los problemas de rendimiento es que cuanto peor son, más fácil es encontrarlos. He sido una verdadera plaga en StackOverflow al señalar esto. This link explica cómo hacerlo, enlaces a un ejemplo detallado e intenta disipar algunos mitos populares. En pocas palabras, cuanto más tiempo gaste haciendo algo que pueda optimizar, más probabilidades tendrá de atraparlo haciendo eso si lo pausa y eche un vistazo. Sospecho que se dedica mucho tiempo a las operaciones en una estructura de datos exagerada, en lugar de solo llegar a la respuesta. Esa es una situación común, pero no solucione nada hasta que las muestras le indiquen directamente el problema.