편집 거리(레벤슈타인) 단계 계산기
두 문자열의 편집 거리를 구하고 어떤 연산을 어느 순서로 하는지 DP 표와 함께 보여 줍니다. 한글을 음절로 셀지 자모로 풀어 셀지에 따라 답이 어떻게 달라지는지 견줄 수 있습니다.
편집 거리
3회
교체 2 · 삽입 1 · 삭제 0
| 단계 | 연산 | 무엇을 | 그 뒤의 모습 |
|---|---|---|---|
| 1 | 교체 | «k» → «s» | sitten |
| 2 | 교체 | «e» → «i» | sittin |
| 3 | 삽입 | «g» 넣기 | sitting |
| ε | s | i | t | t | i | n | g | |
|---|---|---|---|---|---|---|---|---|
| ε | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| k | 1 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| i | 2 | 2 | 1 | 2 | 3 | 4 | 5 | 6 |
| t | 3 | 3 | 2 | 1 | 2 | 3 | 4 | 5 |
| t | 4 | 4 | 3 | 2 | 1 | 2 | 3 | 4 |
| e | 5 | 5 | 4 | 3 | 2 | 2 | 3 | 4 |
| n | 6 | 6 | 5 | 4 | 3 | 3 | 2 | 3 |
사용 방법
- 1원본 문자열과 대상 문자열을 각각 넣습니다.
- 2한글을 음절로 셀지 자모로 풀어 셀지 고릅니다. 답이 달라질 수 있습니다.
- 3연산 목록에서 교체·삽입·삭제가 어느 자리에서 일어나는지, 그 뒤 문자열이 어떻게 바뀌는지 확인합니다.
- 4DP 표의 오른쪽 아래 칸이 답이며, 거기서 왼쪽 위로 되짚어 간 것이 위의 연산 목록입니다.
자주 묻는 질문
D[i][j] = min(D[i−1][j] + 1, D[i][j−1] + 1, D[i−1][j−1] + 비용)으로 표를 채우고 오른쪽 아래 칸을 읽습니다. 비용은 두 글자가 같으면 0, 다르면 1입니다. 세 항이 각각 삭제·삽입·교체에 해당하며, 첫 행과 첫 열은 빈 문자열에서 시작하므로 0, 1, 2…로 채웁니다.
3입니다. k를 s로 교체, e를 i로 교체, 끝에 g를 삽입하면 됩니다. 교체 2회와 삽입 1회이며, 이보다 적은 횟수로 바꾸는 방법은 없습니다.
있습니다. DP 표를 되짚어 갈 때 같은 값을 주는 이웃이 여럿이면 어느 쪽으로 가도 횟수가 같기 때문입니다. 이 계산기는 대각선(교체·일치)을 먼저 잡는 규약으로 그중 하나를 보여 줍니다. 교재의 답과 순서가 달라도 개수가 같으면 둘 다 맞습니다.
목적에 따라 다르고, 값도 달라집니다. 음절로 세면 글자가 다르기만 하면 교체 한 번이라 «가»→«니»가 1이지만, 자모로 풀면 ㄱㅏ → ㄴㅣ이므로 2가 됩니다. 오타의 세밀한 정도를 보려면 자모가, 사람이 세는 감각에는 음절이 가깝습니다. 겹받침은 한 덩어리로 세어 «값»은 자모 3개입니다.
붙어 있는 두 글자를 맞바꾸는 것(전치)을 한 번으로 세느냐가 다릅니다. «안녕»→«녕안»이 레벤슈타인으로는 교체 2회지만 전치를 허용하면 1회입니다. 이 계산기가 함께 내는 값은 OSA(optimal string alignment)라는 제한형으로, 같은 자리를 두 번 건드리지 않는 제약이 있어 제약 없는 다마라우 거리보다 클 때가 있습니다.
전송되지 않습니다. 모든 계산은 브라우저 안에서 이뤄지고, 입력값은 이 기기에만 남습니다.
알아두면 좋은 점
- 입력은 언제나 유니코드 NFC로 정규화한 뒤 셉니다. 같은 «각»이라도 한 글자(U+AC01)로 저장될 수도, ㄱ+ㅏ+ㄱ 세 코드(NFD)로 저장될 수도 있어 정규화하지 않으면 눈에 똑같은 두 글이 거리 3으로 나옵니다. 맥에서 만든 파일 이름이 NFD인 것이 대표적입니다.
- 연산 순서는 여러 최소 경로 가운데 하나입니다. 다른 순서가 나오더라도 연산 «개수»가 같으면 똑같이 옳은 답입니다.
- 이모지나 국기처럼 여러 코드가 모여 한 글자로 보이는 문자는 코드포인트 단위로 나뉘어 셉니다. 눈에 한 글자여도 거리가 2 이상 나올 수 있습니다.
- 계산량이 두 길이의 곱(O(mn))이라 긴 글에는 맞지 않습니다. 표는 한 변이 40자 이하일 때만 그리고, 300자를 넘으면 계산하지 않습니다.
- 거리 값만 필요하거나 긴 글을 견주려면 문자열 유사도 비교 도구가 낫습니다. 이 도구는 과정을 보이는 데 목적이 있습니다.
함께 보면 좋은 도구
마지막 검증: 2026년 9월 1일 · 결과는 참고용 추정치입니다.