편집 거리(edit distance)는 두 개의 문자열 간의 유사도를 측정하는 데 사용되는 개념이다. 이 측정 방법은 한 문자열을 다른 문자열로 변환하는 데 필요한 최소한의 편집 연산 수를 계산한다. 편집 연산은 삽입(insertion), 삭제(deletion), 치환(substitution)의 세 가지 유형이 있다.
예를 들어, "kitten"과 "sitting"이라는 두 문자열을 비교해보겠다. 이 경우에는 다음과 같은 편집 연산을 통해 문자열을 변환할 수 있다.
- "k"를 "s"로 치환
- "e"를 "i"로 치환
- "n"을 "t"로 치환
따라서, 위의 예시에서는 총 3번의 편집 연산이 필요하다. 이 경우, "kitten"과 "sitting" 사이의 편집 거리는 3이다.
편집 거리는 문자열 유사성 비교, 철자 교정, 기계 번역, DNA 서열 비교 등 다양한 응용 분야에서 사용된다.
