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

recieve라고 입력하면 휴대폰이 receive를 추천합니다. 두 단어가 편집 몇 번 차이밖에 나지 않아서 거의 맞았다는 것을 아는 것이죠. 이 가까움, 즉 편집 거리를 재는 것은 동적 계획법의 대표적인 문제입니다.

왼쪽에 세로로 한 단어, 위쪽에 가로로 다른 단어가 있고 칸마다 숫자가 들어 있으며, 왼쪽 위에서 오른쪽 아래 모서리까지 주황색 편집 경로가 이어진 표
왼쪽에 세로로 한 단어, 위쪽에 가로로 다른 단어가 있고 칸마다 숫자가 들어 있으며, 왼쪽 위에서 오른쪽 아래 모서리까지 주황색 편집 경로가 이어진 표

문제

편집은 단어를 한 글자만큼 바꿉니다. 글자를 삽입하거나, 삭제하거나, 다른 글자로 교체하는 것입니다. 두 단어 사이의 편집 거리는 한 단어를 다른 단어로 바꾸는 최소 편집 횟수입니다. cat과 cut은 1, cat과 cast는 1, cat과 act는 2만큼 떨어져 있습니다. 1965년에 이를 연구한 소련의 수학자 블라디미르 레벤슈타인의 이름을 따서 레벤슈타인 거리라고도 합니다.

표

d[i][j]를 한 단어의 처음 i글자와 다른 단어의 처음 j글자 사이의 편집 거리라고 합시다. 단어를 빈 문자열로 만들려면 글자마다 한 번씩 삭제해야 하므로 d[i][0] = i이고, 빈 상태에서 단어를 만들려면 글자마다 한 번씩 삽입해야 하므로 d[0][j] = j입니다. i번째 글자와 j번째 글자가 같으면 d[i][j] = d[i − 1][j − 1]입니다. 그렇지 않으면 d[i][j] = 1 + d[i − 1][j − 1](교체), d[i − 1][j](삭제), d[i][j − 1](삽입) 중 가장 작은 값입니다.

예제

kitten과 sitting의 표는 7행 8열입니다. 오른쪽 아래 칸은 3이고, 거기서 거꾸로 읽으면 다음과 같습니다. k를 s로 교체, i, t, t 유지, e를 i로 교체, n 유지, g 삽입. Kitten, sitten, sittin, sitting: 편집 세 번이며, 표는 이보다 짧은 목록이 없음을 증명합니다.

편집을 거꾸로 읽기

오른쪽 아래 칸에서 시작해 그 값이 어느 이웃에서 왔는지 따져 봅니다. 글자가 같고 칸이 왼쪽 위 이웃과 같으면 글자가 유지된 것이므로 대각선으로 이동합니다. 왼쪽 위 이웃보다 1 크면 교체, 위 칸보다 1 크면 삭제, 왼쪽 칸보다 1 크면 삽입입니다. 여러 경로가 동점일 수 있으며, 어느 경로든 가장 짧은 편집 목록을 줍니다.

역사와 활용

레벤슈타인은 1965년에 오류 정정 부호를 연구하다가 이 거리를 도입했습니다. 표를 이용하는 방법은 여러 사람이 발표했는데, 가장 유명한 것은 1974년 로버트 바그너와 마이클 피셔의 발표여서 흔히 바그너-피셔 알고리즘이라고 부릅니다. 오늘날 편집 거리는 맞춤법 추천의 순위를 매기고, 데이터베이스에서 오타가 있는 이름을 맞춰 찾고, DNA와 단백질 서열을 비교하고, 음성 인식의 결과를 평가하는 데 쓰입니다.

직접 해 보기

앱을 열고 단계를 누르세요. 비교 중인 두 글자가 머리글에서 강조됩니다. 글자가 같으면 왼쪽 위의 파란 칸을 복사하고, 다르면 파란 이웃 세 칸을 모두 읽어 가장 작은 값에 1을 더합니다. 마지막에는 주황색 경로가 모서리에서 거꾸로 이어지고, 편집이 표 아래에 나타납니다.

자주 묻는 질문

편집 거리는 거리 함수(메트릭)인가요?

네. 음수가 되지 않고, 두 단어가 같을 때만 0이며, 어느 방향으로 재도 같고, 세 번째 단어를 거쳐 가도 더 짧아지지 않습니다: d(a, c) ≤ d(a, b) + d(b, c). 그래서 가까운 단어를 검색할 때 유용합니다.

다메라우-레벤슈타인 거리란 무엇인가요?

편집 하나를 더한 편집 거리로, 더해진 편집은 이웃한 두 글자를 맞바꾸는 것입니다. 프레더릭 다메라우는 1964년에 삽입, 삭제, 교체, 맞바꾸기를 합치면 맞춤법 오류의 80% 이상을 설명할 수 있다는 것을 발견했습니다. 맞바꾸기를 허용하면 recieve와 receive의 거리는 2가 아니라 1입니다.

편집 거리를 O(m·n)보다 빠르게 계산할 수 있나요?

크게 빠르게는 어렵습니다. 2015년 아르투르스 바쿠르스와 표트르 인디크는 어떤 ε > 0에 대해 O(n^(2 − ε)) 시간이 걸리는 방법이 있다면, 대부분의 연구자가 옳다고 믿는 강한 지수 시간 가설이 깨진다는 것을 보였습니다. 다만 서로 가까운 단어라면 표의 대각선 주변의 좁은 띠만 계산하면 됩니다.

DNA 비교에는 편집 거리가 어떻게 쓰이나요?

생물학자들은 같은 표를 횟수 대신 점수로 사용합니다. 일치하면 점수를 얻고, 교체와 빈칸(갭)은 글자에 따라 점수를 잃습니다. 서열 전체에는 1970년의 니들먼-분슈 알고리즘을, 가장 잘 맞는 부분에는 1981년의 스미스-워터먼 알고리즘을 씁니다.

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

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

편집 거리 체험하기