問題設定

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

手法

レーベンシュタイン距離

Levenshtein distance

定義

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

例

$s_1$：12346
$s_2$：233567

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

4と6の間に5を「挿入」→ 123456
先頭の1を「削除」→ 23456
4を3に「置換」→ 23356
末尾に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\]