파이썬 편집 거리

오늘은 파이썬에서 편집 거리에 대해 알아보겠습니다. 또한 문자열의 삽입, 삭제, 대체 및 재귀 구현을 탐색합니다.

Python에서 거리 편집

편집 거리는 문자열을 다른 문자열로 조옮김하는 데 필요한 양입니다. 이 전치는 문자열의 문자를 재귀, 대체, 삽입 및 삭제하여 수행됩니다.

한 단어를 다른 단어로 바꾸는 데 필요한 문자 삭제, 삽입 및 교체의 수는 두 단어가 얼마나 밀접하게 편집되었는지에 따라 다릅니다.

또한 Python에서 Levenshtein 거리라고도 합니다. 길이가 동일한 두 문자열을 비교할 필요가 없기 때문입니다. Levenshtein 거리는 중요한 영향을 미칩니다.

Levenshtein 거리는 직관적으로 이해하기 쉽습니다. 단일 문자 수정의 총 수는 둘 사이의 거리를 결정합니다.

출력 거리는 두 단어를 동일하게 만드는 데 필요한 수정 횟수를 나타냅니다. 출력 거리가 작을수록 더 적은 변경이 필요합니다.

문자열의 삽입, 삭제, 대체, 재귀 구현에 대한 다음 예제 코드를 사용하여 편집 거리를 이해해 봅시다.

문자열 삽입

다음 코드에서 machine이라는 단어의 i와 n 사이에 t가 삽입됩니다.

예제 코드:

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

출력:

Machitne

문자열 삭제

다음 코드에서 machine이라는 단어의 a와 h 사이에서 c가 삭제됩니다.

예제 코드:

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

출력:

Mahine

문자열의 대체

다음 코드에서 c는 machine이라는 단어에서 a와 h 사이의 a로 대체됩니다.

예제 코드:

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

출력:

Maahine

문자열의 재귀적 구현

기계와 학습 사이의 편집 거리는 아래 출력과 같이 5입니다.

사용자로부터 모든 문자열 입력을 받을 수 있으며 Levenshtein 거리는 다음 Python 메서드에서 재귀적으로 구현됩니다.

이 재귀 기법은 동일한 하위 문자열의 Levenshtein 거리가 반복적으로 계산되기 때문에 비효율적입니다.

예제 코드:

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])

출력:

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