基于simhash的文本相似检测算法研究

作     者：姜雪 

作者单位：中国工程物理研究院 

学位级别：硕士

导师姓名：陶以政

授予年度：2017年

学科分类：081203[工学-计算机应用技术] 08[工学] 0835[工学-软件工程] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主      题：文本相似 语义指纹 simhash 同义词扩展 分段索引 

摘      要：文本相似检测算法在海量自然语言文本信息处理中具有广泛的应用,包括常见的科技论文查重、大规模网页去重、科技论文自动摘要等。尤其是simhash指纹算法,不仅生成的指纹满足局部敏感特性,即通过指纹之间的距离度量就可以体现文本的相似程度。同时,该算法的指纹检索匹配过程因采用索引的方式而效率较高,能够在大规模文件系统中快速进行检索。经过历年来研究者的实验验证,simhash算法在文本检测过程中都有不错的表现。然而,不同于简单的完全重复查找,自然语言的复杂性对文本语义相似性的计算造成了极大的困难。simhash算法的设计初衷是为了在大规模数量的网页中去掉相同的网页,即只需要将文本表面内容完全或部分相同的内容筛选出来就可。而这里面不涉及文本的语义信息,无法支持近义词、多义词等自然语言处理上的语义问题。因此,利用simhash算法在文本处理上的“降维优势,以及检索过程中的高效性,针对其不能对语义相似的文本内容进行识别,本文进行了基于simhash算法的语义相似性检测算法研究。首先,本文分析了常见文本相似计算算法的特点及其优缺点,通过比较分析,阐述了本文选择simhash算法作为基础算法进行改进研究的理由,并进一步指出其现有问题及针对这方面问题进行改进的研究思路。其次,针对simhash在文本语义相似性表现上的不足,通过对现有同义词扩展方案的研究,提出了基于同义词词林及上下文的语义编码设计。进一步地,根据本文所划分文本块的粒度特点,对指纹权值的确定进行修改,提出利用词汇词性作为权值的调整方案。综合改进方案,提出了融入同义词信息的语义指纹生成算法,解决了无法识别替换同义词的相似文本问题。另外,在海量文本的相似性检测过程中,需要在规模巨大的指纹库中进行比对操作,检索效率对整个算法的性能表现有很大影响。为提高匹配检索效率,在索引思想的基础上,提出将指纹进行分段,并结合位置信息生成分段索引的方案。在理论上,省去了大量冗余的比较计算,提升了整体的检测速度。最后,通过开发原型系统,并与其他文本相似检测算法进行对照实验验证。证明了本文所提出的基于语义指纹的相似文本检测算法可以用于解决当前simhash算法无法支持同义词替换识别以及一词多义判定问题,同时提升了检测效率,在今后更大规模的文本相似检测系统中可以有良好的表现。