레벤슈타인 거리(Levenshtein Distance)란?
레벤슈타인 거리는 두 문자열(시퀀스) 간의 차이를 측정하는 대표적인 문자열 메트릭입니다. 한 단어를 다른 단어로 변환할 때 필요한 최소 편집 횟수, 즉 단일 문자의 삽입(insertion), 삭제(deletion), 치환(substitution) 연산의 최솟값을 의미합니다.
예시
다음과 같은 두 문자열이 있다고 가정해 보겠습니다.
const str1 = 'hitting';
const str2 = 'kitten';
이 두 문자열 간의 레벤슈타인 거리는 3입니다. 아래와 같은 세 번의 편집만으로 'kitten'을 'hitting'으로 바꿀 수 있기 때문입니다.
- kitten → hitten ('k'를 'h'로 치환)
- hitten → hittin ('e'를 'i'로 치환)
- hittin → hitting (마지막에 'g' 삽입)
알고리즘 원리
레벤슈타인 거리는 일반적으로 동적 계획법(Dynamic Programming)을 사용해 계산합니다. 두 문자열의 길이에 해당하는 2차원 배열(행렬)을 만들고, 각 셀에는 첫 번째 문자열의 앞 i개 문자와 두 번째 문자열의 앞 j개 문자 사이의 거리를 저장합니다. 점화식은 다음 세 가지 값 중 최솟값을 취하는 방식으로 구성됩니다.
- 왼쪽 셀 + 1 (문자 삭제)
- 위쪽 셀 + 1 (문자 삽입)
- 대각선 왼쪽 위 셀 + 비용(문자가 같으면 0, 다르면 1) (문자 치환)
자바스크립트 구현 예제
두 개의 문자열을 인자로 받아 두 문자열 사이의 레벤슈타인 거리를 계산하는 함수는 다음과 같이 작성할 수 있습니다.
const str1 = 'hitting';
const str2 = 'kitten';
const levenshteinDistance = (str1 = '', str2 = '') => {
// (str2.length + 1) x (str1.length + 1) 크기의 2차원 배열 생성
const track = Array(str2.length + 1).fill(null).map(() =>
Array(str1.length + 1).fill(null));
// 첫 번째 행 초기화: 빈 문자열에서 str1까지의 거리
for (let i = 0; i <= str1.length; i += 1) {
track[0][i] = i;
}
// 첫 번째 열 초기화: 빈 문자열에서 str2까지의 거리
for (let j = 0; j <= str2.length; j += 1) {
track[j][0] = j;
}
// 행렬을 순회하며 최소 편집 거리 계산
for (let j = 1; j <= str2.length; j += 1) {
for (let i = 1; i <= str1.length; i += 1) {
const indicator = str1[i - 1] === str2[j - 1] ? 0 : 1;
track[j][i] = Math.min(
track[j][i - 1] + 1, // 삭제
track[j - 1][i] + 1, // 삽입
track[j - 1][i - 1] + indicator, // 치환
);
}
}
// 행렬의 마지막 셀이 곧 두 문자열의 레벤슈타인 거리
return track[str2.length][str1.length];
};
console.log(levenshteinDistance(str1, str2));
실행 결과
코드를 실행하면 콘솔에 다음과 같이 출력됩니다.
3
정리
이 알고리즘의 시간 복잡도는 O(m × n), 공간 복잡도 역시 O(m × n)입니다. 여기서 m과 n은 각각 두 문자열의 길이를 의미하며, 공간 복잡도는 이전 행만 유지하는 방식으로 O(min(m, n))까지 최적화할 수 있습니다. 레벤슈타인 거리는 오타 교정, 검색어 자동완성, DNA 서열 분석, 유사 문장 판별 등 다양한 분야에서 폭넓게 활용되는 핵심 알고리즘이므로, 자바스크립트로 직접 구현해 보며 그 원리를 익혀 두면 큰 도움이 됩니다.