Levenshtein Distance 알고리즘

shjk·2025년 5월 12일

Levenshtein Distance(레벤슈타인 거리) 란 두 문자열 사이의 최소 편집 거리를 측정하는 알고리즘으로, 한 문자열을 다른 문자열로 변환할 때 필요한 최소한의 연산(삽입, 삭제, 교체)의 수를 의미한다.

알고리즘의 정의

두 문자열 $A$ 와 $B$ 가 있을 때, 레벤슈타인 거리는 다음 세 가지 기본 연산을 사용하여 $A$ 를 $B$ 로 변환하는 데 필요한 최소한의 연산 횟수를 의미한다.

삽입(Insertion): 문자열에 문자를 삽입
삭제(Deletion): 문자열에서 문자를 삭제
교체(Substitution): 문자열의 문자를 다른 문자로 교체

알고리즘의 동적 프로그래밍 접근법

레벤슈타인 거리 알고리즘은 전형적인 동적 프로그래밍(Dynamic Programming) 방식으로 풀 수 있다.

두 문자열을 각각 $A = a\_1a\_2\cdots a\_n$ , $B = b\_1b\_2\cdots b\_m$ 이라 할 때, 다음과 같이 상태 전이를 정의한다.

D[i,j] = \text{min} \begin{cases} D[i-1, j] + 1 & \text{(삭제)}\\[6pt] D[i, j-1] + 1 & \text{(삽입)}\\[6pt] D[i-1, j-1] + \text{if } a_i \ne b_j \text{ then } 1 \text{ else } 0 & \text{(교체 또는 유지)} \end{cases}

여기서,

$D[i,j]$ 는 문자열 $A$ 의 앞부분 $i$개와 문자열 $B$ 의 앞부분 $j$개 간의 레벤슈타인 거리이다.
초기값은 다음과 같다.

\begin{aligned} D[0,0] &= 0 \\[6pt] D[i,0] &= i \\[6pt] D[0,j] &= j \end{aligned}

알고리즘 예시

문자열 "kitten"을 "sitting" 으로 변환하는 경우를 예시로 들면 다음과 같다.

	Ø	s	i	t	t	i	n	g
Ø	0	1	2	3	4	5	6	7
k	1	1	2	3	4	5	6	7
i	2	2	1	2	3	4	5	6
t	3	3	2	1	2	3	4	5
t	4	4	3	2	1	2	3	4
e	5	5	4	3	2	2	3	4
n	6	6	5	4	3	3	2	3

위 표에서 최종 결과는 3 이므로, "kitten"에서 "sitting"으로 변환하는 최소 편집 연산 수는 3임을 알 수 있다.

시간 복잡도 및 공간 복잡도

시간 복잡도: 두 문자열의 길이를 각각 $m$ , $n$ 이라 할 때,
$O(m \times n)$
공간 복잡도: 동적 프로그래밍 테이블을 저장하는 데 필요한 공간,
$O(m \times n)$

응용 분야

레벤슈타인 거리 알고리즘은 다음과 같은 분야에서 널리 활용된다.

오타 교정 및 맞춤법 검사
검색 엔진에서 근사 매칭 검색
DNA, 단백질 등 생물학적 서열 분석
문자열 유사도 평가

구현 예제 (Python)

다음은 Python으로 간단하게 구현한 예제이다.

def levenshtein_distance(s, t):
    m, n = len(s), len(t)
    dp = [[0] * (n+1) for _ in range(m+1)]

    # 초기화
    for i in range(m+1):
        dp[i][0] = i
    for j in range(n+1):
        dp[0][j] = j

    # DP를 이용한 거리 계산
    for i in range(1, m+1):
        for j in range(1, n+1):
            if s[i-1] == t[j-1]:
                dp[i][j] = dp[i-1][j-1]
            else:
                dp[i][j] = min(
                    dp[i-1][j] + 1,    # 삭제
                    dp[i][j-1] + 1,    # 삽입
                    dp[i-1][j-1] + 1   # 교체
                )
    return dp[m][n]

# 예시
print(levenshtein_distance("kitten", "sitting"))  # 출력: 3