두 문자열 간의 레벤슈타인 거리(Levenshtein Distance)란 한 문자열을 다른 문자열로 변환하기 위해 필요한 최소 편집 횟수를 의미합니다. 여기서 편집 연산은 다음 세 가지를 포함합니다.
- 삽입(Insertion): 새로운 문자 하나를 추가
- 삭제(Deletion): 기존 문자 하나를 제거
- 치환(Substitution): 기존 문자 하나를 다른 문자로 교체
예시: "cat"과 "mat" 사이의 레벤슈타인 거리는 1입니다. 첫 글자 'c'를 'm'으로 치환하는 연산 한 번만 수행하면 두 문자열이 같아지기 때문입니다.
cat → mat ('c'를 'm'으로 치환)이러한 거리는 맞춤법 검사기, DNA 서열 분석, 유사 문자열 검색 등 다양한 분야에서 활용됩니다. 아래는 레벤슈타인 거리 계산 알고리즘을 구현한 C++ 프로그램입니다.
알고리즘
이 알고리즘은 동적 계획법(Dynamic Programming)에 기반하며, 두 문자열의 모든 접두사 쌍에 대한 거리를 2차원 테이블(dist)에 순차적으로 채워 나가는 방식으로 동작합니다.
시작
두 문자열을 입력받고 각각의 길이(l1, l2)를 구한다.
i = 0부터 l1까지 반복
dist[0][i] = i
j = 0부터 l2까지 반복
dist[j][0] = j
j = 1부터 l1까지 반복
i = 1부터 l2까지 반복
만약 s1[i-1] == s2[j-1]이면
track = 0
아니면
track = 1
t = MIN((dist[i-1][j]+1), (dist[i][j-1]+1))
dist[i][j] = MIN(t, (dist[i-1][j-1]+track))
반복 끝
반복 끝
레벤슈타인 거리 dist[l2][l1]을 출력한다.
끝C++ 구현 예제
#include <iostream>
#include <math.h>
#include <string.h>
using namespace std;
#define MIN(x,y) ((x) < (y) ? (x) : (y)) // 두 값 중 최솟값 계산
int main() {
int i,j,l1,l2,t,track;
int dist[50][50];
// 비교할 두 문자열 선언
char s1[] = "tutorials";
char s2[] = "point";
// 문자열 s1과 s2의 길이 저장
l1 = strlen(s1);
l2 = strlen(s2);
// 첫 번째 행 초기화
for(i=0;i<=l1;i++) {
dist[0][i] = i;
}
// 첫 번째 열 초기화
for(j=0;j<=l2;j++) {
dist[j][0] = j;
}
// 테이블 채우기
for (j=1;j<=l1;j++) {
for(i=1;i<=l2;i++) {
if(s1[i-1] == s2[j-1]) {
track = 0; // 문자가 같으면 비용 없음
} else {
track = 1; // 문자가 다르면 치환 비용 1
}
t = MIN((dist[i-1][j]+1), (dist[i][j-1]+1));
dist[i][j] = MIN(t, (dist[i-1][j-1]+track));
}
}
cout<<"레벤슈타인 거리:"<<dist[l2][l1];
return 0;
}실행 결과
레벤슈타인 거리:8
동작 원리 요약
테이블의 각 셀 dist[i][j]는 문자열 s1의 앞 i글자와 s2의 앞 j글자 사이의 편집 거리를 나타냅니다. 각 단계에서 세 가지 선택지, 즉 삭제(dist[i-1][j]+1), 삽입(dist[i][j-1]+1), 치환 또는 일치(dist[i-1][j-1]+track) 중 가장 작은 값을 선택하여 셀을 채웁니다. 최종 결과는 테이블의 마지막 셀 dist[l2][l1]에 저장되며, 이 값이 두 문자열 전체 간의 레벤슈타인 거리입니다.
이 알고리즘의 시간 복잡도와 공간 복잡도는 두 문자열 길이의 곱에 비례하는 O(m × n)입니다. 따라서 매우 긴 문자열을 다룰 때는 공간을 최적화한 변형 알고리즘(예: 두 행만 사용하는 방식)을 고려하는 것이 좋습니다.