홍라이프 계산기레벤슈타인 편집 거리 계산기 쉽게 이해하기 — 개념과 원리
두 문자열 사이의 레벤슈타인 거리는 한 문자열을 다른 문자열로 바꾸는 데 필요한 문자 삽입, 삭제, 교체의 최소 횟수입니다. 맞춤법 검사, 유사 검색, '이것을 찾으셨나요' 제안, 중복 데이터 정리, DNA 서열 비교의 기초가 됩니다. 이 계산기는 편집 거리와 간단한 유사도 백분율을 보여 줍니다.
계산 방법
D[i][j]를 A의 앞 i글자와 B의 앞 j글자 사이의 거리라고 합니다.
- D[i][0] = i, D[0][j] = j입니다(모두 지우거나 모두 넣는 경우).
- D[i][j] = min(D[i−1][j] + 1, D[i][j−1] + 1, D[i−1][j−1] + 비용)이며, A의 i번째 글자와 B의 j번째 글자가 같으면 비용은 0, 다르면 1입니다.
- 최종 거리는 D[A의 길이][B의 길이]입니다.
- 유사도 = (1 − 거리 ÷ 두 길이 중 큰 값) × 100%
원리
어떤 편집 과정이든 마지막 글자에 대한 동작은 A의 마지막 글자 삭제, B의 마지막 글자 삽입, 두 글자 일치 또는 교체 중 하나입니다. 마지막 동작이 무엇이든 나머지는 더 짧은 앞부분끼리의 최적 편집이어야 합니다. 따라서 앞부분의 답을 이용해 전체의 답을 쌓아 올릴 수 있으며, 이것이 동적 계획법(바그너-피셔 알고리즘)입니다. 표의 칸은 (m + 1)(n + 1)개라 시간은 O(mn)이고, 이 계산기는 두 줄만 유지하므로 메모리는 O(n)입니다.
예제 풀이
- 입력값: A = "kitten"(6글자), B = "sitting"(7글자)입니다.
- k를 s로 교체하면 "sitten"입니다.
- e를 i로 교체하면 "sittin"입니다.
- 끝에 g를 삽입하면 "sitting"입니다.
- 더 짧은 방법은 없으며 표 계산으로도 거리는 3입니다.
- 유사도: (1 − 3 ÷ 7) × 100 ≈ 57.14%입니다.
결과 해석
거리 0은 두 문자열이 같다는 뜻이고, 거리는 긴 문자열의 길이를 넘지 않습니다. 오타를 찾을 때 보통 길이의 단어에서 거리가 1~2이면 같은 단어일 가능성이 큽니다. 유사도 백분율은 편의상 만든 점수로 표준 척도는 아니며, 짧은 문자열에서는 한 글자 차이로도 크게 변합니다.
흔한 실수
- "ab" → "ba" 같은 자리 바꿈을 1로 기대합니다. 레벤슈타인 거리로는 2이고, 다메라우-레벤슈타인 거리에서 1입니다.
- 대소문자와 공백을 고려하지 않습니다. "Seoul"과 "seoul"은 교체 1회 차이입니다.
- 한글을 자모가 분리된 형태와 완성형으로 섞어 비교하면 거리가 부풀려집니다.
자주 묻는 질문
유사도 기준은 몇 %가 적당한가요?
데이터마다 다르며, 많은 검색 시스템은 고정 백분율 대신 짧은 단어는 1회, 긴 단어는 2회까지 허용합니다.
해밍 거리와 같은가요?
해밍 거리는 길이가 같은 문자열에서 교체만 세고, 레벤슈타인 거리는 삽입과 삭제도 허용합니다.
O(mn)보다 빠르게 구할 수 있나요?
거리가 k 이하인지만 알면 되는 경우 대각선 띠만 계산해 약 O(k · n)에 판단할 수 있습니다.
출처: V. I. Levenshtein, "Binary codes capable of correcting deletions, insertions, and reversals", Soviet Physics Doklady 10(8), 1966 · R. A. Wagner, M. J. Fischer, "The string-to-string correction problem", Journal of the ACM 21(1), 1974