はじめに
私は現在、弊社セレスの社内システムの開発を担当しています。
システムを開発するにあたり、入力値と登録済みの文字列の類似度をチェックする処理を実装することになりました。
どうやって文字列の類似度を測ればよいのか調べていたところ、レーベンシュタイン距離というものが多くヒットしましたので、ほぼ何も考えずにこれを採用しました。
当時は時間もあまり取れなかったので理解に時間を割こうとせず、実際のコードもほぼ他サイトからのコピペで済ませていました。
しかし、「よく分からないレーベンシュタイン距離というもの」を理解しないままというのは自分の中で気持ち悪いですし、のちのち「なぜか知らないけどレーベンシュタイン距離を使えば文字列の類似度が測れる」というのだけが伝わってカーゴ・カルト・プログラミングと化したらまずいと思いましたので、この機に理解に努めようと思ったのが、当記事を書いたきっかけです。
本記事の目標
レーベンシュタイン距離のアルゴリズムを理解し、かつ実装に落とし込めるようにする！
図でなんとなく理解したつもりにならないようにするため、具体的なコードを挟んで淡々と説明をしています。内容はやや難しいですが、ご容赦頂ければと思います。
レーベンシュタイン距離とは？
レーベンシュタイン距離(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)とした場合、行列の各要素に以下の通り値を代入していきます。
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の場合
これは上でも示したとおり、レーベンシュタイン距離はもう片方の文字列の長さをそのまま採用すれば良いです。
ですので、以下のようになります。
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パターンの中で最小の値を新たなレーベンシュタイン距離として採用することになります。
m[i-1][j]からm[i][j]の候補値を求める
s1への1文字分の挿入となりますので、m[i][j]の候補値はm[i-1][j] + 1となります。m[i][j-1]からm[i][j]の候補値を求める
s2への1文字分の挿入となりますので、m[i][j]の候補値はm[i][j-1] + 1となります。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のレーベンシュタイン距離）を求めてみましょう。
m[0][1]からm[1][1]の候補値を求める
m[0][1]は1ですので、m[1][1]の候補値は1 + 1 = 2となります。m[1][0]からm[1][1]の候補値を求める
m[1][0]は1ですので、m[1][1]の候補値は1 + 1 = 2となります。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でレーベンシュタイン距離を求めるプログラムを書いてみました。
#!/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]))
実行結果は以下の通りとなります。
$ ./levenshtein.py kitten sitting
3
行列の中の表示部分のコメントを外すと、以下のようになります。
$ ./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
出力内容がアルゴリズムの説明で用いた行列の中身と一致していますので、きちんとプログラムで出来ていそうです。
おわりに
アルゴリズムの理解には少し苦しみましたが、実際に手を動かしながらアルゴリズムを追っていくことで、時間はかかったもののようやく理解できました。
今回アルゴリズムを理解する過程で行列に値を埋めていく作業を行いましたが、けっこう頭の体操になりますね（笑）
ですが毎回毎回行列埋めをやっていくのは大変ですし、こういったところはプログラム化してコンピュータに任せてしまうのが一番ですね！
参考
アルゴリズムの理解にあたり、以下のサイトが大変参考になりました。ありがとうございます。