4

長さ 32 ビットの数十万のスパース ビット文字列があります。

それらに対して最近傍検索を行いたいのですが、ルックアップのパフォーマンスが重要です。さまざまなアルゴリズムを調べてきましたが、バイナリ文字列ではなくテキスト文字列を対象としているようです。局所的に敏感なハッシングまたはスペクトルハッシングのいずれかが良い候補と思われるか、圧縮を調べることができると思います。これらのいずれかが私のビット文字列の問題にうまく機能しますか? 任意の指示やガイダンスをいただければ幸いです。

4

2 に答える 2

3

この問題に対処する論文に出くわしました。

ランダム化されたアルゴリズムと NLP: 高速名詞クラスタリングのための局所性に敏感なハッシュ関数の使用(Ravichandran et al, 2005)

基本的な考え方は、Denis の回答 (ビットのさまざまな順列で辞書式に並べ替える) に似ていますが、トピックに関する記事の追加のアイデアや参照が多数含まれています。

実際には、私が見つけたhttps://github.com/soundcloud/cosine-lsh-join-sparkに実装されています。

于 2016-02-19T11:45:50.690 に答える
3

これは、高速で簡単な方法ですが、より多くのメモリを犠牲にしてパフォーマンスを向上させる方法です。

In: 配列 Uint X[]、たとえば 1M 32 ビット ワード
欲しい: 関数near( Uint q )--> 小さい jhammingdist( q, X[j] )
方法: qsortedXで二分探索し、その周りのブロックを線形探索します。
擬似コード:

def near( q, X, Blocksize=100 ):
    preprocess: sort X
    Uint* p = binsearch( q, X )  # match q in leading bits
    linear-search Blocksize words around p
    return the hamming-nearest of these.

これは高速 です。サイズ 100 のブロックで 100 万ワード + 最も近いハミングディストをバイナリ検索すると、私の Mac ppc では 10 us 未満で済みます。(これはキャッシュに大きく依存します — 走行距離は異なります。)

これは、真に最も近い X[j] を見つけるのにどれくらい近いでしょうか? 私は実験することしかできず、数学を行うことはできません:
1M のランダムな単語での 1M のランダムなクエリの場合、最も近い一致は平均で 4 ～ 5 ビット離れていますが、真に最も近い場合は 3 ビット離れています (線形スキャンすべて 1M):

near32  N 1048576  Nquery 1048576  Blocksize 100 
binary search, then nearest +- 50
7 usec
distance distribution: 0 4481 38137 185212  443211 337321 39979 235  0

near32  N 1048576  Nquery 100  Blocksize 1048576 
linear scan all 1048576
38701 usec
distance distribution: 0 0 7 58  35 0

ブロックサイズを 50 と 100 にしてデータを実行し、一致距離がどのように低下​​するかを確認します。

さらに近づけるには、2 倍のメモリを犠牲にして、 の上位/下位ハーフワードを入れ替え
たコピーXswapを作成し、より良い方を返します。X

near( q, X, Blocksize )
near( swap q, Xswap, Blocksize )

多くのメモリを使用すると、より多くのビットシャッフルされた のコピーX、たとえば 32 回転を使用できます。
Nshuffle と Blocksize によってパフォーマンスがどのように変化するかはわかりません — LSH 理論家への質問です。

(追加): 320 ビット、10 ワードなどのビット文字列をほぼ一致させるには、10 個のポインターの配列を作成し、ワード 0、ワード 1 ... で並べ替え、上記のように binsearch でブロックを検索します。

nearest( query word 0, Sortedarray0, 100 ) -> min Hammingdist e.g. 42 of 320
nearest( query word 1, Sortedarray1, 100 ) -> min Hammingdist 37
nearest( query word 2, Sortedarray2, 100 ) -> min Hammingdist 50
...
-> e.g. the 37.

もちろん、これは単一の単語が近くにない類似一致を見逃しますが、非常に単純で、並べ替えとビン検索は非常に高速です。ポインター配列は、データ ビットとまったく同じスペースを占有します。100 ワード、3200 ビットでもまったく同じように機能します。
ただし、これは 0 ビットと 1 ビットの数がほぼ等しい場合にのみ機能し、99 % 0 ビットでは機能しません。

于 2012-04-15T16:06:44.800 に答える