21. 근사문자열매칭(string matching) [10 2주차]

21. 근사문자열매칭(String matching) [10-2주차]

2024년 1월 14일 일요일

오전 2:56

<근사문자열매칭(String matching)>

문자열의 유사도를 판단하는 알고리즘.

 

사용 예

• 주어진 문자열과 비슷한 문자열 검색
• 검색엔진의 유사어 추천 기능
• 악성 코드와 유사한 문자열이 있는지 검색

 

유사도를 판단하는 척도로 다음과 같은 거리 함수들이 사용된다.

• 해밍거리(Hamming distance) : 문자열 두 개의 서로 같은 인덱스마다 문자가 서로 같은지를 비교한다. 한 글자만 밀려도 완전히 다른 문자가 된다는 단점이 있다.
• 편집거리(edit distance)
• 가중편집거리(weighted edit distance) : 문자마다 편집 연산에 드는 비용이 다름. 예) 'a'와 'b'의 삭제 연산 비용이 서로 다름
• 기타

 

 

<편집 거리>

문자열 x[1..m]을 y[1..n]으로 변환하기 위해 필요한 편집 연산의 최소 수.

 

 

<편집 연산(edit operation)>

1.     삽입(Insertion)

x의 한 위치에 문자 하나를 삽입한다. (사이에 끼워 넣음)

2.     삭제(Deletion)

x의 문자 하나를 삭제한다.

3.     교체(Substitution, Replacement, Change)

x의 문자 하나를 다른 문자로 교체한다.

 

 

<편집 거리 구하기>

D(i, j)를 x[1..i]와 y[1..j]의 편집 거리라고 하자.

D(m, n)을 계산하기 위해 각 i와 j(0<=i<=m, 0<=j<=n)에 대해 D(i, j)를 계산한다.

 

동적 프로그래밍 요소

• Recurrence relation
• Tabular Computation
• Traceback

 

 

<편집 거리의 점화식 구하기 (Recurrence relation)>

D(i, j)를 계산할 때, x와 y의 맨 마지막 문자부터 처리하면서, 이전 문자들에 대해 재귀 호출을 하는 식으로 편집 거리들을 구해 보자.

 

맨 마지막 문자들을 비교했을 때, 두 문자가 같을 수 있다.

이때, 편집 연산 없이 D(i-1, j-1)를 구하면 된다.

 

마지막 두 문자가 다른 경우, 다음 세 가지 방법으로 처리할 수 있다.

 

1.     replace 연산을 통해 처리

 

1.     insert 연산을 통해 처리

 

1.     delete 연산을 통해 처리

 

 

이를 통해, D(i, j)에 대해 다음과 같은 점화식을 세울 수 있다.

 

t(i, j) 의 값은 match의 경우 0, mismatch(replace)인 경우 1.

 

 

<Tabular Computation>

위에서 구한 점화식을 이용해, 이번에는 반대로 D(1, 1)부터 D(i, j)까지를 구해 보자.

 

아래 행렬의 (i, j) 칸에 D(i, j)를 적는다.

x = vintner, y = writers

(0, 0)칸은 할 게 없으니 비용이 0.

v를 " "로 바꾸는 데는 delete연산 하나 필요, vi를 " "로 바꾸는 데는 delete연산 둘 필요.

 

위와 같이 0번 행과 0번 열을 쉽게 채울 수 있다.

위에서 구한 점화식을 이용하면 나머지 칸도 채울 수 있다. 특정 칸을 채울 때에는 그 칸의 왼쪽, 위쪽, 왼쪽 위(대각선) 칸만 보면 된다. 총 세 개의 칸 중 가장 작은 값으로 가져올 수 있는 것을 택한다.

 

왼쪽이나 위쪽의 값을 가져온다는 것은 삽입이나 삭제 연산을 한다는 뜻이다. 따라서 무조건 값을 +1을 하여 가져와야 한다.

왼쪽 위, 대각선 방향에서 값을 가져올 때는 교체 연산을 한 것이므로 +1을 하여 값을 가져온다. 단, 현재 칸에 해당하는 x, y 내의 문자가 서로 같은 경우는 연산을 할 필요가 없으므로, 값을 더하지 않고 그대로 가져온다.

 

예를 들어, (4, 4)칸 (* 표시된 부분)을 채우는 과정을 살펴보자.

• 왼쪽에서 가져오는 경우 : 4+1 = 5
• 위쪽에서 가져오는 경우 : 3+1 = 4
• 왼쪽 위 대각선 방향에서 가져오는 경우 : 문자가 t로 같으므로 3을 그대로 가져온다.

위 세 가지 중 가장 값이 작은 3으로 채우면 된다.

 

 

<Traceback>

행렬의 (m, n)칸에 적힌 수부터 (0, 0)칸까지 거꾸로 따라가면 x를 y로 바꾸기 위한 연산 과정을 알 수 있다.