文件相似性判断 -- 超级特征值（super feature）
发布时间：2020-12-14 03:27:56 所属栏目：大数据 来源：网络整理
导读：? ? ?基于内容的变长分块（CDC）技术，可以用来对文件进行变长分块，而后用来进行重复性检测，广泛用于去重系统中。后来又出现了对相似数据块进行delta压缩，进一步节省存储开销。所以就需要一种高效的相似性检测算法，在论文?WAN Optimized Replication of
|
? ? ?基于内容的变长分块（CDC）技术，可以用来对文件进行变长分块，而后用来进行重复性检测，广泛用于去重系统中。后来又出现了对相似数据块进行delta压缩，进一步节省存储开销。所以就需要一种高效的相似性检测算法，在论文?WAN Optimized Replication of Backup Datasets?Using Stream-Informed Delta Compression 提出的super-features 算法具有很好的效果。主要思想是在滑动窗口进行分块的过程中，通过一个窗口的rabin fingerprint 我们可以随机的得到一个数值，如果它比这个块中所有窗口w的rabin指纹都大，就把它记为一个特征值?feature-i，通过这样的方法得到的多个feature，计算rabin 指纹得到的就是超级特征值SF，下图每个SF有四个特征值得到。
下面是对几个文件简单的测试结果，这里每个文件生成俩超级特征值（如果两个文件有一个super feature一样，就可以认为它们相似性很高），效果比simhash好（缺乏大量数据集论证）。
F1,F2,F3 分别在F的基础上头，尾，中间加入额外字节，发现得到的两个超级特征值都一样?Supfeature[0]=5465959093573163876，Supfeature[1]=7673021043978770954。
F4是一个完全不同的文件，?Supfeature[0]=2682386775420212619，Supfeature[1]=3509276326591445061。
参考：
1.?Philip Shilane-WAN Optimized Replication of Backup Datasets?Using Stream-Informed Delta Compression
2.Some applications of rabin's fingerprinting method. ?
（编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |
