Loading article…
| |||
| クラス | 文字列の類似性 | ||
|---|---|---|---|
| データ構造 | 弦 | ||
| 最悪の場合のパフォーマンス | |||
| 最良のパフォーマンス | |||
| 平均的なパフォーマンス | |||
| 最悪の場合の空間計算量 | |||
情報理論において、同じ長さの2つの文字列またはベクトル間のハミング距離とは、対応する記号が異なる位置の数を指します。言い換えれば、一方の文字列を他方の文字列に変換するために必要な最小置換数、あるいは同等に、一方の文字列を他方の文字列に変換しうる最小エラー数を測定するものです。より一般的な文脈では、ハミング距離は2つのシーケンス間の編集距離を測定するための文字列メトリックの1つです。この名前は、アメリカの数学者リチャード・ハミングにちなんで付けられました。
長さが等しい2つの記号列間のハミング距離は、対応する記号が異なる位置の数です。[ 1 ]
記号は、文字、ビット、十進数など、さまざまな形式をとることができます。例えば、ハミング距離は次のようになります。
固定長nに対して、ハミング距離は、非負性、対称性、2 つの単語のハミング距離が0になるのは 2 つの単語が同一である場合のみであること、および三角不等式も満たすという条件を満たすため、長さ n の単語の集合 (ハミング空間とも呼ばれる) 上の距離です。[ 2 ]実際、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の場合、ハミング距離はa XOR bの1 の数 (人口カウント)に等しくなります。[ 3 ]ハミング距離を持つ長さn のバイナリ文字列の距離空間はハミングキューブとして知られています。これは、距離空間として、ハイパーキューブグラフの頂点間の距離の集合と同等です。長さnのバイナリ文字列は、ベクトルとして見ることもできます。文字列内の各記号を実座標として扱うことで、この埋め込みにより、文字列はn次元超立方体の頂点を形成し、文字列のハミング距離は頂点間のマンハッタン距離に等しくなります。
最小ハミング距離または最小距離（通常はd minで表される）は、誤り検出符号や誤り訂正符号など、符号理論におけるいくつかの重要な概念を定義するために使用されます。特に、符号Cは、その符号語の任意の 2 つ間の最小ハミング距離が少なくともk + 1 である場合に限り、 k誤り検出符号であると言われます。[ 2 ]
例えば、「000」と「111」という2つの符号語からなるコードを考えてみましょう。これら2つの符号語間のハミング距離は3なので、k =2の誤り検出が可能です。つまり、1ビットまたは2ビットが反転した場合、誤りを検出できます。3ビットが反転した場合、「000」は「111」となり、誤りを検出できなくなります。
符号Cは、基となるハミング空間Hの任意の単語wに対して、 wとcの間のハミング距離がk以下となるような符号語c ( Cから)が最大で 1 つだけ存在する場合に、k 誤り訂正符号であると言われます。言い換えれば、任意の 2 つの符号語間の最小ハミング距離が 2 k +1以上である場合、符号はk誤り訂正符号であると言えます。これは、異なる符号語を中心とする半径kの任意の閉球が互いに素であるという意味で幾何学的にも理解されます。 [ 2 ]この文脈では、これらの球はハミング球とも呼ばれます。[ 4 ]
例えば、2 つの符号語「000」と「111」からなる同じ 3 ビットのコードを考えてみましょう。ハミング空間は 000、001、010、011、100、101、110、111 の 8 つのワードから構成されます。符号語「000」と、1 ビット誤りワード「001」、「010」、「100」はすべて、「000」とのハミング距離 1 以下です。同様に、符号語「111」とその 1 ビット誤りワード「110」、「101」、「011」はすべて、元の「111」との 1 ハミング距離内にあります。このコードでは、1 ビット誤りは常に元のコードとの 1 ハミング距離内であり、このコードは1 誤り訂正可能、つまりk=1となります。 「000」と「111」の間のハミング距離は3であり、これらはコード内のコードワードの全体を構成するため、最小ハミング距離は3であり、2k+1 = 3を満たします。
したがって、符号語間のハミング距離が最小dの符号は、最大でd -1 個のエラーを検出でき、⌊( d -1)/2⌋ 個のエラーを訂正できます。[ 2 ]後者の数値は、パッキング半径または符号の誤り訂正能力とも呼ばれます。 [ 4 ]
ハミング距離は、1950年にハミング符号に関する基礎論文「誤り検出および誤り訂正符号」でこの概念を導入したリチャード・ハミングにちなんで名付けられました。 [ 5 ]ビットのハミング重み解析は、情報理論、符号理論、暗号理論など、いくつかの分野で使用されています。[ 6 ]
これは、電気通信において、固定長バイナリワード内の反転ビット数をエラーの推定値としてカウントするために使用され、そのため信号距離と呼ばれることもあります。[ 7 ]サイズq ≥ 2 のアルファベット上のq進文字列の場合、 q 進対称チャネルの場合はハミング距離が適用されますが、位相シフトキーイングや、より一般的には同期エラーの影響を受けやすいチャネルでは、リー距離が ±1 のエラーを考慮するため、リー距離が使用されます。 [ 8 ]もし またはどちらの距離も一致するのは、または1だけ異なるが、距離は大きいほど異なる。
ハミング距離は、系統分類学において遺伝的距離の尺度としても用いられる。[ 9 ]
しかし、長さの異なる文字列を比較する場合、あるいは置換だけでなく挿入や削除も想定される文字列を比較する場合は、レーベンシュタイン距離のようなより洗練された指標の方が適切かもしれない。[ 10 ]： 32
以下の関数はPython 3で記述されており、2つの文字列間のハミング距離を返します。
def hamming_distance ( string1 : str , string2 : str ) -> int :"""2つの弦間のハミング距離を返します。"""if len ( string1 ) != len ( string2 ):raise ValueError ( "文字列は同じ長さでなければなりません。" )dist_counter = 0for n in range ( len ( string1 )):string1 [ n ] != string2 [ n ]の場合:dist_counter += 1dist_counterを返す以下のC関数は、2 つの整数 (バイナリ値、つまりビット列として扱われる) のハミング距離を計算します。この処理の実行時間は、入力のビット数ではなく、ハミング距離に比例します。この関数は、2 つの入力のビットごとの排他的論理和を計算し、次にWegner (1960)のアルゴリズムを使用して、結果のハミング重み(非ゼロビットの数)を求めます。このアルゴリズムは、最下位の非ゼロビットを繰り返し見つけてクリアします。一部のコンパイラは、利用可能な場合は専用のプロセッサ ハードウェアを使用してこれを計算できる__builtin_popcount関数をサポートしています。
int hamming_distance ( 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 をゼロに設定します。 }// 異なるビット数を返すreturn dist ; }より高速な代替手段として、個体数カウント（popcount）アセンブリ命令を使用する方法があります。GCCやClangなどの一部のコンパイラでは、組み込み関数として提供されています。
// 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 ); }
この記事は、連邦規格1037C（一般調達局）からのパブリックドメイン資料を組み込んでいます。 2022年1月22日にオリジナルからアーカイブされました。