bitap fuzzy-search string-search

fuzzy search - bitap - Cómo encontrar la mejor coincidencia difusa para una cadena en una gran base de datos de cadenas



fuzzy search npm (7)

Tengo una base de datos de cadenas (longitud arbitraria) que contiene más de un millón de elementos (potencialmente más).

Necesito comparar una cadena proporcionada por el usuario con toda la base de datos y recuperar una cadena idéntica si existe o devolver la (s) coincidencia (s) difusa (s) más cercana (60% de similitud o mejor). El tiempo de búsqueda idealmente debería ser inferior a un segundo.

Mi idea es usar la distancia de edición para comparar cada secuencia de base de datos con la cadena de búsqueda después de reducir los candidatos de la base de datos en función de su longitud.

Sin embargo, como tendré que realizar esta operación muy a menudo, estoy pensando en construir un índice de las cadenas de db para mantener en la memoria y consultar el índice, no el db directamente.

¿Alguna idea sobre cómo abordar este problema de manera diferente o cómo construir el índice en memoria?

Si su base de datos lo admite, debe usar la búsqueda de texto completo. De lo contrario, puede usar un indexador como lucene y sus diversas implementaciones.

Calcule el hash SOUNDEX (que está integrado en muchos motores de base de datos SQL) e indexe por él.

SOUNDEX es un hash basado en el sonido de las palabras, por lo que los errores ortográficos de la misma palabra probablemente tengan el mismo hash SOUNDEX.

Luego, encuentre el hash SOUNDEX de la cadena de búsqueda y haga coincidir.

Dado que la cantidad de datos es grande, al insertar un registro calcularía y almacenaría el valor del algoritmo fonético en una columna indexada y luego restringiría (cláusula WHERE) mis consultas seleccionadas dentro de un rango en esa columna.

No mencionó su sistema de base de datos, pero para PostrgreSQL podría usar el siguiente módulo contrib: trgm - Trigram matching para PostgreSQL

El módulo pg_trgm contrib proporciona funciones y clases de índice para determinar la similitud del texto en función de la concordancia de trigramas.

Una explicación muy extensa de los algoritmos relevantes se encuentra en el libro Algorithms on Strings, Trees and Sequences: Computer Science and Computational Biology, de Dan Gusfield .