問題タブ [hamming-distance]

大量の 2048 ビット バイナリ文字列 ('0111001...0101' など) を含む MySQL データベースを持っています。必要な計算の 1 つは、外部で生成されたビット文字列と比較したこれらの文字列のハミング距離 (XOR の結果に含まれる 1 の総数) です。このクエリの書き方を理解するために、小さなビット文字列用に書いてみました。次に例を示します。

XOR を計算する内部部分は正しく機能しますが、BIT_COUNT は奇妙な結果を返します。この例では、文字列自体よりも長い 14 が返されます。

だから私はいくつかの質問があります：

まず、BIT_COUNT がこのような奇妙な結果を返すのはなぜですか。操作したいバイナリ文字列ではなく、文字列で操作していますか? もしそうなら、どうすればこれに対処できますか？

次に、先頭に b を付けて文字列をバイナリとしてキャストしていることに注意してください (これは正しい言葉ですか?)。列名と変数でこれを行うにはどうすればよいですか? 明らかに、変数名の前に単純に ab を追加することはできず、間にスペースを挿入することもできません。何か案は？

ありがとう、

編集:最初の問題の解決策は次のとおりです。

これをより大きな文字列 (2048 ビット) に使用すると問題が発生するようです。私は試した：

実際のビットカウントは約 1024 であるはずの 28 のような結果が得られます。b を削除すると、64 で最大になるように見えます。この問題を解決する方法について何かアイデアはありますか?

この質問の言い方がよくわからなかったので、ここに詳細を示します。2 つのビット文字列間のハミング距離を計算するトリックを使用しています。クエリは次のとおりです。

基本的に、2 つの文字列間の xor を計算し、すべての 0 を削除してから、長さを返します。これは、2 つのビット文字列間のハミング距離と機能的に同等です。残念ながら、これはハミング距離のみを返し、それ以外は何も返しません。codeTable テーブルには、person_id という列もあります。最小ハミング距離とそれに関連付けられた ID を返せるようにしたいと考えています。最小ハミング距離を返すのは簡単です。'length' 部分の周りに min() を追加するだけです。

これは問題ありませんが、person_id ではなく、ハミング距離のみを返します。そのハミング距離に関連付けられた person_id を返すために何をする必要があるかわかりません。

これを行う方法について誰か考えがありますか？

問題：

私はN（〜100k-1m）の文字列をそれぞれD（例：2000）文字の長さと低いアルファベット（例：3つの可能な文字）で持っています。これらの文字列を並べ替えて、隣接する文字列間の変更ができるだけ少なくなるようにします (たとえば、ハミング距離が低くなるようにします)。解決策は可能な限り最善である必要はありませんが、近いほど良いです。

例

問題についての考え

これは些細な問題ではないと感じています。各文字列を節点、他の文字列までの距離を辺と考えると、巡回セールスマン問題を見ていることになります。文字列の数が多いということは、すべてのペアごとの距離を事前に計算することは潜在的に不可能であることを意味します。この問題をカナダ旅行者問題のようなものに変えると思います。

現時点での私の解決策は、VPツリーを使用して、問題に対する貪欲な最近傍タイプの解決策を見つけることでした

しかし、最初の結果は悪いようです。文字列をハッシュして、より類似したものを近づけることも別のオプションかもしれませんが、これがどの程度優れたソリューションを提供するか、またはこのサイズのデータ​​にどれだけうまくスケーリングするかについてはほとんど知りません.

約 100 万のドキュメントを含む MongoDB があります。これらのドキュメントにはすべて、次のような 1 と 0 の 256 ビット ビンを表す文字列があります。

0110101010101010110101010101

理想的には、バイナリに近い一致を照会したいと思います。これは、2 つのドキュメントに次の番号がある場合を意味します。はい、これがハミング距離です。

これは現在、Mongo ではサポートされていません。そのため、アプリケーション層でやることを余儀なくされています。

したがって、これを考慮して、ドキュメント間で個々のハミング距離を比較する必要がないようにする方法を見つけようとしています。そのため、これを行う時間が基本的に不可能になります。

私はたくさんのRAMを持っています。また、Ruby には、多数のツリーを作成できる優れた gem (アルゴリズム) があるようですが、作成する必要があるクエリの数を減らすような作業を (まだ) 行うことができないようです。

理想的には、100 万件のクエリを作成し、重複に近い文字列を見つけて、それを反映するように更新できるようにしたいと考えています。

誰の考えも大歓迎です。

私は文字列のセットを持っており、[S1 S2 S3 ... Sn]そのようなすべてのターゲット文字列をカウントしTて、それぞれが合計の編集内S1 S2... Snで変換できるようにします。すべての文字列は固定長であり、ここでの編集はハミング距離です。TK
L

私が持っているのは、一種のブルートフォースアプローチです。したがって、アルファベットのサイズが4の場合、O（4 ^ L）のスペースをサンプリングし、それぞれをチェックするのにO（L）の時間がかかります。複雑さを指数関数からいくつかのポリまたは疑似ポリに下げることはできないようです！サンプルスペースを整理して改善する方法はありますか？

L次元のベクトル空間のように視覚化してみました。私はNポイントを与えられており、与えられたNポイントからの距離の合計がK以下であるすべてのポイントを数える必要があります。
i.e. d1 + d2 + d3 +...+ dN <= K
この問題または同様の問題をより複雑に解決する既知の幾何学的アルゴリズムはありますか？親切に私を正しい方向に向けてください。さもないとヒントをいただければ幸いです。
ありがとうございました

私の仕事は遺伝学で、(Matlab の) ハミング距離を使用して、ウイルスの遺伝子型間の遺伝的距離を計算しています。

例: タイプ 1 は構造 01234 を持ち、タイプ 2 は構造 21304 などを持ちます。明らかに、多くの遺伝子型が存在します。遺伝子型の長さが同じなので、ハミング距離でいいと思いました。

私の質問は次のとおりです。ハミング距離に基づいて遺伝子型を注文するにはどうすればよいですか。別の言い方をすれば、ハミング距離に基づいて遺伝子型をクラスターに分類するにはどうすればよいでしょうか?

ありがとう

Matlabのkmeansクラスタリングでハミング距離を使用したいのですが、データがバイナリである必要があるというエラーが表示されます。

とにかくこれの周りにありますか？私が使用するデータマトリックスはバイナリにすることはできません（値0、1、2、3を考慮に入れる必要がある物理的な解釈があります）が、ハミング距離を使用することが重要です。

知覚的なハッシュを生成するtineyeに似たプロセスがあり、これらは32ビットintです。

将来的にはこれらをSQLデータベース（おそらくnosqlデータベース）に保存する予定です。

しかし、ハッシュの類似性に基づいてレコードを取得する方法に困惑しています。

何か案は？

重複の可能性:
32 ビット整数の設定ビット数をカウントする最適なアルゴリズムは?

2 つの数値を比較して 1 のビットの数を取得するプログラムを作成したいと考えています。任意の 2 つの数値のビットを比較して、1 と 0 の 2 進数が異なる場所を見つけます。つまり、排他的 OR (XOR) 関係です。

if 22 (10110 バイナリを持つ) のように、15 (01111 バイナリを持つ) と比較します。

最初のもの 10110

二つ目 01111

結果 11001

答えは 25 になりますが、私が取得したいのは、3 つの 1 と 0 が異なる 3 です。

長さ 32 ビットの数十万のスパース ビット文字列があります。

それらに対して最近傍検索を行いたいのですが、ルックアップのパフォーマンスが重要です。さまざまなアルゴリズムを調べてきましたが、バイナリ文字列ではなくテキスト文字列を対象としているようです。局所的に敏感なハッシングまたはスペクトルハッシングのいずれかが良い候補と思われるか、圧縮を調べることができると思います。これらのいずれかが私のビット文字列の問題にうまく機能しますか? 任意の指示やガイダンスをいただければ幸いです。