레벤슈타인 거리 단계별 추적 소스코드
IT 위키
- 상위 문서: 레벤슈타인 거리
소스 코드 (python)[편집 | 원본 편집]
def print_matrix(matrix, X, Y):
print(" " + " ".join(" " + c for c in Y))
for i, row in enumerate(matrix):
prefix = " " if i == 0 else X[i - 1]
print(prefix + " " + " ".join(f"{cell:2}" for cell in row))
print("\n")
def edit_distance(X, Y):
m, n = len(X), len(Y)
dp = [[0] * (n + 1) for _ in range(m + 1)]
# 초기화
for i in range(m + 1):
dp[i][0] = i
for j in range(n + 1):
dp[0][j] = j
print("초기 상태:")
print_matrix(dp, X, Y)
# DP 테이블 채우기
for i in range(1, m + 1):
for j in range(1, n + 1):
if X[i - 1] == Y[j - 1]:
dp[i][j] = dp[i - 1][j - 1] # 문자가 같으면 비용 없음
else:
dp[i][j] = 1 + min(
dp[i - 1][j], # 삭제
dp[i][j - 1], # 삽입
dp[i - 1][j - 1] # 교체
)
print(f"X[0:{i}] = '{X[:i]}' 까지 고려한 상태:")
print_matrix(dp, X, Y)
print("최종 편집 거리:", dp[m][n])
return dp[m][n]
# 테스트
edit_distance("lengthen", "elongate")
결과 예시[편집 | 원본 편집]
초기 상태:
e l o n g a t e
0 1 2 3 4 5 6 7 8
l 1 0 0 0 0 0 0 0 0
e 2 0 0 0 0 0 0 0 0
n 3 0 0 0 0 0 0 0 0
g 4 0 0 0 0 0 0 0 0
t 5 0 0 0 0 0 0 0 0
h 6 0 0 0 0 0 0 0 0
e 7 0 0 0 0 0 0 0 0
n 8 0 0 0 0 0 0 0 0
X[0:1] = 'l' 까지 고려한 상태:
e l o n g a t e
0 1 2 3 4 5 6 7 8
l 1 1 1 2 3 4 5 6 7
e 2 0 0 0 0 0 0 0 0
n 3 0 0 0 0 0 0 0 0
g 4 0 0 0 0 0 0 0 0
t 5 0 0 0 0 0 0 0 0
h 6 0 0 0 0 0 0 0 0
e 7 0 0 0 0 0 0 0 0
n 8 0 0 0 0 0 0 0 0
X[0:2] = 'le' 까지 고려한 상태:
e l o n g a t e
0 1 2 3 4 5 6 7 8
l 1 1 1 2 3 4 5 6 7
e 2 1 2 2 3 4 5 6 6
n 3 0 0 0 0 0 0 0 0
g 4 0 0 0 0 0 0 0 0
t 5 0 0 0 0 0 0 0 0
h 6 0 0 0 0 0 0 0 0
e 7 0 0 0 0 0 0 0 0
n 8 0 0 0 0 0 0 0 0
X[0:3] = 'len' 까지 고려한 상태:
e l o n g a t e
0 1 2 3 4 5 6 7 8
l 1 1 1 2 3 4 5 6 7
e 2 1 2 2 3 4 5 6 6
n 3 2 2 3 2 3 4 5 6
g 4 0 0 0 0 0 0 0 0
t 5 0 0 0 0 0 0 0 0
h 6 0 0 0 0 0 0 0 0
e 7 0 0 0 0 0 0 0 0
n 8 0 0 0 0 0 0 0 0
X[0:4] = 'leng' 까지 고려한 상태:
e l o n g a t e
0 1 2 3 4 5 6 7 8
l 1 1 1 2 3 4 5 6 7
e 2 1 2 2 3 4 5 6 6
n 3 2 2 3 2 3 4 5 6
g 4 3 3 3 3 2 3 4 5
t 5 0 0 0 0 0 0 0 0
h 6 0 0 0 0 0 0 0 0
e 7 0 0 0 0 0 0 0 0
n 8 0 0 0 0 0 0 0 0
X[0:5] = 'lengt' 까지 고려한 상태:
e l o n g a t e
0 1 2 3 4 5 6 7 8
l 1 1 1 2 3 4 5 6 7
e 2 1 2 2 3 4 5 6 6
n 3 2 2 3 2 3 4 5 6
g 4 3 3 3 3 2 3 4 5
t 5 4 4 4 4 3 3 3 4
h 6 0 0 0 0 0 0 0 0
e 7 0 0 0 0 0 0 0 0
n 8 0 0 0 0 0 0 0 0
X[0:6] = 'length' 까지 고려한 상태:
e l o n g a t e
0 1 2 3 4 5 6 7 8
l 1 1 1 2 3 4 5 6 7
e 2 1 2 2 3 4 5 6 6
n 3 2 2 3 2 3 4 5 6
g 4 3 3 3 3 2 3 4 5
t 5 4 4 4 4 3 3 3 4
h 6 5 5 5 5 4 4 4 4
e 7 0 0 0 0 0 0 0 0
n 8 0 0 0 0 0 0 0 0
X[0:7] = 'lengthe' 까지 고려한 상태:
e l o n g a t e
0 1 2 3 4 5 6 7 8
l 1 1 1 2 3 4 5 6 7
e 2 1 2 2 3 4 5 6 6
n 3 2 2 3 2 3 4 5 6
g 4 3 3 3 3 2 3 4 5
t 5 4 4 4 4 3 3 3 4
h 6 5 5 5 5 4 4 4 4
e 7 6 6 6 6 5 5 5 4
n 8 0 0 0 0 0 0 0 0
X[0:8] = 'lengthen' 까지 고려한 상태:
e l o n g a t e
0 1 2 3 4 5 6 7 8
l 1 1 1 2 3 4 5 6 7
e 2 1 2 2 3 4 5 6 6
n 3 2 2 3 2 3 4 5 6
g 4 3 3 3 3 2 3 4 5
t 5 4 4 4 4 3 3 3 4
h 6 5 5 5 5 4 4 4 4
e 7 6 6 6 6 5 5 5 4
n 8 7 7 7 6 6 6 6 5
최종 편집 거리: 5
