För det första definieras Levenshtein-avståndet som det minsta antal redigeringar som krävs för att omvandla sträng A till sträng B, där en redigering är infogning eller borttagning av ett enstaka tecken, eller ersättning av ett tecken med ett annat tecken. Så det är mycket "skillnaden mellan två strängar", för en viss definition av avstånd. =)
Det låter som att du letar efter en avståndsfunktion F(A, B) som ger ett avstånd mellan strängarna A och B och ett tröskelvärde N där strängar med avstånd mindre än N från varandra är kandidater för stavfel. Förutom Levenshtein-avstånd kan du också överväga Needleman–Wunsch . Det är i princip samma sak men det låter dig ge en funktion för hur nära en given karaktär är en annan karaktär. Du kan använda den algoritmen med en uppsättning vikter som återspeglar tangenternas positioner på ett QWERTY-tangentbord för att göra ett ganska bra jobb med att hitta stavfel. Detta skulle dock ha problem med internationella tangentbord.
Om du har k-strängar och du vill hitta potentiella stavfel, är antalet jämförelser du behöver göra O(k^2). Dessutom är varje jämförelse O(len(A)*len(B)). Så om du har en miljon strängar kommer du att hamna i problem om du gör saker naivt. Här är några förslag på hur du kan snabba upp saker och ting:
- Ursäkta om detta är uppenbart, men Levenshtein-avståndet är symmetriskt, så se till att du inte beräknar F(A, B) och F(B, A).
- abs(len(A) - len(B)) är en nedre gräns för avståndet mellan strängarna A och B. Så du kan hoppa över att kontrollera strängar vars längder är för olika.
Ett problem du kan stöta på är att "1st St." har ett ganska långt avstånd från "First Street", även om du antagligen vill anse att de är identiska. Det enklaste sättet att hantera detta är förmodligen att omvandla strängar till en kanonisk form innan jämförelserna görs. Så du kan göra alla strängar med små bokstäver, använda en ordbok som mappar "första" till "första" osv. Den ordboken kan bli ganska stor, men jag vet inte ett bättre sätt att hantera dessa problem.
Eftersom du taggade den här frågan med php, antar jag att du vill använda php för detta. PHP har en inbyggd levenshtein()-funktion men båda strängarna måste vara 255 tecken eller mindre. Om det inte är tillräckligt länge måste du göra din egen. Alternativt undersöker du med Pythons difflib.