문서 편집기나, 키보드에는 다음과 같이 오타가 났을 때 수정된 단어를 추천해주는 기능이 있습니다.
이렇게 오타를 정정해주기 위해선 어떤 단어와 "비슷한 (가까운) 단어" 를 정의할 수 있어야 합니다.
그렇다면 어떤 단어와 "비슷한" 단어는 어떻게 정의할 수 있을까요? 이와 관련된 문제가 바로 Edit Distance (편집 거리) 문제입니다.
Edit Distance : 두 String 이 얼마나 가까운지 나타내는 척도.
String S1 과 S2 간의 edit distance 는 S1 을 S2 로 만들 때 아래 3가지 type의 연산을 최소한 몇 번 수행하여 만들 수 있는가로 정의합니다.
- Insertion (삽입) : S1 에 Symbol 하나를 추가 (위치는 무관) ex. MONDT -> MONEDT
- Deletion (제거) : S1 에 Symbol 하나를 제거 (위치는 무관) ex. MONEDT -> MONDED
- Substitution (교체) : S1 에 Symbol 하나를 다른 Symbol 로 바꿈, Insertion 과 Deletion을 한 번에 수행하는 데 cost 는 똑같다는 점에서 굉장히 좋은 연산입니다. (위치는 무관) ex. MONED -> MONEY
SNOWY 와 SUNNY 의 Edit Distance 를 구해보겠습니다.
Case 1. SNOWY -> SSNOWY (insert S) -> SSNOWNY (insert N) -> SSNWNY (delete O) -> SSNNY (delete W) -> SUNNY (substitute S to U) = Distance is 5.
Case 2. SNOWY -> SUNOWY (insert U) -> SUNOY (delete W) -> SUNNY (substitute O to N) = distance is 3.
Case 2 보다 더 적은 연산 횟수로 SNOWY 를 SUNNY로 바꾸는 방법은 없으므로, SNOWY 와 SUNNY 의 edit distance 는 3이 됩니다.
다시 한 번, Dynamic Programming 기법을 사용하여 알고리즘을 디자인 하는 절차를 떠올리며 Edit Distance 를 해결하는 알고리즘을 살펴보겠습니다.
Dynamic Programming 으로 문제를 해결하는 절차는 다음과 같습니다.
1. 문제를 정확하게 정의하기. (구하고자 하는 것이 무엇인지 정확하게 파악해야 합니다.)
2. 정의된 문제에 대한 subproblem 을 정의한 뒤 subproblem 을 이용한 recurrence relation 을 세우기. (subproblem 이란 본래 문제보다 size가 작은 문제를 의미합니다. fibonacci 문제에서는 fn' (n' < n) 이 subproblem입니다.)
3. Memoization 을 이용하여 recurrence relation 을 계산
중간 결과물들을 저장할 자료구조 (Data Structure) 를 골라야합니다. 보통은 n차원 array 를 사용합니다. Subproblem 들 간의 dependency 를 확인합니다. ( fibonacci 문제의 Fn을 구하려면 어떤 subproblem 들을 계산해두어야 할까요? 바로 Fn-1과 Fn-2 입니다.)
Dependency 에 기반하여 subproblem 들의 답을 구하는 순서를 정해야합니다. ( fibonacci 문제는 1차원 array 이므로 그냥 순차적으로 구하면 됐습니다.)
4. Time Complexity 분석 및 알고리즘을 작성하기.
1. Edit Distance 의 정의를 그대로 Problem 으로 정의하겠습니다. 따라서 Problem : 두 String S1 과 S2가 주어졌을 때 S1과 S2 간의 edit distance 구하기라고 하겠습니다.
2. 정의된 문제에 대한 Subproblem 을 정의해봅시다. 먼저 S1과 S2를 다음과 같은 table로 나타내봅시다.
위의 Table 에서 Case 1 처럼 S1만 채워져있고 S2가 비워진 경우는 S1 의 symbol 을 deletion 합니다.
Case 2 처럼 S2 만 채워져 있고 S1 이 비워진 경우는 S1 에 Symbol 을 insertion 합니다.
Case 3 처럼 S1과 S2 가 모두 채워져있고 둘의 Symbol이 다른 경우엔 Substitution 을 수행합니다.
이 때, Edit Distance 는 table 에서 Case 1, Case 2, Case 3에 해당하는 Column 의 수가 됩니다.
Subproblem 을 생각하며 Size 를 줄인 Problem 과 원래의 Problem 을 살펴볼까요 ?
S1과 S2의 table 에서 마지막 column 을 제거한 table 은 이에 해당되는 S1과 S2의 Prefix (접두어) 간의 edit distance 를 나타냅니다. 해당하는 prefix 간의 edit distance 가 더 짧다면 그것에 해당하는 table + 제거한 column 추가를 통해 더 짧은 edit distance 를 얻을 수 있기 때문입니다. 그러면 Subproblem 을 String들의 prefix 간의 edit distance로 정의할 수 있겠습니다.
조금 더 명확하게 정의하면, Edit[i,j] = 두 prefix S1[1,2,...,i] 와 S2[1,2,...,j]간의 edit distance 라 하고, S1[1,2,...,i] 와 S2[1,2,...,j] 간의 table 에서 마지막 column 에서 일어난 연산에 따라 다음과 같은 recurrence relation 을 생각해 볼 수 있습니다.
Case 1 ) 마지막 Column 에서 deletion 이 일어난 경우 Edit [i,j] = Edit[i-1,j] + 1
Case 2 ) 마지막 Column 에서 insertion 이 일어난 경우 Edit[i,j] = Edit[i,j-1] + 1
Case 3 ) 마지막 Column 에서 Substitution 이 일어난 경우
S1[i] = S1[j] -> Edit[i,j] = Edit[i-1,j-1] 또는 S1[i] != S2[j] -> Edit[i,j] = Edit[i-1,j-1] + 1
마지막 Column에서 일어날 수 있는 연산의 경우는 반드시 위 3개의 케이스 중 하나에 포함되므로, Edit[i,j] 는 위의 Case 들 중 최소값이 됩니다. 그러면 다음과 같은 Recurrence Relation 을 세울 수 있습니다.
|S1| = n, |S2| = m 이라면 S1과 S2의 edit distance는 Edit[n,m] 이 됩니다.
3. Memoization 을 사용하여 Recurrence relation 을 계산합니다.
- 먼저 Data Sturcture 는 2차원 Array 를 사용하겠습니다. Subproblem 의 정의 상 2개의 index 가 필요하기 때문입니다.
- Dependency 는 Edit[i,j] 를 구하기 위해 Edit[i-1,j] or Edit[i,j-1] or Edit[i-1,j-1]이 필요할 수 있습니다.
- 채워나가는 방향은 row-major 든 column-major 든 상관이 없습니다.
row-major order 로 Array 를 채워나가보겠습니다.
4. 마지막으로 Time Complexity 를 분석해보겠습니다.
Memoization 으로 인해 Edit Array 의 element 를 하나 구할 때 마다 O(1) 의 시간이 소모됩니다. 이것을 n*m 개의 칸에 반복해서 계산해 줘야하므로 O(nm) 시간이 걸립니다. (n=m 일 경우 O(n^2)
이를 Python으로 구현한 코드는 다음과 같습니다.
def EditDistance(A, B):
lenA = len(A)
lenB = len(B)
Edit = [ [0 for _ in range(lenB)] for _ in range(lenA) ]
for i in range(lenA):
Edit[i, 0] = i
for i in range(lenB):
Edit[0, i] = i
for i in range(lenA):
for j in range(lenB):
if A[i] == B[j]:
Edit[i,j] = min(Edit[i-1,j] + 1, Edit[i,j-1] + 1, Edit[i-1,j-1])
else:
Edit[i,j] = min(Edit[i-1,j] + 1, Edit[i,j-1] + 1, Edit[i-1,j-1] + 1)
return Edit[lenA, lenB]'알고리즘' 카테고리의 다른 글
| [Algorithm] Reduction for Decision Problem (0) | 2022.11.24 |
|---|---|
| [Algorithm] Reduction (0) | 2022.11.24 |
| [Algorithm] Longest Increasing Subsequence (LIS 문제) (0) | 2022.11.19 |
| [Algorithm] 다이나믹 프로그래밍 (Dynamic Programming) (0) | 2022.11.19 |
| [Algorithm] 방해꾼 논법 (Adversary Argument) (0) | 2022.11.17 |
