6

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

384:w2mhnFnJF47jDnunEk3SlbJJ+SGfOypAYJwsn3gdqymefD4kkAGxqCfOTPi0ND:wemfOGxqCfOTPi0ND

它们可以分为三个部分（在冒号上拆分字符串）：

  1. 块大小：384在上面的哈希中
  2. 第一个签名：w2mhnFnJF47jDnunEk3SlbJJ+SGfOypAYJwsn3gdqymefD4kkAGxqCfOTPi0ND
  3. 第二个签名：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

还可以计算两个哈希之间的归一化相似度得分（请参阅此处的详细信息）。

我想根据这些哈希值找到任何两个相似度超过 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 x 64 ≃ 19），并且它的正常编辑距离算法没有针对长搜索词进行优化（使用蛮力方法一旦达到距离限制，就不会切断计算。）也就是说，可能是我的查询没有针对我想做的事情进行优化，所以请不要犹豫，纠正我。

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

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

任何帮助/理论/参考/代码或线索都值得赞赏。

4

1 回答 1

3

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

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

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

于 2016-02-24T01:48:17.980 回答