takuti.me ABOUT

2017-07-28

いまさら編集距離 (Levenshtein Distance) を実装するぜ

ある文字列Aに対して『1文字の追加・削除・置換』を何回繰り返せば他の文字列Bになるか。このときの最小回数を、文字列A, B間の編集距離 (Levenshtein Distance)と呼ぶ。

  • 花火 から 火花 までの編集距離は各文字の置換なので 2
  • クワガタ から カブトムシ までの編集距離はなんかもう全文字違うので総入れ替え&文字『シ』の追加で 5

この編集距離、文字列の“類似度”と見ることができて、なかなか便利な子である。『Job Titleの前処理&クラスタリングをどうやって実現するか問題』では、人々の肩書きを編集距離を使って前処理(クラスタリング)している事例も紹介した。

さて、ここでは Levenshtein Distance を求めるアルゴリズムを実装して、備忘録として書き留めておく。ネット上にも多数の解説記事があり「今更ァ?」という話だが、正直どれを読んでもピンとこなかったのだ。

アルゴリズム

動的計画法 (DP) です。おわり。

Wikipedia に書かれている擬似コードをそのまま実装すると次のような感じ:

def levenshtein(s1, s2):
    """
    >>> levenshtein('kitten', 'sitting')
    3
    >>> levenshtein('あいうえお', 'あいうえお')
    0
    >>> levenshtein('あいうえお', 'かきくけこ')
    5
    """
    n, m = len(s1), len(s2)

    dp = [[0] * (m + 1) for _ in range(n + 1)]

    for i in range(n + 1):
        dp[i][0] = i

    for j in range(m + 1):
        dp[0][j] = j

    for i in range(1, n + 1):
        for j in range(1, m + 1):
            cost = 0 if s1[i - 1] == s2[j - 1] else 1
            dp[i][j] = min(dp[i - 1][j] + 1,         # insertion
                           dp[i][j - 1] + 1,         # deletion
                           dp[i - 1][j - 1] + cost)  # replacement

    return dp[n][m]

二次元配列 dp の中身は、たとえば levenshtein('kitten', 'sitting') を実行した後だと:

   |  -  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

理解

たとえば、この 4 は、文字列 ki から sitti までの編集距離を意味する:

   |  -  s  i  t  t  i  n  g
----------------------------
 - |                 .     
 k |                 .
 i |  .  .  .  .  .  4
 t |     
 t |    
 e |    
 n |

アルゴリズムでは、まず dp を次のように初期化する:

   |  -  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

空文字列から sitting のx文字目までの編集距離と、kittenのy文字目から空文字列までの編集距離。これは自明。

そして空白をうめていく。kkittenの一文字目)とssittingの一文字目)の編集距離、つまり X (= dp[i][j] ) の値はなにか:

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

最初に書いたとおり可能な操作は『1文字の追加・削除・置換』で、dp[i][j]に隣接する既知の編集距離から:

既知の編集距離(文字列A→B) 操作 (+1) 得られる編集距離
dp[i-1][j] '-'(空文字列)→ 's' 文字列 A '-' に 'k' を追加 ( → 's' ) 'k' → 's' dp[i][j]
dp[i][j] 'k' → 's' ( 'k' → ) 文字列 B 's' から 's' を削除 'k' → '-' dp[i][j-1]
dp[i-1][j-1] '-' → '-' 文字列 A の次の文字 'k' を 's' に置換 'k' → 's' dp[i][j]

つまり、

  • dp[i-1][j]dp[i][j] の差は追加操作1回分
  • dp[i][j]dp[i][j-1] の差は削除操作1回分
  • dp[i-1][j-1]dp[i][j] の差は置換操作1回分

とわかる。

ただし、置換操作は文字列 A と B の次の文字が既に一致していれば『何もしない』。すなわち、編集距離として dp[i-1][j-1]dp[i][j] は等しくなる。

以上が

cost = 0 if s1[i - 1] == s2[j - 1] else 1
dp[i][j] = min(dp[i - 1][j] + 1,         # insertion
               dp[i][j - 1] + 1,         # deletion
               dp[i - 1][j - 1] + cost)  # replacement/noop

でやっていること。編集距離は最小の操作回数なので追加・削除・置換の min をとる。

あとは同様に、隣接する既知の編集距離から表を埋めていけば、最後(右下)に kittensitting の編集距離が得られる。

   |  -  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

めでたしめでたし。

こういう応用範囲の広いシンプルなアルゴリズムは好きです。

PrestoHive にも近年実装されました。みなさん積極的に使いましょう。(とはいえ計算量 $\mathcal{O}(nm)$ は下手に CROSS JOIN とかすると重すぎて詰むので、過去に求めた編集距離はキャッシュしておくなど、ご利用は計画的に。)