Innanzitutto, la distanza di Levenshtein è definita come il numero minimo di modifiche necessarie per trasformare la stringa A nella stringa B, dove una modifica è l'inserimento o la cancellazione di un singolo carattere o la sostituzione di un carattere con un altro carattere. Quindi è proprio la "differenza tra due stringhe", per una certa definizione di distanza. =)
Sembra che tu stia cercando una funzione di distanza F(A, B) che fornisca una distanza tra le stringhe A e B e una soglia N in cui le stringhe con distanza inferiore a N l'una dall'altra sono candidate per errori di battitura. Oltre alla distanza di Levenshtein potresti anche prendere in considerazione Needleman–Wunsch . È fondamentalmente la stessa cosa, ma ti consente di fornire una funzione per quanto un determinato personaggio è vicino a un altro personaggio. Potresti usare quell'algoritmo con una serie di pesi che riflettono le posizioni dei tasti su una tastiera QWERTY per fare un buon lavoro nel trovare errori di battitura. Ciò avrebbe problemi con le tastiere internazionali.
Se hai k stringhe e vuoi trovare potenziali errori di battitura, il numero di confronti che devi fare è O(k^2). Inoltre, ogni confronto è O(len(A)*len(B)). Quindi, se hai un milione di corde, ti troverai nei guai se fai le cose ingenuamente. Ecco alcuni suggerimenti su come velocizzare le cose:
- Ci scusiamo se è ovvio, ma la distanza di Levenshtein è simmetrica, quindi assicurati di non calcolare F(A, B) e F(B, A).
- abs(len(A) - len(B)) è un limite inferiore sulla distanza tra le stringhe A e B. Quindi puoi saltare il controllo delle stringhe la cui lunghezza è troppo diversa.
Un problema che potresti incontrare è che "1st St." ha una distanza piuttosto elevata da "First Street", anche se probabilmente vorrai considerarle identiche. Il modo più semplice per gestirlo è probabilmente trasformare le stringhe in una forma canonica prima di fare i confronti. Quindi potresti rendere tutte le stringhe minuscole, usare un dizionario che associ "1st" a "first", ecc. Quel dizionario potrebbe diventare piuttosto grande, ma non conosco un modo migliore per affrontare questi problemi.
Dato che hai taggato questa domanda con php, presumo che tu voglia usare php per questo. PHP ha una funzione levenshtein() incorporata ma entrambe le stringhe devono essere di 255 caratteri o meno. Se non è abbastanza lungo dovrai crearne uno tuo. In alternativa, esamini usando difflib di Python.
