ハミング距離

デジタル大辞泉

ハミング‐きょり【ハミング距離】

読み方：はみんぐきょり

《Hamming distance》同じ文字数の二つの文字列を比較したとき、同じ位置にある異なる文字の個数。二つの文字列を同じくするために必要な文字の置換の回数に等しい。米国ベル研究所のR＝ハミングが考案。情報通信の分野では信号距離ともよばれる。

ウィキペディア

ハミング距離

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/09/13 01:06 UTC 版)

4ビット文字列のハミング距離を図示したもの。頂点に特定のビットの組合せが対応していて、頂点間の辺の数がハミング距離に対応する

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

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

ハミング距離の例：

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

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

関連項目

• ハミング符号
• ハミング重み
• ユークリッド距離
• ダメラウ・レーベンシュタイン距離
• レーベンシュタイン距離
• マハラノビス距離
• リー距離
• グレイコード
• カルノー図
• ことばの梯子

ウィキペディア小見出し辞書

ハミング距離

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/11/09 02:06 UTC 版)

「距離空間」の記事における「ハミング距離」の解説

ハミング距離は、2つの文字列の間に定義される距離で、2つの文字列の中に異なる文字何個があるかである。たとえば「simply」と「sample」は異なる文字が2つ(iとa、yとe)あるので、「simply」と「sample」のハミング距離は2である。 このようなものにも距離を定義すると、抽象的で分かりにくかった対象に図形的に分かりやすい解釈を与える事ができる。例えばハミング距離は誤り訂正を図形的で分かりやすいものにしてくれる。誤り訂正とは、データ通信の際に生じる誤りを取り除く方法の事である。例えば「apple」という文章を送ったはずがデータ通信の途中でエラーが入り、「axple」になってしまったとしよう。そうしたらデータを受信した人は辞書を引いて、「axple」とハミング距離が一番近い単語を探す事で誤りを訂正できる。このようにハミング距離は、「誤りを訂正する」という図形的ではないものに、「距離が一番近いものを探す」という図形的な解釈を与えてくれるのである。