用于检测相似文档的Python算法

Question

我需要写一个模块来检测相似的文档。我看了很多关于文档指纹技术的论文，但我不知道怎么写代码或者实现这样的解决方案。这个算法应该能够处理中文、日文、英文和德文，或者说它应该不依赖于语言。我该怎么做呢？

Answer 1

其实我们可以在不进行分类的情况下，轻松找到相似的东西。可以试试这个O(n²)的方法，效果不错。

def jaccard_similarity(doc1, doc2):
    a = sets(doc1.split())
    b = sets(doc2.split())
    similarity = float(len(a.intersection(b))*1.0/len(a.union(b))) #similarity belongs to [0,1] 1 means its exact replica.
    return similarity

Answer 2

如果这些是纯文本文件，或者你有办法从文件中提取文本，你可以使用一种叫做“重叠片段”的技术。

首先，你需要为每个文件计算一个独特的哈希值。如果这些哈希值相同，那就说明文件是一样的。

如果不相同，你就需要把每个文件分成更小的部分，这些小部分就叫做“重叠片段”。

一旦你得到了这些重叠片段，你可以为每个片段计算一个身份哈希值，然后比较这些哈希值，以确定文件是否真的相同。

另一种方法是生成整个文件的n-gram（n元组），然后计算每个文件中相似的n-gram数量，并为每个文件生成一个加权分数。简单来说，n-gram就是把一个词拆成更小的部分。比如“apple”可以拆成“ a”、“ ap”、“app”、“ppl”、“ple”、“le ”。（这实际上是一个3-gram）不过，如果文件数量很多或者两个文件都很大，这种方法可能会消耗很多计算资源。当然，一些常见的n-gram，比如“the”、“ th”、“th ”等，需要降低它们的权重，以便得出更准确的分数。

我在我的博客上也写过关于这个的内容，帖子里有一些链接指向其他相关的文章，重叠片段 - 不仅仅是屋顶工人的专利。

祝你好运！

Answer 3

贝叶斯过滤器正是为了这个目的而设计的。这种技术在大多数识别垃圾邮件的工具中都能找到。

举个例子，来检测一种语言（来自 http://sebsauvage.net/python/snyppets/#bayesian）：

from reverend.thomas import Bayes
guesser = Bayes()
guesser.train('french','La souris est rentrée dans son trou.')
guesser.train('english','my tailor is rich.')
guesser.train('french','Je ne sais pas si je viendrai demain.')
guesser.train('english','I do not plan to update my website soon.')

>>> print guesser.guess('Jumping out of cliffs it not a good idea.')
[('english', 0.99990000000000001), ('french', 9.9999999999988987e-005)]

>>> print guesser.guess('Demain il fera très probablement chaud.')
[('french', 0.99990000000000001), ('english', 9.9999999999988987e-005)]

不过，它也可以用来检测你训练过的任何类型的内容，比如技术文本、歌曲、笑话等等。只要你能提供足够的材料，让这个工具学习你的文档是什么样子的。