5-14. DP: Edit Distance (편집 거리)

1. 편집 거리(Edit Distance)의 정의와 배경

두 문자열 s와 t가 주어졌을 때, 문자열 s를 문자열 t로 변환하기 위해 필요한 최소 연산 횟수를 편집 거리(Edit Distance) 또는 Levenshtein Distance라고 부릅니다. 여기서 가능한 연산은 다음과 같습니다.

1. 삽입(Insertion): 문자열 s에 문자를 삽입합니다.
2. 삭제(Deletion): 문자열 s에서 문자를 삭제합니다.
3. 대체(Substitution): 문자열 s의 문자를 다른 문자로 바꿉니다.

편집 거리는 텍스트 유사도 측정, 오타 교정, DNA 시퀀스 분석 등 다양한 분야에서 활용됩니다. 예를 들어, "kitten"을 "sitting"으로 변환하는 최소 편집 거리는 3입니다. (k → s, e → i, t 삽입)

이 문제는 전형적인 동적 계획법(Dynamic Programming, DP) 문제입니다. DP를 사용하면 중복 계산을 피하고 효율적으로 문제를 해결할 수 있습니다. 즉, 작은 부분 문제들의 해결책을 결합하여 전체 문제를 해결합니다.

2. 편집 거리 알고리즘의 핵심 원리

편집 거리 문제를 해결하기 위해, DP 테이블을 정의하고 점화식을 세워야 합니다.

1) DP 테이블 정의

dp[i][j]를 문자열 s의 처음 i개의 문자와 문자열 t의 처음 j개의 문자를 일치시키기 위한 최소 편집 거리라고 정의합니다. i와 j는 0부터 문자열의 길이까지의 값을 가집니다.

2) 초기 조건 설정

• dp[0][0] = 0: 두 문자열 모두 비어 있는 경우, 편집 거리는 0입니다.
• dp[i][0] = i: 문자열 s의 처음 i개의 문자를 빈 문자열로 만들기 위해서는 i번의 삭제 연산이 필요합니다.
• dp[0][j] = j: 빈 문자열을 문자열 t의 처음 j개의 문자로 만들기 위해서는 j번의 삽입 연산이 필요합니다.

3) 점화식 유도

dp[i][j]를 계산하기 위한 점화식은 다음과 같습니다.

만약 s[i-1] == t[j-1]이라면 (문자가 같다면):

dp[i][j] = dp[i-1][j-1] (문자가 같으므로 연산 불필요)

만약 s[i-1] != t[j-1]이라면 (문자가 다르다면):

dp[i][j] = min(dp[i-1][j-1] + 1, // 대체 dp[i-1][j] + 1, // 삭제 dp[i][j-1] + 1) // 삽입

• dp[i-1][j-1] + 1: s[i-1]을 t[j-1]로 대체하는 경우.
• dp[i-1][j] + 1: s[i-1]을 삭제하는 경우.
• dp[i][j-1] + 1: t[j-1]을 삽입하는 경우.

4) 알고리즘 흐름 요약

1. DP 테이블을 초기화합니다.
2. 점화식을 사용하여 dp[i][j] 값을 계산합니다. (i 1 to len(s), j 1 to len(t))
3. dp[len(s)][len(t)]가 최종 편집 거리가 됩니다.

3. 알고리즘의 구현

다음은 파이썬 코드를 이용한 편집 거리 알고리즘의 구현입니다.

def edit_distance(s, t):
    n = len(s)
    m = len(t)

    # DP 테이블 초기화
    dp = [[0] * (m + 1) for _ in range(n + 1)]

    for i in range(n + 1):
        dp[i][0] = i
    for j in range(m + 1):
        dp[0][j] = j

    # DP 테이블 채우기
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            if s[i - 1] == t[j - 1]:
                dp[i][j] = dp[i - 1][j - 1]
            else:
                dp[i][j] = min(dp[i - 1][j - 1] + 1,  # 대체
                               dp[i - 1][j] + 1,    # 삭제
                               dp[i][j - 1] + 1)    # 삽입

    return dp[n][m]

# 예시 사용
s = "kitten"
t = "sitting"
distance = edit_distance(s, t)
print(f"편집 거리: {distance}")  # 출력: 편집 거리: 3

4. 응용 및 활용 사례

1) 텍스트 유사도 측정

편집 거리는 두 텍스트 간의 유사성을 측정하는 데 사용될 수 있습니다. 편집 거리가 작을수록 두 텍스트는 더 유사합니다.

2) 오타 교정

오타 교정 시스템은 사용자 입력과 사전에 있는 단어 간의 편집 거리를 계산하여 가장 가까운 단어를 제안할 수 있습니다.

3) DNA 시퀀스 분석

생물 정보학에서, DNA 시퀀스 간의 유사성을 비교하기 위해 편집 거리가 사용됩니다. 염기 서열의 삽입, 삭제, 대체를 통해 두 시퀀스의 거리를 측정합니다.

4) 음성 인식

음성 인식 시스템은 입력된 음성을 텍스트로 변환할 때, 편집 거리를 사용하여 텍스트 간의 유사성을 평가하고, 가장 적절한 결과를 선택할 수 있습니다.

5. 주의사항과 트러블슈팅

1) 메모리 최적화

DP 테이블을 저장하는 데 O(m*n)의 공간 복잡도가 필요합니다. 만약 문자열의 길이가 매우 긴 경우에는 공간을 최적화할 수 있습니다. 예를 들어, 현재 행과 이전 행의 정보만 유지하는 방식으로 공간 복잡도를 O(min(m, n))으로 줄일 수 있습니다.

2) 백트래킹(Backtracking)

편집 거리뿐만 아니라, 최소 편집 거리를 달성하는 실제 편집 연산(삽입, 삭제, 대체)의 시퀀스를 알고 싶을 수 있습니다. 이를 위해서는 DP 테이블을 채우는 과정에서 각 dp[i][j]가 어떤 연산에서 왔는지 기록해야 합니다. 예를 들어, dp[i][j] = dp[i-1][j-1] + 1 (대체)인 경우, 대체 연산이 사용되었음을 기록합니다. 이 정보를 바탕으로 백트래킹을 통해 편집 연산 시퀀스를 얻을 수 있습니다.

3) 시간 복잡도

편집 거리 알고리즘의 시간 복잡도는 O(m*n)입니다. 여기서 m과 n은 각각 두 문자열의 길이입니다.

6. 결론

편집 거리는 문자열 간의 유사성을 측정하고, 텍스트 처리, 생물 정보학 등 다양한 분야에서 활용되는 중요한 알고리즘입니다. 동적 계획법을 사용하여 효율적으로 문제를 해결할 수 있으며, 공간 최적화 및 백트래킹 기법을 통해 알고리즘을 개선할 수 있습니다.