레벤슈타인 거리

레벤슈타인 거리는 문자열 사이의 유사도를 측정하는 가장 널리 사용되는 방법 중 하나입니다. 특히 맞춤법 검사기, 검색 엔진, 자동 완성, 자연어 처리(NLP) 등에서 비슷한 단어를 찾거나 오탈자를 수정하는 데 활용됩니다.

레벤슈타인 거리를 계산하기 위해서는 동적 계획법(Dynamic Programming)을 이용한 행렬을 구성합니다. 행렬의 각 셀은 한 부분 문자열을 다른 부분 문자열로 변환하는 데 필요한 최소 비용을 나타내며, 이를 순차적으로 계산해 최종적으로 전체 문자열의 최소 편집 횟수를 구합니다.

해밍 거리와 달리, 레벤슈타인 거리는 길이가 서로 다른 문자열에도 적용할 수 있습니다.

계산 예제

다음 두 문자열을 예로 들어 보겠습니다.

$$ s = "kitten" $$

$$ t = "sitting" $$

목표는 "kitten"을 "sitting"으로 변환하는 데 필요한 최소 편집 연산 횟수, 즉 레벤슈타인 거리를 구하는 것입니다.

1. 치환
   \( k \)를 \( s \)로 바꿉니다. $$ "kitten" \rightarrow "sitten" $$
2. 치환
   \( e \)를 \( i \)로 바꿉니다. $$ "sitten" \rightarrow "sittin" $$
3. 삽입
   마지막에 \( g \)를 추가합니다. $$ "sittin" \rightarrow "sitting" $$

총 세 번의 편집 연산(치환 2회, 삽입 1회)이 필요하므로 두 문자열 사이의 레벤슈타인 거리는 3입니다.

이 과정을 행렬로 표현하면 크기가 \( (m+1) \times (n+1) \)인 표를 사용합니다. 여기서 \( m \)은 "kitten"의 길이인 6이고, \( n \)은 "sitting"의 길이인 7입니다.

첫 번째 행과 첫 번째 열은 빈 문자열과의 변환을 처리하기 위해 추가됩니다.

셀 \( (0,j) \)는 빈 문자열을 "sitting"의 앞에서부터 \( j \)번째 문자까지의 부분 문자열로 바꾸는 비용을 나타냅니다. 따라서 비용은 0부터 7까지 순차적으로 증가합니다.

반대로 셀 \( (i,0) \)는 "kitten"의 앞에서부터 \( i \)번째 문자까지의 부분 문자열을 빈 문자열로 바꾸는 비용을 나타내며, 비용은 0부터 6까지 증가합니다.

각 셀 \( (i,j) \)의 값은 다음 세 가지 경우 가운데 가장 작은 비용을 선택하여 계산합니다.

1. "kitten"에서 문자를 삭제하는 경우: 위쪽 셀의 비용 +1
2. "kitten"에 문자를 삽입하는 경우: 왼쪽 셀의 비용 +1
3. 문자를 치환하는 경우: 대각선 셀의 비용을 사용하며, 두 문자가 같으면 추가 비용은 0이고 다르면 1을 더합니다.

이 규칙을 적용하여 행렬을 한 칸씩 채워 나갑니다.

예를 들어 빈 문자열을 "s", "si", "sit" 등으로 변환하려면 문자를 하나씩 삽입해야 하므로 열이 하나 늘어날 때마다 비용이 1씩 증가합니다.

반대로 "k", "ki", "kit" 등을 빈 문자열로 변환하려면 문자를 하나씩 삭제해야 하므로 행이 하나 늘어날 때마다 비용이 1씩 증가합니다.

• 셀 (1,1)은 "k"를 "s"로 변환하는 비용을 나타냅니다. 한 번의 치환(k→s)만 필요하므로 비용은 1입니다.
  
• 셀 (2,2)는 "ki"를 "si"로 변환하는 비용을 나타냅니다. 두 번째 문자가 모두 i이므로 비용은 그대로 1입니다.
• 셀 (3,3)은 "kit"를 "sit"로 변환하는 비용을 나타냅니다. 세 번째 문자인 t가 동일하므로 비용은 계속 1입니다.
• 셀 (4,4)는 "kitt"를 "sitt"로 변환하는 비용을 나타냅니다. 네 번째 문자도 t로 같으므로 비용은 여전히 1입니다.
• 셀 (5,5)는 "kitte"를 "sitti"로 변환하는 비용을 나타냅니다. e를 i로 치환해야 하므로 비용은 2가 됩니다.
  
• 셀 (6,6)은 "kitten"을 "sittin"으로 변환하는 비용을 나타냅니다. 여섯 번째 문자인 n이 같으므로 비용은 그대로 2입니다.
• 셀 (6,7)은 "kitten"을 "sitting"으로 변환하는 비용을 나타냅니다. 마지막에 g를 하나 삽입해야 하므로 비용은 3이 됩니다.
  

이와 같이 행렬을 끝까지 채우면 마지막 셀에서 전체 변환에 필요한 최소 비용을 확인할 수 있습니다.

오른쪽 아래의 셀 \( (6,7) \)에는 "kitten"을 "sitting"으로 변환하는 최소 비용이 저장되어 있으며, 그 값은 3입니다.

이 값이 바로 레벤슈타인 거리입니다. 즉, k → s 치환 1회, e → i 치환 1회, 그리고 g 삽입 1회가 필요하다는 의미입니다.

레벤슈타인 거리가 유도하는 위상

레벤슈타인 거리는 해밍 거리와 마찬가지로 문자열 집합 위에 거리 공간(metric space)을 정의합니다. 이는 거리 함수가 만족해야 하는 모든 공리를 충족하기 때문입니다.

1. 비음수성(Non-negativity): 두 문자열 \( x \)와 \( y \) 사이의 레벤슈타인 거리는 항상 0 이상이며, \( D_L(x,y)=0 \)은 \( x=y \)인 경우에만 성립합니다. 즉, 문자열을 자기 자신으로 바꾸는 데에는 어떠한 편집 연산도 필요하지 않으므로, 거리가 0이라는 것은 두 문자열이 완전히 동일함을 의미합니다.
2. 대칭성(Symmetry): 레벤슈타인 거리는 \( D_L(x,y)=D_L(y,x) \) 를 만족합니다. 다시 말해, 문자열 \( x \)를 \( y \)로 변환하는 데 필요한 최소 편집 횟수는 \( y \)를 \( x \)로 변환하는 경우와 같습니다. 이는 삽입, 삭제, 치환 연산이 서로 반대 방향으로 대응되기 때문입니다.
3. 삼각 부등식(Triangle Inequality): 레벤슈타인 거리는 \( D_L(x,z)\le D_L(x,y)+D_L(y,z) \) 를 만족합니다. 즉, 문자열 \( x \)에서 \( z \)까지의 최소 편집 거리는 임의의 문자열 \( y \)를 거쳐 이동하는 거리보다 클 수 없습니다. 이는 \( x \)에서 \( z \)까지의 편집 과정을 \( x \)에서 \( y \)까지의 과정과 \( y \)에서 \( z \)까지의 과정으로 나누어 생각할 수 있기 때문입니다.

이러한 성질 덕분에 레벤슈타인 거리는 문자열 집합 위에 거리 공간(metric space)을 정의합니다.

또한 거리 공간의 모든 공리를 만족하므로, 문자열 집합 위에 거리 위상(metric topology)도 자연스럽게 정의할 수 있습니다.

반지름 \( r \)과 문자열 \( x \)가 주어졌을 때, 중심이 \( x \)인 열린 공(open ball)은 레벤슈타인 거리가 \( r \)보다 작은 모든 문자열의 집합으로 정의됩니다.

$$ B(x,r)=\{\,y\mid D_L(x,y)

그리고 이러한 열린 공들의 임의의 합집합이 이 거리 위상의 열린집합을 이룹니다.

이 개념은 문자열 사이의 "가까움"을 수학적으로 표현해야 하는 다양한 분야에서 활용됩니다. 대표적인 예가 자동 맞춤법 교정입니다. 사용자가 입력한 단어와 사전에 있는 단어 사이의 레벤슈타인 거리가 작을수록, 해당 단어는 유력한 교정 후보가 됩니다.

즉, 레벤슈타인 거리를 이용하면 문자열을 거리 공간의 원소로 다룰 수 있으며, 거리 위상을 통해 문자열 사이의 근접성을 체계적으로 분석할 수 있습니다.

실제 예제

길이가 3인 문자열들로 이루어진 집합 \( X \)를 다음과 같이 정의하겠습니다.

$$ X=\{\text{"cat"},\ \text{"bat"},\ \text{"cut"}\} $$

이제 집합 \( X \)의 각 문자열을 중심으로 반지름 \( r=2 \)인 열린 공을 정의하여 위상의 기저를 만들어 보겠습니다.

$$ B(x,r)=\{\,y\mid D_L(x,y)

반지름이 \( r=2 \)인 열린 공에는 중심 문자열과의 레벤슈타인 거리가 2보다 작은 모든 문자열이 포함됩니다. 다시 말해, 한 번의 편집 연산만으로 서로 변환할 수 있는 문자열들이 이 열린 공에 속합니다.

참고: 열린 공에서는 \( D_L(x,y)<2 \)를 만족해야 하므로, 거리가 정확히 2인 문자열은 포함되지 않습니다. 따라서 반지름이 2인 열린 공에는 편집 거리가 최대 1인 문자열만 포함됩니다. $$ B(x,2)=\{\,y\mid D_L(x,y)<2\,\} $$ 반대로 경계까지 포함하는 닫힌 공(closed ball)은 다음과 같이 정의됩니다. $$ C(x,2)=\{\,y\mid D_L(x,y)\le2\,\} $$ 이 경우에는 중심 문자열에서 최대 두 번의 편집 연산으로 도달할 수 있는 모든 문자열이 포함됩니다.

이제 집합 \( X \)의 각 원소를 중심으로 하는 반지름 2의 열린 공을 계산해 보겠습니다.

1. "cat"을 중심으로 하는 열린 공 $$ B(\text{"cat"},2)=\{\text{"cat"},\ \text{"bat"}\} $$ 집합 \( X \)에서 "cat"과의 레벤슈타인 거리가 1 이하인 문자열은 "cat"과 "bat"뿐입니다.
2. "bat"을 중심으로 하는 열린 공 $$ B(\text{"bat"},2)=\{\text{"bat"},\ \text{"cat"}\} $$ 마찬가지로 "bat"과 한 번 이하의 편집 연산으로 서로 변환할 수 있는 문자열은 "bat"과 "cat"뿐입니다.
3. "cut"을 중심으로 하는 열린 공 $$ B(\text{"cut"},2)=\{\text{"cut"}\} $$ 집합 \( X \)에는 "cut"과의 레벤슈타인 거리가 1 이하인 다른 문자열이 없으므로, 이 열린 공에는 "cut"만 포함됩니다.

따라서 \( B(\text{"cat"},2) \), \( B(\text{"bat"},2) \), \( B(\text{"cut"},2) \) 는 반지름 \( r=2 \)에서 레벤슈타인 거리가 유도하는 위상의 기저를 이룹니다.

이 기저를 이용하면 열린 공들의 임의의 합집합으로 모든 열린집합을 만들 수 있습니다.

예를 들어 다음과 같은 합집합을 생각해 보겠습니다.

$$ B(\text{"bat"},2)\cup B(\text{"cut"},2) $$

앞에서 구한 결과를 이용하면

$$ B(\text{"bat"},2)=\{\text{"cat"},\ \text{"bat"}\} $$

$$ B(\text{"cut"},2)=\{\text{"cut"}\} $$

이므로

$$ B(\text{"bat"},2)\cup B(\text{"cut"},2) = \{\text{"cat"},\ \text{"bat"}\} \cup \{\text{"cut"}\} $$

즉,

$$ B(\text{"bat"},2)\cup B(\text{"cut"},2) = \{\text{"cat"},\ \text{"bat"},\ \text{"cut"}\} $$

따라서 \( \{\text{"cat"},\ \text{"bat"},\ \text{"cut"}\} \) 도 이 위상의 열린집합입니다.

이처럼 레벤슈타인 거리는 문자열 집합 위에 거리 위상을 유도하며, 기저를 이루는 열린 공들의 합집합을 통해 모든 열린집합을 생성할 수 있습니다.

같은 원리는 더 큰 문자열 집합이나 다른 문자열 데이터에도 동일하게 적용됩니다.