For det første er Levenshtein-afstand defineret som det mindste antal redigeringer, der kræves for at transformere streng A til streng B, hvor en redigering er indsættelse eller sletning af et enkelt tegn eller udskiftning af et tegn med et andet tegn. Så det er meget "forskellen mellem to strenge", for en bestemt definition af afstand. =)
Det lyder som om du leder efter en afstandsfunktion F(A, B), der giver en afstand mellem strenge A og B og en tærskel N, hvor strenge med afstand mindre end N fra hinanden er kandidater til slåfejl. Ud over afstand til Levenshtein kan du også overveje Needleman–Wunsch . Det er dybest set det samme, men det lader dig give en funktion for, hvor tæt en given karakter er på en anden karakter. Du kan bruge den algoritme med et sæt vægte, der afspejler placeringen af taster på et QWERTY-tastatur til at gøre et ret godt stykke arbejde med at finde stavefejl. Dette ville dog have problemer med internationale tastaturer.
Hvis du har k strenge, og du vil finde potentielle tastefejl, er antallet af sammenligninger, du skal foretage, O(k^2). Derudover er hver sammenligning O(len(A)*len(B)). Så hvis du har en million strenge, vil du finde dig selv i problemer, hvis du gør tingene naivt. Her er et par forslag til, hvordan du kan fremskynde tingene:
- Undskyld, hvis dette er indlysende, men Levenshtein-afstanden er symmetrisk, så sørg for, at du ikke udregner F(A, B) og F(B, A).
- abs(len(A) - len(B)) er en nedre grænse for afstanden mellem strenge A og B. Så du kan springe over at kontrollere strenge, hvis længde er for forskellige.
Et problem, du måske støder på, er, at "1st St." har en ret stor afstand fra "First Street", selvom du nok vil betragte dem som identiske. Den nemmeste måde at håndtere dette på er sandsynligvis at transformere strenge til en kanonisk form, før sammenligningerne udføres. Så du kan lave alle strenge med små bogstaver, bruge en ordbog, der kortlægger "1st" til "first" osv. Den ordbog kan blive ret stor, men jeg kender ikke en bedre måde at håndtere disse problemer på.
Da du taggede dette spørgsmål med php, går jeg ud fra, at du vil bruge php til dette. PHP har en indbygget levenshtein() funktion, men begge strenge skal være på 255 tegn eller mindre. Hvis det ikke er længe nok, bliver du nødt til at lave din egen. Alternativt undersøger du ved hjælp af Pythons difflib.