文字列間の距離を測るレーベンシュタイン距離がシンプルで美しかった

#はじめに
文字列の類似度を測る指標としてレーベンシュタイン距離(英: Levenshtein distance)または編集距離(英: edit distance)と呼ばれるものがあるということは知っていたのですが，どういったアルゴリズムなのかということを勉強したことがありませんでした．
今回初めて使う機会があって真面目に勉強したので記事として残しておきます．

#レーベンシュタイン距離とは？(定義含む)
Wikipediaが結果的に一番わかりやすかったので(一部抜粋)

二つの文字列がどの程度異なっているかを示す距離の一種である。
具体的には、1文字の挿入・削除・置換によって、一方の文字列をもう一方の文字列に変形するのに必要な手順の最小回数として定義される。
レーベンシュタイン距離は、同じ文字数の単語に対する置換編集に使われているハミング距離の一般化であると見なすことが可能である。

と言っても文章のみで理解するのはどんなケースでも難しいと思いますので，具体的に見ていきましょう．

#具体例
こちらもWikipediaの例がわかりやすかったのでそのまま引用します．

「kitten」を「sitting」に変形する場合には、以下に示すように最低でも 3 回の手順が必要とされるので、2単語間のレーベンシュタイン距離は 3 となる。

1. 「kitten」
2. 「sitten」（「k」を「s」に置換）
3. 「sittin」（「e」を「i」に置換）
4. 「sitting」（「g」を挿入して終了）

「挿入」「削除」「置換」という3つの動作の組み合わせである文字列からもう一方と同じ文字列にできるか？ということをやるだけです．

#Pythonでの実装
メモ化のテーブルを作成する(動的計画法による)実装が一般的です．
そこの話はいろんなところにわかりやすい記事が転がってるので省略します．
擬似コードを参考にしながら実装しました．

leven_dist.py

def calc_leven_dist(s1, s2):
        dp_table = []
        distance = [0] * 3
        #文字列操作に対するコスト
        REPLACE_COST = 1
        INSERT_COST = 1
        DELETE_COST = 1

        #DPテーブルの初期化
        for i in range(len(s1) + 1):
            dp_table.append([0] * (len(s2) + 1))
            dp_table[i][0] = i
        for j in range(len(s2) + 1):
            dp_table[0][j] = j

        #DPテーブルを埋めていく(最後の値が文字列間の距離)
        for i in range(1, len(s1) + 1):
            for j in range(1, len(s2) + 1):
                distance[0] = dp_table[i-1][j] + INSERT_COST
                distance[1] = dp_table[i][j-1] + DELETE_COST
                distance[2] = dp_table[i-1][j-1] if s1[i-1] == s2[j-1] else dp_table[i-1][j-1] + REPLACE_COST
                dp_table[i][j] = min(distance)

        #デバッグ用表示
        print('{}と{}のDPテーブル'.format(s1, s2))
        print('------------------------------')
        for line in dp_table:
            print(' '.join(str(el) for el in line))
        print('------------------------------')

        return dp_table[i][j]


def main():
    s1 = 'kitten'
    s2 = 'sitting'
    dist = calc_leven_dist(s1, s2)
    print('{}と{}の距離は{}です．'.format(s1, s2, dist))


if __name__ == '__main__':
    main()

実行結果は以下のような感じです．

$ python3 test.py
kittenとsittingのDPテーブル
------------------------------
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
------------------------------
kittenとsittingの距離は3です．

ちゃんと右下の値が2つの文字列間(今回の場合は'kitten'⇨'sitting')の距離になっていそうです．

#DPテーブルの解釈
僕は最初この出力のテーブルを見たときにどう解釈するのかイマイチわからなかったので，それについても記録を残しておきます．

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

例えば上記のXの値を求める際にどうやって前に計算した値を使用するかという話ですが，以下のようになります．

• 「挿入」の場合
  dp_table[i-1][j]は''⇨'s'という操作のコストで，dp_table[i][j]は'k'⇨'s'のコストなので差分が挿入1回分の操作のコストになる．

• 「削除」の場合
  dp_table[i][j-1]は'k'⇨''という操作のコストで，dp_table[i][j]は'k'⇨'s'のコストなので差分が削除1回分の操作のコストになる．

• 「置換」の場合
  dp_table[i-1][j-1]は''⇨''という操作のコストで，dp_table[i][j]は'k'⇨'s'のコストなので差分が置換1回分の操作のコストになる．

ここら辺で解釈に間違いがあれば教えていただけると幸いです．

#感想
最近はニューラルブームであったり，様々なアルゴリズムがパッケージになっており(この距離を求めるPythonの関数も配布されていました)入力と出力の間のブラックボックス化が著しいですが，こういった感じで中身を理解して実装するのがやはり面白いなと思いました．
シンプルで汎用性の高いアルゴリズムを考える昔の人はとても頭がいいんだなと思いました．

#参考文献
レーベンシュタイン距離(Wikipedia)
いまさら編集距離 (Levenshtein Distance) を実装するぜ