第八章、数据相似性检测算法

第八章、数据相似性检测算法1、引言"数据同步算法研究"一文研究了在网络上高效同步数据的方法，其中有个前提是文件A和B非常相似，即两者之间存在大量相同的数据。如果两个文件相似性很低，虽然这种方法依然可以正常工作，但数据同步性能却不会得到提高，甚至会有所降低。因为会产生部分元数据和网络通信消耗，这在两个文件完全不相关时尤为明显。因此，同步数据前需要计算种子文件(seedfile)与目标文件之间的相似性，如果相似性大于指定阈值(通常应大于50%)则应用该数据同步算法，否则接传输文件即可。如此，可使得数据同步算法则具有较好的自适应性，在数据具有不同相似性的情形下均可进行高性能的数据同步。另外，在数据相似性检测的基础之上，可对于相似性高的数据进行数据编码处理(如Delta编码)，通过一个文件给另一个文件编码的方式进行数据压缩，这是一种基于相似数据检测与编码的重复数据删除技术。2、相似性计算Unixdiff对文档进行逐行对比来检测相似文件，它采用经典的LCS(LongestCommonSubsequence，最长公共子串)算法，运用动态规划方法来计算相似性。LCS的含义是同时包含在字符串里的一个最长字符序列，LCS的长度作为这两个字符串相似性的度量。Diff算法以整行作为"字符"来计算最长公共子串，性能上比字符级的LCS算法快很多。这种方法效率很低，而且只适用文本文件的相似比较，不能直接适用于二进制文件。目前通常的做法是将文件相似性问题转换为集合相似性问题，如基于shingle的计算方法和基于bloomfilter的计算方法，这两种方法都可适用于任何格式的数据文件。这种方式的核心思想是为每个文件提取组特征值，以特征值集合来计算相似性，从而降低计算复杂性来提高性能。shingle用特征值交集来计算相似性会导致高计算和空间开销，bloomfilter技术在计算开销和匹配精度上更具势。Bloomfilter所定义的集合元素是文件按照CDC(content-definedchunking)算法所切分数据块的指纹值，其相似性定义如下：

|fingerprints(f1)∩fingerprints(f2)|Sim(f1,f2)=---------------------------------------------

(公式1)

|fingerprints(f1)∪fingerprints(f2)|另外一种方法，是将二进制文件进行切块，使用数据块指纹来表示数据块，然后将数据块映射为"字符"，再应用LCS算法寻找最大公共子串并计算出相似度。其相似性定义如下：

2*length(LCS(fingerprints(f1),fingerprints(f2)))

Sim(f1,f2)=------------------------------------------------------------------(公式2)

length(fingerprints(f1))+length(fingerprints(f2))上面两种相似性算法中均采用数据切分技术，数据块可以是定长或变长。为了相似性计算的精确性，实现中采用以数据块长度作为权的加权计算方法。3、Bloomfilter算法该文件相似性计算流程如下：

(1)采用CDC算法将文件切分成数据块集，并为每个数据块计算MD5指纹；

(2)计算两个指纹集合的交集和并集，通过hashtable来实现；

(3)按照公式1计算文件相似性，考虑重复数据块和数据块长度来提高计算精确度。

详细参见附录bsim源码中的file_chunk，chunk_file_process和similarity_detect函数实现。4、LCS算法该文件相似性计算流程如下：

(1)采用CDC算法将文件切分成数据块集，并为每个数据块计算MD5指纹；

(2)将MD5指纹串映射为"字符"，则文件转换为"字符串"表示；

(3)应用LCS算法计算出最长公共子串，并计算其加权长度；

(4)按照公式2计算文件相似性，考虑重复数据块和数据块长度来提高计算精确度。详细参见附录bsim源码中的file_chunk，chunk_file_process，LCS和similarity_detect函数实现。5、算法分析比较两种算法都对文件进行切分操作，假设文件f1切为m个块，文件f2切分成n个块。Bloomfilter算法没有考虑数据块顺序，因此在相似性精确度方面要低于LCS算法，其时间和空间复杂性都是O(m+n)。相反，LCS算法考虑了数据块顺序问题，相似性度量相对精确，然而其时间和空间复杂性是O(mn)，这个大大限制了应用规模。综合来看，Bloomfilter算法精确度比LCS算法要低，但计算消耗要小很多，性能和适用性非