Búsqueda aproximada contra una lista de cadenas

Question

Así que sí, leí acerca de cómo se puede usar la distancia de edición entre cadenas para decidir cómo "cerrar" dos cadenas entre sí. Este algoritmo, implementado como un problema dinámico toma O (mn) el tiempo, donde myn son las longitudes del texto y el patrón, respectivamente. Entonces, si tengo que unir una cuerda con otras 5000 cuerdas, tomará MUCHO tiempo, lo cual en mi aplicación simplemente no es aceptable. ¿Hay una solución más rápida que pueda implementarse? No me importa cambiar el espacio de almacenamiento por tiempo.

He visto una aplicación llamada "Swype" en Android, que hace algo similar. Busca su consulta en su propia base de datos y sugiere resultados. ¿Cómo funciona eso tan rápido?

Nota: No sugiera marcos como Lucene, porque no puedo ejecutarlos en J2ME.

Answer 1

de splix es buena. Como otra opción (para grandes conjuntos de cuerda), es posible que desee considerar el uso de una representación de n-gramas:

http://en.wikipedia.org/wiki/N-gram

Éstos se utilizan para la coincidencia de patrones aproximados en una gran cantidad de paquetes de bases de datos, ya que son rápidos y fácil de implementar usando metodologías de indexación convencionales.

Answer 2

Hemos usado http://en.wikipedia.org/wiki/Aho%E2%80%93Corasick_string_matching_algorithm para casi lo mismo, y funcionó bien para nosotros.

Hay pocas implementaciones de Java de la misma, se pueden encontrar en la web

PS también se puede comprobar otros algoritmos cadena de equiparación: Respuesta http://en.wikipedia.org/wiki/String_searching_algorithm

Answer 3

También es una cuestión de cómo definir "cerrar". Si no insiste en lo escrito, pero también funcionaría, podría sugerir soundex. Es un algoritmo muy rápido para ver si 2 palabras tienen un cierre fonético.

Answer 4

Realmente depende de los textos que está comparando. A continuación, presento dos enfoques de aceleración dentro del marco de edición-distancia original.

Una vez tuvimos la misma tarea en la que combinamos una secuencia de palabras corta (algo así como 10-30 caracteres) frente a un diccionario de> 300k frases cortas (también 10-30 caracteres cada una). En este caso, el siguiente enfoque nos salvó un montón de tiempo:

• tipo el diccionario de cadenas de destino (esto se tiene que hacer sólo una vez)
• cuando se genera la tabla n * m de cuerda i que pueda reutilice la tabla de la cadena i-1 ya que la mayoría de las líneas son comunes.

E.g. si tiene las dos cadenas "list of strings" y siguiente "list of words" puede reutilizar las primeras 8 líneas de su tabla y solo tiene que volver a calcular 5 (ambas cadenas tienen 8 caracteres en común). De esta forma, ahorramos hasta el 70-80% del tiempo de ejecución con solo pequeños cambios en nuestro código.

Si en cambio tiene pocos textos largos, el primer enfoque no le ahorrará mucho. Pero en este caso, usted espera que solo unas pocas entradas tengan una pequeña distancia de edición, mientras que las demás tienen una gran distancia. Como la tabla n * m es un tanto monótona en cada dirección (es decir, el mínimo de cada línea es monotónico, así como para cada columna), puede detener el cálculo una vez que alcanza un umbral preestablecido.Incluso puede guardar los resultados intermedios y "reiniciar" el cálculo (con un límite superior) si no encuentra una solución dentro de su umbral inicial.