La Distance de Levenshtein, également connue sous le nom de distance d'édition, est une mesure fondamentale pour évaluer la similarité entre deux chaînes. Il calcule le nombre minimum d'opérations nécessaires pour transformer une chaîne en une autre. Ces opérations comprennent :
Ce concept est au cœur de nombreuses applications modernes, telles que la vérification orthographique, la recherche floue et la comparaison de séquences d'ADN.
La distance de Levenshtein entre deux chaînes ( A ) et ( B ) de longueurs ( n ) et ( m ), respectivement, peut être calculée à l'aide d'une approche de programmation dynamique. Nous définissons une matrice ( D ) de taille ((n 1) fois (m 1)), où chaque entrée ( D[i][j] ) représente le coût minimum pour transformer les premiers ( i ) caractères de ( A ) en les premiers ( j ) caractères de ( B ).
La relation de récurrence est la suivante :
Voici une implémentation Python simple pour calculer la distance de Levenshtein :
def levenshtein_distance(a, b): n, m = len(a), len(b) dp = [[0] * (m + 1) for _ in range(n + 1)] for i in range(n + 1): for j in range(m + 1): if i == 0: dp[i][j] = j elif j == 0: dp[i][j] = i elif a[i - 1] == b[j - 1]: dp[i][j] = dp[i - 1][j - 1] else: dp[i][j] = 1 + min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) return dp[n][m] # Example usage print(levenshtein_distance("kitten", "sitting")) # Output: 3
Les correcteurs orthographiques utilisent la distance de Levenshtein pour suggérer des corrections aux fautes de frappe. Par exemple, si vous tapez helo, cela peut suggérer bonjour ou héros.
Dans les moteurs de recherche, Levenshtein permet de renvoyer des résultats même lorsque les utilisateurs font des fautes de frappe ou d'orthographe.
En bioinformatique, cette distance permet de mesurer la similarité entre deux séquences d'ADN, où chaque opération représente une mutation potentielle.
Les systèmes détectant la fraude à l'identité peuvent comparer les entrées des utilisateurs avec les enregistrements existants, en tenant compte de petites différences textuelles.
L'algorithme classique utilise une matrice complète, qui peut être gourmande en mémoire. Heureusement, il peut être optimisé pour n'utiliser que deux lignes de mémoire, car chacune ( D[i][j] ) ne dépend que de ( D[i-1][j] ), ( D[i][j-1] ), et ( D[i-1][j-1] ).
def optimized_levenshtein(a, b): n, m = len(a), len(b) prev = list(range(m + 1)) curr = [0] * (m + 1) for i in range(1, n + 1): curr[0] = i for j in range(1, m + 1): insert = curr[j - 1] + 1 delete = prev[j] + 1 substitute = prev[j - 1] + (0 if a[i - 1] == b[j - 1] else 1) curr[j] = min(insert, delete, substitute) prev, curr = curr, prev return prev[m] # Example usage print(optimized_levenshtein("kitten", "sitting")) # Output: 3
La distance de Levenshtein est un outil puissant et polyvalent largement utilisé dans divers domaines. Bien que simples à comprendre, ses optimisations et ses applications complexes soulignent sa valeur dans les systèmes modernes.
Pour une exploration plus approfondie, envisagez des variantes comme la distance Damerau-Levenshtein, qui prend en compte les transpositions. Vous êtes désormais équipé pour intégrer cet outil dans vos projets ou impressionner vos pairs par votre profonde compréhension !
Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!