問題タブ [hamming-distance]

奇妙な通信チャネルがあり、チャネル内の特定のシーケンスを排除するだけでなく、エラーを検出する必要があります。

各メッセージの長さは 12 ビットで、3 つのニブル (それぞれ 4 ビット) に分割されます。これから少なくとも 450 の異なるコードを抽出する必要があるため、最大 3 のハミング距離を得ることができます。

ただし、シーケンス内の 2 つのニブルを同じにすることはできないため、次のシーケンスは無効です。

さらに、メッセージは途切れることなく相互に続くことができるため、1 つのシーケンスの開始に、最後のシーケンスの終了と同じ最初のニブルを含めることはできません。

ただし、次のシーケンスは問題ありません。

そして、次の一連のメッセージは問題ありません。

私が最初に考えたのは、メッセージに 9 ビットを使用し、各ニブルの上位ビットとして 3 つの 3 ビット部分に分割することです。

c次に、面倒なシーケンスを排除しながらハミング距離を作成する3 ビットを埋める 512 エントリ テーブルを設計します。

ただし、これはローエンドの組み込みプロセッサで実行されます。算術演算を使用cしてオンザフライでビットを生成できれば、(プロセッサ時間を増やす代わりに) メモリを節約でき、この場合はより価値があります。

テーブルなしでこの問題を解決するために実行できるちょっとした数学はありますか?

あるいは、要件を満たす数学を使用した別のパッキング方法はありますか?

ベクトルのハミング重みに取り組んでいますが、ベクトル内のすべての 1 を線形にカウントしています。より効率的な方法はありますか?

バイナリ ベクトル (数百万個) を k 個のクラスターにクラスター化したいと考えています。ハミング距離を使用して、初期クラスターの最近傍を見つけています (これも非常に低速です)。K-means クラスタリングはここには当てはまらないと思います。問題は、重心を更新するために、いくつかの初期クラスター中心に最も近い近傍 (バイナリ ベクトル) の平均を計算することです。

2 番目のオプションは、新しいクラスター中心が最近傍の 1 つ (特定のクラスター中心のすべての近傍に最も近いもの) から選択される K-medoid を使用することです。しかし、最近傍の数も非常に多いため、それを見つけることは別の問題です。

誰かが私を案内してもらえますか？

FAST と FREAK を使用していくつかの画像の記述子を取得し、次に knnMatch をBruteForceMatcher マッチャーに適用し、次にループを使用して適切な一致を分離しています。

FlannBasedMatcher と一緒に使用すると問題なく動作しますが、BruteForceMatcher と一緒に使用すると非常に奇妙になるため、問題は適切な一致検索方法である可能性があると思います。ハミング距離はバイナリ記述子を使用するため、この方法でナンセンスを行っているのではないかと疑っていますが、それを適応させる方法が思いつきません!

リンク、スニペット、アイデアなどはありますか?

XMLドキュメントから供給されるカスタムインストーラーを構築しています...

ほとんどのプログラマーが自分でビルドしないことは知っていますが、これは特に私が割り当てられたものなので、一緒に働いてください。インストーラーは、ジョブを実行する前に、プログラムの古いバージョンをアンインストールする必要があります。

問題なくレジストリ アンインストール文字列を取得できます。問題は、指示ファイルを作成するユーザーが常に正確な表示名を持っているとは限らないことです。

そう...

レーベンシュタイン差を使用して、70% を超える可能性のある一致を取得しています。これにより、間違いが発生する可能性があります。それらを修正するには、GUID を逆シリアル化して名前を取得し、正しい名前であることを確認できることを望んでいました。またはそれらの線に沿った何か。

レーベンシュタインの違いに基づいて類似度が 100% 未満である場合に冗長チェックを行う方法に関する推奨事項を誰かに教えてもらえますか (単語/フレーズが同じ長さの場合はハミングの違いで確認されます)。

ノート：

古いバージョンをすべて削除すると、バージョンがわからない可能性があります

パブリッシャーはすべてで同一になります

インストール場所はネットワークであるべきですが、ユーザーがローカルにコピーすることを好む保証はありません

文字列 (DNA シーケンス) のすべての可能な文字列の組み合わせを生成するアルゴリズムはありますか (最大のミスマッチ、最大のハミング距離)。

アルファベットは{A,C,T,G}です。

文字列AGCCと Mismatches の最大数の例2:

考えられるアプローチの 1 つは、特定の文字列のすべての順列を含むセットを生成し、それらを反復処理して、ハミング距離が本来よりも大きいすべての文字列を削除することです。

このアプローチは、指定された 20 文字の文字列と最大ハミング距離 5 によって、非常にリソースを消費します。

そのための別のより効率的なアプローチ/実装はありますか?

2 つのバイナリ行列間のハミング距離を計算するにはどうすればよいですか?

例えば：

本当にありがとう！

これらの文字列のバイナリを含むデータベースがあります

だから、私はこれと同様のバイナリ文字列を持っていたレコードを見つけたい:

ご覧のとおり、レコード番号 1 の関連性は 98% です。レコード番号 2 の関連性は 70% で、レコード番号 3 の関連性はわずか 45% です。

これは巨大なデータベース (200.000 レコード) です...