Levenshtein Python Implémentation algo Wagner & Fischer

algorithme knn python

Voici l’implémentation en python de l’algorithme de Wagner & Fischer (Wagner-Fischer). Il permet de calculer la distance de Levenshtein (distance entre deux chaines de caractères).

Wagner python Levenshtein python Voici l'implémentation en python de l'algorithme de Wagner & Fischer (Wagner-Fischer) qui permet de calculer la distance de Levenshtein.

Premièrement le but de l’algorithme est de trouver le coût minimal. Coût minimal pour transformer une chaîne en une autre. Alors une fonction récursive permet de retourner le nombre minimal de transformation. Et pour transformer une sous-chaine de A avec n caractères en une sous-chaine de B avec le même nombre de caractères. La solution est donnée. Il faut calculer la distance entre les 2 lettres à la même position dans la chaine A et B. Alors Soit les lettres et la lettre précédentes sont identiques. Soit il y a une différence et dans ce cas on calcule 3 côuts. Alors le premier est de supprimer une lettre le la chaine A. Et d’insérer une lettre dans la chaine A pour substituer une lettre de la chaine A. Alors On peut alors trouver le cout minimal.

import numpy as np

def levenshtein(chaine1, chaine2):
    taille_chaine1 = len(chaine1) + 1
    taille_chaine2 = len(chaine2) + 1
    levenshtein_matrix = np.zeros ((taille_chaine1, taille_chaine2))
    for x in range(taille_chaine1):
        levenshtein_matrix [x, 0] = x
    for y in range(taille_chaine2):
        levenshtein_matrix [0, y] = y

    for x in range(1, taille_chaine1):
        for y in range(1, taille_chaine2):
            if chaine1[x-1] == chaine2[y-1]:
                levenshtein_matrix [x,y] = min(
                    levenshtein_matrix[x-1, y] + 1,
                    levenshtein_matrix[x-1, y-1],
                    levenshtein_matrix[x, y-1] + 1
                )
            else:
                levenshtein_matrix [x,y] = min(
                    levenshtein_matrix[x-1,y] + 1,
                    levenshtein_matrix[x-1,y-1] + 1,
                    levenshtein_matrix[x,y-1] + 1
                )
    return (levenshtein_matrix[taille_chaine1 - 1, taille_chaine2 - 1])

print("distance de levenshtein = " + str(levenshtein("Lorem ipsum dolor sit amet", "Laram zpsam dilir siy amot")))

Pour calculer la distance de Levenshtein avec un algorithme non récursif. On utilise une matrice qui contient les distances de Levenshtein. Alors Ce sont les distances entre tous les préfixes de la première chaîne et tous les préfixes de la seconde chaîne de caractères.

Aussi on peut calculer dynamiquement les valeurs dans cette matrice. La dernière valeur calculée sera la distance de Levenshtein entre les deux chaînes entières.

Enfin il y a de nombreux cas d’utilisation de la distance de Levenshtein. La distance de Levenshtein est utilisée dans des domaines. La linguistique informatique, la biologie moléculaire. Et encore la bioinformatique, le machine learning. Également le deep learning, l’analyse de l’ADN. De plus, un programme qui fait de la vérification orthographique utilise par exemple la distance de Levenshtein.

Liens sur l’algorithme de Wagner & Fischer (Wagner-Fischer) et la distance de Levenshtein en Python ou d’autre langage :

https://graal.hypotheses.org/tag/algorithme-de-wagner-fischer

https://fr.wikipedia.org/wiki/Algorithme_de_Wagner-Fischer

https://fr.wikipedia.org/wiki/Distance_de_Levenshtein

https://medium.com/@sddkal/wagner-fischer-algorithm-be0d96893f6d

https://www.python-course.eu/levenshtein_distance.php

Liens internes sur les algorithmes

http://128mots.com/index.php/category/python/

http://128mots.com/index.php/category/graphes/

Laisser un commentaire

Votre adresse e-mail ne sera pas publiée. Les champs obligatoires sont indiqués avec *