# Levenshtein 거리

Levenshtein 거리(LD, 레벤슈타인 거리)는 두 문자열 간의 유사도를정하는 데 사용 **편집 거리Edit Distance)의 형태로, 하나 문자열을 다른 문자로 변환하는 필요한 최소 편집 연산수를 나타냅니다. 이 개념 1965년 러시아 수학자블라디미르 레슈타인**(ladimir Levenshtein)에 의해 제안되었으며, 자연어 처리, 철자 교정, 생물정보학, 데이터 정제 등 다양한 분야에서 널리 활용됩니다.

---

## 개요

Levenshtein 거 두 문자열 사이의 차이를 정량화하는 중요한 지표입니다. 이 거리는 다음과 같은 세 가지 기본 편집 연산만을 허용합니다:

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

이 연산 각각은 **비용 1**을 가지며, 두 문자열을 동일하게 만들기 위해 필요한 총 연산 횟수를 Levenshtein 거리로 정의합니다 결과 값이 작을수록 두 문자열은 더 유사하다고 판단할 수 있습니다.

예를 들어, "kitten"과 "sitting"의 Levenshtein 거리는 3이며, 다음과 같은 변환 과정을 거칩니다:

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

---

## 알고리즘 원리

Levenshtein 거리는 **다이나믹 프로그래밍**(Dynamic Programming)을 기반으로 계산됩니다. 두 문자열 `A`와 `B`의 길이를 각각 `m`과 `n`이라고 할 때, `(m+1) × (n+1)` 크기의 2차원 배열 `dp`를 생성하여 점진적으로 거리를 계산합니다.

### DP 테이블 구성

- `dp[i][j]`: 문자열 `A`의 첫 `i`개 문자와 문자열 `B`의 첫 `j`개 문자 사이의 Levenshtein 거리
- 초기 조건:
  - `dp[0][j] = j`: 빈 문자열에서 `B`의 `j`번째 문자까지 만들기 위해 `j`번 삽입 필요
  - `dp[i][0] = i`: `A`의 `i`번째 문자까지를 빈 문자열로 만들기 위해 `i`번 삭제 필요
- 점화식:
  ```markdown
  dp[i][j] = min(
      dp[i-1][j] + 1,           // 삭제
      dp[i][j-1] + 1,           // 삽입
      dp[i-1][j-1] + cost       // 치환 (A[i-1] == B[j-1]이면 cost = 0, 아니면 1)
  )
  ```

### 예시 계산

`A = "cat"`, `B = "car"`의 경우:

|     | "" | c | a | r |
|-----|----|---|---|---|
| ""  | 0  | 1 | 2 | 3 |
| c   | 1  | 0 | 1 | 2 |
| a   | 2  | 1 | 0 | 1 |
| t   | 3  | 2 | 1 | **1** |

결과: Levenshtein리 = **1** (`t` → `r` 치환)

---

## 응용 분야

### 1. 철자 교정 및 오타 감지
입력된 단어가 사전에 없을 경우, 기존 단어들과의 Levenshtein 거리를 계산하여 가장 가까운 단어를 제안합니다.  
예: "speling" → "spelling" (거리: 1)

### 2. 자연어 처리(NLP)
- 문서 유사도 분석
- 음성 인식 후보 정렬
- 기계 번역 품질 평가

### 3. 생물정보학
DNA 또는 단백질 서열 간의 유사성을 분석할 때 사용. 유전자 변이를 정량화하는 데 유용합니다.

### 4. 데이터 정제 및 중복 제거
데이터베이스에서 "New York"과 "New-York" 같은 변형을 동일한 엔티티로 인식하기 위해 활용됩니다.

---

## 변형 및 확장

- **가중치 Levenshtein 거리**: 특정 연산(예: 치환)에 더 높은 비용을 부여하여 실질적인 오류 패턴 반영
- **Damerau-Levenshtein 거리**: 문자열 내 **문자 순서 교환**(transposition) 연산을 추가 (예: "hte" → "the")
- **Jaro-Winkler 거리**: 짧은 문자열(이름 등)에서 순서와 일치도를 더 잘 반영하는 대안

---

## 장점과 한계

| 장점 | 한계 |
|------|------|
| 간단하고 직관적인 정의 | 긴 문자열에서 계산 비용이 큼 (O(m×n)) |
| 다양한 오류 유형을 포괄 | 의미적 유사성은 반영하지 못함 |
| 구현이 비교적 쉬움 | 대소문자, 공백 등 전처리에 민감함 |

---

## 관련 알고리즘 및 도구

- **Wagner-Fischer 알고리즘**: Levenshtein 거리의 표준 DP 구현
- **비타비 알고리즘**: 확률 기반 편집 거리 계산
- **Python 라이브러리**: `python-Levenshtein`, `textdistance`, `NLTK`

### Python 예제 코드

```python
def levenshtein_distance(s1, s2):
    m, n = len(s1), len(s2)
    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):
            cost = 0 if s1[i-1] == s2[j-1] else 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
```

---

## 참고 자료

- Levenshtein, V. I. (1966). "Binary codes capable of correcting deletions, insertions, and reversals". *Soviet Physics Doklady*.
- Gusfield, D. (1997). *Algorithms on Strings, Trees, and Sequences*. Cambridge University Press.
- [Wikipedia - Levenshtein Distance](https://ko.wikipedia.org/wiki/레벤슈타인_거리)

Levenshtein 거리는 문자열 비교의 기초이자 핵심 도구로서, 정확성과 실용성을 모두 갖춘 알고리즘으로 평가받고 있습니다.