편집 거리 알고리즘 (Edit distance, Levenshtein Distance)
2020. 10. 27. 23:53
편집 거리 알고리즘(Levenshtein Distance, Edit Distance)
편집 거리 알고리즘이란, 두 문자열의 유사도를 판단하는 알고리즘이다. 유사도를 판단하는 기준은, 어떠한 문자열을 삽입,삭제,변경을 몇 번이나 해서 바꿀수 있는지를 계산하여 그 최소값을
hsp1116.tistory.com
위 글 예시 이해
ex) MICROSOFT와 NCSOFT
- 마지막 T끼리 비교 (같은 문자) : 뭘 할 필요 없음. MICROSOF 와 NCSOF 의 편집 거리를 그대로 쓰면 됨.
- MI 와 NCS 비교
1. 대각선 (M → NC)
: M → NC 의 편집거리 d 라고 할때, MI → NCS는 M → NC의 경우에 I를 S로 replace 했다고 생각할 수 있음.
따라서 d+1
2. 왼쪽 (MI → NC)
: MI를 NC로 바꾼 다음에, S를 add 했다고 생각할 수 있음. d+1
3. 위 (M → NCS)
: 좀 헷갈리는데, MI → NCS 를 하기 전에 I를 먼저 remove 하면 M → NCS의 경우가 됨.
따라서 기존 M → NCS의 편집거리 d 에 1을 더해준 d+1
1,2,3의 경우 중 가장 작은 편집 거리를 뽑아주는 경우를 선택하면 됨.
fat -> hat 직접 테이블 그려보며 이해해보기.
'<PS> > [특수 알고리즘]' 카테고리의 다른 글
| Monotone Queue Technique (Sliding window, DP 최적화) (0) | 2021.06.10 |
|---|---|
| Traveling Salesman Problem 외판원 문제 (NP-Hard) (0) | 2021.06.07 |
| 비트마스킹 (Bitmasking) - 정보를 비트에 함축해서 간단히 표현하기 (0) | 2021.03.26 |
| 0-1 BFS (0) | 2021.01.20 |
| 슬라이딩 윈도우 알고리즘 (0) | 2020.10.28 |