CATEGORY: STRING

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

ひと言で

ジャロ距離に 「先頭が何文字一致しているか」のボーナス を加えた 0〜1 の類似度。

先頭が一致する文字列ほど高い値になり、人名や住所の名寄せに向く。

MARTHA と MARHTA は先頭 MAR が一致するので、ジャロ距離 0.9444 から 0.9611 に上がる。

なぜ使うか

人名・組織名・住所の照合。先頭が一致する ことは強い手がかりになる
MARTHA と MARHTA のように、途中で入れ替わっても先頭が同じなら高く評価したい
スペルミスの候補提示

手で計算する

まずジャロ距離 J を求める（ここでは MARTHA / MARHTA の J = 0.9444）。

次に 共通の接頭辞の長さ l を数える。ただし 最大4文字 まで。

MARTHA
MARHTA
^^^         → 共通接頭辞は "MAR" → l = 3

あとは式に入れる。p はボーナスの強さ（既定は 0.1）。

JW = J + l * p * (1 - J)
   = 0.9444 + 3 * 0.1 * (1 - 0.9444)
   = 0.9444 + 0.0167
   = 0.9611

Ruby実装

def jaro(a, b)
  return 1.0 if a == b
  return 0.0 if a.empty? || b.empty?

  s1 = a.chars
  s2 = b.chars
  len1 = s1.length
  len2 = s2.length
  window = [0, [len1, len2].max / 2 - 1].max
  match1 = Array.new(len1, false)
  match2 = Array.new(len2, false)
  matches = 0

  (0...len1).each do |i|
    lo = [0, i - window].max
    hi = [len2 - 1, i + window].min
    (lo..hi).each do |j|
      next if match2[j] || s1[i] != s2[j]

      match1[i] = true
      match2[j] = true
      matches += 1
      break
    end
  end
  return 0.0 if matches.zero?

  t = 0
  k = 0
  (0...len1).each do |i|
    next unless match1[i]

    k += 1 until match2[k]
    t += 1 if s1[i] != s2[k]
    k += 1
  end

  m = matches.to_f
  ((m / len1) + (m / len2) + ((m - (t / 2.0)) / m)) / 3.0
end

def jaro_winkler(a, b, scaling = 0.1)
  j = jaro(a, b)

  # 共通する接頭辞の長さ（最大4文字）
  prefix = 0
  [a.length, b.length, 4].min.times do |i|
    break unless a[i] == b[i]

    prefix += 1
  end

  j + prefix * scaling * (1 - j)
end

[
  ["MARTHA", "MARHTA"],
  ["DWAYNE", "DUANE"],
  ["DIXON", "DICKSONX"],
  ["こんにちは", "こんばんは"]
].each do |a, b|
  puts "#{a.inspect} vs #{b.inspect} => JW=#{format('%.4f', jaro_winkler(a, b))}, J=#{format('%.4f', jaro(a, b))}"
end

実行結果

"MARTHA" vs "MARHTA" => JW=0.9611, J=0.9444
"DWAYNE" vs "DUANE" => JW=0.8400, J=0.8222
"DIXON" vs "DICKSONX" => JW=0.8133, J=0.7667
"こんにちは" vs "こんばんは" => JW=0.7867, J=0.7333

ポイント

接頭辞の長さ l は 4で頭打ち。先頭が長く一致してもボーナスは増え続けない。
p（scaling）を大きくすると、先頭一致の影響が強くなる。通常は 0.1 のまま。
ジャロ距離が 0 のときはボーナスも効かない（JW = 0）。
編集距離と違い、値は必ず 0〜1 に収まるので閾値を決めやすい。

計算量と使いどころ

計算量: ジャロ距離と同じ O(mn)、接頭辞の計算は O(1)（最大4文字）
用途: 人名・住所の名寄せ、レコードリンケージ
先頭を重視したい照合の定番手法

前: ジャロ距離

次: 正規化編集距離