問題タブ [hamming-distance]

n 個の文字列 (n > 100 万) を持つデータベースがあり、各文字列は 100 文字で、各文字はa、b、cまたはのいずれかdです。

それぞれに最も近い文字列を見つけたいと思います。最も近いとは、ハミング距離が最小であると定義します。それぞれの k に最も近い文字列 (k < 5) を見つけたいと思います。

例

k=1 の場合、{(i1,i2),(i2,i1),(i3,i4),(i4,i3)} を返す必要があります。k=2 の場合、{ (i1,{i2,i4}),(i2,{i1,i4}),(i3,{i4,i2}),(i4,{i3,i2})} を返す必要があります。等々。各文字列について、k-最も近い文字列を見つける必要があります。

単純なソリューションの複雑さは O(n^2) 時間です。より複雑なソリューションを見つけたいと思います。他の解決策をいくつか見つけましたが、どれもナイーブに勝るものはありませんでした。

このような文字列をクラスターに最適に分散するにはどうすればよいですか? 1 つの文字列が両方または複数のクラスターに存在する可能性があります。解決策は、決定論的または確率論的である可能性があります。

面接の準備を始めたところ、次の問題に遭遇しました。

• 整数の配列が与えられます
• ここで、配列内の整数のすべてのペアのハミング距離の合計をバイナリ表現で計算します。

例：

純粋にブルート フォース ソリューションからの唯一の最適化は、ここで使用できることを知っていますが、ここに示すようにハミング距離の個々の計算にあります。

この問題を解決する最善の方法は何ですか?

問題：

私は N (~100m) 文字列をそれぞれ D (例: 100) 文字の長さで、低いアルファベット (例: 4 文字) 持っています。これらの N ポイント ( k ~ 0.1D) ごとに k 最近傍点を見つけたいと思います。隣接する文字列は、ハミング距離によって定義されます。解決策は可能な限り最善である必要はありませんが、近いほど良いです。

問題についての考え

これは些細な問題ではないと感じています。私は多くの論文とアルゴリズムを読みましたが、それらのほとんどは高次元では結果が悪く、次元が 5 未満の場合に機能します。たとえば、この論文は効率的なアルゴリズムを提案していますが、その定数は次元に指数関数的に関連しています。

現在、ハミング距離を維持または計算できるように次元を削減する方法を調査しています。

別のオプションは、局所性に敏感なハッシングです。選択したメトリックの下で互いに近いポイントは、高い確率で同じバケットにマップされます。ヘルプはありますか？あなたはどのオプションを好みますか？

ハミング距離を計算し、2 列と 45,000 行以上のデータセットの R のクラスターにプロットする必要があります。これに利用できるよく知られたライブラリはありますか？または、他の戦略よりも強力に推奨される戦略はありますか?

パッケージ "e1071" の hamming.distance 関数を試したところ、以下のエラーが発生しました。しかし、ハミング距離の計算方法がわかったとしても、それらの結果からクラスター グラフに移行する方法がわかりません。

私はこのコードを試しました：

df は次のようになります。

この質問をご覧いただきありがとうございます。どんな助けでも大歓迎です。

私は現在、ハミングコード、または特に間違ったビットを検出して修復するためのハミング距離を理解しようとしています。ハミング距離

ハミング距離がわかりにくい。私はビットの異なる単語を比較していて、単語を異なるものにするビット数を見つけています (-> ハミング距離) - しかし、私が比較しているこの単語は何ですか?

例: word= 0110 1001 -> (偶数) 最後に追加されるパリティ ビット: 0110 (最初のパリティ チェック ビット 1 ～ 4、2 番目の 5 ～ 8、3 番目の 3、4、5、6、4 番目の 0、1、7、8) . => (新しい) 単語を 0110 0001 0110 にします。

パリティビットで単語をチェックしていますか？word1: 0110 0 (ビット 1 ～ 4 + パリティ ビット 1)。word2: 0001 1 (ビット 5 ～ 8 + パリティ ビット 2)。word3: 1000 1 (ビット 3、4、5、6、+ パリティ ビット 3)。word4: 0101 0 (ビット 0、1、7、8 + パリティ ビット 4)。

word1->word2: ハミング距離 4. word2->word3: ハミング距離 3. word3->word4: ハミング距離 4

または私はここで完全に間違っていますか？

私は自分の python をより pythonic にし、コードの短いスニペットのランタイムをいじることに取り組んできました。読みやすさを改善するだけでなく、実行を高速化することも私の目標です。

この例は、これまで読んできたベスト プラクティスと矛盾しているため、自分の思考プロセスのどこに欠陥があるかを知りたいと思っています。

問題は、2 つの等しい長さの文字列のハミング距離を計算することです。たとえば、文字列 'aaab' と 'aaaa' のハミング距離は 1 です。

私が考えることができる最も簡単な実装は次のとおりです。

次に、2 つの「pythonic」実装を作成しました。

と

実行中:

戻る:

ラムダの呼び出しは関数呼び出しとして扱われ、組み込みの operator.countOf の呼び出しよりも遅いため、ham_3 は ham_2 よりも遅く実行されると予想しました。

しかし、ham_1 よりも高速に実行するより Pythonic バージョンを取得する方法を見つけることができなかったことに驚きました。ham_1 が純粋な python の下限であるとは信じがたいです。

誰か考えますか？