근사 문자열 매칭

근사 문자열 매칭(approximate string matching)

• 비슷한 문자열을 비교하는 방법이다.
  • 검찰청 철창살은 쇠철창살이고 경찰청 철창살은 철철창살이다.
  • 검색 엔진의 유사어, 유전자의 비교
• 근사 문자열 매칭에는 거리 함수(distance function)가 사용된다.
• 거리 함수를 통해 두 문자열이 얼마나 비슷한지를 확인할 수 있다.
• 거리 함수의 종류는 다음과 같다.
  • 해밍 거리(Hamming distance)
  • 편집 거리(Edit distance)
  • 가중편집거리(Weighted edit distance)
  • 기타

해밍 거리

• 해밍 거리는 간단하게 두 문자열을 비교하여 차이를 파악하는 방법이다.
  • aaba와 acbca를 비교해보자
  • 두번째, 네번째, 다섯번째가 다르므로 해밍 거리는 3이다.
• 해밍 거리는 통신에 자주 쓰인다. 잘못 전달된 bit 단위를 확인할 때 데이터 둘을 비교하는 방법으로 쓰인다.
• 해밍 거리는 간단하지만, 문자열 간의 특성을 고려하지 못한다는 단점이 있다.

편집 거리

• 한 문자열을 다른 문자열로 변경하기 위해 필요한 편집 연산(edit operation)들의 최소 수이다.
• 먼저 문자열을 비교해야 한다. 만약 문자열이 같으면 match이다.
• 만약 문자열이 다르면 편집 연산을 해야한다.
• 편집 연산들의 종류는 다음과 같다.
  • 삽입(Insert)
  • 삭제(Delete)
  • 변경(Change)

편집 거리 계산(DP)

• 두 문자열 $S_1, S_2$가 있다.
• $D(i,j)$는 $S_1[1..i], S_2[1..j]$에 대한 편집 거리를 나타낸다.
  • $S_1, S_2$의 길이가 각각 $n,m$일때, $S_1$과 $S_2$의 편집 거리는 $D(n,m)$이다.
• $D(i,j)$는 다음 중 최소값이다.
  • $D(i,j-1)+1$ : 삽입을 했을 때
  • $D(i-1,j)+1$ : 삭제를 했을 때
  • $D(i-1,j-1)+t(i,j)$ : 변경을 했을 때
    • 마지막 글자가 다르면 $t(i,j) = 1$
    • 마지막 글자가 같으면 $t(i,j) = 0$

예시

Traceback

• 모든 결과가 나온 후, 과정을 알고자 처음으로 다시 되돌아 갈 수 있다.
• 숫자가 같고 대각선에서 오거나, 숫자가 다르고 왼,위에서 온 걸로 판별할 수 있다.