편집 거리(Edit distance)

해밍 거리⁠(Hamming distance)⁠는 길이가 같은 문자열을 같은 자리끼리만 비교합니다. 그래서 '미적분⁠(calculus)⁠'과 '적분학'은 글자 하나가 밀렸을 뿐인데 세 자리가 모두 달라 거리가 3입니다. 편집 거리는 글자를 넣고(삽입), 빼고(삭제), 바꾸는(치환) 연산을 한 번에 1씩 쳐서, 한 문자열을 다른 문자열로 바꾸는 가장 적은 횟수를 셉니다. '미'를 빼고 '학'을 넣으면 되니 2입니다. kitten을 sitting으로 바꾸려면 k→s, e→i로 바꾸고 g를 넣어 3입니다. 1965년 소련의 수학자 블라디미르 레벤시테인이 정의해 레벤시테인 거리라고도 합니다.

모든 편집 순서를 다 해 볼 수는 없습니다. 대신 $D_{i,j}$를 '앞 문자열의 첫 i글자를 뒤 문자열의 첫 j글자로 바꾸는 최소 비용'으로 정하고 작은 문제부터 풉니다. 마지막 글자를 어떻게 처리했는지는 세 가지뿐입니다. 지웠거나(위 칸 + 1), 뒤 문자열의 글자를 넣었거나(왼쪽 칸 + 1), 서로 맞춰 놓았거나(대각선 칸 + 글자가 다르면 1)입니다. 첫 행과 첫 열은 빈 문자열 ε에서 시작하므로 0, 1, 2, …입니다. 이렇게 표를 채우는 방법을 동적 계획법이라고 합니다.

단어 쌍은 입니다. 편집 거리는 , 해밍 거리는 입니다. 아래 단추와 막대로 표를 처음부터 한 칸씩 채우거나 되감아 볼 수 있습니다. 칸에 마우스를 올리거나 칸을 누르면 그 값이 어디서 왔는지 보여 줍니다.

표를 그래프로 보면 더 분명합니다. 칸이 꼭짓점⁠(vertex)⁠이고, 오른쪽 화살표는 삽입, 아래 화살표는 삭제, 대각선 화살표는 치환(같은 글자면 비용 0)입니다. 편집 거리는 왼쪽 위 모서리에서 오른쪽 아래 모서리까지 가는 최단 경로⁠(shortest path)⁠의 길이이고, 색칠한 길이 그 경로입니다. 대각선을 빼고 오른쪽과 아래로만 가는 길만 해도 이항계수⁠(binomial coefficient)⁠만큼 많아 하나하나 따지면 금방 감당할 수 없지만, 표에는 칸이 $(m+1)(n+1)$개뿐이라 계산량이 $O(mn)$에 그칩니다(점근 표기법⁠, asymptotic notation⁠). 이웃 칸에서 값을 모아 오는 방식은 파스칼의 삼각형⁠(Pascal's triangle)⁠을 채우는 방식, 앞의 두 값을 기억해 두고 피보나치 수를 구하는 방식과 같습니다.

편집 거리는 거리 함수⁠(metric)⁠입니다. 삽입은 삭제로, 삭제는 삽입으로, 치환은 반대 치환으로 되돌리면 되니 대칭이고, A를 B로 바꾸는 편집과 B를 C로 바꾸는 편집을 이어 붙이면 A를 C로 바꾸는 편집이 되니 삼각부등식⁠(triangle inequality)⁠이 성립합니다. 이 논증은 연산마다 비용이 같고 되돌리는 연산의 비용도 같다는 데 기대고 있어서, 변형을 만들 때는 조심해야 합니다. 이웃한 두 글자를 맞바꾸는 것(CA → AC)을 한 번으로 치되 '한 번 손댄 글자는 다시 고치지 않는다'고 제한한 흔한 변형에서는 CA → AC가 1, AC → ABC가 1인데 CA → ABC는 3이라 삼각부등식이 깨집니다. 제한을 두지 않은 다메라우–레벤시테인 거리로는 CA → ABC가 2이고, 거리 함수입니다.

길이가 같으면 편집 거리는 해밍 거리보다 크지 않습니다. 다른 자리마다 치환 한 번씩이면 되기 때문입니다. 맞춤법 검사기는 틀린 단어와 편집 거리가 가장 가까운 사전 단어를 권하는데, 이것은 최근접 이웃⁠(nearest neighbor)⁠ 찾기입니다.

생물학에서는 DNA와 단백질 서열을 맞출 때 같은 표를 씁니다. 다만 비슷한 성질의 아미노산끼리 바뀌면 벌점을 적게 주는 식으로 글자 쌍마다 다른 점수를 줍니다. 1970년 솔 니들먼과 크리스천 운슈가 발표해 니들먼–운슈 알고리즘⁠(algorithm)⁠이라 합니다.

이어지는 곳.

• 동적 계획법의 바탕은 미국 수학자 리처드 벨먼이 1950년대에 세운 최적성 원리, 곧 '최적 경로의 일부도 그 구간에서 최적'이라는 사실입니다. 편집 표에서 각 칸의 값을 이웃 칸의 최솟값으로 구할 수 있는 것도 이 때문이고, 여러 단계로 나뉜 최적화⁠(optimization)⁠ 문제에 두루 쓰입니다.
• 상태는 보이지 않고 상태가 내놓는 관측값만 보이는 마르코프 연쇄⁠(Markov chain)⁠에서 관측값들을 가장 그럴듯하게 만든 상태열을 찾는 비터비 알고리즘(은닉 마르코프 모델⁠, hidden Markov model⁠)도 같은 모양입니다. '시각 × 상태'의 격자에서 각 칸까지 가장 그럴듯한 경로를 앞 칸들에서 모아 오니, 편집 표를 채우는 것과 같은 동적 계획법입니다. 1967년 공학자 앤드루 비터비가 제안했습니다.
• 긴 문서끼리는 글자를 하나하나 편집하는 대신, 각 단어가 몇 번 나오는지를 모은 벡터⁠(vector)⁠를 만들어 코사인 유사도⁠(cosine similarity)⁠로 비교하는 편이 흔합니다. 글자 순서보다 어떤 낱말을 얼마나 썼는지가 내용을 더 잘 드러내기 때문입니다.
• 언어학자들은 두 언어의 낱말을 비교할 때 글자 거리만 보지 않고, 규칙적인 소리 대응을 찾습니다(비교 언어학⁠, comparative linguistics⁠). 글자가 조금 닮은 것은 우연으로도 흔하지만, 규칙적인 대응은 한 조상에서 온 낱말을 가려내 줍니다.