単語同士の類似度評価手法「レーベンシュタイン距離」を理解する

# はじめに

私は現在、弊社セレスの社内システムの開発を担当しています。

システムを開発するにあたり、入力値と登録済みの文字列の類似度をチェックする処理を実装することになりました。
どうやって文字列の類似度を測ればよいのか調べていたところ、**レーベンシュタイン距離**というものが多くヒットしましたので、ほぼ何も考えずにこれを採用しました。
当時は時間もあまり取れなかったので理解に時間を割こうとせず、実際のコードもほぼ他サイトからのコピペで済ませていました。

しかし、「よく分からないレーベンシュタイン距離というもの」を理解しないままというのは自分の中で気持ち悪いですし、のちのち「なぜか知らないけどレーベンシュタイン距離を使えば文字列の類似度が測れる」というのだけが伝わって[カーゴ・カルト・プログラミング](https://ja.wikipedia.org/wiki/%E3%82%AB%E3%83%BC%E3%82%B4%E3%83%BB%E3%82%AB%E3%83%AB%E3%83%88%E3%83%BB%E3%83%97%E3%83%AD%E3%82%B0%E3%83%A9%E3%83%9F%E3%83%B3%E3%82%B0)と化したらまずいと思いましたので、この機に理解に努めようと思ったのが、当記事を書いたきっかけです。

# 本記事の目標

**レーベンシュタイン距離のアルゴリズムを理解し、かつ実装に落とし込めるようにする！**

図でなんとなく理解したつもりにならないようにするため、具体的なコードを挟んで淡々と説明をしています。内容はやや難しいですが、ご容赦頂ければと思います。

# レーベンシュタイン距離とは？

レーベンシュタイン距離(Levenshtein Distance)は、**1文字の挿入・削除・置換によって、一方の文字列をもう一方の文字列に変形するのに必要な手順の最小回数**と定義されているそうです。

例えば、`kitten`と`sitting`の間のレーベンシュタイン距離は、`kitten`から`sitting`への変形において、2文字置換（**k** itten → **s** itt **e** n → sitt **i** n）、1文字挿入（sittin → sittin **g**）の3手順が必要になるので、レーベンシュタイン距離は**3**となります。

# アルゴリズム

レーベンシュタイン距離の計算には、**動的計画法**によるアルゴリズムが用いられているそうです。
動的計画法って何？って思ったんですが、ここではフィボナッチ数列のように帰納的に求めるやり方のことを言っているという理解で良いと思います。高校数学でいう漸化式とか、あのあたりの考え方です。

レーベンシュタイン距離の場合、以下の2点から任意の文字列間のレーベンシュタイン距離を求めることができます。

* 長さ0の文字列と長さLの文字列のレーベンシュタイン距離は、**L**（これは**空文字にL文字挿入した**、と考えればすぐ分かると思います）
* 1文字削った文字列の末尾にどのような文字を追加すれば一致するか見ることで、1文字削った文字列との距離から1文字加えた文字列との距離を求めることができる（？？？？？？）

2点目が何を言っているのか分からないので、実際にアルゴリズムを組むとどうなるのか見ていきましょう。

## 実際にアルゴリズムを組んでみる

文字列`s1`の長さを`s1_len`、文字列`s2`の長さを`s2_len`として、以下のような(`s1_len`+1)×(`s2_len`+1)の行列を作ります。
ここでは例として、`s1 = "kitten"`、`s2 = "sitting"`とします。なお`-`は空文字を意味します。

```
   | - s i t t i n g
---------------------
 - |
 k |
 i |
 t |
 t |
 e |
 n |
```

この行列を`m`、レーベンシュタイン距離の関数を`levenshtein(s1, s2)`とした場合、行列の各要素に以下の通り値を代入していきます。

```python
m[i][j] = levenshtein(s1[0:i+1], s2[0:j+1]) # s[0:k+1]は文字列sの0番目からk番目までを表します
```

つまり`m[i][j]`には、`s1`の`i`番目までの文字列と`s2`の`j`番目までの文字列間のレーベンシュタイン距離が入ります。

最終的に求めたいのは、`s1`の`0`番目から`s1_len`番目までの文字列（=`s1`）と`s2`の`0`番目から`s2_len`番目までの文字列（=`s2`）間のレーベンシュタイン距離であり、`m[s1_len][s2_len]`（行列の一番右下）に入る値です。

### 片方の文字列の長さが0の場合

これは上でも示したとおり、レーベンシュタイン距離はもう片方の文字列の長さをそのまま採用すれば良いです。
ですので、以下のようになります。

```python
m[0][j] = j
m[i][0] = i
```

初期化結果は以下の通りです。

```
   | - s i t t i n g
---------------------
 - | 0 1 2 3 4 5 6 7
 k | 1
 i | 2
 t | 3
 t | 4
 e | 5
 n | 6
```

### 行列の残りの要素を入れていく

あとは既知のレーベンシュタイン距離を使って他のパターンのレーベンシュタイン距離を順々に求めていきます。

候補値の求め方として3パターンあり、その3パターンの中で最小の値を新たなレーベンシュタイン距離として採用することになります。

1. `m[i-1][j]`から`m[i][j]`の候補値を求める
`s1`への1文字分の挿入となりますので、`m[i][j]`の候補値は`m[i-1][j] + 1`となります。

2. `m[i][j-1]`から`m[i][j]`の候補値を求める
`s2`への1文字分の挿入となりますので、`m[i][j]`の候補値は`m[i][j-1] + 1`となります。

3. `m[i-1][j-1]`から`m[i][j]`の候補値を求める
2文字列の長さの差は変化していませんので、`m[i-1][j-1]`から挿入手順や削除手順は増えません。新たに加わった末尾の文字が同じであれば`0`を、異なるのであれば置換が1手順発生したと考えて`1`を`m[i-1][j-1]`に足した値が`m[i][j]`の候補値となります。

以上をもとに、まずは`m[1][1]`（`k`と`s`のレーベンシュタイン距離）を求めてみましょう。

1. `m[0][1]`から`m[1][1]`の候補値を求める
`m[0][1]`は`1`ですので、`m[1][1]`の候補値は`1 + 1 = 2`となります。

2. `m[1][0]`から`m[1][1]`の候補値を求める
`m[1][0]`は`1`ですので、`m[1][1]`の候補値は`1 + 1 = 2`となります。

3. `m[0][0]`から`m[1][1]`の候補値を求める
`m[0][0]`は`0`です。末尾に追加された文字はそれぞれ`k`と`s`であり、文字が異なりますので、`1`を足す必要があります。よって`m[1][1]`の候補値は`0 + 1 = 1`となります。

`m[1][1]`の候補値が`2`、`2`、`1`ですので、この中の最小値`1`が`m[1][1]`の値となります。

```
   | - s i t t i n g
---------------------
 - | 0 1 2 3 4 5 6 7
 k | 1 1
 i | 2
 t | 3
 t | 4
 e | 5
 n | 6
```

同じようにして残りの要素を求めていくと、以下のようになります。

```
   | - s i t t i n g
---------------------
 - | 0 1 2 3 4 5 6 7
 k | 1 1 2 3 4 5 6 7
 i | 2 2 1 2 3 4 5 6
 t | 3 3 2 1 2 3 4 5
 t | 4 4 3 2 1 2 3 4
 e | 5 5 4 3 2 2 3 4
 n | 6 6 5 4 3 3 2 3
```

右下の値が`3`となりましたので、`kitten`と`sitting`のレーベンシュタイン距離は`3`ということになります。

# コードを書いてみる

以上の理解をもとに、Pythonでレーベンシュタイン距離を求めるプログラムを書いてみました。

```python:levenshtein.py
#!/usr/bin/env python
# -*- coding: utf-8 -*-

import sys

def levenshtein(s1, s2):
	# s1とs2が同じであれば、0であることは明らか
	if s1 == s2:
		return 0

	# 文字列の長さを取得
	s1_len = len(s1)
	s2_len = len(s2)

	# 空文字列からs2への文字挿入回数 = s2の長さ
	if s1_len == 0:
		return s2_len
	# 空文字列からs1への文字挿入回数 = s1の長さ
	if s2_len == 0:
		return s1_len

	# 行列の初期化
	m = [[j for j in range(s2_len+1)] if i==0 else [i if j==0 else 0 for j in range(s2_len+1)] for i in range(s1_len+1)]

	# m[i-1][j]、m[i][j-1]、m[i-1][j-1]を使ってm[i][j]を求める
	for i in range(1, s1_len+1):
		for j in range(1, s2_len+1):
			# m[i-1][j]から求める
			c1 = m[i-1][j] + 1
			# m[i][j-1]から求める
			c2 = m[i][j-1] + 1
			# m[i-1][j-1]から求める
			c3 = m[i-1][j-1] + (0 if s1[i-1]==s2[j-1] else 1)
			# 最小値を採用
			m[i][j] = min(c1, c2, c3)

	# 行列の中身を表示（コメントを外す）
	# print(m)

	# 行列の右下の値がs1とs2のレーベンシュタイン距離
	return m[s1_len][s2_len]

if __name__ == '__main__':
	args = sys.argv
	if len(args) < 3:
		sys.exit(1)
	print(levenshtein(args[1], args[2]))
```

実行結果は以下の通りとなります。

```console
$ ./levenshtein.py kitten sitting
3
```

行列の中の表示部分のコメントを外すと、以下のようになります。

```console
$ ./levenshtein.py kitten sitting
[[0, 1, 2, 3, 4, 5, 6, 7], [1, 1, 2, 3, 4, 5, 6, 7], [2, 2, 1, 2, 3, 4, 5, 6], [3, 3, 2, 1, 2, 3, 4, 5], [4, 4, 3, 2, 1, 2, 3, 4], [5, 5, 4, 3, 2, 2, 3, 4], [6, 6, 5, 4, 3, 3, 2, 3]]
3
```

出力内容がアルゴリズムの説明で用いた行列の中身と一致していますので、きちんとプログラムで出来ていそうです。

# おわりに

アルゴリズムの理解には少し苦しみましたが、実際に手を動かしながらアルゴリズムを追っていくことで、時間はかかったもののようやく理解できました。

今回アルゴリズムを理解する過程で行列に値を埋めていく作業を行いましたが、けっこう頭の体操になりますね（笑）
ですが毎回毎回行列埋めをやっていくのは大変ですし、こういったところはプログラム化してコンピュータに任せてしまうのが一番ですね！

# 参考

アルゴリズムの理解にあたり、以下のサイトが大変参考になりました。ありがとうございます。

* [いまさら編集距離 (Levenshtein Distance) を実装するぜ | takuti.me](https://takuti.me/note/levenshtein-distance/)