Approximate string matching
- 비슷한 문자열을 비교하는 것이다.
- 검색 엔진의 유사어 추천 기능과 같이 주어진 문자열과 비슷한 문자열을 검색한다.
거리함수
- 해밍거리 (Hamming Distance)
- 편집거리 (Edit Distance)
- 가중편집거리 (Weighted Edit Distance)
- 기타
해밍거리 (Hamming Distance)
- 두 문자열을 같은 자리끼리 비교하는 것
- 다른 문자의 개수가 해밍거리가 된다.
- aabc, abc를 비교할 때 해밍거리는 3이다 aab와 abc를 비교하게 되기 때문이다. 그런데 사실 눈으로 보면 맨 처음 a만 다른 것 뿐이라서 한계가 있다.
편집거리 (Edit Distance)
- 한 문자열을 다른 문자열로 변경하기 위해 필요한 편집 연산(Edit Operation)의 최소 수를 의미
- 편집 연산 - 삽입(Insertion), 삭제(Deletion), 교체(Substitution / Replacement)
- 예를 들어 aaab를 ab로 바꾸는 방법은 여러 개인데, 그 중 가장 비용을 찾는 것이다.
위 점화식을 참고해서 배열의 값을 채울 때에는
i와 j의 값이 같으면 대각선의 값을 그대로 가져오고,
i와 j의 값이 다르면 왼쪽, 대각선, 위쪽의 값 중 가장 작은 것에다가 1을 더해서 적어주면 된다.
t(i,j)는 i와 j가 같으면 0, 다르면 1인 값이다.
맨 우측 마지막에 있는 값 '5'가 구하고자 하는 Edit Distance가 된다.
Game Programmer