1

(配列内のすべてのペアの中で) 共通セット ビットの最大数を持つ配列内のビット文字列のペアを見つけるアルゴリズムを見つけたいと考えています。配列内のビット文字列のすべてのペアを比較することでこれを実行できることはわかっていますが、これは O( n 2 ) です。より効率的なアルゴリズムはありますか? 理想的には、反復ごとに 1 つの入力ビット文字列を処理することで、アルゴリズムが段階的に機能するようにしたいと考えています。

たとえば、次のビット文字列の配列 (長さ 8) があるとします。

B1:01010001 
B2:01101010
B3:01101010
B4:11001010
B5:00110001

ここでの最適なペアはB2とB3で、4 つの共通セット ビットがあります。

そのようなアルゴリズムを説明しているように見える論文を見つけました (S. Taylor & T. Drummond (2011); " Binary Histogrammed Intensity Patches for Efficient and Robust Matching "; Int. J. Comput. Vis. 94:241–265),しかし、252ページからのこの説明がわかりません：

これは、再計算が必要な [ビット文字列] オーバーラップのみが、新しい親フィーチャのオーバーラップと、組み合わせ用に選択された 2 つのうちの 1 つであるルート内の他の [ビット文字列] であるため、反復ごとに段階的に更新できます。これにより、反復ごとに O(N 2 ) オーバーラップ比較が不要になり、通常サイズの 700 フィーチャのデータベースのフォレストを 1 秒未満で構築できます。

4

2 に答える 2

1

私の知る限り、Taylor＆Drummond（2011）は、共通セットビットの数が最も多い配列内のビット文字列のペアを見つけるためのO（ n）アルゴリズムを提供することを意図していません。彼らは、新しいビット文字列が配列に追加された後（および2つの古いビット文字列が削除された後）、そのような最良のペアのレコードをO（n）で更新できるという議論をスケッチします。

確かに、252ページのアルゴリズムの説明はあまり明確ではなく、O（n）でレコードを更新できるという彼らのスケッチの議論はせいぜい不完全であると思うので、なぜあなたが混乱しているのかがわかります。

とにかく、これが論文からアルゴリズム1を説明するための私の最善の試みです。

アルゴリズム

アルゴリズムはビット文字列の配列を取り、ルックアップツリーを構築します。ルックアップツリーはバイナリフォレスト（バイナリツリーのセット）であり、そのリーフは配列の元のビット文字列であり、内部ノードは新しいビット文字列です。ノードAがノードBの親である場合、A＆B = A（つまり、Aのすべての設定ビットはBにも設定されます）。

たとえば、入力がこのビット文字列の配列である場合：

ビット文字列の配列

次に、出力はルックアップツリーです。

ルックアップツリー

このホワイトペーパーで説明されているアルゴリズムは、次のように進行します。

  1. Rをビット文字列の初期セット（ルートセット）とします。

  2. RにパートナーがないRのビット文字列f1ごとに、そのパートナー（f1と共通のセットビット数が最も多いR − {f1}のビット文字列f2）を 見つけて記録し、それらのビット数を記録します。一般。

  3. Rに共通のセットビットを持つビット文字列のペアがない場合は、停止します。

  4. f1とf2を、共通セットビットの数が最も多いRのビット文字列のペアとします。

  5. p = f1＆f2をf1とf2の親とします。

  6. Rからf1とf2を削除します; Rにpを追加します。

  7. 手順2に進みます。

分析

配列に固定長のビット文字列がn個含まれているとします。次に、ステップ2がO（n 2）であり、O（n ）回の反復があるため、説明したアルゴリズムはO（n 3 ）です。これは、各反復でRから2つのビット文字列を削除し、1つ追加するためです。

この論文には、ステップ2がループの最初の部分でのみΩ（n 2）であり、他の反復では、 p "のパートナーとR内の他のビット文字列を見つけるだけでよいため、 O（ n ）であるという引数が含まれています。そのパートナーは、組み合わせのために選ばれた2人のうちの1人でした。」しかし、この議論は私には説得力がありません。他にそのようなビットストリングがO（1）しかないことは明らかではありません。（多分もっと良い議論がありますか？）

ビット文字列のすべてのペア間で共通のセットビットの数を格納することにより、アルゴリズムをO（n 2 ）に下げることができます。これには、O（n 2）の余分なスペースが必要です。

参照

  • S.テイラー＆T。ドラモンド（2011）。「効率的でロバストなマッチングのためのバイナリヒストグラム強度パッチ」。Int。J.計算。Vis。94：241–265。
于 2012-08-26T20:37:39.320 に答える
0

各ビット位置について、その位置がオンのセットとオフのセットの2つのセットを維持できます。たとえば、セットを2つの二分木に配置できます。

次に、2つの要素を持つ和集合が見つかるまで、7などのすべての組み合わせよりも、最初に8ビットすべてで集合和集合を実行します。

ここでの複雑さはビットサイズで指数関数的に増大しますが、それが小さくて修正されている場合、これは問題ではありません。

別の方法として、n個のkビット文字列をkD空間内のn個の点として見ることがあります。タスクは、最も近い2つの点を見つけることです。これを行うための幾何学的アルゴリズムはたくさんあります。

于 2012-08-26T21:43:47.580 に答える