ハミング距離

ハミング距離

[1] ベクトル v = (v₁, v₂, ..., v_n), u = (u₁, u₂, ..., u_n) において要素が等しくない個数、すなわち d_H (u, v) = |{i | v_i ≠ u_i, 1 ≦ i ≦ n}| を v と u のハミング距離 (Humming distance) といいます。

定理

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

... を満たします。

[3] >>2 の証明

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

(3) u, v, w の要素 u_i, v_i, w_i (0 ≦ i ≦ n) がそれぞれ等しいかどうかで分類すると、

となる。ここで、

`u` と `v`	`v` と `w`	`w` と `u`	個数
`u_i = v_i`	`v_i = w_i`	`w_i = u_i`	`a₁`
`u_i = v_i`	`v_i ≠ w_i`	`w_i ≠ u_i`	`a₂`
`u_i ≠ v_i`	`v_i ≠ w_i`	`w_i = u_i`	`a₃`
`u_i ≠ v_i`	`v_i = w_i`	`w_i ≠ u_i`	`a₄`
`u_i ≠ v_i`	`v_i ≠ w_i`	`w_i ≠ u_i`	`a₅`

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

関連

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

メモ

[6] ハミング距離 - Wikipedia (2014-04-22 17:47:17 +09:00 版) http://ja.wikipedia.org/wiki/%E3%83%8F%E3%83%9F%E3%83%B3%E3%82%B0%E8%B7%9D%E9%9B%A2

ハミング距離