基于minwise哈希的文档复制检测的研究及应用

摘要

WEB正经历着爆炸性增长，海量文档中存在大量的相似信息，这些相似性文档一方面消耗了高额的检索资源，另一方面影响了用户的使用。文档的数字化和易获性也使得非法复制、剽窃等行为越来越猖獗。为保护知识产权和提高信息检索效率，文档复制检测技术应运而生并得到迅速发展。
　　文档复制检测就是判断给定文档是否抄袭、剽窃或者相似于一篇或多篇文档的内容。论文以某基金项目相似性检测为实际应用背景，为了在海量数据环境中快速而准确地检测出文档的相似性，主要研究相似性检测系统中涉及的关键技术，重点研究相似度估计算法、相似度检索算法和基于SIMD优化的相似度比对等关键技术，具体进行了如下的研究工作:
　　(1)针对文档相似性检测系统中精度和存储空间只能取离散值、粒度过粗的问题，提出了分数位minwise哈希算法，验证了分数位minwise哈希算法的可行性，构造了使得估计方差最小的最优分数位。分数位minwise哈希算法将整数位minwise哈希扩展到分数位，突破了b整数位的限制，使得相似度可以使用分数位来估计，不仅完善了minwise哈希算法的理论体系，也为实际系统中的用户对于相似度估计的精度和存储空间更加细粒度可选择性需求提供支撑。
　　(2)针对文档相似性检测效率不高的问题，提出了连接位minwise哈希算法。连接位minwise哈希算法将位连接起来进行相似性度量，证明与推导及实验结果显示算法虽然牺牲5％精度，却能成倍地减少比对的次数，大大提升算法的时间性能。一方面，连接位无需任何复杂的操作，方便构建;另一方面，亿万级文档的相似度的估计，通过损失一定的精度误差，获得了性能的成倍提升具有很强的实际应用意义。
　　(3)针对海量文档相似性检索中相似度阈值不能设置过低，初始指纹数少等问题，提出了指纹分组合并检索算法，理论推导及实验结果表明算法能够在低相似度阈值（比如70％）下快速地从已有的文档集中检索目标文档，从而实现相似性文档查询的实时性，并且由于降低了相似度阈值，也增大了相似性检索的应用范围。
　　(4)针对某基金对相似性证据快速采集和清晰呈现的特殊需求，提出了基于SIMD优化的相似性比对算法。通过使用SIMD指令集和OpenCL框架对相似度比对算法进行了一系列的优化，实验结果表明优化算法提升了可提升11.6％-170％的时间性能，一方面使得相似性有迹可循;另一方面也有利于人工复审工作。
　　(5)针对某基金项目相似性检测系统中存在的项目数据难以准确快速提取、海量项目数据比对时间超长、比对结果难以清晰呈现等关键问题，论文论述了如何采用所研究的关键技术形成完整的基金项目相似性检测系统，并为基金项目形式审查提供支持。

目录

声明

摘要

第一章 绪论

1．1 研究背景及意义

1．2 国内外研究现状

1．2．1 基于词频统计的文档复制检测方法

1．2．2 基于字符串比对的文档复制检测方法

1．2．3 基于相似度估计的文档复制检测方法

1．3 论文研究的主要内容

1．4 论文的组织结构

第二章 文档相似性度量技术

2．1 引言

2．2 度量空间和规范化距离

2．3 距离函数

2．4 文档相似度估计算法

2．4．1 minwise哈希算法

2．4．2 b位minwise哈希算法

2．5 本章小结

第三章 分数位minwise哈希算法

3．1 引言

3．2 分数位的构建

3．3 最优分数位

3．4 分数位方差和存储因子分析

3．4．1 分数位方差

3．4．2 分数位存储因子

3．5 小于1的分数位的构建

3．6 扩展分数位

3．7 实验结果分析

3．7．1 实际方差

3．7．2 分数位的准确率和召回率

3．8 本章小结

第四章 连接位minwise哈希算法

4．1 引言

4．2 连接位的构建

4．2．1 b=1时连接位的无偏估计

4．2．2 b=2时连接位的无偏估计

4．2．3 b连接位的无偏估计

4．3 连接位方差和存储因子分析

4．3．1 连接位方差

4．3．2 连接位存储因子

4．4 实验结果分析

4．4．1 连接位的准确率和召回率

4．4．2 连接位的时间性能

4．4．3 连接位的可用性

4．5 本章小结

第五章 指纹分组合并检索算法

5．1 引言

5．2 海明码指纹的提取

5．3 海明距离检索问题

5．4 相似度检索算法

5．4．1 指纹分组检索算法

5．4．2 指纹分组合并检索算法

5．4．3 时间复杂度分析

5．5 实验结果分析

5．5．1 参数ng的分布的测量

5．5．2 检索算法的准确率和召回率

5．5．3 时间耗费

5．6 应用实例—文档段落相似度

5．6．1 段落相似性索引建立

5．6．2 段落相似度查询

5．7 本章小结

第六章 基于SIMD优化的相似性比对技术

6．1 引言

6．2 基于SIMD优化的并行算法

6．2．1 基于SSE4．2优化的指纹比对算法

6．2．2 基于SSE优化的求交集比对算法

6．2．3 基于GPU优化的求交集比对算法

6．3 实验结果分析

6．3．1 基于SSE优化的实验结果

6．3．2 基于GPU优化的实验结果

6．3．3 结合SSE和GPU同时优化的实验结果

6．4 本章小结

第七章 海量项目文档复制检测系统实例

7．1 引言

7．2 系统框架

7．2．1 系统的层次结构

7．2．2 系统的数据流程

7．2．3 系统的功能结构

7．2．4 系统的软硬件结构

7．3 系统的关键技术难点及解决方案

7．3．1 项目信息抽取

7．3．2 文档聚类

7．3．3 项目相似度估计

7．4 软件实现和应用

7．4．1 项目相似性检索

7．4．2 项目相似性比对

7．5 系统性能

7．6 本章小结

第八章 结论与展望

8．1 结论

8．2 下一步的研究工作

参考文献

致谢

攻读学位期间主要的研究成果