문자열의 편집 거리
빌드업 1
문자열에는 다음과 같이 네가지 작용이 있다:
- 삽입: 문자열에 새로운 문자를 끼워넣는다.
- 제거: 문자열에서 문자 하나를 없앤다.
- 교체: 문자열에서 문자 하나를 다른 문자로 바꾼다.
- 전치: 두 문자의 위치를 서로 바꾼다.
정의
편집 거리는 문자열간의 거리 함수로써 편집 방법을 허용하거나 금지함으로써 다음과 같은 타입들로 구분된다:
- (1) Hamming distance: 해밍 거리는 가장 단순하게 교체만을 허용한다. 달리 말하자면 같은 길이의 벡터가 주어졌을 때 같은지 다른지만 카운트하는 것이다. 별거 아니지만 그렇기 때문에 설명이 생략되는 경우가 많으니 이름 자체를 외워두도록 하자. 예로써 다음 두 벡터의 거리는 $3$이다. $$ x = (1,1,0,1) \\ y = (0,1,1,0) $$
- (2) Levenshtein distance: 레벤슈타인 거리는 삽입, 제거, 교체만을 허용한다. 편집 거리다운 거리로는 가장 메이저하게 쓰이며, 정보검색이론이나 생명정보학 등의 분야에서도 접할 일이 있다. 레벤슈타인 거리를 측정하는 알고리즘으로는 레벤슈타인 알고리즘이 있다. 예로써 “cats"와 “facts"는 다음과 같이 두 번 수정되므로 레벤슈타인 거리가 $2$ 다.
- (교체) cats → fats
- (삽입) fats → facts
- (3) Jaro distance : 자로 거리는 레벤슈타인 거리와 반대로 전치만을 허용한다.
- (4) Longest common subsequence distance : LSC 거리는 삽입과 제거만을 허용한다.