la distancia de cadena basado en la comparación de los hashes precalculados

Question

Tengo una lista grande (más de 200.000) de cadenas que me gustaría comparar a una cadena dada. La cadena dada es insertado por un usuario, por lo que puede ser ligeramente incorrecta.

Lo que yo esperaba hacer era crear una especie de picadillo precomputed en cada cadena de añadirlo a la lista. Este hash podría contener información tal como longitud de la cadena, además de todos los personajes, etc.

se, ya existe Mi pregunta algo como esto? Seguramente habría algo que me permite evitar correr distancia Levenshtein en cada cuerda en la lista?

O tal vez hay una tercera opción que no he pensado todavía?

Answer 1

Parece que usted quiere usar un hash difusa de algún tipo. Hay un montón de funciones hash disponibles que pueden hacer cosas como esta. El viejo clásico " SOUNDEX " algoritmo podría incluso trabajo.

Otro pensamiento - si estima que la probabilidad de una entrada incorrecta es baja, entonces usted podría ser en realidad fino que tiene un impacto directo 99,9% de las veces, cayendo de nuevo a SOUNDEX que podría coger el 90% de los casos restantes y luego buscar toda la lista para el 0,01% restante del tiempo.

También vale la pena esta discusión: ¿Cómo encontrar la mejor coincidencia parcial de una cadena en una base de datos cadena grande