Cómo encontrar la mejor coincidencia difusa para una cadena en una base de datos de cadena grande

Question

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 utilizar la distancia de edición para comparar cada cadena de base de datos a 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 crear el índice en memoria?

Answer 1

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.

Answer 2

Compute 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.

A continuación, busque el hash SOUNDEX de la cadena de búsqueda y haga coincidir.

Answer 3

This paper seems to describe exactly what you want.

Lucene (http://lucene.apache.org/) también implementa Levenshtein distancia de edición.

Answer 4

Usted no ha mencionado su sistema de base de datos, pero para PostrgreSQL podría utilizar el siguiente módulo contrib: módulo contrib trgm - Trigram matching for PostgreSQL

El pg_trgm proporciona funciones y clases de índice para determinar la similitud de texto basado en la coincidencia trigrama .

Answer 5

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

Answer 6

Una muy extensa explicación de algoritmos relevantes se encuentra en el libro Algoritmos en cadenas, árboles y Secuencias: Informática y Biología Computacional por Dan Gusfield.

Answer 7

https://en.wikipedia.org/wiki/Levenshtein_distance

algoritmo Levenshtein se ha implementado en algunos DBMS

(Por ejemplo PostgreSQL: http://www.postgresql.org/docs/9.1/static/fuzzystrmatch.html)