問題タブ [hamming-distance]

1 と 0 を含む 2 つの等しい長さの文字列があります。各文字列の長さは 128 ビットで、それらの間のハミング距離を計算したいと考えています。これを行うための最良の方法は何ですか?

例 a='1000001' and b='1110001' --> dist=Hamming(a,b);

私が取り組んでいる問題では、2つのシーケンス間の距離を見つけて類似性を判断するために、シーケンスの順序が非常に重要です。ただし、私が持っているシーケンスはすべて同じ長さではないため、ハミング距離の要件を満たすために、両方のシーケンスが同じ長さになるように、不足している文字列を空のポイントで埋めます。私が気にしているのは転置の数だけなので（レーベンシュタインのように挿入や削除ではない）、これを行うことに大きな問題はありますか？

より長いシーケンスの距離メトリックとして、ハミング距離はレーベンシュタインよりもはるかに高速であることがわかりました。はるかに安いハミング距離の代わりに、いつレーベンシュタイン距離（またはレーベンシュタイン距離の派生物）を使用する必要がありますか？ハミング距離は、2つのシーケンス間の可能なレーベンシュタイン距離の上限と見なすことができるため、シーケンスに一致する絶対最小移動数ではなく、順序に偏った類似性メトリックについて2つのシーケンスを比較している場合、明らかなものはありません。メトリックとしてハミングではなくレーベンシュタインを選択する理由はありますか？

DBにテーブルがあり、SHA256ハッシュをBINARY（32）列に格納しています。列のエントリから指定された値までのハミング距離を計算する方法を探しています。つまり、次のようになります。

（不思議に思うかもしれませんが、文字列AとBのハミング距離はとして定義されますBIT_COUNT(A^B)。ここで^はビット単位のXOR演算子であり、BIT_COUNTはバイナリ文字列の1の数を返します）。

^演算子とBIT_COUNT関数はどちらもINTEGERでのみ機能することがわかっているので、おそらくそれを行う唯一の方法は、バイナリ文字列をサブストリングに分割し、各バイナリサブストリングを整数にキャストし、サブストリングごとに距離をハミングしてから、それらを追加します。これに伴う問題は、それがひどく複雑に聞こえ、効率的ではなく、間違いなくエレガントではないということです。したがって、私の質問は次のとおりです。より良い方法を提案できますか？（私は共有ホスティングを使用しているため、DBサーバーを変更したりライブラリをロードしたりできないことに注意してください）

edit（1）：明らかに、テーブル全体をPHPにロードし、そこで計算を行うことは可能ですが、このテーブルはおそらくかなり大きくなるので、私はむしろそれを避けたいと思います。

edit（2）：DBサーバーはMySQL5.1です

edit（3）：以下の私の答えには、上記で説明したコードが含まれています。

edit（4）：BINARY（32）の代わりに4つのBIGINTを使用してハッシュを格納すると、速度が大幅に向上する（100倍以上高速）ことがわかりました。以下の私の答えへのコメントを参照してください。

私は N < 2^n のランダムに生成された n ビットの数値をファイルに保存しており、その検索にはコストがかかります。数値 Y が与えられた場合、ファイル内で最大 k ハミング距離である数値を検索する必要があります。Yから。これは、私の場合は実行できない最悪のケースのルックアップである C(n 1) + C(n 2) + C(n 3)...+C(n,k) を呼び出します。メモリ内の各ビット位置での 1 と 0 の分布を格納して、ルックアップの優先順位を付けてみました。したがって、ビット i が 0/1 である確率を保存しました。

しかし、N が大きすぎて、すべてのビット位置で 1/0 がほぼ均等に分布しているため、あまり役に立ちませんでした。このことをより効率的に行う方法はありますか。今のところ、n=32、N = 2^24 と仮定できます。

私の修士論文の一部として、2つの重要なビット（2番目と4番目）を持つ数値（たとえば5ビット）を取得します。これは、たとえばx1x0x、$x \in {0,1}$（xは0または1）であり1,0、固定値のビットであることを意味します。

私の最初のタスクは、上記の数のすべての組み合わせを計算すること2^3 = 8です。これはS_1グループと呼ばれます。

次に、「S_2」グループを計算する必要があります。これは、2つの数値のすべての組み合わせでありx0x0x、x1x1x（これは、重要なビットの1つの不一致を意味します）、これにより、が得られ$\bin{2}{1} * 2^3 = 2 * 2^3 = 16ます。

編集 各番号x1x1xとは、元の番号とは1ビット大きくx0x0x異なります。x1x0x

最後のグループ、S_3はもちろん、重要なビットからの2つの不一致です。つまり、フォームを通過するすべての数値x0x1x、8つの可能性があります。

計算は再帰的または独立して計算できますが、これは問題ではありません。

私が持っているものはそれほど効率的ではないので、誰かがこれらの計算の出発点を与えることができれば幸いです。

編集多分私は重要なビット を使用して、私の言葉を間違って選択しました。私が言いたかったのは、5ビット数の特定の場所でビットが固定されているということです。私が特定のビットとして定義した場所。

編集 私はすでに2つの答えを見ました、そしてそれは私がもっと明確にすべきだったようです。私がもっと興味を持っているのは、数字を見つけることですx0x0x。これは単なる例です。実際には、グループ（この例では）は少なくとも12ビット長の数値で構築され、11個の有効ビットを含めることができます。それなら私は12のグループを持つでしょう...x1x1xx0x1xS_1x1x0x

それでも不明な点がある場合は、お問い合わせください;）

問題：

符号なし32ビット整数の大きな（〜1億）リスト、符号なし32ビット整数入力値、および最大ハミング距離が与えられた場合、入力値の指定されたハミング距離内にあるすべてのリストメンバーを返します。

リストを保持するための実際のデータ構造はオープンであり、パフォーマンス要件によってメモリ内ソリューションが決まります。データ構造を構築するためのコストは二次的であり、データ構造をクエリするための低コストが重要です。

例：

これまでの私の考え：

ハミング距離が0の縮退した場合は、ソートされたリストを使用して、特定の入力値の二分探索を実行します。

ハミング距離が1だけの場合、元の入力の各ビットを反転して、上記を32回繰り返すことができます。

（リスト全体をスキャンせずに）ハミング距離が1より大きいリストメンバーを効率的に検出するにはどうすればよいですか。

ルビーでは、2つの符号なし整数間のビット差（ハミング距離など）を計算する最も効率的な方法は何ですか？

たとえば、整数a=2323409845およびb=178264714​​4があります。

それらのバイナリ表現は次のとおりです。

aとbのビット差は17です。

それらに対して論理XORを実行できますが、それによって別の整数！= 17が得られます。次に、結果のバイナリ表現を反復処理して、1の数を集計する必要があります。

ビット差を計算する最も効率的な方法は何ですか？

さて、多くのintのシーケンスのビット差を計算するための答えは変わりますか？たとえば、符号なし整数の2つのシーケンスが与えられた場合：

2つのシーケンス間のビット差を計算する最も効率的な方法は何ですか？

シーケンスを反復処理しますか、それともシーケンス全体の差を一度に計算するより高速な方法がありますか？

ここで定義されているバイナリ文字列は、固定サイズのビットの「配列」です。それらには順序がないため（数字としてソート/インデックス付けすることは意味がありません）、各ビットは他のビットから独立しているため、文字列と呼びます。このような文字列はそれぞれ N ビットの長さで、N は数百にのぼります。

これらの文字列を保存し、ハミング距離を距離メトリックとして使用して、最近傍の新しいバイナリ文字列クエリを指定する必要があります。
メトリック ベースの検索 (VP ツリー、カバー ツリー、M ツリー) 用の特殊なデータ構造 (メトリック ツリー) がありますが、通常のデータベース (私の場合は MongoDB) を使用する必要があります。

1 対 1 のハミング距離一致を実行する前に、DB がレコードのサブセットのみにアクセスできるようにするバイナリ文字列に適用できるインデックス作成機能はありますか? あるいは、標準の DB でそのようなハミング ベースの検索を実装するにはどうすればよいでしょうか?

問題

N (~100k-1m) 個の整数/ビット文字列がそれぞれ K (例: 256) ビットの長さであるとします。アルゴリズムは、ペアごとのハミング距離が最小の k ペアを返す必要があります。

例

k=1 の場合、ペアリスト {(i3,i4)} を返す必要があります。k=3 の場合、{(i1,i2), (i1,i4), (i3,i4)} を返す必要があります。等々。

アルゴリズム

単純な実装では、すべてのペアごとの距離を計算し、ペアを並べ替えて、距離が最小の k を返します: O(N^2)。より良いデータ構造またはアルゴリズムはありますか? 単一のクエリ整数がないため、大きなセットでハミング距離が低いバイナリ文字列を効率的に見つけるのアイデアは使用できないようです。

これは宿題の問題であり、私はそれを理解するのにいくつかの困難に直面しています。宿題の質問は

私は、最初はそれらすべてをクラスターと見なしてから、最も近いものをマージし始める必要があるという本を読みました。新しいクラスターが形成されます。ここで、質問で述べたように、両方のクラスターの各要素間の距離を平均して、この新しいクラスターと他のクラスター間の距離を計算することにより、この新しく形成されたクラスターに最も近いクラスターを見つける必要があります。

私の解決策：すべてのペア間のハミング距離を見つけ、C3とC5（ハミング距離は2）の1つが最も少ないものを選択します。これで、これを新しいクラスターにマージできます。

私の懸念は、ここでマージすることの正確な意味は何ですか？どうすればいいのですか？または、単にそれらをそのままにして、新しいクラスターという名前を付けますか？

また、新しいクラスターの各要素と他のクラスターとの間の平均距離を見つけるにはどうすればよいですか？

また、平均を計算するには、与えられた式は|C1|で割ると言います および|C2|。つまり、ここで要素の数で割る必要があるということですか（1つのグループあたり8で、マージされるクラスターを掛けたものですか？）

どんな助けでも大歓迎です。ありがとうございました。