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

Question

我有 spamsum数据库表中大约一千万个文件的复合哈希，我想找到彼此相当相似的文件。 Spamsum 散列由两个最大 64 字节的 CTPH 散列组成，它们如下所示:

384:w2mhnFnJF47jDnunEk3SlbJJ+SGfOypAYJwsn3gdqymefD4kkAGxqCfOTPi0ND:wemfOGxqCfOTPi0ND

它们可以分为三个部分(将字符串拆分为冒号):

块大小:384在上面的哈希中

第一个签名:w2mhnFnJF47jDnunEk3SlbJJ+SGfOypAYJwsn3gdqymefD4kkAGxqCfOTPi0ND

第二个签名:wemfOGxqCfOTPi0ND

块大小是指第一个签名的块大小，第二个签名的块大小是第一个签名的两倍(此处:384 x 2 = 768)。每个文件都有这些复合散列之一，这意味着每个文件都有两个不同块大小的签名。

只有当它们的块大小对应时，才能比较垃圾邮件签名。也就是说，上面的复合散列可以与任何其他包含块大小为 384 或 768 的签名的复合散列进行比较。由哈希表示的文件。

所以如果我们有:

file1.blk2 = 768

file1.sig2 = wemfOGxqCfOTPi0ND

file2.blk1 = 768

file2.sig1 = LsmfOGxqCfOTPi0ND

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

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

还可以计算两个散列之间的归一化相似度得分(参见详细信息 here)。

我想根据这些哈希找到任何两个相似度超过 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的 incredibly fast Levenshtein automata不接受超过 2 的编辑距离限制(我需要它支持高达 0.7 x 64 ≃ 19)并且它的正常编辑距离算法没有针对长搜索词进行优化( the brute force method used does not cut off calculation once the distance limit is reached 。)也就是说，这可能是我的查询没有针对我想做的事情进行优化，所以请不要犹豫纠正我。

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

鉴于我仅使用 Lucene 来预匹配散列，并且我稍后使用适当的算法计算真实的相似度分数，我只需要一种至少与相似度分数计算中使用的 Levenshtein 距离具有包容性的方法——即，我不希望预匹配方法排除会被评分算法标记为匹配的哈希。

感谢任何帮助/理论/引用/代码或线索。

Answer 1

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

将所有签名(每个哈希 2 个)及其相应的块大小保存在单独的子表中。由于只能比较相同大小的签名，因此您可以在开始比较签名之前按块大小过滤表。

将超过三个字符的所有重复序列减少到三个字符('bbbbb' -> 'bbb')。 Spamsum 的比较算法会自动执行此操作。

Spamsum 使用滚动窗口 7 来比较签名，并且不会在消除过多重复后比较任何两个没有 7 字符重叠的签名。如果您使用的数据库支持列表/数组作为字段，请创建一个字段，其中包含从每个签名中提取的所有可能的 7 字符序列的列表。然后在此字段上创建您可以访问的最快的完全匹配索引。在尝试找到两个签名的距离之前，首先尝试对该字段进行精确匹配(任何 7 克共同点？)。

我正在试验的最后一步是将签名和它们的七克保存为二部图的两种模式，将图投影到单一模式(仅由散列组成)，然后仅在具有相似块的相邻节点上计算 Levenshtein 距离尺寸。

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