[GO] Erläuterung der Bearbeitungsentfernung und Implementierung in Python

Algorithmusbeschreibung

Der Bearbeitungsabstand (Lebenstein-Abstand) ist die Anzahl der Schritte, die erforderlich sind, um eine Zeichenkette in eine andere zu ändern. Dieser Schritt ist ・ Löschen Sie ein Zeichen ・ Fügen Sie ein einzelnes Zeichen ein ・ Ersetzen Sie ein Zeichen durch ein anderes Ist einer von

Lassen Sie uns zunächst den Levenstein-Distanzalgorithmus verstehen

Zum Beispiel bei den Saiten "Cafe" und "Kaffee" cafe→caffe→coffe→coffee Etwas wie das

Lassen Sie uns zuerst einen Tisch machen

		c	o	f	f	e	e

c
a
f
e

Geben wir den Anfangswert ein Wenn die Zielzeichenfolge leer ist (die Zielzeichenfolge wird nach und nach erhöht), entspricht der Levenstein-Abstand natürlich der Länge der Zeichenfolge. Damit

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

Der Produktionsalgorithmus beginnt bei "*****" in (3,3) Alle verbleibenden Zellen sind das ** Minimum ** darunter • Wenn das oberste Zeichen in der Spalte in dieser Zelle mit dem Zeichen ganz links in der Zeile in dieser Zelle übereinstimmt, entspricht der Wert in dieser Zelle ** dem Wert in der oberen linken Zelle ** Ansonsten ** der Wert in der oberen linken Zelle + 1 ** ・ Wert in der linken Zelle +1 ・ Wert der oberen Zelle +1

Hier im Fall von (3,3) ・ Da das oberste Zeichen "c" in der Spalte bei (3,3) und das am weitesten links stehende Zeichen "c" in der Zeile identisch sind, wird es zu 0. ・ Weil es (2,3) wird, wird es 1. ・ Weil es (3,2) wird, wird es 1. (3,3) wird 0, weil es das Minimum der obigen drei Werte annimmt

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

Füllen Sie alle Zellen so

		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

Holen Sie sich diesen Tisch. Der Wert unten rechts in dieser Tabelle ist der Levenstein-Abstand.

Implementiert von Python 3.5.2

Wenn Sie diesen Algorithmus in ein Programm einfügen

`levenshtein.py`


class Levenshtein:
#Starten Sie das Array hier und geben Sie den Anfangswert ein
    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
#Fügen Sie einen Wert in eine Zelle ein
    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)