ハミング距離

ハミング距離
ハミング距離を見つけるための4 ビットのバイナリテッセラクト。	2つの距離の例: 0100→1001 の距離は 3、0110 →1110 の距離は 1
クラス	文字列の類似性
データ構造	弦
最悪のパフォーマンス	お（n）{\displaystyle O(n)}
最高のパフォーマンス	お（n）{\displaystyle O(n)}
平均的なパフォーマンス	お（n）{\displaystyle O(n)}
最悪の場合の空間複雑度	お（n）{\displaystyle O(n)}

ハミング距離を求めるための3ビットバイナリキューブ

2つの距離の例: 100→011の距離は3、010 →111の距離は2

任意の 2 つの頂点間の最小距離は、2 つのバイナリ文字列間のハミング距離です。

情報理論において、等しい長さの2つの文字列またはベクトル間のハミング距離は、対応する記号が異なる位置の数です。言い換えれば、一方の文字列を他方の文字列に置き換えるために必要な置換の最小数、あるいは、一方の文字列を他方の文字列に変換できる可能性のあるエラーの最小数を測定します。より一般的な文脈では、ハミング距離は、2つの配列間の編集距離を測定するための文字列指標の1つです。アメリカの数学者リチャード・ハミングにちなんで名付けられました。

主な応用は符号理論、より具体的には、等しい長さの文字列が有限体上のベクトルであるブロック符号です。

意味

2つの等しい長さの記号列間のハミング距離は、対応する記号が異なる位置の数である。^{[ 1 ]}

例

記号は文字、ビット、10進数など、様々なものが考えられます。例えば、以下の記号間のハミング距離は次のようになります。

「ka rol in」と「ka thr in」は3です。
「k a r ol in」と「k e r st in」は3です。
「k athr in」と「k erst in」は 4 です。
0000 と 1111は 4 です。
2 17 3 8 96 と 2 23 3 7 96 は 3 です。

プロパティ

固定長nの場合、ハミング距離は長さnの単語の集合（ハミング空間とも呼ばれる）上の測定基準であり、非負性、対称性、2 つの単語が同一の場合のみ 2 つの単語のハミング距離が 0 となる、という条件を満たし、三角不等式も満たします。^[²^]実際、3 つの単語a、b、c を固定すると、 a の i 番目の文字と c の i 番目の文字に違いがある場合は必ず、 aのi番目の文字とbのi番目の文字、またはbのi番目の文字とcのi番目の文字にも違いがあるはずです。したがって、 aとc間のハミング距離は、aとb間およびbとc間のハミング距離の合計よりも大きくなりません。 2 つの単語aとb間のハミング距離は、 - 演算子を適切に選択した場合のa − bのハミング重みとして見ることもできます。これは、2 つの整数の差が数直線上のゼロからの距離として見られるのと同じです。

バイナリ文字列aとb のハミング距離は、XOR b内の1 の数（人口カウント）に等しくなります。^[³^]ハミング距離を持つ長さn のバイナリ文字列の距離空間は、ハミングキューブとして知られています。これは、距離空間としては、ハイパーキューブグラフの頂点間の距離の集合に相当します。また、文字列内の各シンボルを実座標として扱うことにより、長さnのバイナリ文字列をのベクトルとして見ることもできます。この埋め込みにより、文字列はn次元ハイパーキューブの頂点を形成し、文字列のハミング距離は頂点間のマンハッタン距離に等しくなります。 $\mathbb {R} ^{n}$

エラー検出とエラー訂正

最小ハミング距離（または最小距離、通常d _minと表記される）は、誤り検出符号や誤り訂正符号など、符号理論におけるいくつかの重要な概念を定義するために使用される。特に、符号Cがk誤り検出性であるとは、その符号語間の最小ハミング距離が少なくともk + 1である場合に限る。^[²^]

例えば、2つのコードワード「000」と「111」からなるコードを考えてみましょう。これら2つのワード間のハミング距離は3なので、k =2のエラー検出となります。つまり、1ビットまたは2ビットが反転してもエラーを検出できます。3ビットが反転すると、「000」は「111」になり、エラーは検出できません。

コードCがk 誤り訂正可能であるとは、ハミング空間H内の任意のワードwに対して、 wとc間のハミング距離がk以下となるようなコードワードc（Cから）が最大で 1 つ存在することを意味する。言い換えれば、コード Cの任意の 2 つのコードワード間の最小ハミング距離が 2 k + 1 以上である場合、コードはk誤り訂正可能である。これは幾何学的にも、異なるコードワードを中心とする半径kの閉球が互いに素であることとして理解される。^[²^]これらの球は、この文脈ではハミング球とも呼ばれる。^[⁴^]

例えば、2つのコードワード「000」と「111」からなる同じ3ビットコードを考えてみましょう。ハミング空間は、000、001、010、011、100、101、110、111の8つのワードで構成されます。コードワード「000」と、その単一ビットエラーワード「001」、「010」、「100」はすべて、1から「000」までのハミング距離以下です。同様に、コードワード「111」とその単一ビットエラーワード「110」、「101」、「011」はすべて、元の「111」からハミング距離1以内です。このコードでは、単一ビットエラーは常に元のコードからハミング距離1以内であり、コードは1エラー訂正、つまりk=1になります。「000」と「111」間のハミング距離は3であり、これらがコード内のコードワードのセット全体を構成するため、最小ハミング距離は3となり、2k+1 = 3を満たします。

したがって、符号語間のハミング距離dが最小の符号は、最大d -1個の誤りを検出でき、⌊( d -1)/2⌋個の誤りを訂正できる。^{[ 2 ]}後者の数値はパッキング半径または符号の誤り訂正能力とも呼ばれる。 ^{[ 4 ]}

歴史と応用

ハミング距離は、1950年にハミング符号に関する基礎論文「誤り検出と誤り訂正符号」でこの概念を導入したリチャード・ハミングにちなんで名付けられました。 ^[⁵^]ビットのハミング重み分析は、情報理論、符号理論、暗号学など、いくつかの分野で使用されています。^[⁶^]

これは通信において、固定長のバイナリワード内の反転ビット数を数えて誤差の推定値とするために使用されるため、信号距離と呼ばれることもあります。^{[ 7 ]}サイズq ≥ 2 のアルファベット上のq元文字列の場合、 q 元対称チャネルの場合はハミング距離が適用されますが、リー距離は位相偏移変調や、より一般的には同期エラーの影響を受けやすいチャネルに使用されます。これは、リー距離が ±1 のエラーを考慮できるためです。^[⁸^]またはの両方の距離が一致する場合、またはからの要素の任意のペアは1 だけ異なるため、距離は一致しますが、より大きいの場合は距離が異なります。 $q=2$ $q=3$ ${\textstyle \mathbb {Z} /2\mathbb {Z} }$ ${\textstyle \mathbb {Z} /3\mathbb {Z} }$ $q$

ハミング距離は系統学では遺伝的距離の尺度としても使われている。^{[ 9 ]}

しかし、異なる長さの文字列を比較する場合や、置換だけでなく挿入や削除も予想される文字列を比較する場合は、レーベンシュタイン距離などのより洗練された指標の方が適している可能性があります。^{[ 10 ]}^：32

アルゴリズムの例

Python 3 で記述された次の関数は、2 つの文字列間のハミング距離を返します。

定義ハミング距離(文字列1 : str 、文字列2 : str ) -> int :「2 つの文字列間のハミング距離を返します。」len (文字列1 ) != len (文字列2 )の場合:ValueErrorを発生させます( "文字列の長さは同じでなければなりません。" )分布カウンタ= 0範囲( len (文字列1 ))内のnの場合:文字列1 [ n ] !=文字列2 [ n ]の場合:分布カウンタ+= 1dist_counterを返す

以下のC関数は、2つの整数（2進値、つまりビット列として扱われます）のハミング距離を計算します。この関数の実行時間は、入力のビット数ではなく、ハミング距離に比例します。この関数は、2つの入力のビット単位の排他的論理和を計算し、その結果のハミング重み（非ゼロビットの数）を、最下位の非ゼロビットを繰り返し検出してクリアするWegner (1960)のアルゴリズムを用いて算出します。一部のコンパイラは、利用可能な場合は専用のプロセッサハードウェアを用いてこの計算を行う __builtin_popcount関数をサポートしています。

intハミング距離( unsigned x 、unsigned y ) { int dist = 0 ;// ^ 演算子は異なるビットのみを 1 に設定しますfor ( unsigned val = x ^ y ; val > 0 ; ++ dist ) { // 次に、Peter Wegner の方法で 1 に設定されたビットをカウントしますval = val & ( val - 1 ); // val の最下位の 1 を 0 に設定します}// 異なるビットの数を返しますreturn dist ; }

より高速な代替手段は、popcount（アセンブリ命令）を使用する方法です。GCCやClangなどの一部のコンパイラでは、組み込み関数としてpopcountを利用できます。

// 32ビット整数のハミング距離int hamming_distance32 ( unsigned int x , unsigned int y ) { return __builtin_popcount ( x ^ y ); }// 64ビット整数のハミング距離int hamming_distance64 ( unsigned long long x , unsigned long long y ) { return __builtin_popcountll ( x ^ y ); }

参照

参考文献

^ワグナー、ビル（1995年）『パルス符号変調技術』シュプリンガー、p.206、ISBN 978-0-442-01436-0. 2020年6月13日閲覧。
^ ^a ^b ^c ^dロビンソン、デレク・JS (2003).抽象代数入門.ウォルター・デ・グリュイター. pp. 255– 257. ISBN 978-3-11-019816-4。
^ウォーレン・ジュニア、ヘンリー・S. (2013) [2002]. Hacker's Delight (第2版). Addison Wesley – Pearson Education, Inc. pp. 81– 96. ISBN 978-0-321-84268-80-321-84268-5。
^ ^a ^b Cohen, G. ; Honkala, I.; Litsyn, S.; Lobstein, A. (1997)、「Covering Codes」、North-Holland Mathematical Library、vol. 54、Elsevier、pp. 16– 17、ISBN 978-0-08-053007-9
^ Hamming, RW (1950年4月). 「誤り検出および誤り訂正符号」(PDF) . The Bell System Technical Journal . 29 (2): 147– 160. doi : 10.1002/j.1538-7305.1950.tb00463.x . hdl : 10945/46756 . ISSN 0005-8580 . S2CID 61141773. 2022年10月9日時点のオリジナルよりアーカイブ(PDF) .
^ Jarrous, Ayman; Pinkas, Benny (2009). 「安全なハミング距離に基づく計算とその応用」 Abdalla, Michel; Pointcheval, David; Fouque, Pierre-Alain; Vergnaud, Damien (編). 『応用暗号とネットワークセキュリティ』コンピュータサイエンス講義ノート第5536巻. ベルリン、ハイデルベルク: Springer. pp. 107– 124. doi : 10.1007/978-3-642-01957-9_7 . ISBN 978-3-642-01957-9。
^アヤラ、ホセ (2012).集積回路とシステム設計.シュプリンガー. p. 62. ISBN 978-3-642-36156-2。
^ロス、ロン (2006).符号理論入門.ケンブリッジ大学出版局. p. 298. ISBN 978-0-521-84504-5。
^ Pilcher, Christopher D.; Wong, Joseph K.; Pillai, Satish K. (2008-03-18). 「系統配列関係からのHIV伝播動態の推論」 . PLOS Medicine . 5 (3): e69. doi : 10.1371/journal.pmed.0050069 . ISSN 1549-1676 . PMC 2267810. PMID 18351799 .
^ Navarro, Gonzalo (2001). 「近似文字列マッチングのガイドツアー」(PDF) . ACM Computing Surveys . 33 (1): 31– 88. CiteSeerX 10.1.1.452.6317 . doi : 10.1145/375360.375365 . S2CID 207551224 .

さらに読む

この記事には、連邦規格1037Cのパブリックドメイン資料が含まれています。一般調達局。2022年1月22日時点のオリジナル記事からのアーカイブ。
ウェグナー、ピーター(1960). 「バイナリコンピュータにおける1を数える手法」 Communications of the ACM . 3 (5): 322. doi : 10.1145/367236.367286 . S2CID 31683715 .
MacKay, David JC (2003). 『情報理論、推論、学習アルゴリズム』ケンブリッジ:ケンブリッジ大学出版局. ISBN 0-521-64298-1。

[1] ワグナー、ビル（1995年）『パルス符号変調技術』シュプリンガー、p.206、ISBN 978-0-442-01436-0. 2020年6月13日閲覧。

[Robinson2003-2] ロビンソン、デレク・JS (2003).抽象代数入門.ウォルター・デ・グリュイター. pp. 255– 257. ISBN 978-3-11-019816-4。

[Warren_2013-3] ウォーレン・ジュニア、ヘンリー・S. (2013) [2002]. Hacker's Delight (第2版). Addison Wesley – Pearson Education, Inc. pp. 81– 96. ISBN 978-0-321-84268-80-321-84268-5。

[cc17-4] Cohen, G. ; Honkala, I.; Litsyn, S.; Lobstein, A. (1997)、「Covering Codes」、North-Holland Mathematical Library、vol. 54、Elsevier、pp. 16– 17、ISBN 978-0-08-053007-9

[5] Hamming, RW (1950年4月). 「誤り検出および誤り訂正符号」(PDF) . The Bell System Technical Journal . 29 (2): 147– 160. doi : 10.1002/j.1538-7305.1950.tb00463.x . hdl : 10945/46756 . ISSN 0005-8580 . S2CID 61141773. 2022年10月9日時点のオリジナルよりアーカイブ(PDF) .

[6] Jarrous, Ayman; Pinkas, Benny (2009). 「安全なハミング距離に基づく計算とその応用」 Abdalla, Michel; Pointcheval, David; Fouque, Pierre-Alain; Vergnaud, Damien (編). 『応用暗号とネットワークセキュリティ』コンピュータサイエンス講義ノート第5536巻. ベルリン、ハイデルベルク: Springer. pp. 107– 124. doi : 10.1007/978-3-642-01957-9_7 . ISBN 978-3-642-01957-9。

[Ayala2012-7] アヤラ、ホセ (2012).集積回路とシステム設計.シュプリンガー. p. 62. ISBN 978-3-642-36156-2。

[Roth2006-8] ロス、ロン (2006).符号理論入門.ケンブリッジ大学出版局. p. 298. ISBN 978-0-521-84504-5。

[9] Pilcher, Christopher D.; Wong, Joseph K.; Pillai, Satish K. (2008-03-18). 「系統配列関係からのHIV伝播動態の推論」 . PLOS Medicine . 5 (3): e69. doi : 10.1371/journal.pmed.0050069 . ISSN 1549-1676 . PMC 2267810. PMID 18351799 .

[navarro-10] Navarro, Gonzalo (2001). 「近似文字列マッチングのガイドツアー」(PDF) . ACM Computing Surveys . 33 (1): 31– 88. CiteSeerX 10.1.1.452.6317 . doi : 10.1145/375360.375365 . S2CID 207551224 .

[ 1 ]

[

[

[

[

[

[ 7 ]

[

[ 9 ]

[ 10 ]