Edit Distance: 두 판 사이의 차이

youngwiki
← 이전 편집다음 편집 →
시각위키텍스트
10번째 줄: 10번째 줄:


==Recursive Algorithm==
==Recursive Algorithm==
Edit Distance 계산은 문자열 뒤에서부터 비교하면서 재귀적으로 해결할 수 있다. 이는 두 문자열 두 문자열 S[1..i], T[1..j]이 있을때 마지막 문자를 비교하여 해결할 수 있다. 만약 비교하는 두 문자가 같으면 비용 증가 없이 이전 문제로 이동한다.<ref>(s[1..i-1], t[1..j-1])에 해당한다.</ref> 반면 두 문자가 다른 경우에는 substitution을 통해 Edit Distance를 1 증가시킨다.<ref>혹은 S에 문자를 추가하거나 삭제하는 방식을 취할 수도 있다.</ref> 즉, 큰 문제를 작은 문제로 쪼개며 해결하는 [[Dynamic Programming|동적 프로그래밍]] 방식을 사용한다.
Edit Distance 계산은 문자열 뒤에서부터 비교하면서 재귀적으로 해결할 수 있다. 이는 두 문자열 두 문자열 S[1..i], T[1..j]이 있을때 마지막 문자를 비교하여 해결할 수 있다. 만약 비교하는 두 문자가 같으면 비용 증가 없이 이전 문제로 이동한다.<ref>(s[1..i-1], t[1..j-1])에 해당한다.</ref> 반면 두 문자가 다른 경우에는 substitution을 통해 Edit Distance를 1 증가시킨다.<ref>혹은 S에 문자를 추가하거나 삭제하는 방식을 취할 수도 있다.</ref>  


===Recurrence Relation===
===Recurrence Relation===

2025년 11월 16일 (일) 02:31 판

상위 문서: Dynamic Programming

개요

문자열을 비교할 때는 오탈자가 있는 문자열을 고려해야 하는 경우가 있으며, 이를 위해서 근사(approximate) 매칭이 필요하다. 이를 위해서 두 문자열이 얼마나 다른지를 측정하는 척도가 필요하며, 이를 Edit Distance라고 한다. 이는 문자열 A를 문자열 B로 바꾸기 위해 필요한 최소 변경 횟수에 해당한다. Edit Distance는 보통 세 가지 연산을 기반으로 한다:

  1. Substitution (치환): 한 글자를 다른 글자로 바꾸기[1]
  2. Insertion (삽입): 문자 하나를 새로 삽입[2]
  3. Deletion (삭제): 문자 하나 삭제[3]

Recursive Algorithm

Edit Distance 계산은 문자열 뒤에서부터 비교하면서 재귀적으로 해결할 수 있다. 이는 두 문자열 두 문자열 S[1..i], T[1..j]이 있을때 마지막 문자를 비교하여 해결할 수 있다. 만약 비교하는 두 문자가 같으면 비용 증가 없이 이전 문제로 이동한다.[4] 반면 두 문자가 다른 경우에는 substitution을 통해 Edit Distance를 1 증가시킨다.[5]

Recurrence Relation

위에서 설명한 원리를 점화식으로 풀면 아래와 같다: 

D[i,j] is minimum of:
• D[i−1,j−1] if S[i]=T[j]: 둘이 같으면 비용 추가 안 됨
• D[i−1,j−1]+1 if S[i]≠T[j]: 둘이 다르면 substitution 필요
• D[i,j−1]+1 for an insertion into S: T에서 문자를 하나 가져오는 경우(insertion)
• D[i−1,j]+1 for a deletion from S: S에서 문자를 하나 버리는 경우(deletion)

각주

  1. ↑ 예를 들어, shot → spot의 경우는 ‘g’를 삽입하므로 Insertion 1회에 해당한다.
  2. ↑ 예를 들어, ago → agog의 경우는 ‘h’를 ‘p’로 바꾸므로 Substitution 1회에 해당한다.
  3. ↑ 예를 들어, hour → our의 경우는 ‘h’ 삭제 → Deletion 1회에 해당한다.
  4. ↑ (s[1..i-1], t[1..j-1])에 해당한다.
  5. ↑ 혹은 S에 문자를 추가하거나 삭제하는 방식을 취할 수도 있다.
원본 주소 "https://junhoahn.kr/junyoung/index.php?title=Edit_Distance&oldid=4033"