Une définition possible du problème de correspondance approximative des chaînes est la suivante: Étant donné une chaîne de motif P = p 1 p 2. . . p m {\displaystyle P = p_{1} p_{2}…p_{m}}
et une chaîne de texte T = t 1 t 2 … t n {\displaystyle T = t_ {1} t_{2}\dots t_{n}}
, trouvez une sous-chaîne T j’, j = t j’ t t j {\displaystyle t_ {j’,j} =t_ {j ‘} \dots t_ {j}}
dans T, qui, de toutes les sous-chaînes de T, a la plus petite distance d’édition au motif P.
Une approche par force brute consisterait à calculer la distance d’édition à P pour toutes les sous-chaînes de T, puis à choisir la sous-chaîne avec la distance minimale. Cependant, cet algorithme aurait le temps d’exécution O(n3 m).
Une meilleure solution, proposée par les vendeurs, repose sur la programmation dynamique. Il utilise une formulation alternative du problème : pour chaque position j du texte T et chaque position i du motif P, calculez la distance d’édition minimale entre les i premiers caractères du motif, P i {\displaystyle P_{i}}
, et toute sous-chaîne T j’, j {\displaystyle T_ {j’, j}}
de T qui se termine à la position j.
Pour chaque position j du texte T, et chaque position i du motif P, parcourez toutes les sous-chaînes de T se terminant à la position j, et déterminez laquelle d’entre elles a la distance minimale aux i premiers caractères du motif P. Écrivez cette distance minimale comme E (i, j). Après avoir calculé E(i,j) pour tous les i et j, nous pouvons facilement trouver une solution au problème d’origine: c’est la sous-chaîne pour laquelle E(m,j) est minimal (m étant la longueur du motif P.)
Le calcul de E(m,j) est très similaire au calcul de la distance d’édition entre deux chaînes. En fait, nous pouvons utiliser l’algorithme de calcul de distance de Levenshtein pour E (m, j), la seule différence étant qu’il faut initialiser la première ligne avec des zéros, et enregistrer le chemin de calcul, c’est−à−dire si nous avons utilisé E (i−1, j), E (i, j−1) ou E (i-1, j-1) dans le calcul de E (i, j).
Dans le tableau contenant les valeurs E(x, y), nous choisissons ensuite la valeur minimale dans la dernière ligne, que ce soit E(x2, y2), et suivons le chemin de calcul en arrière, jusqu’au numéro de ligne 0. Si le champ auquel nous sommes arrivés était E(0, y1), alors T… T est une sous-chaîne de T avec la distance d’édition minimale au motif P.
Le calcul du tableau E(x, y) prend du temps O(mn) avec l’algorithme de programmation dynamique, tandis que la phase de travail en arrière prend du temps O(n + m).
Une autre idée récente est la jointure de similarité. Lorsque la base de données correspondante concerne une grande échelle de données, le temps O (mn) avec l’algorithme de programmation dynamique ne peut pas fonctionner dans un temps limité. L’idée est donc, au lieu de calculer la similitude de toutes les paires de chaînes, de réduire le nombre de paires candidates. Les algorithmes largement utilisés sont basés sur la vérification des filtres, le hachage, le hachage sensible à la localité (LSH), les essais et d’autres algorithmes gourmands et d’approximation. La plupart d’entre eux sont conçus pour s’adapter à un cadre (tel que Map-Reduce) pour calculer simultanément.