Tout d'abord, la distance de Levenshtein est définie comme le nombre minimum de modifications requises 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. C'est donc bien la "différence entre deux cordes", pour une certaine définition de la distance. =)
Il semble que vous recherchiez 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 des autres sont des candidats pour les fautes de frappe. En plus de la distance de Levenshtein, vous pouvez également envisager Needleman–Wunsch . C'est fondamentalement la même chose mais cela vous permet de fournir une fonction pour savoir à quel point un caractère donné est proche d'un autre caractère. Vous pouvez utiliser cet algorithme avec un ensemble de poids qui reflètent les positions des touches sur un clavier QWERTY pour faire un assez bon travail de recherche de fautes de frappe. Cela aurait cependant 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 chaînes, vous allez avoir des ennuis si vous faites les choses naïvement. Voici quelques suggestions pour accélérer les choses :
- Excuses si cela est évident, mais la distance de Levenshtein est symétrique, alors assurez-vous que vous ne calculez pas F(A, B) et F(B, A).
- abs(len(A) - len(B)) est une borne inférieure sur la distance entre les chaînes A et B. Vous pouvez donc ignorer 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 distance assez élevée de "First Street", même si vous voulez probablement les considérer comme identiques. La façon la plus simple de gérer cela est probablement de transformer les chaînes en une forme canonique avant de faire les comparaisons. Ainsi, vous pouvez mettre toutes les chaînes en minuscules, utiliser un dictionnaire qui mappe "1st" à "first", etc. Ce dictionnaire peut devenir assez volumineux, mais je ne connais pas de meilleure façon de gérer ces problèmes.
Puisque vous avez marqué cette question avec php, je suppose que vous voulez utiliser php pour cela. PHP a une fonction intégrée levenshtein() mais les deux chaînes doivent être de 255 caractères ou moins. Si ce n'est pas assez long, vous devrez créer le vôtre. Alternativement, vous étudiez en utilisant la difflib de Python.
