文件类似的推理 -- 超级本征值（super feature）

     基于内容的变长分块（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.    

版权声明：本文博主原创文章。博客，未经同意不得转载。