我需要编写一个模块来检测相似的文档。我已经阅读了许多文件指纹技术和其他技术的论文，但是我不知道如何编写代码或者实现这样的解决方案。该算法应适用于中文，日文，英文和德文，或者与语言无关。我该怎么做？

解决方案

我们可以使用Python的stdlib或者最后研究difflib来编写代码。

它非常灵活，并具有查找字符串列表之间的差异并指出这些差异的算法。然后，我们可以使用get_close_matches()查找相似的单词：

>>> get_close_matches('appel', ['ape', 'apple', 'peach', 'puppy'])
['apple', 'ape']

这不是解决方案，但也许是一个开始。

我们需要使问题更具体。如果我们已经阅读了指纹文件，那么我们已经了解了工作原理，因此在此处描述常用方法将无济于事。如果我们还没有，还应该查阅有关"重复检测"的论文以及近年来来自Stanford，Google，Yahoo和MS的各种与Web垃圾邮件检测相关的论文。

我们在编码所描述的算法时遇到特定问题吗？

入门困难吗？

我可能要做的第一件事是从重复检测逻辑中分离标记化(提取"单词"或者其他明智序列的过程)，以便轻松插入不同语言的不同解析器并保留重复检测件相同。

如果我们准备为要在其中搜索的文件建立索引，那么Xapian是一个出色的引擎，并提供Python绑定：

http://xapian.org/

http://xapian.org/docs/bindings/python/

如果这些是纯文本文档，或者我们有一种从文档中提取文本的方法，则可以使用一种称为"拼接"的技术。

首先，我们需要为每个文档计算一个唯一的哈希。如果这些相同，则完成。

如果不是，则将每个文档分成较小的块。这些是"带状疱疹"。

有了木瓦后，我们便可以为每个木瓦计算身份哈希，并比较木瓦的哈希以确定文档是否实际上相同。

我们可以使用的另一种技术是生成整个文档的n-gram，并计算每个文档中类似的n-gram的数量，并为每个文档生成加权分数。基本上，一个n-gram将一个单词分成较小的块。 "苹果"将变成" a"，" ap"，" app"，" ppl"，" ple"，" le"。 (从技术上讲，这是3克)这种方法在大量文档或者两个非常大的文档上在计算上变得非常昂贵。当然，需要对常见的n-gram的" the"，" th"，" th"等进行加权，以使其得分更低。

我已经在我的博客上发布了有关此内容的文章，并且该文章中还有一些链接，涉及有关主题为"盖屋顶"的其他几篇文章，这不仅仅适用于屋顶工。

祝你好运！

如果我们试图检测正在讨论同一主题的文档，则可以尝试收集最常用的单词，扔掉停用词。具有最常用单词相似分布的文档可能正在谈论相似的事物。如果需要更高的精度，可能需要做一些词干并将概念扩展为n-gram。有关更高级的技术，请研究机器学习。

在Google Techtalks上有一个关于神经网络的相当不错的演讲，它谈到了使用分层的Boltzmann机器生成文档的特征向量，然后可以将其用于测量文档距离。主要问题是需要设置大量样本文档来训练网络发现相关功能。

我认为，如果我们只是想检测文件是否不同，杰里米(Jeremy)就是个大难题，像MD5或者SHA1这样的哈希算法是一个不错的选择。

Linus Torvalds的Git源代码控制软件以这种方式使用SHA1哈希来检查何时修改了文件。

贝叶斯滤波器恰好具有此目的。在大多数识别垃圾邮件的工具中都可以找到这种技术。

例如，检测一种语言(来自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)]

但是它可以检测要训练的任何类型的内容：技术文字，歌曲，笑话等。只要我们能提供足够的材料来让该工具了解我们所要记录的内容，它就会起作用。

无需分类即可轻松找到相似性。尝试此O(n2)，但效果很好。

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

我们可能希望研究本文概述的DustBuster算法。

从纸上来说，他们甚至无需检查页面内容就能检测到重复的页面。当然，检查内容可以提高效率，但是使用原始服务器日志足以检测重复页面。

与使用MD5或者SHA1哈希的建议相似，DustBuster方法在很大程度上取决于将文件大小作为主要信号进行比较。听起来很简单，但是对于初次通过非常有效。