ハミング距離とは、同じ長さの2つの記号列を比較したとき、対応する位置で記号が異なる箇所の数です。1950年にリチャード・ハミングが誤り検出・訂正符号に関する論文で提唱し、符号理論とデジタル通信の基礎概念として定着しています。

最小ハミング距離が d である符号は、最大 d − 1 個のビット誤りを検出でき、最大 ⌊(d − 1) / 2⌋ 個の誤りを訂正できます。たとえば各ビットを3回繰り返す反復符号は最小距離が 3 となり、任意の2ビット誤りを検出し、1ビット誤りを訂正できます。

誤り訂正以外にも、暗号理論における鍵の類似度評価、DNAシーケンス解析による塩基配列の比較、機械学習でのハッシュを用いた近傍探索など、幅広い分野で利用されています。

はい。ハミング距離は、対応する位置ごとに記号を比べる操作を前提としているため、同じ長さの列に対してのみ定義されます。長さが異なる場合は余分な記号を対応させる自然な方法がなく、距離を一意に定義できません。

長さが異なる文字列を比較する場合は、レーベンシュタイン距離（編集距離）が標準的な代替手法です。一方の文字列をもう一方に変換するために必要な、1文字単位の挿入・削除・置換の最小回数を距離として定義します。