근사문자열매칭과 거리함수

• 근사문자열배칭 (approximate string matching)
  • 비슷한 문자열 비교 (↔KMP: 똑같은 문자열 찾음)
  • 예: 주어진 문자열과 비슷한 문자열 검색
    • 검찰청 철창살은 쇠철창살이고 경찰청 철창살은 철철창살이다.
    • 검색엔진의 유사어 추천 기능
• 거리함수: 얼마나 비슷한가를 측정해줌
  • 해밍 거리 (Hamming distance)
    • 같은 자리끼리 비교 (자리 교정)
    • ababc와 abbc의 해밍 거리는 3이다.
  • 편집 거리 (Edit distance)
    • change, insert, delete
    • copy/move가 없기 때문에 abcdef와 defabc의 편집 거리는 크다.
  • 가중편집거리 (Weighted edit distance)
    • change, insert, delete의 weight를 주거나
    • change/insert/delete 내에서의 weight를 다르게 줌
  • 기타

Edit Distance

• 한 문자열을 다른 문자열로 변경하기 위해 필요한 편집 연산(edit operation)들의 최소 수
• 편집 연산
  • 삽입 (insertion)
  • 삭제 (deletion)
  • 교체 (substitution/replacement, change)

Edit Distance 계산 (DP 이용)

• 두 문자열 S1과 S2에 대해 D(i, j)는 S1[1, …, i]과 S2[1, …, j]에 대한 편집 거리를 나타냄
  • S1, S2의 길이가 각각 n, m일 때, S1과 S2의 편집거리는 D(n, m)
  • D(n, m)을 계산하기 위해 모든 i와 j (0≤i≤n, 0≤j≤m)에 대해 D(i, j)를 계산
• Dynamic Programming의 요소
  • Recurrence Relation
  • Tabular Computation
  • Traceback

가능한 쌍을 모두 구해야 하므로 총 (n+1)*(m+1) 번의 계산을 한다.

S1의 길이가 7, S2의 길이가 5라 하고 아래처럼 가로가 S1, 세로가 S2인 표를 그리면 이해하기 쉽다.

각 칸에는 edit distance를 적는다. 이 표를 다 채우면 빨리 계산할 수 있다. 그리고 각 칸을 채우기 위해 이전에 채운 값들을 사용할 것이다.

Recurrence Relation

D(i, j) = 
min(
	D(i, j-1) + 1, 
	D(i-1, j) + 1, 
	D(i-1, j-1) + t(i, j)
)

길이가 i인 문자열 “o o o o o o”을 길이가 j인 문자열 “o o o o o”로 바꾸는 모든 방법의 수를 계산해보자.

여러 방식으로 계산할 수 있겠지만, 일단 마지막 글자만 보자.

가장 좋은 답에서 마지막 글자가 match라 하면, 나머지끼리 edit distance를 구하는 것이 좋다. 그러면 처음~마지막-1까지 string들의 edit distance를 구하는 것으로 문제가 분리된다.

이렇게 계속 진행하면 마지막 글자가 match인 경우에는 답을 구할 수 있게 된다. 그럼 마지막 글자가 다른 경우에는? 이때는 match일 수 없으므로 change를 생각해볼 수 있다.

이런 식으로 하면 총 네가지의 경우가 나온다. (a는 길이가 i인 문자열의 마지막 글자, b는 길이가 j인 문자열의 마지막 글자이다)

1. match
2. change
3. a가 delete되는 경우: 나머지 i-1개 세트들끼리 잘 해보면 됨
4. b가 추가되는 경우

다르게 생각해보면, operation(change, delete 등)들은 1차원으로 한 줄로 늘어놓을 수 있으므로, 각각의 경우에 가장 좋은 operation을 찾으면 된다. 근데 operation은 네 개인데 식은 왜 세 개인가? 왜냐하면 match와 change는 동시에 생길 수 없기 때문이다. 그래서 S1[i]=S2[j]이면 t(i, j)가 0, 다르면 t(i, j)는 1이다.

근데 문제는 이렇게 풀면 시간이 엄청 오래 걸린다다는 것이다.

Tabular Computation

• Bottom-up computation S1 = vintner, S2 = writers

O(mn)의 시간복잡도를 가진다.