최종 업데이트: 2026-07-01

레벤슈타인 거리

레벤슈타인 거리는 편집 거리라고도 하며, 한 문자열을 다른 문자열로 바꾸는 데 필요한 문자 단위 편집의 최소 횟수를 세어 두 문자열이 얼마나 다른지를 측정합니다. 허용되는 편집은 삽입, 삭제, 치환이며 각각 비용이 1입니다. 이 계산기는 두 문자열을 받아 그 거리와 유사도 백분율을 반환하므로, 맞춤법 검사, 퍼지 매칭, DNA 같은 서열 비교에 유용합니다.

세 가지 편집 연산

두 문자열 사이의 모든 변환은 세 가지 기본 동작의 순서로 표현할 수 있습니다. 삽입은 한 문자를 더하고, 삭제는 한 문자를 빼며, 치환은 한 문자를 다른 문자로 바꿉니다. 레벤슈타인 거리는 이러한 동작 중 가장 적은 비용의 순서를 찾으며, 각 동작의 비용은 1입니다. 치환은 삭제 후 삽입이 아니라 한 단계이므로, 한 글자를 바꾸는 것은 항상 두 번이 아니라 한 번의 편집으로 셉니다.

이 척도는 1965년 블라디미르 레벤슈타인이 정의했으며, 더 오래된 해밍 거리 계산기를 일반화한 것입니다. 해밍 거리는 치환만, 그것도 길이가 같은 문자열에 대해서만 허용하지만, 레벤슈타인 거리는 삽입과 삭제도 허용하므로 길이가 다른 문자열도 처리합니다.

동적 계획법 표

거리는 표 $D$를 채워서 계산합니다. 표에는 첫 번째 문자열의 각 문자에 대응하는 행(앞에 빈 행 하나 추가)과 두 번째 문자열의 각 문자에 대응하는 열(앞에 빈 열 하나 추가)이 있습니다. 칸 $D[i][j]$는 문자열 A의 처음 $i$개 문자와 문자열 B의 처음 $j$개 문자 사이의 편집 거리를 담습니다.

첫 행과 첫 열은 빈 문자열에 대한 편집 횟수를 세므로 $D[i][0] = i$, $D[0][j] = j$입니다. 그 밖의 모든 칸은 세 후보의 최솟값입니다.

여기서 치환 비용 $c$는 문자가 일치하면 0, 다르면 1입니다. 답은 오른쪽 아래 칸에 있습니다. 표를 채우는 데는 두 길이의 곱 $m \times n$에 비례하는 시간이 듭니다.

풀이 예시

전형적인 짝인 「kitten」과 「sitting」을 봅시다. 표의 최적 경로를 따라가면 세 번의 편집이 나옵니다.

이보다 짧은 순서는 없으므로 거리는 3입니다. 더 긴 문자열은 7자이므로 유사도는 $1 - 3/7 \approx 0.571$, 즉 약 57%입니다.

유사도와 그 한계

이 계산기는 원시 거리를 다음 식으로 유사도 점수로 정규화합니다.

$S = 1 - \dfrac{d_L}{\max(m, n)}$

더 긴 문자열의 길이로 나누면 결과가 완전히 다른 문자열의 0%부터 동일한 문자열의 100%까지의 범위에 들어옵니다. 두 문자열이 모두 비어 있으면 동일한 것으로 봅니다. 이는 흔한 정규화 방식 중 하나로, 다른 도구는 길이의 합으로 나누거나 비율 기반 척도를 쓰기도 하므로 출처가 다른 유사도 수치는 직접 비교할 수 없습니다.

어디에 쓰이는가

맞춤법 검사기는 잘못 쓴 단어로부터의 편집 거리로 수정 후보의 순위를 매깁니다. 검색 및 데이터베이스 시스템은 퍼지 매칭에 사용해 이름이나 주소를 조회할 때의 오타를 허용합니다. 생물정보학에서 편집 거리는 DNA, RNA, 단백질을 비교하는 서열 정렬의 기초가 되며, 삽입과 삭제는 돌연변이에 대응합니다. 단순한 레벤슈타인 비용 모델은 모든 편집을 동일하게 취급하지만, 연산마다 다른 벌점이 필요하거나 매우 긴 서열을 효율적으로 정렬해야 하는 응용에서는 가중치 비용이나 전용 정렬 알고리즘으로 확장합니다.