一种支持模糊匹配的云存储数据去重复方法

摘要

本发明公开了一种支持模糊匹配的云存储数据去重复方法。其步骤为：1、读取文件内容，2、计算文件元数据，3、判断是否满足分块条件，4、计算模糊哈希值，5、压缩模糊哈希值，6、计算索引相似度，7、比对模糊哈希值，8、判断是否存在重复的数据块哈希值，9、进行块级的文件所有权证明，10、发送不重复的数据块序号，10、上传不重复的数据块。本发明克服了现有技术中上传和存储完整文件、按比特串长度对文件进行等长划分，内容相似但首尾未对齐的文件无法被识别出重复数据带来的缺陷，降低了网络上传带宽和服务器存储空间的开销，提高了重复数据删除率。

主权项

一种支持模糊匹配的云存储数据去重复方法，包括以下具体步骤：(1)采用内存映射文件方法，逐字节地读取待模糊匹配文件的内容；(1a)计算机操作系统在待模糊匹配文件中创建映射内核对象，读取文件的字节数，设置操作系统的分页粒度；(1b)计算机操作系统将待模糊匹配文件的映射内核对象全部映射到计算机的进程地址空间；(1c)判断是否读取完待模糊匹配文件的所有字节数，若是，则执行步骤(1d)，否则，执行步骤(1a)；(1d)计算机操作系统释放待模糊匹配文件的映射内核对象；(2)计算文件元数据：(2a)采用滚动哈希算法，计算待模糊匹配文件的字节，得到待模糊匹配文件字节的校验和：s＝x+y+w其中，s表示待模糊匹配文件字节的校验和，x表示在一个长度为7的滚动窗口内的待模糊匹配文件的所有字节数之和，y表示待模糊匹配文件的字节数与滚动窗口长度的乘积，w表示待模糊匹配文件的字节数与常数32的乘积；(2b)按照下式，计算待模糊匹配文件的分块长度：b＝b_min*2^k其中，b表示待模糊匹配文件的分块长度，b_min表示待模糊匹配文件的分块长度b的最小值，缺省情况下b_min＝3，*表示乘法操作，k表示待模糊匹配文件的分块长度的扩大系数，0≤k≤14；(3)判断当前待模糊匹配文件字节的校验和是否满足分块条件，若是，则执行步骤(4)，否则，执行步骤(2)；(4)计算模糊哈希值：(4a)将满足分块条件的待模糊匹配文件的字节作为文件的分割点，记录该分割点在待模糊匹配文件中的位置；(4b)使用哈希函数FNV hash计算待模糊匹配文件的分块内容，得到模糊哈希值h₁||h₂||…||h_i||…||h_n，i∈{1,2,…,n}，其中，h_i表示待模糊匹配文件的第i个分块哈希值，i表示待模糊匹配文件的分块序号，n表示待模糊匹配文件的分块个数，||表示拼接操作；(5)压缩模糊哈希值：采用Base64编码处理模糊哈希值，得到由32～64个字符组成的字符串，将该字符串作为模糊哈希值的索引；(6)按照下式，计算用户上传的索引和云存储数据库中索引之间的相似度：$M=(1-\frac{D_{\min }}{Max(L1,L2)})*100\%$其中，M表示用户上传的索引与云存储数据库中索引之间的相似度，D_min表示用户上传的索引与云存储数据库中索引之间的最小编辑距离，Max表示作最大值操作，L1表示用户上传索引的长度，L2表示云存储数据库中的索引长度，*表示乘法操作；(7)比对模糊哈希值：(7a)服务器从云存储数据库中，选取与用户上传索引的相似度最高的目标索引；(7b)服务器在云存储数据库中查找出目标索引对应的目标模糊哈希值h₁′||h₂′||…||h_i′||…||h_n′′，i∈{1,2,…,n′}，其中，h′_i表示目标文件的第i个分块哈希值，i表示目标文件的分块序号，n′表示目标文件的分块个数，||表示拼接操作；(7c)服务器将用户上传的模糊哈希值与云存储数据库中的目标模糊哈希值进行比对；(8)判断在目标模糊哈希值中是否存在与用户上传的模糊哈希值重复的数据块哈希值，若是，则执行步骤(9)，否则，执行步骤(10)；(9)进行块级的文件所有权证明：(9a)按照下式，计算重复数据块哈希值的询问信息：c＝f_τ(H₁||H₂||…||H_j||…||H_m)其中，c表示重复数据块哈希值的询问信息，f_τ表示伪随机函数，τ表示伪随机函数f_τ的安全参数，H_j表示第j个重复的数据块哈希值，j表示重复的数据块序号，j∈{1,2,…,m}，m表示重复的数据块个数；(9b)服务器将重复数据块哈希值的询问信息发送给用户；(9c)用户接收重复数据块哈希值的询问信息，从待模糊匹配文件中查找对应的重复文件数据块；(9d)按照下式，计算重复文件数据块的证明信息：p＝f_τ(b₁||b₂||…||b_j||…||b_m)其中，p表示重复文件数据块的证明信息，f_τ表示伪随机函数，τ表示伪随机函数f_τ的安全参数，b_j表示第j个重复的文件数据块，j表示重复数据块的序号，j∈{1,2,…,m}，m表示重复数据块的个数；(9e)用户将重复文件数据块的证明信息发送给服务器；(9f)服务器接收重复文件数据块的证明信息，利用重复数据块哈希值的询问信息对重复文件数据块的证明信息进行验证，证明用户确实拥有这些文件内容；(10)服务器将不重复的数据块序号发送给用户；(11)上传不重复的数据块：用户接收不重复的数据块序号，利用不重复的数据块序号以及分割点在待模糊匹配文件中的位置，从待模糊匹配文件中查找不重复的文件数据块，将不重复的文件数据块、用户保存的文件元数据，以及索引一起上传给服务器。