simhash文本相似度检测介绍_Simhash文本相似度 - CSDN文库

文本相似度

需积分: 24 30 浏览量更新于2023-05-29 评论收藏 22KB DOCX 举报

身份认证购VIP最低享 7 折!

领优惠券(最高得80元）

资源详情

资源评论

资源推荐



相似数据检测算法

分类：计算机理论数据结构与算法



2011-10-22 22:214893 人阅读评论(20)收藏举报

相似数据检测算法对给定的一对数据序列计算两者之间的相似度([0,1], 1 表示完全相同)或距离([0, ), 0 表

示完全相同)，从而度量数据之间的相似程度。相似数据检测在信息科学领域具有非常重要的应用价值，

比如搜索引擎检索结果的聚类与排序、数据聚类与分类、Spam 检测、论文剽窃检测、重复数据删除、

Delta 数据编码等应用。正是由于它的重要性，近年来成为了研究的重点，不断有新检测方法涌现并得到

评估。其中，Broder 提出的 shingling 算法和 Charikar 的 simhash 算法被认为是目前为止最好的算法。

对于相似数据检测，最为简单地可以采用类似 Unix diff 的方法。Unix diff 对文档进行逐行对比来检测相似

文件，它采用经典的 LCS(Longest Common Subsequence，最长公共子串)算法，运用动态规划方法来计

算相似性。LCS 的含义是同时包含在字符串里的一个最长字符序列，LCS 的长度作为这两个字符串相似

性的度量。Diff 算法以整行作为"字符"来计算最长公共子串，性能上比字符级的 LCS 算法快很多。这种方

法效率很低，而且只适用文本文件的相似比较，不能直接适用于二进制文件。为此，研究者们提出为每个

文档提取一组特征，这样将文件相似性问题转换为集合相似性问题，如基于 shingle 的计算方法。这种方

式的核心思想是为每个文件提取组特征值，以特征值集合来计算相似性，从而降低空间和计算复杂性来提

高性能。

经过对 shingle 算法和 simhash 算法以及笔者基于 bloom filter 实现算法的分析，相似数据检测算法大致流

程如下：

(1) 将数据段分解成一组 shingle(即子序列或数据块)，可以采用定长、变长、单词或段落(文本文件)等分

块算法；

(2) 为了降低空间和时间计算复杂性，可以对 shingle 集合进行抽样，比如 Min-Wise，Modm，Mins 方法；

(3) 基于选定的 shingle 集合为数据文件抽取特征，通常是为每个 shingle 计算 hash 值组成的序列作为特

征值；

(4) 为了降低空间和时间计算复杂性，可以对文件特征进行降维处理，比如 simhash 和 bloom filter；

(5) 基于文件特征计算两个数据对象之间的相似性，计算方法有 Cosine、Overlap、Dice、Jaccard 或

Hamming 距离。

Shingle 算法

Shingle 算法的核心思想是将文件相似性问题转换为集合的相似性问题，集合的相似性度量方法主要有

resemblance 和 containment 两种，其定义如下。

 |shingle(f1, w) ∩ shingle(f2, w)|

　Rw(f1, f2) = ----------------------------------------------

       |shingle(f1, w) ∪ shingle(f2, w)|

       |shingle(f1, w) ∩ shingle(f2, w)|

　Cw(f1, f2) = ----------------------------------------------

 |shingle(f1, w)|

数量较大时，如果对所有 shingle 进行相似性处理则系统开销较大，包括内存和 CPU 资源。这时就可以考

虑对 shingle 集合进行抽样，以降低空间和时间计算复杂性，但同时由于样本覆盖率有限，相似性精确度

会有所降低。shingle 取样主要有三种方法，即 Min-Wise，Modm，和 Mins。Min-Wise 技术是通过将

本内容试读结束，登录后可阅读更多

下载后可阅读完整内容，剩余3页未读，立即下载

评论0

梦无痕123

粉丝: 97
资源: 34

会员权益专享

图片转文字

全年可省5，000元立即开通

最新资源

资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！点击此处反馈