Levenshtein Distance, 또는 Edit Distance는 한 문자열을 다른 문자열로 변환하기 위해 필요한 최소 편집 연산 수를 계산합니다.
기본 연산은 다음 세 가지입니다.
- Insert
- Delete
- Replace
일반적으로 각 연산의 비용은 1입니다.
예:
cat → cut
a를 u로 한 번 교체하면 되므로:
Distance = 1
대표적인 예제
kitten → sitting
다음과 같이 변환할 수 있습니다.
kitten → sitten
sitten → sittin
sittin → sitting
총 3개의 연산이 필요하므로 거리는 3입니다.
Dynamic Programming 정의
dp[i][j]
를 첫 번째 문자열의 앞 i개 문자를 두 번째 문자열의 앞 j개 문자로 바꾸는 최소 비용이라고 정의합니다.
Base Case:
dp[0][j] = j
dp[i][0] = i
현재 문자가 같으면:
dp[i][j] = dp[i - 1][j - 1]
다르면:
dp[i][j] = 1 + min(
dp[i - 1][j],
dp[i][j - 1],
dp[i - 1][j - 1]
)
각 상태는 Delete, Insert, Replace를 의미합니다.
TypeScript 구현
function levenshteinDistance(a: string, b: string): number {
const dp = Array.from(
{ length: a.length + 1 },
() => new Array(b.length + 1).fill(0)
);
for (let i = 0; i <= a.length; i++) {
dp[i][0] = i;
}
for (let j = 0; j <= b.length; j++) {
dp[0][j] = j;
}
for (let i = 1; i <= a.length; i++) {
for (let j = 1; j <= b.length; j++) {
if (a[i - 1] === b[j - 1]) {
dp[i][j] = dp[i - 1][j - 1];
} else {
dp[i][j] = 1 + Math.min(
dp[i - 1][j],
dp[i][j - 1],
dp[i - 1][j - 1]
);
}
}
}
return dp[a.length][b.length];
}
복잡도
문자열 길이가 n, m일 때:
Time Complexity: O(n × m)
Space Complexity: O(n × m)
현재 Row와 이전 Row만 저장하면 공간은:
O(min(n, m))
까지 줄일 수 있습니다.
Spell Checking
사용자가:
programing
이라고 입력한 경우 programming과의 거리는 1입니다.
따라서 오타 수정 후보를 찾는 데 활용할 수 있습니다.
Fuzzy Search
저장된 값이:
Alexander
이고 사용자가:
Alexnder
를 검색해도 Edit Distance를 이용하면 두 문자열이 매우 유사하다는 것을 알 수 있습니다.
CRM과 중복 데이터
CRM에서 다음과 같은 두 레코드가 있을 수 있습니다.
Arian Soleimanzadeh
Arian Soleimanzade
작은 Levenshtein Distance는 Duplicate 가능성을 나타내는 하나의 Signal이 될 수 있습니다.
다만 실제 시스템에서는 Email, Phone 등의 추가 정보도 함께 사용해야 합니다.
활용 분야
- Spell Checking
- Fuzzy Search
- Data Cleaning
- Duplicate Detection
- OCR
- NLP
- Bioinformatics
Hamming Distance와의 차이
Hamming Distance는 같은 위치끼리 비교하며 일반적으로 길이가 같아야 합니다.
Levenshtein은 Insert와 Delete까지 지원합니다.
따라서:
cat → cats
의 Levenshtein Distance는 1입니다.
Weighted Edit Distance
연산별 비용을 다르게 설정할 수도 있습니다.
Insert = 1
Delete = 1
Replace = 2
이렇게 하면 특정 도메인에 맞게 Similarity 계산을 조정할 수 있습니다.
기술 면접
대표 문제는 다음과 같습니다.
두 문자열을 주고 Insert, Delete, Replace를 사용해 한 문자열을 다른 문자열로 바꾸는 최소 연산 횟수를 구하라.
예:
horse → ros
정답은 3입니다.
정리
Levenshtein Distance는 한 문자열을 다른 문자열로 만들기 위한 최소 Insert, Delete, Replace 횟수를 계산합니다.
표준 Dynamic Programming 구현의 복잡도는:
Time: O(n × m)
Space: O(n × m)
이며, Fuzzy Search, Spell Checking, CRM Deduplication, OCR, NLP 등 실제 시스템에서도 활용됩니다.