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

ジャロ・ウィンクラー距離（ジャロ・ウィンクラーきょり、）とは2つの文字列の類似度の指標である。1989年にマシュー・A・ジャロによって提案されたジャロ距離の変種として1990年にウィリアム・E・ウィンクラーが提案したものである。ジャロ・ウィンクラー距離が小さいほど、2つの文字列は似ている。
ジャロ・ウィンクラー距離は、文字列の先頭部分（接頭辞）が一致している場合により類似度が高いと判別されるよう、ジャロ距離を変形したものである。ジャロ・ウィンクラー距離は、ジャロ距離を元に、（ある最大値を持つ）一致する接頭辞の長さ formula_1 と、ジャロ・ウィンクラー距離が 0 以上 1 以下の範囲で定義されるよう調整されたスケール因子 formula_2 を用いて計算される。
ジャロ・ウィンクラー距離 formula_3 は完全一致する文字列に対して 0、完全に異なる文字列に対して 1 となる。ただし原論文では距離ではなく類似度 formula_4 を定義しており、1 が完全一致、0 が完全不一致となるようになっている（すなわち formula_5）。
慣習的に「距離」と呼ばれるが、ジャロ・ウィンクラー距離は三角不等式を満たさないため数学的な意味での距離ではない。
定義.
ジャロ類似性.
文字列 "s"1 と "s"2 のジャロ類似性 "sim_j" は以下の式で表される。
ここで、
を表す。
一致する文字数は、単に "s"1 と "s"2 内で文字は共に含まれる文字ではなく、位置の差がformula_10文字以内に同じ文字がある文字の数である（同じ文字を何度も数えることはない）。
"s"1 の文字はそれぞれ "s"2 の文字と「一致」するか比較される。そして文字は「一致」しているが場所が入れ替わっている場合、それを「転置」と呼ぶ。
例えば CRATE と TRACE の2単語に対してジャロ類似性を計算すると、まず R, A, E の3文字は文字も位置も一致しているため、"m" = 3 である。C と T は "s"1 にも "s"2 にも含まれているが、位置の差が3であり、formula_11より大きいため「一致」する文字とはみなさない。また「一致」していないため位置は入れ替わっているが転置としても数えず "t" = 0である。
したがってジャロ類似性は1/3 * (3/5 + 3/5 + 3/3) = 11/15 である。
上記のように重みは全てformula_12とされることが多いが、
のように、異なる重みを与える場合もある。
ジャロ・ウィンクラー類似性.
ジャロ・ウィンクラー類似性はプレフィックススケール "p" を用いる。これにより、文字列の先頭が一致する文字列により高い類似度を与える。2つの文字列 "s"1 と "s"2 に対するジャロ・ウィンクラー類似性 "sim_w" は以下の式で表される。
ここで
を表す。
また同様にジャロ・ウィンクラー距離 formula_3 は formula_20と定義されている。
ジャロ・ウィンクラー距離は三角不等式を満たさないため距離函数ではないどころか、同一律 formula_21 さえ満たさないことがあり得る。
他の編集距離との関係.
多くの編集距離は、文字列 "s"1 を "s"2 へ変換するために必要な編集の数を用い、それぞれの編集距離において可能な編集操作が異なる。例えば可能な編集操作には以下の物がある。
編集距離は可能な編集操作を用いて計算され、パラメーター化可能な距離函数として定義されている。また各操作にはコスト（場合によっては無限）が割り当てられ、その総和が距離となる。またより一般化された例としてDNAのシーケンスアラインメントに用いられるスミス・ウォーターマンアルゴリズムがあり、このアルゴリズムでは編集操作の種別だけでなく、編集操作が適用される場所によってコストが異なる。