Numeri di corrispondenza fuzzy

Question

Ho lavorato con Double Metaphone e Caverphone2 per confronti con String e funzionano bene su nomi, indirizzi, ecc. (Caverphone2 funziona meglio per me). Tuttavia, essi producono troppi falsi positivi quando si arriva a valori numerici, come numeri di telefono, indirizzi IP, numeri di carte di credito, ecc

Così ho guardato gli algoritmi Luhn e Verhoeff e descrivono in sostanza quello che Voglio, ma non del tutto. Sembrano validi in fase di validazione, ma non sembrano costruiti per la corrispondenza fuzzy. C'è qualcosa che si comporta come Luhn e Verhoeff, che potrebbe rilevare errori a una cifra e errori di trasposizione che coinvolgono due cifre adiacenti, per scopi di codifica e confronto simili agli algoritmi di stringa fuzzy?

Mi piacerebbe codificare un numero, quindi confrontarlo con altri 100.000 numeri per trovare corrispondenze strettamente identiche. Quindi qualcosa come 7041234 corrisponderebbe a 7041324 come possibile errore di trascrizione, ma qualcosa come 4213704 non lo farebbe.

Answer 1

andfriends può essere utile per individuare la distanza tra stringhe o numeri specifici. Tuttavia, se si desidera creare un correttore ortografico, non si desidera eseguire l'intero database delle parole ad ogni query.

Peter Norvig ha scritto a very nice article su un semplice correttore ortografico di "corrispondenza sfocata" basato su una parte della tecnologia alla base dei suggerimenti di ortografia di Google.

Se il dizionario ha voci N e la parola media ha lunghezza L, l'approccio "Brute force Levenshtein" richiederebbe un tempo O(N*L^3). L'approccio di Peter Norvig invece genera tutte le parole entro una determinata distanza di modifica dall'input e le ricerca nel dizionario. Quindi raggiunge O(L^k), dove k è la distanza di modifica più lontana considerata.