CATEGORY: STRING

ジャロ距離

ひと言で

2つの文字列の 「一致した文字」と「その並び順のズレ」 から求める 0〜1 の類似度。

同じ文字列なら 1.0
共通の文字がなければ 0.0
大きいほど似ている

MARTHA と MARHTA のジャロ距離は 0.9444。T と H の順番が違うだけなので、かなり高い値になる。

なぜ使うか

人名・地名などの短い文字列の照合（名寄せ）
編集距離と違い、長さの違いに寛容で、文字の順序のズレを評価できる
ジャロ・ウィンクラー類似度の土台になる

手で計算する

次の3ステップで求める。

一致窓 を決める
```
一致窓 = floor(max(|s1|, |s2|) / 2) - 1
```
MARTHA と MARHTA はどちらも6文字なので、窓は 6/2 - 1 = 2。

窓内で一致する文字 を数える（m）。同じ文字を二重に数えないよう、使った文字に印を付ける。

s1 の文字	一致した s2 の文字
M	M
A	A
R	R
T	T
H	H
A	A

m = 6。

転置数（並び順のズレ）を求める。一致した s1 の並び M A R T H A と、一致した s2 の並び（位置順）M A R H T A を頭から比べ、食い違う個数を2で割る。
```
M A R T H A
M A R H T A
      ^ ^      → 食い違い2個 → t = 2 / 2 = 1
```

最後に式へ入れる。

J = ( m/|s1| + m/|s2| + (m - t)/m ) / 3
  = ( 6/6   + 6/6    + (6 - 1)/6 ) / 3
  = ( 1     + 1      + 0.8333    ) / 3
  = 0.9444

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

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

実行結果

"MARTHA" vs "MARHTA" => 0.9444
"DWAYNE" vs "DUANE" => 0.8222
"DIXON" vs "DICKSONX" => 0.7667
"abc" vs "abc" => 1.0000
"abc" vs "xyz" => 0.0000
"こんにちは" vs "こんばんは" => 0.7333

ポイント

m（一致文字数）が 0 のときは 0.0 を返す。0 で割らないためのガード。
一致窓があるので、離れた位置の同じ文字は数えない。
長さが違っても計算できるのが編集距離との大きな違い。
先頭の一致を重視したい場合はジャロ・ウィンクラー類似度を使う。

計算量と使いどころ

計算量: 時間 O(mn)（実際は窓の幅ぶんだけなので O(nw)、w は窓の幅）
用途: 人名・住所の名寄せ、短い文字列の照合
転置を評価できるので、文字の入れ替わりに強い

前: ハミング距離

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