搜索数百万个模糊哈希的最佳方法

Question

我在数据库表中有大约一千万个文件的spamsum复合哈希值,我想找到彼此相似的文件.Spamsum哈希由两个最大64字节的CTPH哈希组成,它们看起来像这样:

384:w2mhnFnJF47jDnunEk3SlbJJ+SGfOypAYJwsn3gdqymefD4kkAGxqCfOTPi0ND:wemfOGxqCfOTPi0ND

它们可以分为三个部分(在冒号上分割字符串):

1. 块大小:384在上面的哈希中
2. 第一个签名: w2mhnFnJF47jDnunEk3SlbJJ+SGfOypAYJwsn3gdqymefD4kkAGxqCfOTPi0ND
3. 第二个签名: wemfOGxqCfOTPi0ND

块大小是指第一个签名的块大小,第二个签名的块大小是第一个签名的块大小(此处:384 x 2 = 768).每个文件都有这些复合哈希中的一个,这意味着每个文件都有两个具有不同块大小的签名.

只有当它们的块大小相对应时,才能比较spamsum签名.也就是说,上面的复合哈希可以与包含块大小为384或768的签名的任何其他复合哈希进行比较.具有相似块大小的哈希的签名字符串的相似性可以作为两者之间相似性的度量.哈希表示的文件.

所以如果我们有:

• file1.blk2 = 768
• file1.sig2 = wemfOGxqCfOTPi0ND
• file2.blk1 = 768
• file2.sig1 = LsmfOGxqCfOTPi0ND

通过计算两个签名的一些加权编辑距离(如Levenshtein距离),我们可以了解两个文件的相似程度.这两个文件看起来非常相似.

leven_dist(file1.sig2, file2.sig1) = 2

还可以计算两个哈希值之间的归一化相似度得分(详见此处).

我想找到基于这些哈希值超过70%相似的任何两个文件,并且我非常喜欢使用可用的软件包(或API/SDK),尽管我不怕编码通过问题.

我试图打破哈希并使用Lucene(4.7.0)索引它们,但搜索似乎缓慢而乏味.这是我尝试过的Lucene查询的示例(对于每个单一签名 - 每个哈希两次并使用区分大小写的KeywordAnalyzer):

(blk1:768 AND sig1:wemfOGxqCfOTPi0ND~0.7) OR (blk2:768 AND sig2:wemfOGxqCfOTPi0ND~0.7)

似乎Lucene的速度非常快Levenshtein自动机不接受超过2的编辑距离限制(我需要它支持高达0.7 x64≃19)并且它的正常编辑距离算法不适用于长搜索术语(使用的强力方法)一旦达到距离限制,就不会切断计算.)也就是说,可能是我的查询没有针对我想做的事情进行优化,所以请不要犹豫,纠正我.

我想知道我是否可以使用Lucene提供的任何算法来完成我所需要的,而不是直接计算编辑距离.我听说BK树是索引此类搜索的最佳方式,但我不知道算法的可用实现(Lucene是否使用了这些？).我也听说过一个可能的解决方案是使用n-gram方法缩小搜索列表的范围,但我不确定如何在包容性和速度方面编辑距离计算(我很确定Lucene支持那个).顺便说一句,有没有办法让Lucene在并行模式下运行术语搜索？

鉴于我使用Lucene仅预先匹配哈希并且我稍后使用适当的算法计算真实相似度得分,我只需要一种至少与相似性得分计算中使用的Levenshtein距离一样包容的方法 - 即,我不希望预匹配方法排除将被评分算法标记为匹配的哈希值.

任何帮助/理论/参考/代码或线索开始是值得赞赏的.

Answer 1

这不是问题的明确答案，但从那时起我尝试了多种方法。我假设哈希值保存在数据库中，但这些建议对于内存中的数据结构也仍然有效。

1. 将所有签名（每个哈希 2 个）及其相应的块大小保存在单独的子表中。由于只有相同大小的签名才能相互比较，因此您可以在开始比较签名之前按块大小过滤表。
2. 将所有超过三个字符的重复序列减少到三个字符（'bbbbb' -> 'bbb'）。Spamsum 的比较算法会自动执行此操作。
3. Spamsum使用7个滚动窗口来比较签名，并且在消除过多的重复后不会比较任何两个没有7个字符重叠的签名。如果您使用的数据库支持列表/数组作为字段，请创建一个字段，其中包含从每个签名中提取的所有可能的 7 字符序列的列表。然后创建您可以在此字段上访问的最快的精确匹配索引。在尝试找到两个签名的距离之前，首先尝试在该字段上进行精确匹配（有共同的七克吗？）。
4. 我实验的最后一步是将签名及其七元模型保存为二部图的两种模式，将图投影为单一模式（仅由哈希组成），然后仅在具有相似块的相邻节点上计算编辑距离尺寸。

上述步骤进行了良好的预匹配，并大大减少了每个签名必须比较的签名数量。只有在这些之后才必须计算修改后的 Levenshtein/Damreau 距离。