레벤슈타인 거리 계산기 (편집 거리)

레벤슈타인 거리는 한 문자열을 다른 문자열로 바꾸는 데 필요한 한 글자 삽입, 삭제, 치환의 최소 횟수입니다. 맞춤법 추천, 유사 검색, 중복 탐지, DNA 정렬의 바탕이 되는 척도입니다. 이 계산기는 거리와 유사도(%)를 구하고, 실제 편집 목록을 보여 주며, 짧은 문자열에는 동적 계획법 표를 보여 주고, 후보 목록 전체를 내 문자열과의 가까운 정도로 순위 매길 수도 있습니다.

사용 방법

1. 두 문자열을 입력합니다(또는 문자열 하나와 한 줄에 후보 하나씩의 목록).
2. 기본 레벤슈타인을 쓰거나, 이웃한 글자 교환을 한 번의 편집으로 세려면 Damerau를 고릅니다.
3. 필요하면 대소문자와 공백을 무시하거나 단어 단위로 비교합니다.
4. 거리, 유사도, 편집을 확인합니다. 표는 20자 이하의 문자열에서 나타납니다.

계산식

d[i][j] = min(d[i−1][j] + 1, d[i][j−1] + 1, d[i−1][j−1] + (aᵢ ≠ bⱼ)) · 유사도 = 1 − d ÷ max(|a|, |b|)

d[i][j]는 a의 앞 i글자와 b의 앞 j글자 사이의 거리이며 d[i][0] = i, d[0][j] = j에서 시작합니다. 인접 교환(최적 문자열 정렬) 변형은 이웃한 두 글자가 바뀌었을 때 d[i−2][j−2] + 1을 추가하지만 같은 부분 문자열을 두 번 편집하지는 않습니다. 제한 없는 Damerau–레벤슈타인 거리는 이 제한을 없앱니다(CA → ABC는 3이 아니라 2). 글자는 유니코드 코드 포인트이고, 단어는 공백으로 구분합니다.

예시

된장찌개 → 김치찌개 = 2입니다. 된 → 김, 장 → 치 두 글자를 치환합니다. 두 문자열의 길이는 모두 4이므로 유사도는 1 − 2/4 = 50%입니다. 서울 → 서울시는 1(시 삽입)입니다. 김치찌개를 기준으로 목록 김치전, 된장찌개, 김치볶음밥, 김치찌게의 순위를 매기면 거리 1인 김치찌게가 1위가 됩니다.