ハミング距離

ハミング距離

[1] ベクトル v = (v1, v2, ..., vn), u = (u1, u2, ..., un) において要素が等しくない個数、すなわち dH (u, v) = |{i | viui, 1 ≦ in}|vuハミング距離 (Humming distance) といいます。

[2] 定理: ハミング距離は距離の公理

  1. dH (u, v) ≧ 0 であり、等号成立は v = u の時に限る。
  2. dH (u, v) = dH (v, u) (交換法則)
  3. dH (u, v) + dH (v, w) ≧ dH (u, w) (三角不等式)

を満たします。

[3] >>2 の証明

(1), (2) >>1 の定義より明らかである。

(3) u, v, w要素 ui, vi, wi (0 ≦ in) がそれぞれ等しいかどうかで分類すると、

となる。ここで、

uvvwwu個数
ui = vivi = wiwi = uia1
ui = viviwiwiuia2
uiviviwiwi = uia3
uivivi = wiwiuia4
uiviviwiwiuia5

であるから、三角不等式が成立することがわかる。

関連

[7] ハミング距離に関連するもの