Distance de Levenshtein : le guide ultime pour mesurer la similarité textuelle

Patricia Arquette
Libérer: 2024-11-07 21:05:03
original
1065 Les gens l'ont consulté

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 :

  1. Insertion : Ajout d'un personnage.
  2. Suppression : Supprimer un personnage.
  3. Substitution : Remplacement d'un caractère par un autre.

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.

Le concept mathématique

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 :

Levenshtein Distance: The Ultimate Guide to Measuring Textual Similarity

Implémentation Python

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
Copier après la connexion

Applications pratiques

1. Vérification orthographique

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.

2. Recherche floue

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.

3. Comparaison d'ADN

En bioinformatique, cette distance permet de mesurer la similarité entre deux séquences d'ADN, où chaque opération représente une mutation potentielle.

4. Authentification et détection de fraude

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.

Optimisation : distance de Levenshtein avec mémoire réduite

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
Copier après la connexion

Conclusion

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 !

Vous avez des questions ou des idées sur la distance de Levenshtein ? Partagez-les dans les commentaires ! ?

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!

source:dev.to
Déclaration de ce site Web
Le contenu de cet article est volontairement contribué par les internautes et les droits d'auteur appartiennent à l'auteur original. Ce site n'assume aucune responsabilité légale correspondante. Si vous trouvez un contenu suspecté de plagiat ou de contrefaçon, veuillez contacter admin@php.cn
Derniers articles par auteur
Tutoriels populaires
Plus>
Derniers téléchargements
Plus>
effets Web
Code source du site Web
Matériel du site Web
Modèle frontal