Fuzzy Matching Numbers

Question

He estado trabajando con Double Metaphone y Caverphone2 para las comparaciones de cadenas y funcionan bien en cosas como nombres, direcciones, etc. (Caverphone2 funciona mejor para mí). Sin embargo, producen demasiados falsos positivos cuando llega a valores numéricos, como números de teléfono, direcciones IP, números de tarjetas de crédito, etc.

Así que he observado los algoritmos Luhn y Verhoeff y describen esencialmente qué Quiero, pero no del todo. Parecen buenos para la validación, pero no parecen estar diseñados para la coincidencia difusa. ¿Hay algo que se comporte como Luhn y Verhoeff, que podría detectar errores de un dígito y errores de transposición que involucran dos dígitos adyacentes, con fines de codificación y comparación similares a los algoritmos de la secuencia difusa?

Me gustaría codificar un número, luego compararlo con otros 100.000 números para encontrar coincidencias idénticas. Entonces algo como 7041234 podría coincidir con 7041324 como un posible error de transcripción, pero algo como 4213704 no lo haría.

Answer 1

Levenshteinandfriends puede ser bueno para encontrar la distancia entre cadenas específicas o números. Sin embargo, si desea construir un corrector ortográfico, no desea ejecutar toda su base de datos de palabras en cada consulta.

Peter Norvig escribió a very nice article en un corrector de ortografía "coincidencia aproximada" basado en la tecnología detrás de las sugerencias de ortografía de google.

Si su diccionario tiene N entradas, y la palabra promedio tiene longitud L, el enfoque "Brute force Levenshtein" llevaría tiempo O(N*L^3). El enfoque de Peter Norvig genera todas las palabras dentro de una cierta distancia de edición desde la entrada, y las busca en el diccionario. Por lo tanto, alcanza O(L^k), donde k es la distancia de edición más lejana considerada.