我有一个数据库表中大约1000万个文件的spamsum复合哈希值，我想找到彼此相当相似的文件。Spamsum哈希由两个最大64字节的CTPH哈希组成，它们看起来像这样:
384:w2mhnFnJF47jDnunEk3SlbJJ+SGfOypAYJwsn3gdqymefD4kkAGxqCfOTPi0ND:wemfOGxqCfOTPi0ND
它们可以分为三个部分(用冒号分隔字符串):
- 块大小:
384在上面的哈希 - 第一个签名:
w2mhnFnJF47jDnunEk3SlbJJ+SGfOypAYJwsn3gdqymefD4kkAGxqCfOTPi0ND - 第二个签名:
wemfOGxqCfOTPi0ND
块大小指的是第一个签名的块大小，第二个签名的块大小是第一个签名的两倍(这里:384 × 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 x 64≃19)，并且其正常的编辑距离算法没有针对长搜索词进行优化(使用的蛮力方法不会在达到距离限制后切断计算)。也就是说，可能是我的查询没有针对我想要做的事情进行优化，所以不要犹豫，请纠正我。
我想知道我是否可以完成我需要使用任何Lucene提供的算法，而不是直接计算编辑距离。我听说bk树是索引此类搜索的最佳方式，但我不知道该算法的可用实现(Lucene是否使用这些?)。我还听说一个可能的解决方案是使用n-gram方法缩小搜索列表，但我不确定这与编辑距离计算在包容性和速度方面相比如何(我很确定Lucene支持这一点)。顺便说一句，有没有办法让Lucene在并行模式下运行术语搜索?
考虑到我只使用Lucene来预匹配哈希，并且我稍后使用适当的算法来计算真正的相似性得分，我只需要一个至少与相似性得分计算中使用的Levenshtein距离一样具有包容性的方法——也就是说，我不希望预匹配方法排除将被评分算法标记为匹配的哈希。
任何帮助/理论/参考/代码或线索开始是感激的。
这不是对这个问题的明确答案，但从那以后我尝试了许多方法。我假设哈希值保存在数据库中，但是这些建议对于内存中的数据结构也是有效的。
- 将所有签名(每个哈希值2个)及其相应的块大小保存在单独的子表中。由于只有相同大小的签名才能相互比较，所以在比较签名之前可以根据块大小对表进行过滤。
- 将所有超过三个字符的重复序列减少到三个字符('bbbbb' -> 'bbb')。
- Spamsum使用7个滚动窗口来比较签名，并且在消除过多重复后不会比较任何两个不具有7个字符重叠的签名。如果您正在使用支持列表/数组作为字段的数据库，则使用从每个签名中提取的所有可能的7个字符序列的列表创建一个字段。然后在此字段上创建您可以访问的最快的精确匹配索引。在试图找到两个签名的距离之前，首先尝试在这个域中做精确匹配(任何7克的共同点?)。
- 我正在试验的最后一步是将签名及其7克保存为二部图的两种模式，将图投影为单模态(仅由哈希组成)，然后仅在具有相似块大小的相邻节点上计算Levenshtein距离。
以上步骤进行了很好的预匹配，大大减少了每个签名需要比较的签名数量。只有在这些之后，才需要计算修改后的Levenshtein/Damreau距离