4

我有数十万个长度为 32 位的稀疏位串。

我想对它们进行最近邻搜索，查找性能至关重要。我一直在阅读各种算法，但它们似乎针对的是文本字符串而不是二进制字符串。我认为本地敏感散列或频谱散列似乎是不错的候选者，或者我可以研究压缩。这些中的任何一个都可以很好地解决我的位串问题吗？任何方向或指导将不胜感激。

4

2 回答 2

3

这是一种快速简便的方法，然后是一种以更多内存为代价的具有更好性能的变体。

在：数组 Uint X[]，例如 1M 32 位字
想要：一个函数near( Uint q )--> j with smallhammingdist( q, X[j] )
方法：q在 sorted 中进行二分搜索X，然后在其周围线性搜索一个块。
伪代码：

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.

这很快—— 在我的 Mac ppc 上，在大小为 100 的块中二进制搜索1M 单词 + 最近的 hammingdist 需要 < 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 运行您的数据，以查看匹配距离如何下降。

为了更接近，以两倍的内存为代价，
制作一个交换了上/下半字的副本，并返回更好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.

这当然会错过没有一个单词接近的近似匹配，但它非常简单，并且排序和 binsearch 非常快。指针数组占用的空间与数据位完全相同。100 个字，3200 位将以完全相同的方式工作。
但是：这只有在 0 位和 1 位的数量大致相等时才有效，而不是 99 % 0 位。

于 2012-04-15T16:06:44.800 回答
3

我刚看到一篇解决这个问题的论文。

随机算法和 NLP：使用局部敏感散列函数进行高速名词聚类(Ravichandran et al, 2005)

基本思想类似于丹尼斯的回答（按不同的位排列按字典顺序排序），但它包括许多其他想法和有关该主题的文章的进一步参考。

它实际上是在我找到它的地方https://github.com/soundcloud/cosine-lsh-join-spark中实现的。

于 2016-02-19T11:45:50.690 回答