我需要编写一个模块来检测类似的文档。我已经阅读了很多文档指纹技术和其他论文，但我不知道如何编写代码或实现这样的解决方案。该算法应适用于中文、日文、英文和德文或独立于语言。我怎样才能做到这一点？
问问题
13269 次
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)]
但它可以检测你将训练它的任何类型：技术文本、歌曲、笑话等。只要你能提供足够的材料让工具了解你记录的内容是什么样的。
于 2008-09-20T18:46:25.027 回答
10
如果这些是纯文本文档，或者您有从文档中提取文本的方法，则可以使用一种称为 shingling 的技术。
您首先为每个文档计算一个唯一的哈希值。如果这些是相同的，你就完成了。
如果没有，您将每个文档分解成更小的块。这些是你的“带状疱疹”。
一旦你有了带状疱疹，你就可以计算每个带状疱疹的身份散列，并比较带状疱疹的散列以确定文档是否实际上相同。
您可以使用的另一种技术是生成整个文档的 n-gram，并计算每个文档中相似 n-gram 的数量，并为每个文档生成加权分数。基本上，n-gram 是将一个单词分成更小的块。'apple' 会变成 'a'、'ap'、'app'、'ppl'、'ple'、'le'。（这在技术上是 3-gram）对于大量文档或两个非常大的文档，这种方法可能会变得非常昂贵。当然，常见的 n-gram 'the'、'th、'th' 等需要加权以降低它们的得分。
我已经在我的博客上发布了这个帖子，并且帖子中有一些链接指向关于“ Singling”主题的其他几篇文章 - 这不仅仅是针对屋顶工的。
祝你好运！
于 2008-09-19T13:01:56.970 回答
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
于 2009-01-15T21:37:08.843 回答
7
您可以使用或最后学习Python 标准库中的difflib来编写代码。
它非常灵活，并且具有查找字符串列表之间差异并指出这些差异的算法。然后你可以使用get_close_matches()来查找相似词：
>>> get_close_matches('appel', ['ape', 'apple', 'peach', 'puppy'])
['apple', 'ape']
这不是解决方案，但也许是一个开始。
于 2008-09-19T12:53:05.637 回答
3
你需要让你的问题更具体。如果您已经阅读过指纹识别论文，那么您已经知道工作原理，因此在这里描述常用方法将无益。如果你还没有，你还应该看看斯坦福、谷歌、雅虎和 MS 近年来发表的关于“重复检测”的论文和各种网络垃圾邮件检测相关的论文。
您在对所描述的算法进行编码时遇到具体问题吗？
入门有问题？
我可能要做的第一件事是将标记化（提取“单词”或其他合理序列的过程）与重复检测逻辑分开，以便为不同语言插入不同的解析器并保留重复检测片段相同。
于 2008-09-19T12:56:56.670 回答
2
Google Techtalks 上有一个关于神经网络的很好的演讲，其中谈到了使用分层玻尔兹曼机为文档生成特征向量，然后可以用来测量文档距离。主要问题是需要有大量样本文档集来训练网络以发现相关特征。
于 2008-09-19T15:24:41.450 回答
1
如果您准备索引要在其中搜索的文件，Xapian 是一个出色的引擎，并提供 Python 绑定：
于 2008-09-19T12:57:05.750 回答
0
我认为 Jeremy 已经一针见血了——如果你只是想检测文件是否不同，像 MD5 或 SHA1 这样的哈希算法是一个不错的选择。
Linus Torvalds 的 Git 源代码控制软件正是以这种方式使用 SHA1 散列 - 检查文件何时被修改。
于 2008-09-20T16:32:32.120 回答
0
您可能想研究本文中概述的 DustBuster 算法。
从论文中，他们甚至无需检查页面内容就能够检测到重复的页面。当然检查内容会提高效率，但使用原始服务器日志足以检测重复页面的方法。
与使用 MD5 或 SHA1 哈希的建议类似，DustBuster 方法很大程度上依赖于比较文件大小作为主要信号。听起来很简单，但对于最初的第一次通过来说是相当有效的。
于 2010-02-03T06:01:58.947 回答