Explication de la distance d'édition et de l'implémentation en Python

Description de l'algorithme

La distance d'édition (distance de Lebenstein) est le nombre d'étapes nécessaires pour changer une chaîne de caractères en une autre. Cette étape est ・ Supprimer un caractère ・ Insérez un seul caractère ・ Remplacez un personnage par un autre Fait partie de

Comprenons d'abord l'algorithme de distance de Levenstein

Par exemple, dans le cas des chaînes "cafe" et "coffee" cafe→caffe→coffe→coffee Quelque chose comme ça

Faisons d'abord une table

		c	o	f	f	e	e

c
a
f
e

Entrons la valeur initiale Lorsque la chaîne cible est vide (la chaîne cible sera augmentée petit à petit), bien sûr, la distance de Levenstein est égale à la longueur de la chaîne. Alors

		c	o	f	f	e	e
	0	1	2	3	4	5	6
c	1	*
a	2
f	3
e	4

L'algorithme de production commence à partir de "*****" dans (3,3) Toutes les cellules restantes seront au ** minimum ** en dessous de cela • Si le caractère supérieur de la colonne de cette cellule est le même que le caractère le plus à gauche de la ligne de cette cellule, la valeur de cette cellule est égale à ** la valeur de la cellule supérieure gauche **, donc Sinon ** la valeur dans la cellule supérieure gauche + 1 ** ・ Valeur dans la cellule de gauche +1 ・ Valeur de la cellule supérieure +1

Ici, dans le cas de (3,3) ・ Puisque le caractère supérieur "c" dans la colonne en (3,3) et le caractère le plus à gauche "c" dans la ligne sont identiques, il devient 0. ・ Parce qu'il devient (2,3), il devient 1. ・ Parce qu'il devient (3,2), il devient 1. (3,3) devient 0 car il prend le minimum des trois valeurs ci-dessus

		c	o	f	f	e	e
	0	1	2	3	4	5	6
c	1	0
a	2
f	3
e	4

Remplissez toutes les cellules comme ça

		c	o	f	f	e	e
	0	1	2	3	4	5	6
c	1	0	1	2	3	4	5
a	2	1	1	2	3	4	5
f	3	2	2	1	2	3	4
e	4	3	3	2	2	2	3

Obtenez cette table. La valeur en bas à droite de ce tableau est la distance de Levenstein.

Implémenté par Python 3.5.2

Si vous mettez cet algorithme dans un programme

`levenshtein.py`


class Levenshtein:
#Lancez le tableau ici et entrez la valeur initiale
    def initArray(self,str1,str2):
        distance = []
        for i in range(len(str1)+1):
            distance.append([0]*(len(str2)+1))
            distance[i][0] = i
        for j in range(len(str2)+1):
            distance[0][j] = j
        return distance
#Mettre une valeur dans une cellule
    def editDist(self,str1,str2,distance):
        dist = [0]*3
        for i in range(1,len(str1)+1):
            for j in range(1,len(str2)+1):
                dist[0] = distance[i-1][j-1] if str1[i-1]==str2[j-1] else distance[i-1][j-1]+1
                dist[1] = distance[i][j-1]+1
                dist[2] = distance[i-1][j]+1
                distance[i][j]=min(dist)
        return distance[i][j]

    def __init__(self,str1,str2):
        self.str1 = str1
        self.str2 = str2
        Levenshtein.distance = self.initArray(str1,str2)
        Levenshtein.dist = self.editDist(str1,str2,Levenshtein.distance)

if __name__ == '__main__':
    str1 = 'coffee'
    str2 = 'cafe'
    leven = Levenshtein(str1,str2)
    print(leven.dist)