Help us understand the problem. What is going on with this article?

レーベンシュタイン距離のコードの解釈

Wikipediaのレーベンシュタイン距離のコードの解釈で混乱したため、メモを残します。

レーベンシュタイン距離は文字列の類似度を調べる最も基本的なアルゴリズムです。この記事ではレーベンシュタイン距離そのものの説明はしないで、コードの解釈に集中します。

レーベンシュタイン距離の説明は色々な記事がありますが、分かりやすそうな記事を1つ挙げておきます。

日本語版

まず日本語版のWikipediaを読みます。

次の記述があります。

以下に、文字数 lenStr1 の文字列 str1 と、文字数 lenStr2 の 文字列 str2 間のレーベンシュタイン距離を求める擬似コードを示す。このコードにおいて d[i1,i2] には、str1i1 文字目までの文字列と str2i2 文字目までの文字列の間のレーベンシュタイン距離が格納される。

str1="biting", str2="whiten" のときの配列 d[i1,i2] の様子を部分文字列と共に示します。

d i1=0 i1=1 i1=2 i1=3 i1=4 i1=5 i1=6
i2=0

0
b

1
bi

2
bit

3
biti

4
bitin

5
biting

6
i2=1
w
1
b
w
1
bi
w
2
bit
w
3
biti
w
4
bitin
w
5
biting
w
6
i2=2
wh
2
b
wh
2
bi
wh
2
bit
wh
3
biti
wh
4
bitin
wh
5
biting
wh
6
i2=3
whi
3
b
whi
3
bi
whi
2
bit
whi
3
biti
whi
3
bitin
whi
4
biting
whi
5
i2=4
whit
4
b
whit
4
bi
whit
3
bit
whit
2
biti
whit
3
bitin
whit
4
biting
whit
5
i2=5
white
5
b
white
5
bi
white
4
bit
white
3
biti
white
3
bitin
white
4
biting
white
5
i2=6
whiten
6
b
whiten
6
bi
whiten
5
bit
whiten
4
biti
whiten
4
bitin
whiten
3
biting
whiten
4

i1i2 の縦横への割り当てには任意性があります。ここではセル内で str1str2 を上下に並べたとき、最初の行で見出しと上下に隣接して分かりやすいため i1 を横に割り当てました。あくまで表現上の工夫のため、アルゴリズムの本質には影響しません。

掲載されている擬似コードを見ます。

まず d の1行目と1列目を埋めます。片方が空文字列のため、もう片方の文字列長がそのままレーベンシュタイン距離となります。

   for Integer i1 := 0 to lenStr1 do let d[i1,0] := i1 ;
   for Integer i2 := 0 to lenStr2 do let d[0,i2] := i2 ;

残りは左から1列ずつ、列内を上から埋めていきます。その際に左 d[i1-1,i2] と上 d[i1,i2-1] と左上 d[i1-1,i2-1] の要素を参照します。

   for Integer i1 := 1 to lenStr1 do
       for Integer i2 := 1 to lenStr2 do
           begin
           constant Integer cost := if str1[i1] == str2[i2] then 0 else 1 ;
           let d[i1,i2] := minimum
             (
             d [i1-1, i2  ] + 1,     (* 文字の削除 *)
             d [i1  , i2-1] + 1,     (* 文字の挿入 *)
             d [i1-1, i2-1] + cost   (* 文字の置換 *)
             )
           end ;

参照した要素には既に値が入っているのがポイントです。このように依存関係を考慮して計算順序をうまく組み上げる手法を動的計画法と呼びます。

レーベンシュタイン距離を計算するためには、一般的に動的計画法によるアルゴリズムが用いられている。

それぞれの要素がどの要素から由来するかを矢印で示します。



0
b

1
bi

2
bit

3
biti

4
bitin

5
biting

6

w
1
b
w
1
bi
w
2
bit
w
3
biti
w
4
bitin
w
5
biting
w
6

wh
2
b
wh
2
bi
wh
2
bit
wh
3
biti
wh
4
bitin
wh
5
biting
wh
6

whi
3
b
whi
3
bi
whi
2
bit
whi
3
biti
whi
3
bitin
whi
4
biting
whi
5

whit
4
b
whit
4
bi
whit
3
bit
whit
2
biti
whit
3
bitin
whit
4
biting
whit
5

white
5
b
white
5
bi
white
4
bit
white
3
biti
white
3
bitin
white
4
biting
white
5

whiten
6
b
whiten
6
bi
whiten
5
bit
whiten
4
biti
whiten
4
bitin
whiten
3
biting
whiten
4

右下の要素が最終的に求めるレーベンシュタイン距離です。右下から矢印を逆にたどると左上までの経路が抽出できます。それを赤字で示しました。

赤字の部分を抽出すると2つの経路が得られます。最初に分岐していますが、その次で合流します。



0

w
1
b
wh
2
bi
whi
2
bit
whit
2
biti
white
3
bitin
whiten
3
biting
whiten
4


0
b
w
1
b
wh
2
bi
whi
2
bit
whit
2
biti
white
3
bitin
whiten
3
biting
whiten
4

コードと比較すれば、左に由来する「→」が削除、上に由来する「↓」が挿入、左上に由来する「↘」が置換とされています。

           constant Integer cost := if str1[i1] == str2[i2] then 0 else 1 ;
           let d[i1,i2] := minimum
             (
             d [i1-1, i2  ] + 1,     (* 文字の削除 *)
             d [i1  , i2-1] + 1,     (* 文字の挿入 *)
             d [i1-1, i2-1] + cost   (* 文字の置換 *)
             )

これは str1 を1文字ずつ調べながら変形して str2 を得る操作のコストを表します。求めているのはあくまでコストであって、文字列の変形は行っていないのに注意が必要です。

変形の過程を表に追加します。「↘」は必ずしも置換するわけではなく、cost0 なら何もしません。

str1 挿入 置換 なし なし 置換 なし 削除
biting wbiting whiting whiting whiting whiteng whiteng whiteng
0 1 2 2 2 3 3 4
str1 置換 挿入 なし なし 置換 なし 削除
biting witing whiting whiting whiting whiteng whiteng whiteng
0 1 2 2 2 3 3 4

部分文字列を示した配列の表において、削除や挿入を行う対象はまた別にあるというのがポイントです。部分文字列だけを見て解釈しようとして、削除の意味が分からずに混乱しました。

配列を解釈しようとする姿勢については次の記事を参考にしました。

グラフ

グラフ化することで2つの経路の関係を視覚的に把握することができます。

こちらの記事を参考に手動でグラフを作成してみました。

Lebenshtein.dot
digraph {
    node [shape=record style=filled]
    start [label="biting" color=pink shape=circle]
    end [label="whiten" color=pink shape=circle]
    node1 [label="[w]biting"]
    node2 [label="[w]iting"]
    node3 [label="w[h]iting"]
    node4 [label="wh[i]ting"]
    node5 [label="whi[t]ing"]
    node6 [label="whit[e]ng"]
    node7 [label="white[n]g"]
    start -> node1 [label="insert 'w'"]
    node1 -> node3 [label="replace 'b' -> 'h'"]
    start -> node2 [label="replace 'b' -> 'w'"]
    node2 -> node3 [label="insert 'h'"]
    node3 -> node4
    node4 -> node5
    node5 -> node6 [label="replace 'i' -> 'e'"]
    node6 -> node7
    node7 -> end [label="delete 'g'"]
}

leben.png

英語版

次に英語版の記事を読みます。

再帰

まず再帰によるC言語のコードが示されます。

// len_s and len_t are the number of characters in string s and t respectively
int LevenshteinDistance(const char *s, int len_s, const char *t, int len_t)
{ 
  int cost;

  /* base case: empty strings */
  if (len_s == 0) return len_t;
  if (len_t == 0) return len_s;

  /* test if last characters of the strings match */
  if (s[len_s-1] == t[len_t-1])
      cost = 0;
  else
      cost = 1;

  /* return minimum of delete char from s, delete char from t, and delete char from both */
  return minimum(LevenshteinDistance(s, len_s - 1, t, len_t    ) + 1,
                 LevenshteinDistance(s, len_s    , t, len_t - 1) + 1,
                 LevenshteinDistance(s, len_s - 1, t, len_t - 1) + cost);
}

return の直前のコメントは、文字列の末尾の文字を削って再帰することを説明しています。

以下の記事にはほぼ同じアルゴリズムがPythonで説明されています。末尾ではなく先頭を削って再帰している点が異なりますが、最終的には同じ結果が得られます。

@lru_cache(maxsize=4096)
def ld(s, t):
    if not s: return len(t)
    if not t: return len(s)
    if s[0] == t[0]: return ld(s[1:], t[1:])
    l1 = ld(s, t[1:])
    l2 = ld(s[1:], t)
    l3 = ld(s[1:], t[1:])
    return 1 + min(l1, l2, l3)

Wikipediaでは再帰は同じ計算を何度も繰り返すため非効率だとして動的計画法に進みますが、このコードは再帰のままデコレーターによりメモ化しています。前掲の記事ではデコレーターとメモ化について詳しく説明されているため、レーベンシュタイン距離に限らず参考になります。

Wagner–Fischer アルゴリズム

レーベンシュタイン距離を求めるための動的計画法によるアルゴリズムの名前です。

このアルゴリズムによるコードは日本語版のものと基本的に同じです。

          if s[i] = t[j]:
            substitutionCost := 0
          else:
            substitutionCost := 1

          d[i, j] := minimum(d[i-1, j] + 1,                   // deletion
                             d[i, j-1] + 1,                   // insertion
                             d[i-1, j-1] + substitutionCost)  // substitution

Wikipediaではコードの後に掲載されています。経路に下線が引かれていて、マウスポインタを載せると説明(deleteやinsert)が表示されます。その説明から i が縦(行)で j が横(列)に割り当てられていることが分かります。

2つ例が示されていますが、それぞれ次の組み合わせです。deletionやinsertionは s に対する操作で、最終的に t に変形されます。

  • s="sitting", t="kitten" (削除・置換)
  • s="Sunday", t="Saturday" (挿入・置換)

日本語版では縦横は明示されていませんでしたが、自分が理解する際に英語版とは縦横が逆の表を作ったことで混乱してしまいました。

また、Wikipediaでは日本語版と英語版ともに「kitten」を「sitting」に変形する例が示されています。表でも同じ向きの変形かと早合点して st を逆に捉えてしまったため、コードの解釈で混乱しました。

  • kitten → sitten (substitution of "s" for "k")
  • sitten → sittin (substitution of "i" for "e")
  • sittin → sitting (insertion of "g" at the end).

英単語

英語版には2つの例が載っていますが、1つの例で3つの操作(削除・挿入・置換)のうち2つしか使っていません。説明の便宜上1つの例で3つの操作を行いたかったため、sittingとkittenを変形して作ったのがbitingとwhitenです。

実在しない単語を使いたくなかったのですが、うまい組み合わせがすぐには思い浮かびませんでした。そのため正規表現で英単語を検索するサイトを利用しました。検索はサーバー側ではなく、圧縮した辞書データを読み込んだクライアント側が行っているようです。

パブリックドメインの英和辞書データを利用しているそうです。

参考

様々な言語によるレーベンシュタイン距離の実装が載っています。

7shi
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
No comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
ユーザーは見つかりませんでした