Correspond à deux chaînes mais autorise un certain degré d'erreur

Comment puis-je faire correspondre deux chaînes, mais en même temps permettre au nombre X de caractères d'être incorrect dans la correspondance. Le nombre d'erreurs doit être une variable contrôlable.

Bien que le nombre X de caractères ne puisse pas correspondre dans la chaîne, il devrait y avoir une limite au nombre de caractères exécutés dans une séquence. Étant donné deux chaînes, je pourrais permettre à 5 caractères d'être différents, mais pas plus de 2 d'affilée.

Je cherche un algorithme recommandé pour comparer ces deux chaînes, ou peut-être existe-t-il déjà une solution connue pour cela.

Un point de départ approximatif de recherche de chaîne est celui de la distance de Levenshtein . Cet algorithme compte le nombre de modifications d'un seul caractère (insertion, suppression et substitution) pour changer un mot en un autre.

Un exemple de ceci est kitten-> sittingqui a une distance d'édition de trois

1. k itten -> s itten (remplacer 's' par 'k')
2. sitt e n -> sitt i n (remplacer 'i' par 'e')
3. sittin -> sittin g (ajoutez 'g' à la fin)

Il existe des variantes de cet algorithme, notamment la distance Damerau – Levenshtein qui permet la transposition de deux caractères adjacents ('hte' à 'the' a une distance DL de 1 et une distance Levenshtein de 2) et est donc souvent plus approprié pour vérification orthographique. D'autres variantes existent pour les applications où les lacunes sont importantes (chaînes d'ADN).

La distance de Levenshtein est bien connue et pas trop difficile à trouver (j'ai eu une fois une raison de rechercher une implémentation de celle-ci en tant que fonction dans Oracle - c'était beaucoup plus rapide que de retirer toutes les données et d'exécuter le côté code de requête). Rosettacode a une multitude (54) d'implemntations de la distance Levenshtein (notez que certaines langues ont cela dans la bibliothèque de chaînes quelque part - si vous faites Java, regardez la langue apache commons ). Wikibooks a 31 implémentations et un coup d'œil rapide sur les deux n'affiche pas le même code pour la même langue.

La façon dont cela fonctionne est de construire une matrice qui correspond à la relation entre les deux chaînes:

 .kitten
.0123456
s1123456
i2212345
t3321234
t4432123
i5543223
n6654332
g7765443

La .ligne et la colonne indiquent que vous pouvez accéder à la chaîne cible en insérant «simplement» chaque lettre d'une chaîne vide. Ce n'est pas le cas idéal, mais il est là pour amorcer l'algorithme.

Si la valeur est la même que ce point ('i' == 'i'), la valeur est la même que la valeur en diagonale vers la gauche. Si les deux spots sont différents ('s'! = 'K') la valeur est le minimum de:

• diagonale vers le haut et vers la gauche + 1 (une substitution)
• directement au-dessus de + 1 (une insertion)
• directement à gauche + 1 (une suppression)

La valeur de retour de distance d'édition est la valeur en bas à droite de la matrice.

Si vous suivez du bas à droite vers le haut à gauche avec le minimum, vous pouvez voir les modifications effectuées:

 .kitten
.0.   .
s.1   .
i  1  .
t   1 .
t    1.
i.....2
n      2
g......3

Notez que c'est l'approche plutôt gourmande en mémoire. Il peut être réduit dans l'étendue de la mémoire en ne construisant pas la matrice complète - tout l'algorithme se soucie est un sous-ensemble des données et il peut être réduit d' N*Mespace en 2*max(N,M)espace en stockant simplement la ligne précédente (et ce qui a été calculé sur le courant rangée). Code Project montre comment cela peut être fait (avec du code C # à télécharger).