問題設定

2つの文字列 $s_1$ と $s_2$ の類似度を評価したい

手法

レーベンシュタイン距離

Levenshtein distance

定義

編集操作 =「1文字を挿入 or 削除 or 置換する」を何度か行うことで、一方の文字列をもう一方の文字列に変形しようとしたとき、必要な操作の最小回数

  • $s_1$:12346
  • $s_2$:233567

のとき、$s_1$ を操作して $s_2$ に一致させる最小工程は

  1. 4と6の間に5を「挿入」→ 123456
  2. 先頭の1を「削除」→ 23456
  3. 4を3に「置換」→ 23356
  4. 末尾に7を「挿入」→ 233567(完了)

よって、$s_1$ と $s_2$ のレーベンシュタイン距離は4。

ジャロ・ウィンクラー距離

Jaro–Winkler distance

定義

1. $c$ の計算

文字列 $s_1$, $s_2$ の長さを $ s_1 $, $ s_2 $ として、$n$ を以下の式で定義する。
\[n = \cfrac{\max{(|s_1|, |s_2|)}}{2} - 1\]

次にカウンター $c$ をゼロで初期化し、$s_1$ の文字列を最初から順に見ていく。 $s_1$ のすべての文字について、$s_1$ の $k$ 番目の文字が $s_2$ の $k \pm n$ 番目よりも近くに存在すればカウンター $c$ の値を1増やす。

2. $\tau$ の計算

文字列 $s_1, s_2$ に共通する文字を順序を変えずに抜き出した部分文字列 $s_1’, s_2’$ を作る。 次に $\tau$ をゼロで初期化し、$s_1’, s_2’$ の同じ位置の文字を比較していく。 文字が一致すれば $\tau$ の値を $\cfrac{1}{2}$ 増やす。

3. ジャロ類似度の計算

ジャロ類似度 $sim_j$ を以下の式で定義:

\[sim_j = W_1 \cfrac{c}{|s_1|} + W_2 \cfrac{c}{|s_2|} + W_3 \cfrac{c-\tau}{c}\]

$W_1, W_2, W_3$ は重みで、すべて$\cfrac{1}{3}$ に設定するのが一般的。

  • $W_1$:1つ目の文字列にかける重み
  • $W_2$:2つ目の文字列にかける重み
  • $W_3$:置換にかける重み

4. ジャロ・ウィンクラー距離の計算

「スペルミスをする際、先頭の文字を間違えることは少ないはず」という考えから、ジャロ類似度に対して「先頭部分が一致したボーナス」を追加したジャロ・ウィンクラー類似度 $sim_w$ を計算:

\[sim_w = sim_j + lp (1 - sim_j)\]
  • $l$:$s_1, s_2$ の先頭何文字が一致するか(上限は4)
  • $p$:定数。一般的に $p = 0.1$ に設定する

これを1から引いたものをジャロ・ウィンクラー距離 $d_w$ と定義する。

\[d_w = 1 - sim_w\]

  • $s_1$:12346
  • $s_2$:203167

のとき、

\[n = \cfrac{\max{(5, 7)}}{2} - 1 = 2.5\]

次にカウンタ $c$ について、

  • $s_1$ の1番目の文字「1」:カウントしない
    • $s_2$ の4番目の文字と一致するが、差が $4-1=3$ で $n$ 文字以上に遠い
  • $s_1$ の2番目の文字「2」:カウントする
    • $s_2$ の1番目の文字と一致し、差は $2-1=1$ で $n$ 文字よりも近い
  • $s_1$ の3番目の文字「3」:カウントする
    • $s_2$ の3番目の文字と一致し、差は $3-3=0$ で $n$ 文字よりも近い
  • $s_1$ の4番目の文字「4」:カウントしない
    • $s_2$ のどの文字とも一致しない
  • $s_1$ の5番目の文字「6」:カウントする
    • $s_2$ の5番目の文字と一致し、差は $5-5=0$ で $n$ 文字よりも近い

なので、

\[c = 3\]

また、$s_1, s_2$ のうち一致する文字からなる部分文字列 $s_1’, s_2’$ は

  • $s_1’$:1236
  • $s_2’$:2316

となるため、

  • $s’_1$ の1番目の文字 $\neq$ $s_2’$ の1番目の文字
  • $s’_1$ の2番目の文字 $\neq$ $s_2’$ の2番目の文字
  • $s’_1$ の3番目の文字 $\neq$ $s_2’$ の3番目の文字
  • $s’_1$ の4番目の文字 $=$ $s_2’$ の4番目の文字

より \(\tau = \cfrac{1}{2} = 0.5\)

したがって、ジャロ類似度およびジャロ・ウィンクラー距離は

\[sim_j = \cfrac{1}{3} \left( \cfrac{3}{5} + \cfrac{3}{6} + \cfrac{3-0.5}{3} \right) = \cfrac{29}{45} = 0.644\] \[d_w = 1 - sim_j = \cfrac{16}{45} = 0.356\]