[Algorithm] Dynamic Programming(3) - Edit Distance(편집거리)

🤔 Dynamic Programming

다이나믹 프로그래밍이란 큰 문제를 작은문제로 나누어 문제를 해결하는 것을 말합니다.

 

다이나믹 프로그래밍 알고리즘을 이용하는 다양한 알고리즘에 대해 알아보겠습니다.

 

이번 포스팅에서는  Edit Distance 문제를 해결하기 위해 Dynamic Programming을 사용하여 해결하는 과정을 정리했습니다.

 

Edit Distance 문제는 어떤 단어와 비슷한 단어는 어떤 방식으로 정의할 수 있을까? 라는 의구심에서 시작되었습니다.

 

아래의 그림과 같이 Microsoft Word spell check 기능을 사용하면 비슷한 단어를 자동으로 추천해줍니다.

 

우리도 이를 Edit Distance를 통해 해결해보겠습니다.

 

 

 

 

 

 

 

 

 

 

 

🔎 Edit Distance

위에서 어떤 단어와 비슷한 단어는 어떤 방식으로 정의할 수 있을까에 대한 의구심을 해결하기 위해 사람들은 Edit Distance를 도입했습니다.

 

즉, 비슷하다는 것은 얼마나 '가깝냐'라는 것과 같다고 생각하여 문제를 해결한 것입니다.

 

Edit distance는 두 stiring이 얼마나 가까운 지를 나타내는 척도입니다.

 

 

 

 

✍️ Edit Distance 정의하기

String S1과 S2 간의 edit distance는 S1에서 아래 3가지 방법의 연산을 최소한 몇 번 수행하여 S2를 만들 수 있는가로 정의합니다.

 

 

1. Insertion(삽입)

S1에 symbol 하나를 추가합니다

    ex) MONDT → MONEDT

 

 

2. Deletion(제거)

S1에 symbol 하나를 제거합니다.

    ex) MONEDT → MONED

 

 

3. Substitution(교체)

S1에 symbol 하나를 제거합니다.

    ex) MONED → MONEY

 

 

 

즉, String S1과 S2간의 edit distance는 S1에서 Insertion, Deletion, Substitution을 최소 몇 번 수행하여 S2를 만들 수 있는가로 정의합니다.

 

또한 distance 중 가장 작은 값을 edit distance로 선정합니다.

 

 

 

예를 들어 S1 = SNOWY, S2 = SUNNY라 하고 S1에서 S2를 만들 수 있는 최소 수행 횟수를 구해보겠습니다.

 

case1)  SNOWY → SSNOWY (insert S) → SSNOWNY (insert N) → SSNWNY (delete O) → SSNNY (delete W) → SUNNY (substitute S to U) → distance = 5.

 

case2) SNOWY → SUNOWY (insert U) → SUNOY (delete W) → SUNNY (substitute O to N) → distance = 3

 

위의 두 가지 방법 중 case2) 의 경우가 더 적은 연산을 이용하여 S1을 S2로 바꾸었습니다.

 

또한 case2) 보다 더 적은 연산을 이용하여 S1을 S2로 바꾸는 방법은 없으므로 S1과 S2의 edit distance는 3이 됩니다.

 

 

 

 

✍️ Gap Table

우리는 이를 table을 이용하여 나타낼 수 있습니다.

 

 

 

 

Case1) S1 채워져 있는 column : S1에서 deletion

Case2) S2 채워져 있는 column : S1에서 insertion

Case3) S1, S2 모두 채워져 있지만 symbol이 서로 다른 colmn : S1에서 substitution

 

이 때 S1과 S2의 edit distance는 gap table의 Case1 + Case2 + Case3에 속한 column의 개수 ( = match 되지 않는 column의 개수 )

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

🔎 DP를 이용한 Edit Distance 문제 해결

Dynamic Programming을 이용하여 Edit Distance 문제를 해결해보겠습니다.

 

앞의 예시에서 Gap Table을 살펴보면 마지막 column은 같은 값을 가지고 있는 것을 알 수 있습니다.

 

 

 

 

 

 

Key Observation

이를 통해  S1, S2 의 gap table 에서 마지막 column 을 제거한 table 은 이에 해당되는 S1 과 S2 의 prefix 간의 edit distance 를 나타낸다는 것을 알 수 있습니다.

 

해당하는 prefix간의 edit distance가 더 짧다면 그것에 해당하는 Gap Table + 제거한 column 추가를 통해 더 짧은 edit distance를 얻을 수 있습니다.

 

이를 통해 S1과 S2의 edit distance는 S1과 S2의 prefix간의 edit distance에 의해 결정할 수 있습니다.

 

 

 

예를 들어 Edit[i , j]를 두 prefix S1[1, ..., i] 와  S2[1, ..., j]간의 edit distance라 하겠습니다.

 

이를 통해 S1과 S2간의 gap table에서 마지막 column에서 일어난 연산에 따라 다음과 같은 recurrence relation을 생각할 수 있습니다.

 

 

 

 

 

✍️ Edit Distance Case에 따른 해결방법

case1 ) 마지막 column에서 deletion이 일어난 경우.

마지막 column에서 S1→S2를 위해 deletion 연산이 일어납니다.

 

즉,  한 번의 연산이 추가된다는 것입니다.

 

이를 식으로 나타내면 아래와 같습니다.

 

$$Edit[i, j] = Edit[i-1, j] + 1$$

 

 

case2 ) 마지막 column에서 insertion이 일어난 경우.

마지막 column에서 S1→S2를 위해 insertion 연산이 일어납니다.

 

즉,  한 번의 연산이 추가된다는 것입니다.

 

이를 식으로 나타내면 아래와 같습니다.

 

$$Edit[i, j] = Edit[i, j-1] + 1$$

 

 

 

 

 

 

case3 ) 마지막 column에서 insertion이 일어난 경우.

마지막 column에서 S1→S2를 위해 substitution 연산이 일어납니다.

 

만약 S1[i] = S2[j]라면 추가 연산을 진행하지 않아도 됩니다.

 

하지만 S[i] != S2[j]라면 추가 연산 한 번이 필요합니다.

 

 

$$Edit[i, j] = Edit[i-1 j-1] + 1$$

$$Edit[i, j] = Edit[i-1, j-1] + 1$$

 

 

 

 

위의 세 가지를  바탕으로 Recurrence Relation을 세우면 아래와 같습니다.

 

 

 

|S1| = n, |S2| = m 이라면 S1과 S2의 edit distnce는 Edit(n, m)이 됩니다.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

🔎 Memoization

DP를 사용하여 Edit Distance 문제를 해결하기 위해 memoization을 활용하겠습니다.

 

 

Structure

Edit Distance 문제에서 memoization를 이용하기 위해서는 모든 1 ≤ i ≤ n, 1 ≤ j ≤ m 에 대해 Edit[i, j]를 저장해야 합니다.

 

2차원 array를 사용하여 해당 값들을 저장할 수 있습니다.

 

 

Dependency

Edit[i, j]는 Edit [i-1, j], Edit[i, j-1], Edit [i-1, j-1] 에만 의존합니다.

 

위의 dependency를 바탕으로 array를 row-major order 또는 column-major order로 계산하면서 array를 채워나가면 됩니다.

 

S1 : snow 와 S2 : sunny를 예시로 array를 채워가는 과정을 풀어보겠습니다.

 

 

 

 

수도코드

이를 수도코드로 나타내면 아래와 같습니다.

 

 

 

 

Time Complexity

memoization으로 인해 Edit array의 element하나를 구할 때마다 $O(1)$의 시간이 소모됩니다.

→ 총 $O(nm)$의 시간이 소모됩니다.