logo标签列表

Python脚本中检测相似文档的算法

pythonalgorithmdiff
10

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

与其他答案类似的问题：https://dev59.com/tWox5IYBdhLWcg3w6oZf - Joachim Wagner
10个回答
20

贝叶斯过滤器正是有这个目的。在大多数用于识别垃圾邮件的工具中，你会发现这种技术。

例如，为了检测语言（源自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)]

但是它可以用来检测你训练的任何类型：技术文本、歌曲、笑话等。只要你提供足够的材料让这个工具学习你的文档长什么样子。

10
如果这些是纯文本文档，或者您有一种方法从文档中提取文本，则可以使用称为shingling的技术。首先为每个文档计算一个唯一的哈希值。如果它们相同，则完成了。如果不是，则将每个文档分解成较小的块。这些是您的“shingles”。一旦您拥有了shingles，就可以计算每个shingle的标识哈希，并比较shingle的哈希以确定文档是否实际相同。您可以使用的另一种技术是生成整个文档的n-gram，并计算每个文档中相似n-gram的数量，并为每个文档生成加权分数。基本上，n-gram是将单词分成较小的块。'apple'变成'a', 'ap', 'app', 'ppl', 'ple', 'le'。（这在技术上是一个3-gram）。在大量文档或两个非常大的文档上，这种方法可能变得非常耗费计算资源。当然，常见的n-gram“the”，“th”，“th”等需要加权以使它们得分更低。我在我的博客上发布了关于此的文章，文章中有一些链接指向其他几篇有关该主题的文章Shingling - it's not just for roofers。祝你好运！
8

不需要分类即可轻松找到相似性。尝试使用这个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
2
顺便提一下，这个在 Python 3 中是可行的，只需要去掉集合名称中的复数 s（sets -> set）。谢谢。 - David
7
你可以使用或至少学习Python标准库中的difflib来编写代码。
它非常灵活，并且具有查找字符串列表之间差异并指出这些差异的算法。然后，您可以使用get_close_matches()来查找相似的单词：
>>> get_close_matches('appel', ['ape', 'apple', 'peach', 'puppy'])
['apple', 'ape']

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

3
您需要将问题具体化。如果您已经阅读了指纹识别论文，那么您已经了解了其中的原理，因此在这里描述常见方法是没有益处的。如果您还没有阅读过相关论文，建议您查看关于“重复检测”以及来自斯坦福、谷歌、雅虎和微软等机构的各种网络垃圾检测相关论文。
您是否在编写所述算法时遇到了特定问题？
是否难以入手？
我可能会首先将标记化（提取“单词”或其他合理序列的过程）与重复检测逻辑分开，以便轻松地插入不同语言的解析器并保持重复检测部分不变。
2

这里有一个非常好的谈论神经网络 的Google Techtalks视频，讲解使用分层玻尔兹曼机生成特征向量来衡量文档距离。主要问题是需要一个大样本文件集来训练网络以发现相关特征。

1
0

你可能想要查看DustBuster算法，如this paper中所述。

从这篇论文中，他们能够检测重复的网页，甚至不需要检查页面内容。当然，检查内容可以增加效力，但是使用原始服务器日志已足以使该方法检测到重复页面。

与建议使用MD5或SHA1哈希值类似，DustBuster方法主要依赖于比较文件大小作为其主要信号。尽管听起来很简单，但对于第一轮初始处理而言相当有效。

0

如果您正在尝试检测谈论同一主题的文档，则可以尝试收集最常用的单词，并且丢弃 停用词。具有类似最常使用单词分布的文档可能谈论相似的内容。如果您想要更高的准确度，您可能需要对某些词干进行处理并将其概念扩展为n-grams。对于更高级的技术，请研究机器学习。

0

我认为Jeremy说得很对 - 如果你只想检测文件是否不同，像MD5或SHA1这样的哈希算法是一个不错的选择。

Linus Torvalds的Git源代码控制软件就是以这种方式使用SHA1哈希算法来检查文件是否被修改过。

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接