基于语义指纹的海量文本快速相似检测算法研究

姜雪　万正景　梁燕　陶以政

摘要：相似检测算法在海量文本信息处理中具有广泛的应用，尤其是Simhash算法因其指纹局部敏感特性、检测效率高在文本查重、网页检测等大规模数据处理中都十分常见。针对传统Simhash算法无法支持近义词、多义词等自然语言处理上的语义问题，通过对现有同义词扩展方案的研究，提出基于语义指纹的相似检测算法。在Simhash算法基础上，融入同义词扩展编码信息，生成文本语义指纹进行匹配检测，以提高文本相似度检测性能。另外，根据文本语义指纹建立多层分段索引，实现在海量文本信息中快速匹配出相似文档。通过与传统的Simhash算法进行实验对比，体现出该方法在准确率、效率等方面的优势。

关键词：文本相似；语义指纹；Simhash；同义词扩展；互信息

中图分类号：TP391 文献标识码：A 文章编号：1009-3044（2016）36-0175-03

Research on Fast Duplicate Detection Algorithm for Massive Documents Based on Semantic Fingerprints

JIANG Xue，WAN Zheng-jing，LIANG Yan，TAO Yi-zheng

（Institute of Computer Application， China Academy of Engineering Physics， Mianyang 621900， China）

Abstract： Simhash algorithm is widely used in large-scale data processing， such as document duplication detection or web page ， because of its local sensitive characteristics and high efficiency. In terms of the problem that traditional Simhash algorithm can not support the semantic analysis of natural language processing such as synonyms or polysemous words， a similarity detection algorithm based on semantic fingerprint is proposed by studying the existing synonym expansion scheme. On the basis of Simhash algorithm， the semantic fingerprints are generated by matching synonyms to improve the performance of text similarity detection. In addition， establishing multi-level segment indexes based on the text semantic fingerprints can aggregation the similar documents in the mass document data quickly. Compared with the traditional Simhash algorithm， this method shows the advantages in terms of accuracy， efficiency and so on.

Key words：document similarity； semantic fingerprint； simhash； synonym expansion； mutual information

1 概述

在這个海量信息充斥的时代，信息的重复也随之增多，而其中一些相似文本的出现不仅不能丰富信息的价值，反而造成资源的浪费。因此，如何在大规模数据中快速检测出这些相似的文档是一项十分重要的技术。目前，国内、外在该领域的检测手段普遍都采用将文本哈希成数字指纹的技术。特别是Simhash算法，由于其检测准确率高，“降维”的思想使得检测速度快，同时还可以根据指纹距离反映文本内容的差异程度，因此受到广泛的应用。但由于中文语义的复杂性，包括同义词，一词多义等问题，现有Simhash算法对于不同文档采用同义词作为关键字的相似检测性能并不是很理想。例如，两篇文档的关键词分别为：大规模、文档、去重、技术和海量、文本、查重、算法。

基于上述原因，本文在现有Simhash算法的基础上，通过对其进行改进，提出一种基于同义词扩展编码的语义指纹生成方法，实现海量文本的快速相似检测。该方法利用基于同义词词典的语义扩展编码，通过Simhash函数映射生成固定长度的语义指纹，解决了其中普通哈希函数无法进行语义表达的问题，扩展了指纹的表达能力，提升了检测准确率。再根据指纹信息进行分段索引建立，减少了比对过程中的冗余操作，提高整体检测效率。通过实验验证，该算法在海量文本相似检测过程中性能良好，其快速匹配机制也满足了大数据环境下的检测需求。

2 相关工作

2.1 Simhash算法

Simhash算法在2002年由Charikar[1]提出，后由Manku对其进行扩展研究，被认为是当前文本相似检测处理中最有效的算法之一[2]。Simhash算法实质上是一种具有局部敏感特征的哈希算法，它能够将文本内容特征向量映射到一个指定维度的二进制比特向量上，并由这个二进制哈希值来表示文本内容的数字指纹（ Digital Fingerprint） 。区别于其他哈希算法，Simhash不仅在保证低碰撞率的条件下通过哈希映射将原本不同的文本内容映射到不同的哈希空间中，同时还能通过比特位数的不同体现两个比较文本的相似性，这也正是其局部敏感特性的体现。根据局部敏感哈希算法（Local Sensitive Hashing，LSH）的基本思想[3]，两篇文本p，q相似的可能性与其距离呈负相关关系，即它们之间的距离越小，相似的可能性就越高，反之，则相似的可能性就越低。这里我们定义Simhash函数h，则映射后h（p），h（q）与其距离的关系满足以下两个局部敏感性质（公式1）：

[If||p-q||≤R，thenPrH（h（p）=h（q））≥P1If||p-q||≥cR，thenPrH（h（p）=h（q））≤P2] （1）

这里参数c>1，概率P1>P2，p与q的距离也就是我们所需计算的文本相似度，h（p），h（q）的距离由二者的汉明距离来确定。两篇文档的相似性计算经过哈希映射后，转化为两篇文本的指纹值汉明距离计算。

基于Simhash的相似文本检测需要经过文本特征提取、指纹生成和指纹索引匹配三个数据处理过程。首先，算法以经过分词的文档词项作为文档的特征，其对应的频率作为每个特征的权值wi。通过普通的hash函数计算得到每个分词的一个f位的二进制哈希值，再将所有特征的哈希值加权累加，得到一个同样为f位的总向量V，根据V中各位的符号生成文档的数字指纹F。最后根据指纹的索引值指纹库中进行比对，找到满足一定条件的其他指纹作为相似比对结果。

2.2同义词词林

在信息检索领域，将关键词进行同义词扩展实现模糊检索，这类方案目前已有一定研究[4][5][6]一般地，通过同义词挖掘算法事先建立同义词词库，再运用该词库对检索关键词进行语义扩展，生成一个扩展关键词集合。在检索时，根据集合内的关键词生成索引，依据索引进行查询比对。在本文中，需要对关键词的语义进行同义词概念的扩展，把从属于某一概念下的同义词和关联词均划归到该概念下的集合中，并以该集合的编码作为语义编码返回处理。

同义词的扩展是以同义词词典作为基础进行操作，而“同义词词林”作为其中一个具有代表性的中文词典，在中文自然语言处理领域受到广泛关注。在词林中，将所有词汇按照树状结构分层地组织到其中，树中的每个结点代表一个概念域。自顶向下整个词林树共有5层，依次对应1到2个编码进行标识，将各个标识排列后就形成词元的编码。词林的层次与其分类相对应，而分类的原则是依据汉语语言特点，以词义为主，兼顾词类，充分体现词义的聚集。

同义词词林依据“词义为主，兼顾词类”的原则，结合汉语语言本身的特点及其使用规则将收录的所有词语划分为三个等级：其中大类共12个，中类94个，小类多达1428个。再向下根据词义集中的原则划分成3925个词群并排列，每个词群对应一个标题词。最后按照以下三个原则划分成最小的子群：一、词义的细微差别；二、修辞色彩与使用范围的不同；三、词语结构的差异。其中第一个是主要的。

3 基于语义指纹的快速相似检测算法

本文提出的文本相似检测算法主要是基于经典的Simhash 算法，而其主体思想是“降维”，通过将高维的文本特征向量映射成一个唯一的二进制指纹值，从而达到减少文本表示空间的作用。不同于其他指纹生成算法，Simhash算法可以将两篇相似的文本映射到一个距离相对较近的低维特征空间中，通过在该空间中距离的大小判别两个文本向量的相似程度。但由于中文语义的复杂性，包括同义词，一词多义等问题，现有Simhash算法对于不同文档采用同义词作为关键字的相似检测性能并不是很理想。例如，两篇文档的关键词分别为：大规模、文档、去重、技术和海量、文本、查重、算法。基于上述原因，本课题在现有Simhash指纹生成算法的基础上，通过对其进行改进，提出一种基于同义词扩展编碼的语义指纹生成方法。语义指纹的生成流程如图1所示。

文本最终的语义指纹值是基于离散化的文本特征提取的结果，数据指纹间的汉明距离越接近，则代表文本的语义越相似。根据同义词词林在词语组织上的层次架构，对待文本中的关键词进行定位标识，在词林层级结构树中找到该关键词所有义项所属的层次，考虑到一词多义的情况，一个词的不同义项间可能差距较大，因此根据其上下文信息进行筛选，取最大概率的词项所属词群编码进行扩展。概率判定的指标主要基于该词与其上下文词汇的互信息。

[I（wx，wy）=wx∈Xwy∈Yp（wx，wy）logp（wx，wy）p（wx）p（wy）] （2）

一般地，在应用Simhash算法时，将划分出的词语作为文本的基本特征，再结合每一个词语的词频作为其权重。考虑到本课题算法中，文本块的划分以句子为单位，而各个单词在一句话中出现的频率区分度并不会很大，因此在本课题中特征的权值采用另一个指标——单词的词性。从词性角度来说，名词表征着文档更多的特征，因此其权重应该最高，动词次之，形容词再次之，其余词权重最低。

根据文本的特征向量信息生成文本语义指纹的算法如下：

输入： 一个64维特征向量 V = {w1，w2…，wn}，其中 w1，w2，…，wn 分别是文本关键词特征，其对应相对值分别为we1，we2，……wen；

输出： 一个64位的二进制语义指纹 F = {f1，f2，…，fb}；

1） 初始化一组64位的二进制向量，其中一个向量F作为文本的语义指纹，其他向量用来存储关键词对应的同义词扩展词群编码；

2） 将各个关键词在同义词词林中找到对应多个词项，并根据与前一个词以及后一个词互信息（公式2），计算该词汇对应的词群编码，并转换成64位二进制hash值；

3） 根据关键词各位的hash值以及其标注词性的权重进行调整。如果第i位为1，则将该词hash值的第i位置为权值，如果为0，则将该位置为负权值；

4） 将所有词向量的对应位进行求和运算，结果向量记为F；

5） 按照向量F各个位的正负确定语义指纹F的数值：如果F第i位为正，则指纹F的第i位置为1，反之，则置对应位为0。

这样，就得到了经过同义词扩展后的文本特征hash值的加权综合结果。

4 实验验证

4.1实验数据及工具

由于汉语中没有句子相似度检索用的标准测试数据集，因此本实验的数据是通过从搜狗语料库网页数据中进行处理得到。实验所用语料为标准中文数据集SOGOU-T，从中选取800篇文档作为基础数据集，经过本课题语义指纹生成算法处理后形成指纹存入数据库中，作为相似检测依据。测试文档集中，其中一部分从基础数据集中选取200篇，并作不同种类的修改，构成论文相似目标数据集。通过将本文算法和其他算法，包括经典的词频统计算法，未改进的simhash算法进行比较。

文本处理过程中，采用ICTALAS中文分词系统实现，该系统采用层叠隐马模型，该工具具有 160 万字/秒的高速处理能力，同时支持外文字母以及数字等的分词处理和用户自定义词典的扩展，目前共收录有392755个词汇。

4.2 评价标准

本文采用传统的准确率、召回率两个关键指标来对本文提出的算法进行性能评价。假设在进行文本相似性检测的实验结果如表1所列，则其各参数的定义如下：

准确率：被检测相似句子中实际相似句子所占的比例，衡量的是查准率；

[Precision=TP/（TP+FP）] （3）

召回率：实际相似句子中被检测出的比例，衡量的是查全率；

[Recall=TP/（TP+TN）] （4）

4.3 实验结果分析

通过上述流程介绍，下面进行实验，对本文提出的相似度检测算法进行验证。实验运行环境是CPU 为Intel（R） i5 3210 .2.50GHz，内存 4GB，操作系统为 windows8.1 64bit，采用Java 语言实现算法，并在My Eclipse上运行。

首先对算法运行情况进行分析。从整体流程上看，本文采用的相似检测方法可以分为个主要步骤：文本的语句划分及分词处理、构建特征向量、文本语义指纹生成、指纹对比计算四个过程。

如图2、图3所示，本文算法的经过加入同义词替换等处理的测试文本，文本的准确率和召回率都达到80%以上。而相比之下，传统simhash算法和词频统计算法的两项指标都只有70%左右，通过图2曲线的比较可以很直观地发现本文算法在语义识别上准确率有很大提升。同时，由于简化传统simhash算法根据Tfidf来计算关键词相对值的过程，本文算法在计算速度上也有一定提高，这与理论预期结果相一致。

5 结束语

针对传统的Simhash算法无法处理中文文本信息中一词多义、同义词等语义问题，本文提出一种基于同义词扩展词群编码的语义指纹改进算法，利用同义词词林中的语义项层次结构关系，对检测文本中关键词进行语义词群的扩展，利用词群中的关系信息来融合不同的同义词，再通过基于词性对关键词权值的确定，生成具有语义信息的语义指纹。经过与Simhash算法以及词频统计算法进行比对研究，实验表明，本文中的算法能对相似文本实现快速去重，而且能够保持较高的准确率、召回率以及F1值，弥补了其他算法在文本语义表达方面的不足，特别针对同义词替换的情况。同时，在时间效率上，本文提出的算法相比原始simhash算法，节省了大量无意义的比较计算处理，总体上提高了检测效率。

今后的研究目标是完善语料库，不断改进文本相似检测算法，不仅考虑到词汇对相似度计算的影响，同时挖掘更复杂情况如词汇组合、语句结构修改等方面的检测算法，力求在文本相似度计算中达到更高的准确度。

参考文献：

[1] Moses S.Charikar. Similarity Estimation Techniques from Roundings Algorithms[R].ACM STOC`02. May，2002：19-21.

[2] Sadowski C， Levin G. Simhash： Hash-based similarity detection[R]. Technical report， Google，2007.

[3] Datar M， Immorlica N， Indyk P， et al. Locality sensitive hashing scheme based on p-stable distributions[R].In Proceedings of the ACM Symposium on Computational Geometry.2004.23-36.

[4] 田久樂，赵蔚.基于同义词词林的词语相似度计算方法[J].吉林大学学报：信息科学版，2012，28（6）：602-608.

[5] 张继东，刘萍.基于语料库同义词辨析的一般方法[J].解放军外国语学院学报，2005，28（6）：49-52.

[6] 张敏，宋睿华，马少平，等. 基于语义关系查询扩展的文档重构方法[J].计算机学报，2004，27（10）：1395-1401.