Ten eerste wordt de Levenshtein-afstand gedefinieerd als het minimale aantal bewerkingen dat nodig is om tekenreeks A in tekenreeks B te transformeren, waarbij een bewerking het invoegen of verwijderen van een enkel teken is, of de vervanging van een teken door een ander teken. Het is dus heel erg het "verschil tussen twee snaren", voor een bepaalde definitie van afstand. =)
Het klinkt alsof je op zoek bent naar een afstandsfunctie F(A, B) die een afstand geeft tussen strings A en B en een drempel N waarbij strings met een afstand kleiner dan N van elkaar kandidaten zijn voor typefouten. Naast Levenshtein-afstand kunt u ook Needleman–Wunsch overwegen . Het is eigenlijk hetzelfde, maar het laat je een functie geven voor hoe dicht een bepaald karakter bij een ander karakter is. Je zou dat algoritme kunnen gebruiken met een set gewichten die de posities van toetsen op een QWERTY-toetsenbord weergeven om typefouten te vinden. Dit zou echter problemen geven met internationale toetsenborden.
Als je k strings hebt en je wilt mogelijke typefouten vinden, dan is het aantal vergelijkingen dat je moet maken O(k^2). Bovendien is elke vergelijking O(len(A)*len(B)). Dus als je een miljoen snaren hebt, kom je in de problemen als je dingen naïef doet. Hier zijn een paar suggesties om dingen te versnellen:
- Excuses als dit duidelijk is, maar de Levenshtein-afstand is symmetrisch, dus zorg ervoor dat u F(A, B) en F(B, A) niet berekent.
- abs(len(A) - len(B)) is een ondergrens voor de afstand tussen strings A en B. U kunt dus strings controleren waarvan de lengte te verschillend is, overslaan.
Een probleem waar u tegenaan kunt lopen, is dat "1st St." heeft een vrij grote afstand van "First Street", hoewel je die waarschijnlijk als identiek wilt beschouwen. De gemakkelijkste manier om hiermee om te gaan, is waarschijnlijk om strings in een canonieke vorm te transformeren voordat je de vergelijkingen maakt. U kunt dus alle tekenreeksen in kleine letters maken, een woordenboek gebruiken dat "1e" aan "eerste" toewijst, enz. Dat woordenboek kan behoorlijk groot worden, maar ik weet geen betere manier om met deze problemen om te gaan.
Aangezien je deze vraag hebt getagd met php, neem ik aan dat je php hiervoor wilt gebruiken. PHP heeft een ingebouwde levenshtein()-functie, maar beide strings moeten 255 tekens of minder zijn. Als dat niet lang genoeg is, moet je er zelf een maken. Als alternatief onderzoek je met behulp van Python's difflib.