Python-Distanz bearbeiten

Heute werden wir etwas über die Bearbeitungsentfernung in Python lernen. Wir werden auch das Einfügen, Löschen, Ersetzen und die rekursive Implementierung der Zeichenkette untersuchen.

Abstand in Python bearbeiten

Die Bearbeitungsdistanz ist der Betrag, der für die Transposition einer Saite in eine andere Saite erforderlich ist. Diese Transposition erfolgt durch Rekursion, Substitution, Einfügung und Löschung der Zeichen einer Zeichenfolge.

Die Anzahl der Zeichenlöschungen, -einfügungen und -ersetzungen, die erforderlich sind, um ein Wort in ein anderes umzuwandeln, hängt davon ab, wie genau die beiden Wörter bearbeitet wurden.

Sie wird in Python auch als Levenshtein-Distanz bezeichnet, weil es nicht erforderlich ist, dass zwei Strings die gleiche Länge haben, um verglichen zu werden; die Levenshtein-Distanz hat einen wesentlichen Einfluss.

Die Levenshtein-Distanz ist intuitiv leicht zu verstehen. Die Gesamtzahl der Einzelzeichenänderungen bestimmt den Abstand zwischen den beiden.

Der Ausgabeabstand gibt an, wie viele Modifikationen erforderlich waren, um die beiden Wörter identisch zu machen. Je kleiner der Ausgangsabstand ist, desto weniger Änderungen sind erforderlich.

Lassen Sie uns den Bearbeitungsabstand anhand des folgenden Beispielcodes zum Einfügen, Löschen, Ersetzen und zur Rekursionsimplementierung der Zeichenfolge verstehen.

Einfügen der Zeichenkette

Im folgenden Code wird in der Wortmaschine zwischen i und n ein t eingefügt.

Beispielcode:

w = "Machine"
w = w[:5] + "t" + w[5:]
print(w)

Ausgang:

Machitne

Löschung der Zeichenkette

Im folgenden Code wird in der Wortmaschine das c zwischen a und h gestrichen.

Beispielcode:

w = "Machine"
w = w[:2] + w[3:]
print(w)

Ausgang:

Mahine

Substitution der Zeichenkette

Im folgenden Code wird in der Wortmaschine zwischen a und h c durch a ersetzt.

Beispielcode:

w = "Machine"
w = w[:2] + "a" + w[3:]
print(w)

Ausgang:

Maahine

Rekursive Implementierung der Zeichenkette

Der Bearbeitungsabstand zwischen Maschine und Lernen beträgt fünf, wie in der Ausgabe unten gezeigt.

Wir können beliebige Zeichenfolgeneingaben vom Benutzer entgegennehmen, und die Levenshtein-Distanz wird in der folgenden Python-Methode rekursiv implementiert.

Diese rekursive Technik ist ineffizient, da die Levenshtein-Abstände der identischen Teilstrings wiederholt berechnet werden.

Beispielcode:

w1 = input("Type here for word 1: ")
w2 = input("Type here for word 2: ")

len1 = len(w1)
len2 = len(w2)

a = [[0] * (len2 + 1) for _ in range(len1 + 1)]

for m in range(0, len1 + 1):
    a[m][0] = m

for n in range(0, len2 + 1):
    a[0][n] = n

for m in range(1, len1 + 1):
    for n in range(1, len2 + 1):
        if w1[m - 1] == w2[n - 1]:
            a[m][n] = a[m - 1][n - 1]
        else:
            a[m][n] = min(a[m][n - 1], a[m - 1][n], a[m - 1][n - 1]) + 1
print(a[m][n])

Ausgang:

Type here for word 1: machine
Type here for word 2: learning
5