83

問題：

符号なし32ビット整数の大きな（〜1億）リスト、符号なし32ビット整数入力値、および最大ハミング距離が与えられた場合、入力値の指定されたハミング距離内にあるすべてのリストメンバーを返します。

リストを保持するための実際のデータ構造はオープンであり、パフォーマンス要件によってメモリ内ソリューションが決まります。データ構造を構築するためのコストは二次的であり、データ構造をクエリするための低コストが重要です。

例：

For a maximum Hamming Distance of 1 (values typically will be quite small)

And input: 
00001000100000000000000001111101

The values:
01001000100000000000000001111101 
00001000100000000010000001111101 

should match because there is only 1 position in which the bits are different.

11001000100000000010000001111101

should not match because 3 bit positions are different.

これまでの私の考え：

ハミング距離が0の縮退した場合は、ソートされたリストを使用して、特定の入力値の二分探索を実行します。

ハミング距離が1だけの場合、元の入力の各ビットを反転して、上記を32回繰り返すことができます。

（リスト全体をスキャンせずに）ハミング距離が1より大きいリストメンバーを効率的に検出するにはどうすればよいですか。

4

7 に答える 7

115

質問：ハミング距離d（x、y）について私たちは何を知っていますか？

答え：

  1. 負ではありません：d（x、y）≥0
  2. 同一の入力の場合はゼロのみです：d（x、y）=0⇔x= y
  3. 対称です：d（x、y）= d（y、x）
  4. 三角不等式d（x、z）≤d（x、y）+ d（y、z）に従います

質問：なぜ私たちは気にするのですか？

回答：ハミング距離が距離空間の距離であることを意味するためです。距離空間にインデックスを付けるためのアルゴリズムがあります。

また、空間がユークリッド空間ではなく距離空間であるという知識を備えた、一般的な「空間インデックス」のアルゴリズムを検索することもできます。この主題に関する多くの本は、ハミング距離などのメトリックを使用した文字列の索引付けをカバーしています。

脚注：固定幅の文字列のハミング距離を比較している場合は、アセンブリまたはプロセッサの組み込み関数を使用することで、パフォーマンスを大幅に向上させることができる場合があります。たとえば、GCC（手動）では、次のようにします。

static inline int distance(unsigned x, unsigned y)
{
    return __builtin_popcount(x^y);
}

次に、SSE4aを搭載したコンピューター用にコンパイルしていることをGCCに通知すると、オペコードは2、3に減るはずです。

編集：多くの情報源によると、これは通常のマスク/シフト/追加コードよりも遅い場合があります。ベンチマークは、私のシステムでは、CバージョンがGCCよりも__builtin_popcount約160％優れていることを示しています。

補遺：私は自分で問題に興味があったので、線形検索、BKツリー、VPツリーの3つの実装のプロファイルを作成しました。VPツリーとBKツリーは非常に似ていることに注意してください。BKツリーのノードの子は、ツリーの中心からそれぞれ一定の距離にあるポイントを含むツリーの「シェル」です。VPツリーのノードには2つの子があり、1つはノードの中心を中心とする球内のすべてのポイントを含み、もう1つは外側のすべてのポイントを含みます。したがって、VPノードは、多くの細かいシェルではなく、2つの非常に厚い「シェル」を持つBKノードと考えることができます。

結果は私の3.2GHzPCでキャプチャされ、アルゴリズムは複数のコアを利用しようとはしません（これは簡単なはずです）。100Mの疑似乱数整数のデータベースサイズを選択しました。結果は、距離1..5の場合は1000クエリ、6..10および線形検索の場合は100クエリの平均です。

  • データベース：1億の疑似乱数整数
  • テストの数：距離1..5の場合は1000、距離6..10の場合は100、線形
  • 結果：クエリヒットの平均数（非常に概算）
  • 速度：1秒あたりのクエリ数
  • カバレッジ：クエリごとに調査されたデータベースの平均パーセンテージ
                --BKツリー----VPツリー---線形-
距離の結果SpeedCovSpeed Cov Speed Cov
1 0.90 3800 0.048％4200 0.048％
2 11300 0.68％330 0.65％
3130 56 3.8％63 3.4％
4970 18 12％22 10％
5 5700 8.5 26％10 22％
6 2.6e4 5.2 42％6.0 37％
7 1.1e5 3.7 60％4.1 54％
8 3.5e5 3.0 74％3.2 70％
9 1.0e6 2.6 85％2.7 82％
10 2.5e6 2.3 91％2.4 90％
任意の2.2100％

あなたのコメントで、あなたは次のように述べました：

BKツリーは、ルートノードが異なるBKツリーの束を生成し、それらを分散させることで改善できると思います。

これが、VPツリーがBKツリーよりも（わずかに）パフォーマンスが優れている理由だと思います。「浅い」ではなく「深い」ので、より少ないポイントに対してよりきめ細かい比較を使用するのではなく、より多くのポイントと比較します。高次元の空間では、その違いはもっと極端だと思います。

最後のヒント：ツリー内のリーフノードは、線形スキャンの整数のフラット配列である必要があります。小さなセット（おそらく1000ポイント以下）の場合、これはより高速でメモリ効率が高くなります。

于 2011-06-17T19:07:47.743 に答える
14

入力番号を232ビットのビットセットで表すソリューションを作成したので、O（1）で特定の番号が入力に含まれているかどうかを確認できます。次に、照会された数値と最大距離について、その距離内のすべての数値を再帰的に生成し、ビットセットと照合します。

たとえば、最大距離5の場合、これは242825の数値です（合計d =0から5 {32はdを選択}）。比較のために、たとえば、Dietrich EppのVPツリーソリューションは、1億の数値の22％、つまり2,200万の数値を通過します。

私は、Dietrichのコード/ソリューションを基礎として使用して、ソリューションを追加し、彼と比較しました。最大距離が10の場合の、1秒あたりのクエリ数での速度は次のとおりです。

Dist     BK Tree     VP Tree         Bitset   Linear

   1   10,133.83   15,773.69   1,905,202.76   4.73
   2      677.78    1,006.95     218,624.08   4.70
   3      113.14      173.15      27,022.32   4.76
   4       34.06       54.13       4,239.28   4.75
   5       15.21       23.81         932.18   4.79
   6        8.96       13.23         236.09   4.78
   7        6.52        8.37          69.18   4.77
   8        5.11        6.15          23.76   4.68
   9        4.39        4.83           9.01   4.47
  10        3.69        3.94           2.82   4.13

Prepare     4.1s       21.0s          1.52s  0.13s
times (for building the data structure before the queries)

距離が短い場合、ビットセットソリューションは4つのうちではるかに高速です。質問の著者であるエリックは、関心のある最大の距離はおそらく4〜5であると以下にコメントしました。当然、私のビットセットソリューションは、距離が長くなると遅くなり、線形探索よりもさらに遅くなります（距離32の場合、2 32の数値を通過します）。しかし、距離9の場合でも、簡単にリードします。

また、ディートリッヒのテストを変更しました。上記の各結果は、アルゴリズムに少なくとも3つのクエリと、約15秒で可能な限り多くのクエリを解決させるためのものです（少なくとも10秒になるまで、1、2、4、8、16などのクエリでラウンドを行います合計で合格）。それはかなり安定していて、たった1秒間で同じような数値が得られます。

私のCPUはi7-6700です。私のコード（Dietrichのものに基づく）はここにあります（少なくとも今のところそこにあるドキュメントを無視し、それについて何をすべきかわからないが、tree.cすべてのコードと私test.batがどのようにコンパイルして実行したかを示しています（Dietrichのもののフラグを使用しましたMakefile）） 。私の解決策へのショートカット。

注意点：クエリ結果に含まれる数値は1回だけなので、入力リストに重複する数値が含まれている場合は、それが望ましい場合と望ましくない場合があります。質問の著者であるエリックの場合、重複はありませんでした（以下のコメントを参照）。いずれにせよ、このソリューションは、入力に重複がないか、クエリ結果に重複がないか、必要がない人に適している可能性があります（純粋なクエリ結果は、目的を達成するための手段にすぎない可能性があります。他のコードは、数値を別のものに変換します。たとえば、数値を、その数値がハッシュであるファイルのリストにマッピングするマップなどです。

于 2016-09-21T04:20:59.243 に答える
4

一般的なアプローチ（少なくとも私には一般的です）は、ビット文字列をいくつかのチャンクに分割し、これらのチャンクをクエリして、フィルター前の手順として完全に一致するようにすることです。ファイルを操作する場合は、チャンクと同じ数のファイル（たとえば、ここでは4つ）を作成し、各チャンクを前に並べ替えてから、ファイルを並べ替えます。バイナリ検索を使用でき、ボーナスのために一致するチャンクの上下で検索を拡張することもできます。

次に、返された結果に対してビット単位のハミング距離の計算を実行できます。これは、データセット全体のより小さなサブセットにすぎないはずです。これは、データファイルまたはSQLテーブルを使用して実行できます。

要約すると、DBまたはファイルに32ビットの文字列がたくさんあり、「クエリ」ビット文字列から3ビット以下のハミング距離内にあるすべてのハッシュを検索するとします。

  1. 4つの列を持つテーブルを作成します。それぞれに32ビットハッシュの8ビット（文字列または整数として）スライス、islice 1〜4が含まれます。または、ファイルを使用する場合は、4つのファイルを作成します。各「行」の前に1つの「islice」

  2. qslice1から4と同じ方法でクエリビット文字列をスライスします。

  3. のいずれかになるようにこのテーブルをクエリしますqslice1=islice1 or qslice2=islice2 or qslice3=islice3 or qslice4=islice4。8 - 1これにより、クエリ文字列から7ビット（）以内にあるすべての文字列が得られます。ファイルを使用する場合は、4つの並べ替えられたファイルのそれぞれでバイナリ検索を実行して、同じ結果を取得します。

  4. 返されたビット文字列ごとに、クエリビット文字列を使用してペアごとに正確なハミング距離を計算します（DBまたは並べ替えられたファイルのいずれかからの4つのスライスからインデックス側のビット文字列を再構築します）

ステップ4の操作の数は、テーブル全体の完全なペアワイズハミング計算よりもはるかに少なく、実際には非常に効率的です。さらに、並列処理を使用してより高速にする必要があるため、ファイルを小さなファイルに簡単に分割できます。

もちろん、あなたの場合は、ある種の自己結合、つまり、互いにある程度の距離内にあるすべての値を探しています。同じアプローチがIMHOでも機能しますが、開始チャンクを共有し、結果のクラスターのハミング距離を計算する順列（ファイルまたはリストを使用）の開始点から上下に拡張する必要があります。

ファイルではなくメモリで実行している場合、100M32ビット文字列データセットは4GBの範囲になります。したがって、4つの並べ替えられたリストには約16GB以上のRAMが必要になる場合があります。代わりにメモリマップトファイルで優れた結果が得られますが、同様のサイズのデータ​​セットではRAMを少なくする必要があります。

利用可能なオープンソースの実装があります。スペースで最高のものは、Moz、C ++によってSimhashに対して行われたものですが、32ビットではなく64ビットの文字列用に設計されたIMHOです。

この制限されたハッピング距離アプローチは、モーゼスチャリカルによって、その「simhash」独創的な論文と対応するGoogle特許で最初にAFAIKで説明されました。

  1. ハミング空間での近似最近傍探索

[...]

それぞれdビットで構成されるビットベクトルが与えられた場合、ビットのN = O（n 1 /（1+））ランダム順列を選択します。ランダム置換σごとに、ビットベクトルのソートされた順序Oσを、σによって置換されたビットの辞書式順序で維持します。クエリビットベクトルqが与えられると、次のようにして近似最近傍を見つけます。

各順列σについて、Oσで二分探索を実行して、qに最も近い2つのビットベクトルを見つけます（σによって順列されたビットによって取得される辞書式順序で）。ここで、qに一致する最長のプレフィックスの長さの順に、バイナリ検索によって返された位置の上下の要素を調べる、ソートされた順序Oσのそれぞれで検索します。

Monika Henzigerは、彼女の論文「ほぼ重複するWebページの検索：アルゴリズムの大規模な評価」でこれを拡張しました。

3.3アルゴリズムCの結果

各ページのビット文字列を重複しない12個の4バイト部分に分割し、20B個を作成し、少なくとも1個の共通部分を持つすべてのページのC類似度を計算しました。このアプローチでは、最大11の違い、つまりC類似度373のページのすべてのペアを見つけることが保証されていますが、大きな違いがある場合は一部を見逃す可能性があります。

これは、Gurmeet Singh Manku、Arvind Jain、およびAnishDasSarmaによる論文「 DetectingNear-DuplicatesforWebCrawlings 」でも説明されています。

  1. ハミング距離の問題

定義：fビットフィンガープリントのコレクションとクエリフィンガープリントFが与えられた場合、既存のフィンガープリントが最大kビットでFと異なるかどうかを識別します。（上記の問題のバッチモードバージョンでは、単一のクエリフィンガープリントではなく、一連のクエリフィンガープリントがあります）

[...]

直感：2dfビットの真にランダムなフィンガープリントのソートされたテーブルを考えてみましょう。表の最上位のdビットだけに注目してください。これらのdビット数のリストは、（a）かなりの数の2 dビットの組み合わせが存在し、（b）非常に少数のdビットの組み合わせが複製されるという意味で「ほぼカウンター」になります。一方、最下位のf −dビットは「ほぼランダム」です。

ここで、| d −d|となるようにdを選択します。は小さな整数です。テーブルはソートされているため、d個の最上位ビット位置でFに一致するすべてのフィンガープリントを識別するには単一のプローブで十分です。| d −d|以降 が少ない場合、そのような一致の数も少ないと予想されます。一致するフィンガープリントごとに、最大でkビット位置でFと異なるかどうかを簡単に判断できます（これらの違いは、当然、f − dの最下位ビット位置に制限されます）。

上記の手順は、kビット位置でFとは異なる既存のフィンガープリントを見つけるのに役立ちます。これらはすべて、Fの最下位f − dビットに制限されます。これにより、かなりの数のケースが処理されます。すべてのケースをカバーするには、次のセクションで正式に概説するように、少数の追加のソート済みテーブルを作成するだけで十分です。

注：関連するDBのみの質問に対して同様の回答を投稿しました

于 2017-11-27T19:42:29.730 に答える
2

指定されたハミング距離内で元のリストのすべての可能なバリエーションを事前に計算し、それをブルームフィルターに保存することができます。これはあなたに速い「いいえ」を与えますが、必ずしも「はい」についての明確な答えではありません。

「はい」の場合、ブルームフィルターの各位置に関連付けられているすべての元の値のリストを保存し、一度に1つずつ調べます。速度とメモリのトレードオフのために、ブルームフィルターのサイズを最適化します。

すべてが正確に機能するかどうかはわかりませんが、実行時RAMを焼き付けて、事前計算に非常に長い時間を費やすことをいとわない場合は、良いアプローチのようです。

于 2011-06-17T18:52:51.580 に答える
1

リストを並べ替えてから、その並べ替えられたリストで、ハミング距離内のさまざまな可能な値に対してバイナリ検索を実行するのはどうですか？

于 2011-06-17T18:39:58.853 に答える
1

この問題を解決するための1つの可能なアプローチは、素集合データ構造を使用することです。アイデアは、同じセット内のハミング距離<=kのリストメンバーをマージすることです。アルゴリズムの概要は次のとおりです。

  • 各リストメンバーについて、ハミング距離<=kで可能なすべての値を計算します。k = 1の場合、32個の値があります（32ビット値の場合）。k = 2の場合、32 + 32*31/2の値。

    • 計算された値ごとに、それが元の入力にあるかどうかをテストします。サイズ2^32の配列またはハッシュマップを使用して、このチェックを行うことができます。

    • 値が元の入力にある場合は、リストメンバーとの「和集合」操作を実行します。

    • 実行されたユニオン操作の数を変数に保持します。

N個の互いに素なセット（Nは入力内の要素の数）でアルゴリズムを開始します。ユニオン演算を実行するたびに、互いに素なセットの数が1つ減ります。アルゴリズムが終了すると、互いに素なセットのデータ構造には、ハミング距離<=kのすべての値が互いに素なセットにグループ化されます。この素集合データ構造は、ほぼ線形時間で計算できます。

于 2015-04-06T15:25:33.833 に答える
1

簡単なアイデアは次のとおりです。外部構造の最初の3つのレベルでバケット境界を追跡しながら、100mの入力整数のバイト単位の基数ソートを実行します。最も重要なバイトが最初になります。

クエリを実行するには、距離バジェットdと入力ワードから始めますw。バイト値を持つトップレベルの各バケットについて、との上位バイトの間bのハミング距離を計算します。：のバジェットでそのバケットを再帰的に検索します。つまり、各バイト値について、との2番目のバイトの間のハミング距離とします。の予算で第3層を再帰的に検索します。d_0bwd - d_0b'd_1b'wd - d_0 - d_1

バケットがツリーを形成することに注意してください。予算がマイナスになったときはいつでも、そのサブツリーの検索を停止してください。距離バジェットを吹き飛ばさずにリーフに再帰的に下降する場合、そのリーフ値は出力の一部である必要があります。

外部バケット境界構造を表す1つの方法は次のとおりです。長さ16_777_216（= (2**8)**3 = 2**24）の配列があります。ここで、indexの要素iは、範囲[256 * i、256 * i+255]の値を含むバケットの開始インデックスです。そのバケットの終わりを超えたインデックス1を見つけるには、インデックスi + 1を調べます（または、i + 1 = 2 ** 24の場合は配列の終わりを使用します）。

メモリバジェットは、100m*ワードあたり4バイト=入力の場合は400MB、アドレスあたり2 ** 24 *4バイト=インデックス構造の場合は64MiB、つまり合計で0.5ギガのシャイです。インデックス構造は、生データに対して6.25％のオーバーヘッドです。もちろん、インデックス構造を構築したら、各入力ワードの最下位バイトを格納するだけで済みます。他の3つはインデックスに暗黙的に含まれているため、合計で〜（64 + 50）MBになります。

入力が均一に分散されていない場合は、入力ワードのビットを（単一の、普遍的に共有される）順列で並べ替えて、すべてのエントロピーをツリーの最上部に向けることができます。そうすれば、最初のレベルのプルーニングにより、検索スペースのより大きなチャンクが排除されます。

私はいくつかの実験を試みましたが、これは線形探索とほぼ同じように機能し、場合によってはさらに悪化します。この派手なアイデアはこれだけです。まあ、少なくともそれはメモリ効率が良いです。

于 2020-05-21T12:59:16.747 に答える