ハミング距離

情報理論において、ハミング距離（ハミングきょり、英: Hamming distance）とは、等しい文字数を持つ二つの文字列の中で、対応する位置にある異なった文字の個数である。別の言い方をすれば、ハミング距離は、ある文字列を別の文字列に変形する際に必要な置換回数を計測したものである。この用語は、リチャード・ハミング (Richard Wesley Hamming) にちなんで命名されたもので、鼻歌 (humming) ではない。

ハミング距離は、遠距離通信における固定長バイナリー文字列の中で弾かれたビット数や、エラーの概算を数えるのに用いられるために、信号距離とも呼ばれる。文字数 n の1ビット文字列間のハミング距離は、それらの文字列間の排他的論理和のハミング重み（文字列内の 1 の個数）か、 n 次元超立方体の 2 頂点間のマンハッタン距離に相当する。

ハミング距離の例：

1011101 と 1001001 の間のハミング距離は 2 である。
2173896 と 2233796 の間のハミング距離は 3 である。
"toned" と "roses" の間のハミング距離は 3 である。

異なる文字数の文字列を比較する場合や、文字の置換だけではなく挿入や削除が求められる場合には、より適切なレーベンシュタイン距離のような洗練された計測法が存在する。

関連項目