채운 칸
편집 거리
유지한 글자

  • 채우는 중
  • 읽는 칸
  • 답

편집 거리 더 알아보기

편집 거리(레벤슈타인 거리)

kitten을 sitting으로 바꾸려면 한 글자 변경이 몇 번 필요할까요? 세 번입니다. k를 s로, e를 i로 교체하고 g를 추가하면 됩니다. 이 수가 편집 거리이며, 맞춤법 검사기가 추천 단어의 순위를 매기고 생물학자가 유전자를 비교할 때 쓰입니다. 두 단어를 입력하고 표가 이 값을 찾는 과정을 지켜보세요. 재생을 눌러 표가 채워지는 과정을 보거나, 단계와 뒤로로 한 단계씩 진행하세요. 단계 슬라이더를 끌면 원하는 곳으로 이동합니다. 두 단어를 입력하세요. 첫 번째 단어는 표의 왼쪽을 따라 세로로, 두 번째 단어는 위쪽을 따라 가로로 놓입니다. 각 칸에는 그 행까지의 글자를 그 열까지의 글자로 바꾸는 데 필요한 최소 편집 횟수가 들어갑니다. 마지막에는 오른쪽 아래 칸에서부터 편집을 거꾸로 읽어 냅니다. 새 예제는 다른 단어 쌍을 고릅니다. 보드를 선택한 상태에서 화살표 키는 단계 이동, 스페이스 바는 재생과 일시 정지, Home과 End는 처음과 끝으로 이동합니다.

작동 원리

  1. 두 단어를 입력하세요. 첫 번째 단어는 표의 왼쪽을 따라 세로로, 두 번째 단어는 위쪽을 따라 가로로 놓입니다.
  2. 재생을 누르거나, 단계와 뒤로로 한 단계씩 이동하세요. 단계 슬라이더를 끌면 원하는 곳으로 이동합니다.
  3. 각 칸이 세 이웃 중 가장 저렴한 값을 가져오는 모습을 본 다음, 편집이 주황색으로 거꾸로 읽히는 것을 확인하세요.

표의 작동 방식

각 칸에는 첫 번째 단어의 그 행까지의 글자를 두 번째 단어의 그 열까지의 글자로 바꾸는 최소 편집 횟수가 들어갑니다. 첫 행은 삽입 횟수로, 두 번째 단어를 빈 상태에서 만들어 가고, 첫 열은 삭제 횟수입니다. 칸의 두 글자가 같으면 왼쪽 위 칸을 복사합니다. 편집이 필요 없기 때문입니다. 그렇지 않으면 세 이웃 중 가장 작은 값보다 1 큽니다. 왼쪽 위는 교체, 위는 삭제, 왼쪽은 삽입에 해당합니다.

편집 거꾸로 읽기

오른쪽 아래 칸이 편집 거리입니다. 앱은 거기서 시작해 그 칸의 값이 어느 이웃에서 왔는지 찾아 그쪽으로 이동합니다. 유지하거나 교체한 글자는 대각선으로, 삭제한 글자는 위로, 삽입한 글자는 왼쪽으로 갑니다. 왼쪽 위부터 읽으면 이 단계들이 가장 짧은 편집 목록이 되며, 표 아래에 표시됩니다. 그냥 글자는 유지, k→s는 교체, −e는 삭제, +g는 삽입입니다.

자주 묻는 질문

레벤슈타인 거리란 무엇인가요?

이 편집 거리의 다른 이름으로, 한 문자열을 다른 문자열로 바꾸는 한 글자 삽입, 삭제, 교체의 최소 횟수입니다. 1965년에 이를 정의한 블라디미르 레벤슈타인의 이름을 땄습니다.

kitten과 sitting의 편집 거리는 얼마인가요?

3입니다. k를 s로, e를 i로 교체하고 끝에 g를 삽입합니다. 이보다 짧은 편집 목록이 없다는 것을 표가 보여 줍니다.

편집 거리 알고리즘은 얼마나 빠른가요?

길이가 m과 n인 단어라면 표에는 (m + 1)·(n + 1)개의 칸이 있고 각 칸을 한 단계에 채우므로 O(m·n) 시간이 걸립니다. 거리만 필요하다면 표의 두 행만 있으면 됩니다.

다른 편집 거리에는 무엇이 있나요?

다메라우-레벤슈타인 거리는 이웃한 두 글자를 맞바꾸는 것도 한 번의 편집으로 세므로 오타에 잘 맞습니다. 해밍 거리는 교체만 허용하며 길이가 같은 문자열에 쓰입니다. LCS 거리는 삽입과 삭제만 허용합니다.

어딘가로 데이터가 전송되나요?

아니요. 모든 계산은 브라우저에서 이루어지며, 마지막 설정은 이 브라우저의 로컬 저장소에 남습니다.

시도해 볼 준비가 되셨나요?

브라우저에서 PictorX를 엽니다. 설치가 필요 없고 시작하는 데 신용 카드가 필요하지 않습니다.

편집기로 이동