相似文本判断算法 I-Match算法和Shingle算法
之前保存了一篇关于搜索引擎判断页面相似度算法的文章，现在分享下。
相似文本判断两种比较经典的算法，“I-Match算法”、“Shingle算法”。
“I-Match算法”是不依赖于完全的信息分析，使用数据集合的统计特征来抽取文档的主要特征，将非主要特征抛弃。
“Shingle算法”通过抽取多个特征词汇，比较两个特征集合的相似程度实现文档查重。
I-Match算法的特征只有一个，当输入一篇文档，根据词汇的IDF值过滤出一些关键特征，即一篇文章中特别高和特别低频的词汇往往不能反应这篇文章的本质。因此通过文档中去掉高频和低频词汇，并且计算出这篇文档的唯一的Hash值，Hash值相同的文档就是重复的。
举例：这里有两段网页文字：
1.中国足球队在米卢的率领下首次获得世界杯决赛阶段的比赛资格，新浪体育播报 。
2.米卢率领中国足球队员首次杀入世界杯决赛阶段，搜狐体育播报。
文档(一)中
去掉高频：中国，在，的，获得，比赛，资格，新浪，体育，播报
去掉低频：米卢
则剩下中频词有：足球队，率领，首次，世界杯，决赛，阶段
文档(二)中
去掉高频：中国，搜狐，体育，播报
去掉低频：米卢，杀入
则剩下中频词有：率领，足球队，首次，世界杯，决赛 ，阶段
两者是一模一样，这就是相似性的存在。
Shingle算法是抽取多个特征进行比较，处理起来比较复杂一些，比较的方法是完全一致的Shingle个数。然后除以两个文档的Shingle总数减去一致的Shingle个数，这种方法计算出的数值为“Jaccard系数”，它可以判断集合的相似度。
网页查重技术，即判断一个文件内容是否存在抄袭、复制另外一个或多个文件的技术。
1993年Arizona大学的Manber（Google现副总裁、工程师）推出了一个sif工具，寻找相似文件。
1995年Stanford大学的Brin（Sergey Brin，Google创始人之一）和Garcia-Molina等人在“数字图书馆”工程中首次提出文本复制检测机制COPS（Copy Protection System）系统与相应算法[Sergey Brin et al 1995].之后这种检测重复技术被应用到搜索引擎中，基本的核心技术相似。
作者：搜索引擎营销-大鹏
转载请注明出处：http://www.ueoer.org/post/i-match-shingle.html
相似文本判断两种比较经典的算法，“I-Match算法”、“Shingle算法”。
“I-Match算法”是不依赖于完全的信息分析，使用数据集合的统计特征来抽取文档的主要特征，将非主要特征抛弃。
“Shingle算法”通过抽取多个特征词汇，比较两个特征集合的相似程度实现文档查重。
I-Match算法的特征只有一个，当输入一篇文档，根据词汇的IDF值过滤出一些关键特征，即一篇文章中特别高和特别低频的词汇往往不能反应这篇文章的本质。因此通过文档中去掉高频和低频词汇，并且计算出这篇文档的唯一的Hash值，Hash值相同的文档就是重复的。
举例：这里有两段网页文字：
1.中国足球队在米卢的率领下首次获得世界杯决赛阶段的比赛资格，新浪体育播报 。
2.米卢率领中国足球队员首次杀入世界杯决赛阶段，搜狐体育播报。
文档(一)中
去掉高频：中国，在，的，获得，比赛，资格，新浪，体育，播报
去掉低频：米卢
则剩下中频词有：足球队，率领，首次，世界杯，决赛，阶段
文档(二)中
去掉高频：中国，搜狐，体育，播报
去掉低频：米卢，杀入
则剩下中频词有：率领，足球队，首次，世界杯，决赛 ，阶段
两者是一模一样，这就是相似性的存在。
Shingle算法是抽取多个特征进行比较，处理起来比较复杂一些，比较的方法是完全一致的Shingle个数。然后除以两个文档的Shingle总数减去一致的Shingle个数，这种方法计算出的数值为“Jaccard系数”，它可以判断集合的相似度。
网页查重技术，即判断一个文件内容是否存在抄袭、复制另外一个或多个文件的技术。
1993年Arizona大学的Manber（Google现副总裁、工程师）推出了一个sif工具，寻找相似文件。
1995年Stanford大学的Brin（Sergey Brin，Google创始人之一）和Garcia-Molina等人在“数字图书馆”工程中首次提出文本复制检测机制COPS（Copy Protection System）系统与相应算法[Sergey Brin et al 1995].之后这种检测重复技术被应用到搜索引擎中，基本的核心技术相似。
作者：搜索引擎营销-大鹏
转载请注明出处：http://www.ueoer.org/post/i-match-shingle.html
