読み方：ハミングきょり

ハミング距離【Hamming distance】

概要

ハミング距離とは、同じ長さの二つの符号列を比較した際に、対応する位置の符号が異なっている箇所の数を表す指標。ビット列や文字列など固定長のデータ同士の違いの大きさを定量的に示すために用いられ、通信における誤り検出・訂正や、データ比較、類似度判定などに利用される。

二つの符号列を先頭から順に同じ位置同士で比較し、値が一致しない箇所を数えることでハミング距離が求められる。例えばビット列「01010101」と「01110111」を比較すると、異なる位置は2か所であり、ハミング距離は2となる。文字列「confirm」と「comfort」では3文字が異なるため、ハミング距離は3である。

ハミング距離は、一方の符号列を他方に変換する際に必要となる最小の置き換え回数とみなすこともできる。ただし、比較する符号列は同じ長さでなければならず、文字やビットの挿入・削除は考慮しない。長さの異なる符号列同士を比較する場合は、編集距離（レーベンシュタイン距離）などの指標が用いられる。

情報理論や通信工学では、ハミング距離は誤り検出や誤り訂正の性能を評価するための基本的な物差しとなる。符号語同士の最小ハミング距離が大きいほど、通信中に生じた誤りを検出しやすく、一定範囲の誤りであれば訂正できる可能性も高くなる。この考え方は、あらかじめハミング距離が離れた符号の組み合わせを定義しておき、受信データに誤りがあっても最も近い符号へ自動的に補正する仕組みとして応用されている。

コンピュータの分野では、データ比較やパターン認識、機械学習、バイオインフォマティクスなどでもハミング距離が用いられる。固定長のデータ同士の類似度を高速に評価できるため、大量のデータから近い特徴を持つ要素を検索する処理や、近似文字列検索、重複データの検出などに活用されている。「ハミング」の名称は、誤り訂正符号の研究で知られるアメリカの数学者リチャード・ハミング（Richard W. Hamming）に由来する。「Hamming」と、鼻歌を意味する「Humming」は綴りが一文字だけ異なり、ハミング距離は1である。