Edit Distance
youngwiki
상위 문서: Dynamic Programming
개요
문자열을 비교할 때는 오탈자가 있는 문자열을 고려해야 하는 경우가 있으며, 이를 위해서 근사(approximate) 매칭이 필요하다. 이를 위해서 두 문자열이 얼마나 다른지를 측정하는 척도가 필요하며, 이를 Edit Distance라고 한다. 이는 문자열 A를 문자열 B로 바꾸기 위해 필요한 최소 변경 횟수에 해당한다. Edit Distance는 보통 세 가지 연산을 기반으로 한다:
Recursive Algorithm
Edit Distance 계산은 문자열 뒤에서부터 비교하면서 재귀적으로 해결할 수 있다. 이는 두 문자열 두 문자열 S[1..i], T[1..j]이 있을때 마지막 문자를 비교하여 해결할 수 있다. 만약 비교하는 두 문자가 같으면 비용 증가 없이 이전 문제로 이동한다.[4] 반면 두 문자가 다른 경우에는 substitution을 통해 Edit Distance를 1 증가시킨다.[5] 즉, 큰 문제를 작은 문제로 쪼개며 해결하는 동적 프로그래밍 방식을 사용한다.
