0

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

0 から n-1 までのすべての i に対して Pr(bi=0)、Pr(bi=1)。

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

4

5 に答える 5

2

Google は、この論文で、k=3、n=64、N=2^34 (コーパスがはるかに大きく、ビット フリップが少なく、フィンガープリントが大きい) について、この問題の解決策を示しています。基本的な考え方は、k が小さい場合、n/k は非常に大きいため、並べ替えられたビット順序でいくつかのテーブルを作成した場合、近くのフィンガープリントには比較的長い共通のプレフィックスが必要であると予想されます。ただし、n/k がかなり小さいため、うまくいくかどうかはわかりません。

于 2011-06-14T02:29:48.360 に答える
1

量子計算を使用して、検索プロセスを高速化すると同時に、必要なステップ数を最小限に抑えることができます。グローバーの検索アルゴリズムは、検索問題に二次的な速度を提供するので、あなたにとって十分に役立つと思います.....

于 2011-06-13T08:50:01.017 に答える
1

「ルックアップ」とは、ファイル全体で指定された番号を検索し、一致する可能性のあるそれぞれについて「ルックアップ」を繰り返すことを意味する場合、ファイル全体を一度読み込んで、各エントリのハミング距離をチェックする方が高速です。指定された番号に移動します。そうすれば、ファイルを C(n 1) + C(n 2) + C(n 3)...+C(n,k) 回ではなく 1 回だけ読み取ることができます。

于 2011-02-15T01:36:24.177 に答える
0

アプリケーションで大規模な前処理を行う余裕がある場合は、n ビットの数値を生成するときに、その数値から最大で k 離れた他のすべての数値を計算し、ルックアップ テーブルに格納することができます。マップのようなものになります>。riri は、メモリに収まると主張しているので、ハッシュ テーブルはうまく機能するかもしれませんが、それ以外の場合は、Map に B+ ツリーが必要になるでしょう。もちろん、これは前に述べたようにコストがかかりますが、事前に行うことができれば、後で O(1) または O(log(N) + log(2^k)) のいずれかで高速に検索できます。

于 2011-02-15T01:28:12.600 に答える
0

おそらく、ハミング距離によって、セット内の次に近い数値へのリンクを含むグラフとして保存できます。その後、別の数値へのリンクの 1 つをたどって、次に近い数値を見つけるだけです。次に、インデックスを使用して、ファイル オフセットごとに数値がどこにあるかを追跡します。これにより、近くにあるグラフを見つける必要があるときに Y のグラフを検索する必要がなくなります。

また、2^24 の数字があると言っていますが、これは wolfram alpha (http://www.wolframalpha.com/input/?i=2^24+*+32+bits) によると 64MB しかありません。アクセスを高速化するために、すべてをRAMに入れていただけますか？おそらく、それはあなたのマシンのキャッシングで自動的に起こるでしょうか?

于 2011-02-15T01:12:37.933 に答える