레벤슈타인 거리
레벤슈타인 거리은 두 문자열을 삽입·삭제·치환 연산으로 같게 만들기 위한 최소 편집 횟수이다 문자열 거리·동적 계획법 분야의 대표적인 알고리즘 또는 핵심 계산 문제로, 자료 표현과 입력 조건에 맞는 계산 절차를 사용한다. 명시적인 수학적 불변식·상태 정의를 바탕으로 구현하므로 단순한 명...
| 분류 | 알고리즘 · 문자열 거리·동적 계획법 |
|---|---|
| 핵심 문제 | 두 문자열을 삽입·삭제·치환 연산으로 같게 만들기 위한 최소 편집 횟수이다 |
| 방법 | dp[i][j]를 첫 문자열 i글자와 두 번째 문자열 j글자 사이의 최소 비용으로 정의한다 |
| 계산 비용 | 문자열 길이 n,m에서 O(nm) 시간·O(nm) 공간, 행만 유지하면 O(min(n,m)) 공간 |
| 적용 조건 | 비용 정의가 단위 편집 거리인지, 가중치가 있는 변형인지 구분해야 한다 |
| 관련 활용 | 맞춤법 교정·데이터 중복 탐지·생물정보학에 사용한다 |
| 관련 이론 | 자료구조, 계산 복잡도 |
| 참고 자료 | CP-Algorithms |
레벤슈타인 거리은 두 문자열을 삽입·삭제·치환 연산으로 같게 만들기 위한 최소 편집 횟수이다 문자열 거리·동적 계획법 분야의 대표적인 알고리즘 또는 핵심 계산 문제로, 자료 표현과 입력 조건에 맞는 계산 절차를 사용한다. 명시적인 수학적 불변식·상태 정의를 바탕으로 구현하므로 단순한 명령어 조합과는 구별된다.[1]
계산 절차는 dp[i][j]를 첫 문자열 i글자와 두 번째 문자열 j글자 사이의 최소 비용으로 정의한다. 삽입·삭제·치환의 전이에서 최소값을 선택하고 빈 접두사에 대한 초기값을 지정한다. 각 단계의 상태가 무엇을 의미하는지 정의하고 초기값과 경계 입력을 검사하면 결과의 정확성을 증명하거나 테스트할 수 있다.
복잡도는 문자열 길이 n,m에서 O(nm) 시간·O(nm) 공간, 행만 유지하면 O(min(n,m)) 공간 적용 전제는 비용 정의가 단위 편집 거리인지, 가중치가 있는 변형인지 구분해야 한다 실제 연산량·메모리 사용은 구현의 자료구조와 정수·실수 표현, 전처리 및 입력 크기에 따라 달라진다.
응용과 관련 기법을 보면 맞춤법 교정·데이터 중복 탐지·생물정보학에 사용한다. 단순 Levenshtein 거리는 문자열 중간의 인접 교환을 하나의 연산으로 취급하지 않는다. 같은 문제라도 최악 시간 보장, 메모리 요구 사항과 정밀도·확률적인 실패 가능성에 따라 적합한 알고리즘이 달라진다.[2]