ハミング距離 【Hamming distance】

概要

ハミング距離（Hamming distance）とは、同じ長さの符号列(ビット列や文字列など)を比較して、同じ位置の符号が異なっている箇所の数。

同じ長さの二つの符号列について、先頭から順に同じ位置同士を比較していったとき、内容が食い違っている符号の数を表す。片方の符号列をもう一方に変形するのに必要な置き換え回数と理解することができる。

例えば、ビット列で考える場合、「01010101」と「01110111」では同じ位置で値が一致しているビットが6つ、異なっているビットが2つであるため、ハミング距離は2となる。ビットに限らず任意の符号列で考えることができ、文字列 “confirm” と “comfort” であれば不一致は3文字であるためハミング距離は3である。

ちなみに、「ハミング」はハミング符号などで知られるアメリカの数学者リチャード・ハミング（Richard W. Hamming）にちなんだもので、鼻歌の “humming” とは異なる。“Hamming” と “Humming” のハミング距離は1である。

この記事の著者 ： (株)インセプト IT用語辞典 e-Words 編集部
1997年8月より「IT用語辞典 e-Words」を執筆・編集しています。累計公開記事数は1万ページ以上、累計サイト訪問者数は1億人以上です。学術論文や官公庁の資料などへも多数の記事が引用・参照されています。