参考项目3——文档相似性比较1
需积分: 0 48 浏览量
2022-08-04
15:51:53
上传
评论
收藏 268KB PDF 举报
《用 Python 玩转数据》项目——文档相似性比较
相似性比较算法在许多领域有着重要应用。在剽窃检测方面，相似性比较算法可以帮助
检查抄袭；在代码管理方面，可以帮助查找大型代码的相似部分，以便进一步优化与修改；
在存储方面，可以帮助检测冗余，等等。
借助 Python，我们可以比较简单地实现一些复杂的相似性算法。
相似性比较算法有很多种类，这里介绍的 winnowing 算法基于 2003 年的一篇论文。
一、算法原理和背景知识
算法将文档划分为长度为 n 的连续字符串集合，对每个字符串分片进行哈希，并选择
一部分哈希值作为文档的指纹集合。在恰当选择哈希函数的前提下，当两个文档共享一个或
多个指纹时，它们很可能共享相同的文档分片。
1. n-gram 模型（n 元模型）
n 元模型是一种概率语言模型，是自然语言处理中一个非常重要的概念，常用于评估字
符串之间的差异程度或句子出现的可能性。n-gram 基于马尔科夫假设，即第 n 个词出现的
概率只与之前的（n-1）个词有关。
简单举例而言，一串字符“abcdefghijk”，它的 3-gram 表示如下：
abc bcd cde def … ijk
n-gram 的单元可以是字符或词汇。若以词汇为单元，则”… to be or not to be …”的 2-
gram 表示如下：
…, “to be”, “be or”, “or not”, “not to”, “to be”, …
在本应用中，对文档使用 n-gram 分割为一组子字符串集合，以方便进一步处理。
2. 哈希算法
哈希（hash）算法是一类算法的统称，根据确定的运算规则对输入进行处理，将较长的
串映射为较短的固定长度的值，以达到方便查找、压缩存储空间等目的。使用哈希算法的目
的在于使用较短的结果值，可以得知原串的某些性质，同时减少存储和时间上的消耗，所以
哈希算法有时又被叫做数据摘要算法。
哈希算法的主要特征是单向性和抗碰撞。两个特征的根本来源都是哈希算法本身将一个
大的地址空间映射到一个小空间的原理。单向性是指，无法从哈希值逆向计算出原值，因为
对应一个哈希值，可能有很多，甚至无穷多个原值。抗碰撞是指，当我们已知一个原串和它
的哈希值，很难构造出另一个串，让它们的哈希值相同。由于哈希函数的值空间一般小于原
串的取值空间，对原值作映射运算必定存在碰撞，即多个原串映射到同一个哈希值，一个好
的哈希函数应当做到难以通过构造得出碰撞，通俗理解就是分布比较随机，在正常使用时难
以出现碰撞，同时在遇到碰撞时有相应的处理方法。
评论0