レーベンシュタイン距離

レーベンシュタイン距離は、文字列同士がどれだけ似ているかを数値で表す代表的な指標です。スペルチェッカーや検索エンジン、OCR、自然言語処理など、多くの分野で利用されています。入力された文字列と候補を比較し、最も近いものを見つける際に特に有効です。

この距離は、通常、動的計画法を用いて計算します。各セルに部分文字列同士を変換するための最小コストを記録した行列を作成し、それを順番に埋めていくことで、全体の最小編集回数を求めます。

ハミング距離とは異なり、レーベンシュタイン距離は長さの異なる文字列にも適用できます。

具体例

次の2つの文字列 \( s \) と \( t \) を考えます。

$$ s = "kitten" $$

$$ t = "sitting" $$

ここでは、"kitten" を "sitting" に変換するために必要な編集操作の最小回数、つまりレーベンシュタイン距離を求めます。

1. 置換
   \( k \) を \( s \) に置き換えます。 $$ "kitten" \rightarrow "sitten" $$
2. 置換
   \( e \) を \( i \) に置き換えます。 $$ "sitten" \rightarrow "sittin" $$
3. 挿入
   末尾に \( g \) を挿入します。 $$ "sittin" \rightarrow "sitting" $$

必要な編集操作は合計3回です。内訳は、置換が2回、挿入が1回です。したがって、"kitten" と "sitting" のレーベンシュタイン距離は3になります。

この計算は、\( (m+1) \times (n+1) \) の行列を使って行います。ここで、\( m \) は "kitten" の文字数（6）、\( n \) は "sitting" の文字数（7）です。

空文字列との変換も扱えるようにするため、行列には先頭に1行と1列を追加します。

セル \( (0, j) \) は、空文字列を "sitting" の先頭から \( j \) 文字までの部分文字列へ変換するコストを表します。そのため、値は0から7まで1ずつ増加します。

セル \( (i, 0) \) は、"kitten" の先頭から \( i \) 文字までの部分文字列を空文字列へ変換するコストを表します。そのため、値は0から6まで1ずつ増加します。

各セル \( (i, j) \) の値は、次の3つの候補のうち最小のものを選んで決定します。

1. "kitten" 側の文字を1文字削除する（上のセルの値 \( +1 \)）
2. "kitten" 側に1文字挿入する（左のセルの値 \( +1 \)）
3. 文字を置換する（左上の対角セルの値を利用し、文字が異なる場合のみ \( +1 \)）

この規則に従って、行列を左上から右下へ順番に埋めていきます。

たとえば、空文字列を "s"、"si"、"sit" のような部分文字列へ変換する場合は、文字を1つずつ挿入するため、列が進むたびにコストが1ずつ増加します。

逆に、"k"、"ki"、"kit" のような部分文字列を空文字列へ変換する場合は、文字を1つずつ削除するため、行が進むたびにコストが1ずつ増加します。

• セル (1,1) は、"k" を "s" に変換するコストです。置換1回（k→s）だけで済むため、値は1になります。
  
• セル (2,2) は、"ki" を "si" に変換するコストです。2文字目の i は一致しているため、コストは1のままです。
• セル (3,3) は、"kit" を "sit" に変換するコストです。3文字目の t も一致しているため、コストは変わりません。
• セル (4,4) は、"kitt" を "sitt" に変換するコストです。4文字目も一致しているため、値は1です。
• セル (5,5) は、"kitte" を "sitti" に変換するコストです。e→i の置換が必要になるため、コストは2になります。
  
• セル (6,6) は、"kitten" を "sittin" に変換するコストです。6文字目の n は一致しているため、コストは2のままです。
• セル (6,7) は、"kitten" を "sitting" に変換するコストです。最後に g を1文字挿入する必要があるため、コストは3になります。
  

このように行列を最後まで埋めると、右下のセルに変換全体の最小コストが得られます。

この例では、右下のセル \( (6,7) \) の値は3です。

つまり、"kitten" を "sitting" に変換するためには、置換2回（k → s、e → i）と挿入1回（g）の合計3回の編集操作が必要であり、これがレーベンシュタイン距離となります。

レーベンシュタイン距離が誘導する位相

レーベンシュタイン距離は、ハミング距離と同様に距離の公理をすべて満たすため、文字列全体の集合上に距離空間を定義できます。

1. 非負性: 任意の2つの文字列 \( x \) と \( y \) に対して、レーベンシュタイン距離は常に0以上です。また、\( D_L(x,y)=0 \) が成り立つのは \( x=y \) の場合に限られます。つまり、文字列をそれ自身へ変換するためには編集操作は不要であり、距離が0になるのは2つの文字列が完全に一致するときだけです。
2. 対称性: レーベンシュタイン距離は対称性を満たし、 \( D_L(x,y)=D_L(y,x) \) が成り立ちます。言い換えれば、\( x \) を \( y \) に変換するために必要な編集操作の回数は、\( y \) を \( x \) に変換する場合と等しくなります。これは、挿入・削除・置換という各操作が逆方向の変換にも対応しているためです。
3. 三角不等式: レーベンシュタイン距離は \( D_L(x,z)\leq D_L(x,y)+D_L(y,z) \) を満たします。つまり、文字列 \( x \) から \( z \) への直接の距離は、途中で文字列 \( y \) を経由した場合の距離の和を超えることはありません。これは、\( x \) から \( z \) への編集操作列を、\( x \) から \( y \)、さらに \( y \) から \( z \) への編集操作列に分けて考えられるためです。

これらの性質により、レーベンシュタイン距離は文字列集合上に距離空間を定義します。

さらに、距離空間の公理を満たしていることから、この距離を用いて距離位相（距離が誘導する位相）を定義することもできます。

半径 \( r \) と文字列 \( x \) を与えると、中心を \( x \) とする開球は、\( x \) からのレーベンシュタイン距離が \( r \) 未満であるすべての文字列 \( y \) の集合として定義されます。

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

そして、このような開球の任意個の和集合が、この距離位相における開集合になります。

この考え方は、文字列同士の「近さ」を評価するさまざまな分野で活用されています。たとえば自動スペル修正では、辞書中の単語とのレーベンシュタイン距離が小さい単語を候補として提示することで、入力ミスを効率よく修正できます。

このように、レーベンシュタイン距離を用いることで、文字列を距離空間の要素として扱い、その距離が誘導する位相を利用して文字列同士の近さを数学的に解析できます。

具体例

3文字からなる文字列の集合 \( X \) を考えます。

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

ここでは、それぞれの文字列を中心とする半径 \( r=2 \) の開球を考え、それらを位相の基底として用います。

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

半径 \( r=2 \) の開球には、中心の文字列からレーベンシュタイン距離が1以下の文字列がすべて含まれます。

注意: 開球では距離が「2未満」であることが条件です。そのため、半径 \( r=2 \) の開球に含まれるのは、中心から高々1回の編集操作で到達できる文字列になります。すなわち、 $$ B(x,2)=\{\,y\mid D_L(x,y)<2\,\} $$ です。一方、境界を含む閉球では、 $$ C(x,2)=\{\,y\mid D_L(x,y)\le2\,\} $$ となり、編集距離が2以下のすべての文字列が含まれます。

それでは、それぞれの文字列について半径2の開球を求めてみましょう。

1. "cat" を中心とする開球 $$ B(\text{"cat"},2)=\{\text{"cat"},\ \text{"bat"}\} $$ 集合 \( X \) の中で、"cat" と "bat" は1文字を置き換えるだけで相互に変換できます。そのため、この2つの文字列が開球に含まれます。
2. "bat" を中心とする開球 $$ B(\text{"bat"},2)=\{\text{"bat"},\ \text{"cat"}\} $$ 同様に、"bat" から編集距離1以下にある文字列は、"bat" 自身と "cat" の2つです。
3. "cut" を中心とする開球 $$ B(\text{"cut"},2)=\{\text{"cut"}\} $$ 集合 \( X \) の中には、"cut" から編集距離1以下で到達できる別の文字列は存在しません。そのため、この開球には "cut" 自身だけが含まれます。

以上の3つの開球 \( B(\text{"cat"},2) \)、\( B(\text{"bat"},2) \)、\( B(\text{"cut"},2) \) は、レーベンシュタイン距離が誘導する位相の基底になります。

この基底を用いれば、任意の開集合は、これらの開球の任意個の和集合として表すことができます。

たとえば、\( B(\text{"bat"},2) \) と \( B(\text{"cut"},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"}\} \) も、この位相における開集合の1つになります。

このように、レーベンシュタイン距離によって文字列集合 \( X \) 上に距離位相を導入でき、その基底となる開球を組み合わせることで、すべての開集合を構成できます。

他の場合も同様に考えることができます。