Levenshtein 거리

AI
qwen-3-235b-a22b-instruct-2507
작성자
익명
작성일
2025.09.05
조회수
4
버전
v1
기술 → 자연어처리 → 편집 거리
Levenshtein 거리 편집 거리 동적 프로그래밍 자연어처리 스펠링 교정

📋 문서 버전

이 문서는 2개의 버전이 있습니다. 현재 버전 1을 보고 있습니다.

Levenshtein리

Levensin 거리(LD, 레벤슈타인 거리)는 문자열 간의 유사도를 측정하는 편집 거리(Edit Distance)의 한 형태로, 러시아 수학자 블라디미르 레벤슈타인(Vladimir Levenshtein)이 965년에 제안 알고리즘입니다. 이 거리는 한 문자열을 다른 문자열로 변환하기 위해 필요한 최소한의 단일 문자 편집 연산 횟수를 의미하며, 자연어처리(NLP), 스펠링 교정, 생물정보학, 문자열 매칭 등 다양한 분야에서 널리 사용됩니다.

개요

Levenshtein 거리는 두 문자열 간의 차이를 정량적으로 표현하는 지표로, 다음 세 가지 기본 연산을 허용합니다:

  1. 삽입(Insertion): 한 문자를 문자열에 추가
  2. 삭제(Deletion): 한 문자를 문자열에서 제거
  3. 치환(Substitution): 한 문자를 다른 문자로 변경

예를 들어, "kitten"을 "sitting"으로 변환하는 과정은 다음과 같습니다:

  1. kitten → sitten (k → s, 치환)
  2. sitten → sittin (e → i, 치환)
  3. sittin → sitting (n 뒤에 g 삽입)

총 3회의 연산이 필요하므로, "kitten"과 "sitting"의 Levenshtein 거리는 3입니다.

알고리즘 원리

Levenshtein 거리는 동적 프로그래밍(Dynamic Programming)을 기반으로 계산됩니다. 두 문자열 A와 B의 길이를 각각 m과 n이라고 할 때, m × n 크기의 2차원 배열 dp를 생성하여 각 위치 (i, j)에서 A[0..i-1]과 B[0..j-1] 사이의 최소 편집 거리를 저장합니다.

점화식 (Recurrence Relation)

다음은 Levenshtein 거리의 핵심 점화식입니다:

dp[i][j] = \begin{cases}
\max(i, j) & \text{if } \min(i, j) = 0 \\
\min \begin{cases}
dp[i-1][j] + 1 & \text{(삭제)} \\
dp[i][j-1] + 1 & \text{(삽입)} \\
dp[i-1][j-1] + \text{cost} & \text{(치환)}
\end{cases} & \text{otherwise}
\end{cases}

여기서 cost는 A[i-1] == B[j-1]이면 0, 아니면 1입니다.

계산 예시

문자열 A = "cat", B = "cut"일 때:

c u t
0 1 2 3
c 1 0 1 2
a 2 1 1 2
t 3 2 2 1

최종 결과는 dp[3][3] = 1이며, 이는 'a'를 'u'로 치환하는 한 번의 연산만 필요함을 의미합니다.

응용 분야

1. 스펠링 교정

입력된 단어가 사전에 없을 경우, Levenshtein 거리를 이용해 가장 유사한 단어를 찾아 제안합니다. 예: "speling" → "spelling" (거리: 1)

2. 자연어처리 (NLP)

3. 생물정보학

DNA 또는 단백질 서열의 유사성을 분석할 때 사용됩니다. 각 염기(A, T, C, G)의 삽입, 삭제, 변이를 편집 연산으로 간주합니다.

4. 데이터 정제 및 중복 탐지

이름, 주소 등 구조화되지 않은 데이터에서 오타나 표기 차이를 감안해 중복 레코드를 식별합니다. 예: "John Smith" vs "Jon Smyth"

변형 및 확장

가중 Levenshtein 거리

기본 알고리즘은 모든 연산에 동일한 비용(1)을 부여하지만, 특정 상황에서는 연산별로 다른 가중치를 부여할 수 있습니다. 예를 들어, 자판 오류에서 'e'와 'r'은 인접 키이므로 치환 비용을 낮게 설정할 수 있습니다.

Damerau-Levenshtein 거리

기본 Levenshtein 거리에 문자 교환(Transposition) 연산을 추가한 버전입니다. 예: "hte" → "the" (h와 t 교환)는 1회 연산으로 처리 가능.

시간 및 공간 복잡도

  • 시간 복잡도: O(m × n)
  • 공간 복잡도: O(m × n) (전체 테이블 저장 시)

공간 최적화를 위해 두 줄만 유지하는 방식으로 O(min(m, n))의 공간 복잡도로도 구현 가능합니다.

관련 도구 및 라이브러리

언어 라이브러리 함수 예시
Python [python-Levenshtein](/doc/%EA%B8%B0%EC%88%A0/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%B0%8D/Python/python-Levenshtein) [Levenshtein.distance](/doc/%EA%B8%B0%EC%88%A0/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%B0%8D/Python/Levenshtein.distance)(str1, str2)
Java Apache Commons Text [LevenshteinDistance.apply](/doc/%EA%B8%B0%EC%88%A0/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%B0%8D/Java/LevenshteinDistance.apply)(str1, str2)
R [stringdist](/doc/%EA%B8%B0%EC%88%A0/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%B0%8D/R/stringdist) 패키지 stringdist(str1, str2, method = "lv")

참고 자료 및 관련 문서

Levenshtein 거리는 단순하면서도 강력한 문자열 유사도 측정 방법으로, 여전히 현대 정보 기술에서 핵심적인 역할을 수행하고 있습니다.

AI 생성 콘텐츠 안내

이 문서는 AI 모델(qwen-3-235b-a22b-instruct-2507)에 의해 생성된 콘텐츠입니다.

주의사항: AI가 생성한 내용은 부정확하거나 편향된 정보를 포함할 수 있습니다. 중요한 결정을 내리기 전에 반드시 신뢰할 수 있는 출처를 통해 정보를 확인하시기 바랍니다.

이 AI 생성 콘텐츠가 도움이 되었나요?