레벤슈타인 거리

작성자

익명

작성일

2025.09.30

조회수

버전

레벤슈타인 거리## 개요

레벤슈타인 거리Levenshtein)는 두 문자열 간의 유사도를 측정하는 편집 거리(Edit Distance)의 형태로, 러시아 수학자 블라디미르 레벤슈타인(Vladimir Levenshtein)이 1965년에 제안한 개념이다. 이 거리는 한 문자열을 다른 문자열로 변환하기 위해 필요한 최소 편집 연산 횟수**를 계산함으로써 두 문자열의 차이를 정량화한다. 주로 자연어처리(NLP), 철자 교정, DNA 서열 비교, 음성 인식, 검색 엔진 등 다양한 분야에서 활용된다.

레벤슈타인 거리는 삽입(Insertion), 삭제(Deletion), 치환(Substitution)의 세 가지 기본 편집 연산을 허용하며, 각 연산은 일반적으로 비용 1로 간주된다.

정의와 계산 원리

레벤슈타인 거리는 두 문자열 $ A $와 $ B $ 사이에서, $ A $를 $ B $로 변환하기 위해 필요한 최소 편집 연산의 수로 정의된다. 예를 들어:

문자열 A: "kitten"
문자열 B: "sitting"

이 둘 사이의 레벤슈타인 거리는 다음과 같이 계산된다:

k → s (치환, 1회2. e → i (치환, 1회)
s 삽입 (삽입, 1회)

총 3회의 연산이 필요하므로, 레벤슈타인 거리는 3이다.

수학적 정의

자열 $ A $의 길이를 $ m $, 문자열 $ B $의 길이를 $ n $이라고 할 때, 레벤슈타인 거리는 다음과 같은 점화식으로 정의된다:

$$ \text{lev}_{A,B}(i,j) = \begin{cases} \max(i,j) & \text{if } \min(i,j) = 0 \\ \min \begin{cases} \text{lev}_{A,B}(i-1,j) + 1 & \text{(삭제)} \\ \text{lev}_{A,B}(i,j-1) + 1 & \text{(삽입)} \\ \text{lev}_{A,B}(i-1,j-1) + 1_{(A_i \neq B_j)} & \text{(치환)} \end{cases} & \text{otherwise} \end{cases} $$

여기서 $ 1_{(A_i \neq B_j)} $는 $ A $의 $ i $번째 문자와 $ B $의 $ j $번째 문자가 다르면 1, 같으면 0을 나타낸다.

동적 프로그래밍을 이용한 구현

레벤슈타인 거리는 동적 프로그래밍(Dynamic Programming)을 사용하여 효율적으로 계산할 수 있다. 일반적으로 $ (m+1) \times (n+1) $ 크기의 2차원 배열을 생성하고, 각 셀 $ (i,j) $에 문자열 $ A[1..i] $와 $ B[1..j] $ 사이의 거리를 저장한다.

알고리즘 절차

$ m = \text{len}(A), n = \text{len}(B) $로 초기화
$ (m+1) \times (n+1) $ 배열 dp 생성
첫 번째 행과 열을 0부터 $ m $, $ n $까지 채움 (빈 문자열로 변환 시 필요한 연산 수)
각 셀에 대해 위의 점화식을 적용하여 값을 계산
dp[m][n]이 최종 레벤슈타인 거리

Python 예제 코드

def levenshtein_distance(a, b):
    m, n = len(a), len(b)
    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

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if a[i-1] == b[j-1]:
                cost = 0
            else:
                cost = 1
            dp[i][j] = min(
                dp[i-1][j] + 1,      # 삭제
                dp[i][j-1] + 1,      # 삽입
                dp[i-1][j-1] + cost  # 치환
            )
    
    return dp[m][n]

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

응용 분야

1. 철자 교정 및 오타 검출

사용자의 입력 오타를 자동으로 수정하는 시스템(예: 검색 엔진, 스마트폰 키보드)에서 가장 흔히 사용된다. 입력 단어와 사전에 등록된 단어들 간의 레벤슈타인 거리를 계산하여 가장 가까운 단어를 추천한다.

2. 자연어처리(NLP)

음성 인식: 인식된 문장과 정답 문장 간의 오류율 계산(WER, Word Error Rate)에 활용
머신 트랜스레이션 평가: 번역 결과의 정확도를 측정하는 보조 지표로 사용
문서 유사도 분석: 두 문장이나 문서가 얼마나 유사한지를 판단

3. 생물정보학

DNA 또는 단백질 서열의 유사성을 분석할 때 사용되며, 유전자 간의 진화적 거리 추정에 활용된다.

4. 데이터 정제 및 중복 제거

데이터베이스에서 이름, 주소 등이 약간 다르게 기록된 중복 레코드를 식별하는 데 유용하다.

변형 및 확장

레벤슈타인 거리는 여러 가지 방식으로 확장되어 사용된다:

가중 레벤슈타인 거리: 특정 연산(예: 자음 치환 vs 모음 치환)에 다른 비용을 부여
다마레우-레벤슈타인 거리(Damerau-Levenshtein): 인접한 두 문자의 교환(transposition) 연산도 추가
지역 편집 거리: 전체 문자열이 아닌 부분 문자열 간의 유사도를 측정

장점과 한계

장점	한계
간단하고 직관적인 개념	문자열 길이가 길어질수록 계산 비용 증가 (시간 복잡도 $ O(mn) $)
다양한 분야에 적용 가능	의미적 유사성은 고려하지 않음 (예: "사과"와 "애플"은 거리 멀지만 의미 유사)
오타, 철자 오류에 강함	대소문자, 공백 등 전처리에 민감함

관련 문서 및 참고 자료

Damerau–Levenshtein distance - Wikipedia
Edit Distance - GeeksforGeeks
Navarro, G. (2001). "A guided tour to approximate string matching". ACM Computing Surveys.
Jurafsky, D., & Martin, J. H. (2023). Speech and Language Processing (3rd ed.). Chapter on Spelling Correction.

레벤슈타인 거리는 단순한 문자열 비교 이상의 의미를 지닌 핵심적인 알고리즘으로, 자연어처리 분야에서 여전히 널리 사용되고 있으며, 다양한 최적화와 확장이 연구되고 있다.

📝 마크다운 원본

이 문서의 마크다운 원본 내용입니다.

# 레벤슈타인 거리## 개요

**레벤슈타인 거리Levenshtein)는 두 문자열 간의 유사도를 측정하는 **편집 거리**(Edit Distance)의 형태로, 러시아 수학자 **블라디미르 레벤슈타인**(Vladimir Levenshtein)이 1965년에 제안한 개념이다. 이 거리는 한 문자열을 다른 문자열로 변환하기 위해 필요한 **최소 편집 연산 횟수**를 계산함으로써 두 문자열의 차이를 정량화한다. 주로 자연어처리(NLP), 철자 교정, DNA 서열 비교, 음성 인식, 검색 엔진 등 다양한 분야에서 활용된다.

레벤슈타인 거리는 **삽입**(Insertion), **삭제**(Deletion), **치환**(Substitution)의 세 가지 기본 편집 연산을 허용하며, 각 연산은 일반적으로 **비용 1**로 간주된다.

---

## 정의와 계산 원리

레벤슈타인 거리는 두 문자열 $ A $와 $ B $ 사이에서, $ A $를 $ B $로 변환하기 위해 필요한 최소 편집 연산의 수로 정의된다. 예를 들어:

- 문자열 A: "kitten"
- 문자열 B: "sitting"

이 둘 사이의 레벤슈타인 거리는 다음과 같이 계산된다:

1. `k` → `s` (치환, 1회2. `e` → `i` (치환, 1회)
3. `s` 삽입 (삽입, 1회)

총 **3**회의 연산이 필요하므로, 레벤슈타인 거리는 **3**이다.

### 수학적 정의

자열 $ A $의 길이를 $ m $, 문자열 $ B $의 길이를 $ n $이라고 할 때, 레벤슈타인 거리는 다음과 같은 점화식으로 정의된다:

$$
\text{lev}_{A,B}(i,j) = 
\begin{cases}
\max(i,j) & \text{if } \min(i,j) = 0 \\
\min \begin{cases}
\text{lev}_{A,B}(i-1,j) + 1 & \text{(삭제)} \\
\text{lev}_{A,B}(i,j-1) + 1 & \text{(삽입)} \\
\text{lev}_{A,B}(i-1,j-1) + 1_{(A_i \neq B_j)} & \text{(치환)}
\end{cases} & \text{otherwise}
\end{cases}
$$

여기서 $ 1_{(A_i \neq B_j)} $는 $ A $의 $ i $번째 문자와 $ B $의 $ j $번째 문자가 다르면 1, 같으면 0을 나타낸다.

---

## 동적 프로그래밍을 이용한 구현

레벤슈타인 거리는 **동적 프로그래밍**(Dynamic Programming)을 사용하여 효율적으로 계산할 수 있다. 일반적으로 $ (m+1) \times (n+1) $ 크기의 2차원 배열을 생성하고, 각 셀 $ (i,j) $에 문자열 $ A[1..i] $와 $ B[1..j] $ 사이의 거리를 저장한다.

### 알고리즘 절차

1. $ m = \text{len}(A), n = \text{len}(B) $로 초기화
2. $ (m+1) \times (n+1) $ 배열 `dp` 생성
3. 첫 번째 행과 열을 0부터 $ m $, $ n $까지 채움 (빈 문자열로 변환 시 필요한 연산 수)
4. 각 셀에 대해 위의 점화식을 적용하여 값을 계산
5. `dp[m][n]`이 최종 레벤슈타인 거리

### Python 예제 코드

```python
def levenshtein_distance(a, b):
    m, n = len(a), len(b)
    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

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if a[i-1] == b[j-1]:
                cost = 0
            else:
                cost = 1
            dp[i][j] = min(
                dp[i-1][j] + 1,      # 삭제
                dp[i][j-1] + 1,      # 삽입
                dp[i-1][j-1] + cost  # 치환
            )
    
    return dp[m][n]

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

---

## 응용 분야

### 1. 철자 교정 및 오타 검출
사용자의 입력 오타를 자동으로 수정하는 시스템(예: 검색 엔진, 스마트폰 키보드)에서 가장 흔히 사용된다. 입력 단어와 사전에 등록된 단어들 간의 레벤슈타인 거리를 계산하여 가장 가까운 단어를 추천한다.

### 2. 자연어처리(NLP)
- **음성 인식**: 인식된 문장과 정답 문장 간의 오류율 계산(WER, Word Error Rate)에 활용
- **머신 트랜스레이션 평가**: 번역 결과의 정확도를 측정하는 보조 지표로 사용
- **문서 유사도 분석**: 두 문장이나 문서가 얼마나 유사한지를 판단

### 3. 생물정보학
DNA 또는 단백질 서열의 유사성을 분석할 때 사용되며, 유전자 간의 진화적 거리 추정에 활용된다.

### 4. 데이터 정제 및 중복 제거
데이터베이스에서 이름, 주소 등이 약간 다르게 기록된 중복 레코드를 식별하는 데 유용하다.

---

## 변형 및 확장

레벤슈타인 거리는 여러 가지 방식으로 확장되어 사용된다:

- **가중 레벤슈타인 거리**: 특정 연산(예: 자음 치환 vs 모음 치환)에 다른 비용을 부여
- **다마레우-레벤슈타인 거리**(Damerau-Levenshtein): 인접한 두 문자의 **교환**(transposition) 연산도 추가
- **지역 편집 거리**: 전체 문자열이 아닌 부분 문자열 간의 유사도를 측정

---

## 장점과 한계

| 장점 | 한계 |
|------|------|
| 간단하고 직관적인 개념 | 문자열 길이가 길어질수록 계산 비용 증가 (시간 복잡도 $ O(mn) $) |
| 다양한 분야에 적용 가능 | 의미적 유사성은 고려하지 않음 (예: "사과"와 "애플"은 거리 멀지만 의미 유사) |
| 오타, 철자 오류에 강함 | 대소문자, 공백 등 전처리에 민감함 |

---

## 관련 문서 및 참고 자료

- [Damerau–Levenshtein distance - Wikipedia](https://en.wikipedia.org/wiki/Damerau–Levenshtein_distance)
- [Edit Distance - GeeksforGeeks](https://www.geeksforgeeks.org/edit-distance-dp-5/)
- Navarro, G. (2001). "A guided tour to approximate string matching". *ACM Computing Surveys*.
- Jurafsky, D., & Martin, J. H. (2023). *Speech and Language Processing* (3rd ed.). Chapter on Spelling Correction.

레벤슈타인 거리는 단순한 문자열 비교 이상의 의미를 지닌 핵심적인 알고리즘으로, 자연어처리 분야에서 여전히 널리 사용되고 있으며, 다양한 최적화와 확장이 연구되고 있다.

AI 생성 콘텐츠 안내

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

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

위키너와나