学位论文 > 优秀研究生学位论文题录展示
基于minwise哈希的文档复制检测的研究及应用
作 者: 袁鑫攀
导 师: 桂卫华; 张祖平; 龙军
学 校: 中南大学
专 业: 计算机应用技术
关键词: 文档复制检测 minwise哈希 相似度估计 指纹 分数位 连接位
分类号: TP391.1
类 型: 博士论文
年 份: 2012年
下 载: 47次
引 用: 0次
阅 读: 论文下载
内容摘要
WEB正经历着爆炸性增长,海量文档中存在大量的相似信息,这些相似性文档一方面消耗了高额的检索资源,另一方面影响了用户的使用。文档的数字化和易获性也使得非法复制、剽窃等行为越来越猖獗。为保护知识产权和提高信息检索效率,文档复制检测技术应运而生并得到迅速发展。文档复制检测就是判断给定文档是否抄袭、剽窃或者相似于一篇或多篇文档的内容。论文以某基金项目相似性检测为实际应用背景,为了在海量数据环境中快速而准确地检测出文档的相似性,主要研究相似性检测系统中涉及的关键技术,重点研究相似度估计算法、相似度检索算法和基于SIMD优化的相似度比对等关键技术,具体进行了如下的研究工作:(1)针对文档相似性检测系统中精度和存储空间只能取离散值、粒度过粗的问题,提出了分数位minwise哈希算法,验证了分数位minwise哈希算法的可行性,构造了使得估计方差最小的最优分数位。分数位minwise哈希算法将整数位minwise哈希扩展到分数位,突破了b整数位的限制,使得相似度可以使用分数位来估计,不仅完善了minwise哈希算法的理论体系,也为实际系统中的用户对于相似度估计的精度和存储空间更加细粒度可选择性需求提供支撑。(2)针对文档相似性检测效率不高的问题,提出了连接位minwise哈希算法。连接位minwise哈希算法将位连接起来进行相似性度量,证明与推导及实验结果显示算法虽然牺牲5%精度,却能成倍地减少比对的次数,大大提升算法的时间性能。一方面,连接位无需任何复杂的操作,方便构建;另一方面,亿万级文档的相似度的估计,通过损失一定的精度误差,获得了性能的成倍提升具有很强的实际应用意义。(3)针对海量文档相似性检索中相似度阂值不能设置过低,初始指纹数少等问题,提出了指纹分组合并检索算法,理论推导及实验结果表明算法能够在低相似度阈值(比如70%)下快速地从已有的文档集中检索目标文档,从而实现相似性文档查询的实时性,并且由于降低了相似度阈值,也增大了相似性检索的应用范围。(4)针对某基金对相似性证据快速采集和清晰呈现的特殊需求,提出了基于SIMD优化的相似性比对算法。通过使用SIMD指令集和OpenCL框架对相似度比对算法进行了一系列的优化,实验结果表明优化算法提升了可提升11.6%-170%的时间性能,一方面使得相似性有迹可循;另一方面也有利于人工复审工作。(5)针对某基金项目相似性检测系统中存在的项目数据难以准确快速提取、海量项目数据比对时间超长、比对结果难以清晰呈现等关键问题,论文论述了如何采用所研究的关键技术形成完整的基金项目相似性检测系统,并为基金项目形式审查提供支持。
|
全文目录
摘要 4-6 ABSTRACT 6-11 第一章 绪论 11-28 1.1 研究背景及意义 11-13 1.2 国内外研究现状 13-25 1.2.1 基于词频统计的文档复制检测方法 14-18 1.2.2 基于字符串比对的文档复制检测方法 18-21 1.2.3 基于相似度估计的文档复制检测方法 21-25 1.3 论文研究的主要内容 25-26 1.4 论文的组织结构 26-28 第二章 文档相似性度量技术 28-39 2.1 引言 28 2.2 度量空间和规范化距离 28-30 2.3 距离函数 30-32 2.4 文档相似度估计算法 32-38 2.4.1 minwise哈希算法 32-35 2.4.2 b位minwise哈希算法 35-38 2.5 本章小结 38-39 第三章 分数位MINWISE哈希算法 39-60 3.1 引言 39-40 3.2 分数位的构建 40-43 3.3 最优分数位 43-45 3.4 分数位方差和存储因子分析 45-48 3.4.1 分数位方差 45-47 3.4.2 分数位存储因子 47-48 3.5 小于1的分数位的构建 48-53 3.6 扩展分数位 53-55 3.7 实验结果分析 55-58 3.7.1 实际方差 55-56 3.7.2 分数位的准确率和召回率 56-58 3.8 本章小结 58-60 第四章 连接位MINWISE哈希算法 60-71 4.1 引言 60 4.2 连接位的构建 60-64 4.2.1 b=1时连接位的无偏估计 60-62 4.2.2 b=2时连接位的无偏估计 62-63 4.2.3 b连接位的无偏估计 63-64 4.3 连接位方差和存储因子分析 64-66 4.3.1 连接位方差 64-65 4.3.2 连接位存储因子 65-66 4.4 实验结果分析 66-69 4.4.1 连接位的准确率和召回率 66-68 4.4.2 连接位的时间性能 68 4.4.3 连接位的可用性 68-69 4.5 本章小结 69-71 第五章 指纹分组合并检索算法 71-89 5.1 引言 71-73 5.2 海明码指纹的提取 73-75 5.3 海明距离检索问题 75-76 5.4 相似度检索算法 76-81 5.4.1 指纹分组检索算法 76-78 5.4.2 指纹分组合并检索算法 78-80 5.4.3 时间复杂度分析 80-81 5.5 实验结果分析 81-84 5.5.1 参数n_g的分布的测量 81-82 5.5.2 检索算法的准确率和召回率 82-83 5.5.3 时间耗费 83-84 5.6 应用实例一文档段落相似度 84-87 5.6.1 段落相似性索引建立 85-87 5.6.2 段落相似度查询 87 5.7 本章小结 87-89 第六章 基于SIMD优化的相似性比对技术 89-102 6.1 引言 89-90 6.2 基于SIMD优化的并行算法 90-98 6.2.1 基于SSE4.2优化的指纹比对算法 90-91 6.2.2 基于SSE优化的求交集比对算法 91-96 6.2.3 基于GPU优化的求交集比对算法 96-98 6.3 实验结果分析 98-101 6.3.1 基于SSE优化的实验结果 98-100 6.3.2 基于GPU优化的实验结果 100 6.3.3 结合SSE和GPU同时优化的实验结果 100-101 6.4 本章小结 101-102 第七章 海量项目文档复制检测系统实例 102-115 7.1 引言 102-103 7.2 系统框架 103-106 7.2.1 系统的层次结构 103 7.2.2 系统的数据流程 103-105 7.2.3 系统的功能结构 105 7.2.4 系统的软硬件结构 105-106 7.3 系统的关键技术难点及解决方案 106-110 7.3.1 项目信息抽取 106-107 7.3.2 文档聚类 107-108 7.3.3 项目相似度估计 108-110 7.4 软件实现和应用 110-113 7.4.1 项目相似性检索 111 7.4.2 项目相似性比对 111-113 7.5 系统性能 113-114 7.6 本章小结 114-115 第八章 结论与展望 115-118 8.1 结论 115-116 8.2 下一步的研究工作 116-118 参考文献 118-130 致谢 130-132 攻读学位期间主要的研究成果 132-133
|
相似论文
- 消癌平制剂及其绿原酸单体的药动学研究与质量控制,R285
- 赤芍商品药材调查及品质评价研究,R282.71
- 土壤酶活测定及土壤微生物总蛋白的提取、纯化与鉴定,S154
- 拮抗芽孢杆菌的分离鉴定及其多样性和系统发育分析,S476.1
- 天山雪莲指纹图谱及总黄酮提取物研究,R284.1
- 枇杷止咳颗粒质量标准的修订及指纹图谱研究,R286.0
- 成都地区儿童脓疱疮皮损中金黄色葡萄球菌药敏及随机扩增多态性DNA指纹分析,R440
- 一种FFTT非对称加解密算法的研究与实现,TP309.7
- 压感式指纹识别系统及算法研究,TP391.41
- 基于SELDI-TOF-MS技术的乳头状甲状腺癌血清差异蛋白质组学分析及筛选模型的构建,R736.1
- DNA指纹图谱的自动识别与分析定位研究,TP391.41
- 指纹图像预处理与增强算法的研究,TP391.41
- 指纹图像分割方法评价与半监督学习在指纹图像分割中的应用研究,TP391.41
- 滨海湿地药用植物盐地碱蓬HPLC化学指纹图谱与网状软柳珊瑚化学成分及其生物活性研究,R284
- 非综合征性唇腭裂患者血浆和尿液的核磁共振代谢组学研究,R782.21
- 压感指纹识别系统关键技术的研究,TP391.41
- 山东省食源性沙门氏菌监测及分型研究,R155.5
- 基于指纹识别和PKI的网上银行身份认证系统设计,TP393.09
- 中药喜树果、枳实活性成分的荧光分析及牛蒡子三维荧光指纹图谱的建立,R284
- 基于指纹识别的驾校考勤系统设计与实现,TP311.52
- 指纹图像增强算法在考勤系统中的应用与实现,TP391.41
中图分类: > 工业技术 > 自动化技术、计算机技术 > 计算技术、计算机技术 > 计算机的应用 > 信息处理(信息加工) > 文字信息处理
© 2012 www.xueweilunwen.com
|