在python脚本中检测类似文档的算法

Question

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

Answer 1

贝叶斯过滤器正是出于这个目的.这是大多数识别垃圾邮件的工具中的技术.

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

但它可以检测你将训练它的任何类型:技术文本,歌曲,笑话等.只要你能提供一些材料让工具学习你的文档是什么样的.

Answer 2

如果这些是纯文本文档,或者您有从文档中提取文本的方法,则可以使用称为shingling的技术.

首先为每个文档计算唯一的哈希值.如果这些是相同的,那么你就完成了.

如果没有,则将每个文档分解为较小的块.这些是你的"带状疱疹".

一旦你有了带状疱疹,你就可以为每个木瓦计算身份哈希值,并比较带状疱疹的哈希值来确定文件是否真的相同.

您可以使用的另一种技术是生成整个文档的n-gram并计算每个文档中相似n-gram的数量,并为每个文档生成加权分数.基本上,n-gram将一个单词拆分成更小的块.'apple'会变成'a','ap','app','ppl','ple','le'.(这在技术上是3克)这种方法在大量文档或两个非常大的文档上可能变得非常昂贵.当然,常见的n-gram'the','th,'th'等需要加权才能将它们降低.

我已经在我的博客上发布了这个帖子,并且在帖子中有一些关于该主题Shingling的其他文章的链接- 它不仅仅适用于屋顶工人.

祝你好运!

Answer 3

您可以使用或最后研究来自Python的stdlib的difflib来编写代码.

它非常灵活,并且具有查找字符串列表之间差异的算法,并指出这些差异.然后你可以用它get_close_matches()来找到类似的单词:

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

这不是解决方案,但可能是一个开始.

Answer 4

无需分类即可轻松找到相似性.试试这个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