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

ジャロ・ウィンクラー距離（ジャロ・ウィンクラーきょり、英: Jaro–Winkler distance）とは2つの文字列の類似度の指標である。1989年にマシュー・A・ジャロによって提案されたジャロ距離の変種として1990年にウィリアム・E・ウィンクラーが提案したものである。ジャロ・ウィンクラー距離が小さいほど、2つの文字列は似ている。

ジャロ・ウィンクラー距離は、文字列の先頭部分（接頭辞）が一致している場合により類似度が高いと判別されるよう、ジャロ距離を変形したものである。ジャロ・ウィンクラー距離は、ジャロ距離を元に、（ある最大値を持つ）一致する接頭辞の長さ $l$ と、ジャロ・ウィンクラー距離が 0 以上 1 以下の範囲で定義されるよう調整されたスケール因子 $p$ を用いて計算される。

ジャロ・ウィンクラー距離 $d_{w}$ は完全一致する文字列に対して 0、完全に異なる文字列に対して 1 となる。ただし原論文では距離ではなく類似度 $\operatorname {sim} _{w}$ を定義しており、1 が完全一致、0 が完全不一致となるようになっている（すなわち $\operatorname {sim} _{w}=1-d_{w}$ ）。

慣習的に「距離」と呼ばれるが、ジャロ・ウィンクラー距離は三角不等式を満たさないため数学的な意味での距離ではない。

定義

ジャロ類似性

文字列 s1 と s2 のジャロ類似性 sim_j は以下の式で表される。

sim_{j}=\left\{{\begin{array}{l l}0&{\text{if }}m=0\\{\frac {1}{3}}\left({\frac {m}{|s_{1}|}}+{\frac {m}{|s_{2}|}}+{\frac {m-t}{m}}\right)&{\text{otherwise}}\end{array}}\right.

ここで、

$|s_{i}|$ は文字列の長さ
$m$ は近くで一致する文字数（以下を参照）
$t$ は転置の数（以下を参照）

を表す。

一致する文字数は、単に s1 と s2 内で文字は共に含まれる文字ではなく、位置の差が $\left\lfloor {\frac {\max(|s_{1}|,|s_{2}|)}{2}}\right\rfloor -1$ 文字以内に同じ文字がある文字の数である（同じ文字を何度も数えることはない）。

s1 の文字はそれぞれ s2 の文字と「一致」するか比較される。そして文字は「一致」しているが場所が入れ替わっている場合、それを「転置」と呼ぶ。

例えば CRATE と TRACE の2単語に対してジャロ類似性を計算すると、まず R, A, E の3文字は文字も位置も一致しているため、m = 3 である。C と T は s1 にも s2 にも含まれているが、位置の差が3であり、 $\lfloor {\tfrac {5}{2}}\rfloor -1=1$ より大きいため「一致」する文字とはみなさない。また「一致」していないため位置は入れ替わっているが転置としても数えず t = 0である。

したがってジャロ類似性は1/3 * (3/5 + 3/5 + 3/3) = 11/15 である。

上記のように重みは全て ${\frac {1}{3}}$ とされることが多いが、

sim_{j}=\left\{{\begin{array}{l l}0&{\text{if }}m=0\\W_{1}{\frac {m}{|s_{1}|}}+W_{2}{\frac {m}{|s_{2}|}}+W_{3}{\frac {m-t}{m}}&{\text{otherwise}}\end{array}}\right.

のように、異なる重みを与える場合もある。

ジャロ・ウィンクラー類似性

ジャロ・ウィンクラー類似性はプレフィックススケール p を用いる。これにより、文字列の先頭が一致する文字列により高い類似度を与える。2つの文字列 s1 と s2 に対するジャロ・ウィンクラー類似性 sim_w は以下の式で表される。

sim_{w}=sim_{j}+\ell p(1-sim_{j})

ここで

$sim_{j}$ は s1 と s2 のジャロ類似性
$\ell$ は文字列の先頭の共通する文字の長さ（ただし5文字以上一致した場合は4とする）
$p$ は先頭で一致する文字による類似度の上方修正の強さ（ただし p は0.25以下。ウィンクラーによれば、 $p=0.1$ が標準。）

を表す。

また同様にジャロ・ウィンクラー距離 $d_{w}$ は $d_{w}=1-sim_{w}$ と定義されている。

ジャロ・ウィンクラー距離は三角不等式を満たさない^[1]ため距離函数ではないどころか、同一律 $d(x,y)=0\leftrightarrow x=y$ さえ満たさないことがあり得る。

他の編集距離との関係

多くの編集距離は、文字列 s1 を s2 へ変換するために必要な編集の数を用い、それぞれの編集距離において可能な編集操作が異なる。例えば可能な編集操作には以下の物がある。

レーベンシュタイン距離：削除、挿入、置換
ダメラウ・レーベンシュタイン距離：2文字の隣接する文字の挿入、削除、置換、転置
最長共通部分列（LCS）距離：挿入、削除
ハミング距離：置換（同じ長さの文字列にのみ定義される）

編集距離は可能な編集操作を用いて計算され、パラメーター化可能な距離函数として定義されている。また各操作にはコスト（場合によっては無限）が割り当てられ、その総和が距離となる。またより一般化された例としてDNAのシーケンスアラインメントに用いられるスミス・ウォーターマンアルゴリズムがあり、このアルゴリズムでは編集操作の種別だけでなく、編集操作が適用される場所によってコストが異なる。

脚注

^ “Jaro-Winkler « Inviting Epiphany”. RichardMinerich.com. 12 June 2017閲覧。

参考文献

Cohen, W. W.; Ravikumar, P.; Fienberg, S. E. (2003). “A comparison of string distance metrics for name-matching tasks”. KDD Workshop on Data Cleaning and Object Consolidation 3: 73–8.
Jaro, M. A. (1989). “Advances in record linkage methodology as applied to the 1985 census of Tampa Florida”. Journal of the American Statistical Association 84 (406): 414–20. doi:10.1080/01621459.1989.10478785.
Jaro, M. A. (1995). “Probabilistic linkage of large public health data file”. Statistics in Medicine 14 (5–7): 491–8. doi:10.1002/sim.4780140510. PMID 7792443.
Winkler, W. E. (1990). “String Comparator Metrics and Enhanced Decision Rules in the Fellegi-Sunter Model of Record Linkage”. Proceedings of the Section on Survey Research Methods (American Statistical Association): 354–359.

Winkler, W. E. (2006). “Overview of Record Linkage and Current Research Directions”. Research Report Series, RRS.

外部リンク

strcmp.c-アルゴリズムの作成者による元のC実装

[1] “Jaro-Winkler « Inviting Epiphany”. RichardMinerich.com. 12 June 2017閲覧。

[1]