Tout d'abord, la distance de Levenshtein est définie comme le nombre minimum d'edi ts requis pour transformer la chaîne A en chaîne B, où une modification est l'insertion, ou la suppression d'un seul caractère, ou le remplacement d'un caractère par un autre caractère. Donc, c'est vraiment la "différence entre deux chaînes", pour une certaine définition de la distance. =)
Il semble que vous cherchiez une fonction de distance F (A, B) qui donne une distance entre les chaînes A et B et un seuil N où les chaînes dont la distance est inférieure à N les unes par rapport aux autres sont des fautes de frappe . En plus de la distance Levenshtein, vous pouvez également envisager Needleman–Wunsch. C'est fondamentalement la même chose mais cela vous permet de fournir une fonction pour la proximité d'un personnage par rapport à un autre personnage. Vous pouvez utiliser cet algorithme avec un ensemble de poids qui reflètent les positions des touches sur un clavier QWERTY pour faire un bon travail de recherche de fautes de frappe. Cela aurait des problèmes avec les claviers internationaux.
Si vous avez k chaînes et que vous voulez trouver des fautes de frappe potentielles, le nombre de comparaisons que vous devez faire est O (k^2). De plus, chaque comparaison est O (len (A) * len (B)). Donc, si vous avez un million de cordes, vous allez vous retrouver en difficulté si vous faites des choses naïvement. Voici quelques suggestions sur la façon d'accélérer les choses:
- Toutes mes excuses si cela est évident, mais la distance Levenshtein est symétrique, alors assurez-vous ne calcule pas F (A, B) et F (B, A). Abs (len (A) - len (B)) est une limite inférieure de la distance entre les chaînes A et B. Vous pouvez donc sauter la vérification des chaînes dont les longueurs sont trop différentes.
Un problème que vous pourriez rencontrer est que "1st St." a une assez grande distance de "First Street", même si vous voulez probablement considérer ceux d'être identiques. Le moyen le plus simple de gérer ceci est probablement de transformer les chaînes en une forme canonique avant de faire les comparaisons. Donc, vous pouvez faire toutes les chaînes en minuscules, utiliser un dictionnaire qui mappe "1er" à "premier", etc Ce dictionnaire pourrait devenir assez gros, mais je ne connais pas une meilleure façon de régler ce problème.
Depuis que vous avez étiqueté cette question avec php, je suppose que vous voulez utiliser php pour cela. PHP a une fonction levenshtein() intégrée, mais les deux chaînes doivent avoir 255 caractères ou moins. Si ce n'est pas assez long, vous devrez créer le vôtre. Alternativement, vous étudiez en utilisant le difflib de Python.