Hay una base de datos con N cadenas de longitud fija. Hay una cadena de consulta de la misma longitud. El problema es obtener las primeras k cadenas de la base de datos que tienen la menor distancia de Hamming a q.

N es pequeño (alrededor de 400), las cadenas son largas, de longitud fija. La base de datos no cambia, por lo que podemos calcular previamente los índices. Las consultas varían mucho, el almacenamiento en caché y / o el cálculo previo no es una opción. Hay muchos por segundo. Siempre necesitamos k resultados, incluso si los resultados de k-1 tienen coincidencia 0 (ordenando la distancia de Hamming y tomando la primera k, por lo que el hashing sensible a la localidad y enfoques similares no funcionarán) La partición de kd-tree y espacio similar probablemente llevará a cabo una búsqueda peor que la búsqueda lineal (las cadenas pueden ser muy largas). BK-tree es actualmente la mejor opción, pero sigue siendo lento y complicado de lo que debe ser.

Parece que hay un algoritmo, que creará un índice, que descartará la mayoría de las entradas en muy pocos pasos, dejando k <= t << N entradas para calcular la distancia real de Hamming.

Personas que sugieren una coincidencia de cadenas difusa basada en la distancia de Levenstein, gracias, pero el problema es mucho más simple. Los enfoques basados en métricas de distancia generalizada (como los árboles BK) son buenos, pero tal vez haya algo que utilice los hechos descritos anteriormente (DB pequeño / cadenas de tamaño fijo largas, distancia de Hamming simple)

Enlaces, palabras clave, documentos, ideas? =)