文本相似检测(simhashsingling).docx

相似数据检测算法分类: 计算机理论数据结构与算法 2011-10-22 22:21 4893 人阅读评论(20) 收藏举报相似数据检测算法对给定的一对数据序列计算两者之间的相似度([0,1], 1表示完全相同)或距离([0, ),0表示完全相同),从而度量数据之间的相似程度。相似数据检测在信息科学领域具有非常重要的应用价值,比如搜索引擎检索结果的聚类与排序、数据聚类与分类、 Spam 检测、论文剽窃检测、重复数据删除、 Delta 数据编码等应用。正是由于它的重要性,近年来成为了研究的重点,不断有新检测方法涌现并得到评估。其中, Broder 提出的 shingling 算法和 Charikar 的 simhash 算法被认为是目前为止最好的算法。对于相似数据检测,最为简单地可以采用类似 Unix diff 的方法。 Unix diff 对文档进行逐行对比来检测相似文件,它采用经典的 LCS(mon 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 、 ard 或 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) = -------------------------------------