ハミング距離

ひと言で

同じ長さ の2つの文字列を比べて、異なっている位置の数。

karolin と kathrin を1文字ずつ並べると、違うのは3か所なのでハミング距離は 3。

位置	1	2	3	4	5	6	7
`karolin`	k	a	r	o	l	i	n
`kathrin`	k	a	t	h	r	i	n
一致?	○	○	×	×	×	○	○

なぜ使うか

ビット列の 誤り検出・誤り訂正（誤り訂正符号）
固定長データの比較（ハッシュ、ID、DNA配列など）
挿入や削除がないと分かっている場合の最速の比較

手で計算する

位置ごとに比較して、違った回数を数えるだけ。挿入・削除は考えない。

karolin
kathrin
^^ ^^^ ^
一致 不一致 一致

1011101
1001001
^^ ^ ^^^
  不一致は2か所

Ruby実装

def hamming(a, b)
  raise ArgumentError, "長さが違います (a=#{a.length}, b=#{b.length})" unless a.length == b.length

  a.chars.zip(b.chars).count { |x, y| x != y }
end

[
  ["karolin", "kathrin"],
  ["1011101", "1001001"],
  ["toned", "roses"],
  ["abc", "abc"]
].each do |a, b|
  puts "#{a.inspect} vs #{b.inspect} => #{hamming(a, b)}"
end

begin
  hamming("abc", "ab")
rescue ArgumentError => e
  puts "エラー: #{e.message}"
end

実行結果

"karolin" vs "kathrin" => 3
"1011101" vs "1001001" => 2
"toned" vs "roses" => 3
"abc" vs "abc" => 0
エラー: 長さが違います (a=3, b=2)

ポイント

長さが違う文字列には定義できない。実装では例外にして、呼び出し側で気付けるようにする。
String#chars と Array#zip を使えば、日本語でも1文字ずつ比較できる。
挿入・削除がある可能性があるなら、レーベンシュタイン距離を使う。

計算量と使いどころ

計算量: 時間 O(n)、メモリ O(1)（zip を使わなければ）
用途: 誤り訂正符号、固定長データの照合
挿入・削除を扱えないぶん、レーベンシュタイン距離より速く単純

前: ダメラウ・レーベンシュタイン距離

次: ジャロ距離