基于词性分类统计的重复网页和近似网页的识别方法

技术领域

本发明涉及一种重复网页和近似网页的识别方法，尤其涉及一种基于词性 分类统计的重复网页和近似网页的识别方法。

背景技术

随着互联网的深入发展，网页的数量显著增加，搜索引擎也越来越重要。 在对网页的搜索、分类、分析过程中，对重复网页和近似网页的识别也显得越 来越重要。对重复网页和近似网页的识别，能够为互联网信息有序化过程中的 信息去重和整合提供必要依据，提高搜索引擎的检全率和检准率，提升搜索结 果中有效信息含量，提升用户体验。

目前，重复网页和近似网页的识别方法有很多，举例如下：

1、以句法为基准的聚类算法即DSC算法：在DSC算法中，文档由若干个 shingle（shingle表示若干词组成的一个词段）组成，通过比较文本中含有相同 shingle的个数判定网页是否重复。与全文比较而言，此算法降低了比较次数， 但是效率依然较低，因此该方法创始人又提出了一个改进的算法：DSC-SS算法。 DSC-SS算法为了提高效率，将若干个shingle合并成一个大的shingle，并且把 这些大的shingle转换为一个散列值。但是，DSC-SS的效率对当前大规模网页 而言依然较低。

2、在SCAM（Stanford Copy Analysis Mechanism，斯坦福副本分析机制） 系统近似镜像检测算法的基础上提出了后来用于Google系统的分块签名算法： 该算法将文本以词、词序列、句子、段落或者全文为单位分块，把每一个块作 为单独的输入对应地生成一个32比特位的散列值，一篇文档就由若干个32位 的散列值表示。本算法的优点在于分块灵活，查询速度快，缺点是需要频繁的 更新索引。

3、针对中文网页的大规模网页去重算法：在此算法中，提取以句号为中心 的前5个汉字和后5个汉字组成特征码，并且通过B-Tree（多路搜索树）来索 引所用的特征码，减少比较次数，加快对比效率。该算法效率极高，但是网页 页面结构布局的繁复导致该算法无法推广。

4、I-Match算法：对shingle采取了过滤，并且把shingle作为输入生成一个 MD5（MD表示信息摘要算法）值。shingle在全部文档频率中具有不确定性， 导致签名结果不稳定。

5、基于特征串的大规模网页去重算法：本算法在网页内容上引入了网页文 本的结构信息。但是，文本段落顺序的差异或段落的丢失对算法的结果影响较 大。

6、基于网页文本结构的网页去重算法：通过网页结构生成目录结构树。本 算法在镜像网页识别的正确率和召回率极高，但是算法复杂，效率较低，需要 较大的空间维护所有的目录结构树。

7、基于正文结构和长句提取的网页去重算法：本算法动态地、分层地对正 文进行特征抽取和层次指纹计算，保证了去重算法的效率；通过长句提取算法 得到节点指纹，保证了算法的鲁棒性。但是，该算法复杂，开销大，需要为每 一篇网页维护一棵树，对内存资源消耗大。

8、将布隆过滤器算法引入到网页消重技术中，提出了基于布隆过滤器算法 的网页消重技术，此方法时空效率高，但是不足在于，并未能把元素间的全排 列顺序考虑在内，最后生成的二进制数组里内容的顺序不确定。

9、合并特征码、特征句和K-CC（一种改进的基于关键词和特征码的网页 去重算法）算法的基于关键词和特征码的页面去重算法，此算法复杂度较高， 关键词选取采用了贝叶斯模型，需要不断的升级训练样本。

10、基于概念和语义网络的近似网页检测算法：本算法具有良好的时空复 杂度，且不依赖于语料库。但是，此算法在短小网页的处理中由于关键概念识 别困难，而导致算法识别率降低。

综上，过去传统的经典算法较为简单、实用性强，但是互联网发展迅速， 目前网页结构布局复杂，噪声量增多，导致算法失效；而当前现用的算法，能 够应对当前网页结构布局的繁复，降低了噪声的影响，但是算法较为复杂，实 用性较低。

发明内容

本发明的目的就在于为了解决上述问题而提供一种算法步骤简单、实用性 强的基于词性分类统计的重复网页和近似网页的识别方法。

为了达到上述目的，本发明采用了以下技术方案：

本发明包括以下步骤：

（1）从网页文本中提取正文；

（2）对正文进行切词操作；

（3）将切词得到的词语以词性进行分类；

（4）分别对每一类词语进行词频统计；

（5）分别提取每一类词语中词频最高的词语；

（6）将步骤（5）中提取的词语在词级倒排索引中查询，直到查询成功，结 束当前词性类别词语的查询，记录下查询出来的对应文本编号；当查 询完所有当前词性类别词语仍未成功时，则表示当前词性类别的集合 为空；所述词级倒排索引结构如下：

<T，ducument ID_i，ducument ID_j，...,ducument ID_n>

上式中，T表示索引项，即某个词语；document ID_i(i=1,2,...,n) 表示含有T的网页文本编号，所述词级倒排索引用于：以词语为分类标 准，将文档编号按其文档所包含的词语分为若干类，类和类之中的文档 编号存在交集，表明了文档中所有包含的词语；

（7）统计步骤（6）中查找出来的所有文本编号中出现次数最多的文本编号 及其次数；统计所有词性类别的集合中不为空的集合个数；

（8）判断步骤（7）中频率最高的文本次数是否大于或等于1，如果不是， 则转至步骤（9），如果是，则转至步骤（10），所述文本次数=不为空 的集合个数×阈值，其值取下整数，所述阈值的取值范围为大于0且 小于等于1；

（9）将步骤（5）中所有的词频最高的词语添加至所述词级倒排索引，结束；

（10）将步骤（7）中出现次数最多的文本编号添加至类型倒排索引中，所

述类型倒排索引的结构如下：

<ducoment ID_T,ducoment ID_i,ducoment ID_j，...,ducoment ID_n>

上式中，ducoment ID_T表示索引项，document ID_i(i=1,2，...,n)表 示同ducoment ID_T属于重复网页和近似网页的文本编号，所述类型倒排 索引用于：将所有的文档编号以是否为重复网页或近似网页为标准分 类，每一条记录表示一种分类，即一个重复网页或近似网页集合；结束。

具体地，所述步骤（3）中，所述词性的类别包括时间词、人名词、地名词、 机构团体名词、专有名词、其它名词和动词共七类，所述动词为去掉“是”和 “有”后的动词。

作为优选，所述步骤（8）中，所述阈值取0.8。

本发明的有益效果在于：

本发明的算法步骤简单、实用性强，能借助于现有搜索引擎系统已有的模块完 成重复网页和近似网页的识别，和现有传统算法相比，本发明算法在准确率和 召回率方面有明显的提升，其中召回率能够提升10-20个百分点，效果显著。

附图说明

图1是本发明所述识别方法的流程图；

图2是本发明算法与传统算法在准确率和召回率方面的对比示意图。

具体实施方式

下面结合附图对本发明作进一步具体描述：

如图1所示，本发明包括以下步骤：

（1）从网页文本中提取正文；

（2）对正文进行切词操作，对应图1中的“切词”；

（3）将切词得到的词语以词性进行分类，所述词性的类别包括时间词、人 名词、地名词、机构团体名词、专有名词、其它名词和动词共七类， 所述动词为去掉“是”和“有”后的动词；步骤（3）对应图1中的 “以词性分类”；

（4）分别对每一类词语进行词频统计，对应图1中的“分类统计词频”；

（5）分别提取每一类词语中词频最高的词语，对应图1中的“分类高频词 提取”；

（6）将步骤（5）中提取的词语在词级倒排索引中查询，直到查询成功， 结束当前词性类别词语的查询，记录下查询出来的对应文本编号；当 查询完所有当前词性类别词语仍未成功时，则表示当前词性类别的集 合为空；所述词级倒排索引结构如下：

<T，ducument ID_i，ducument ID_j，...,ducument ID_n>

上式中，T表示索引项，即某个词语；document ID_i(i=1,2,...,n) 表示含有T的网页文本编号，所述词级倒排索引用于：以词语为分类 标准，将文档编号按其文档所包含的词语分为若干类，类和类之中的 文档编号存在交集，表明了文档中所有包含的词语；步骤（6）对应 图1中的“词级索引查询”；

（7）统计步骤（6）中查找出来的所有文本编号中出现次数最多的文本编 号及其次数；统计所有词性类别的集合中不为空的集合个数；步骤（7） 对应图1中的“统计频率最高的文档次数，统计不为空的集合个数”；

（8）判断步骤（7）中频率最高的文本次数是否大于或等于1，如果不是， 则转至步骤（9），如果是，则转至步骤（10），所述文本次数=不为空 的集合个数×阈值，其值取下整数，所述阈值的取值范围为大于0且 小于等于1，最佳取值为0.8；步骤（8）对应图1中的“判断频率最 高的文档次数是否大于或等于1”；

（9）将步骤（5）中所有的词频最高的词语添加至所述词级倒排索引，结 束；步骤（9）对应图1中的“词级索引添加”；

（10）将文本编号与步骤（7）中出现次数最多的文本标号添加至类型倒排 索引中，所述类型倒排索引的结构如下：

<ducoment ID_T,ducoment ID_i,ducoment ID_j，...,ducoment ID_n>

上式中，ducoment ID_T表示索引项，document ID_i(i=1,2，...,n) 表示同ducoment ID_T属于重复网页和近似网页的文本编号，结束；步 骤（10）对应图1中的“类型索引添加”。

下面以新闻报道类文章的分析为例，对本发明的具体操作过程进行说明： 设在汉语词性标记集中最能突出新闻报道文章文意的核心词汇为w，w的取值范 围为：

{w∈C|T∪N∪{x∈Ve|x∈V∧x≠x_shi∧x≠x_you}}式I

式I中，T表示时间词类集合，N表示名词类集合，V表示动词类集合，x_shi表示动词“是”，x_you表示动词“有”，Ve表示动词类集合中除去“是”和“有” 后剩下的动词集合。N又可以表示为：

{n|n∈(Na∪Pl∪Og∪Pn∪

式II

式II中，Na、Pl、Og、Pn分别表示人名类集合、地名类集合、机构团体 名类集合和其他专名类集合，On表示除去上述四类名词外的其他名词集合。

由式I和式II可得，核心词汇所分布的词性类集合共7个，分别是：T、Na、 Pl、Og、Pn、On和Ve。

若对属于7个集合中的元素全部加以考虑，存在两个问题：1、在On和Ve集 合中涉及词汇范围广泛，不能突出最具有文章大意特色的词汇；2、词汇量庞大 加重了后续评价系统的压力。基于对上述问题的判断，本发明采用最简单的方 法，以词频作为唯一参考依据，分别在7个集合中选取在原文中词频最高的词 汇认定为本集合的核心词汇。

定义1：假设f(x)(x∈S，S=T，Na，Pl，Og，Pn，On，Ve)表示x在某一 特定文章中出现的次数，若不存在一个σ∈S使得f(σ)>f(x)，那么 x∈max(S)

最后核心词汇范围缩小至：

{w|max(T)∪max(Na)∪max(Pl)∪max(Og)

∪max(Pn)∪max(On)∪max(Ve)}       式III

定义2：假设S_k=T_k,Na_k,Pl_k,Og_k,Pn_k,On_k,Ve_k(k∈document ID)且 当S_i,S_j(i≠j)同为特定集合类型时，若存在一个α使得α∈max(S_i)且 α∈max(S_j)，那么认为S_i以S_j为参考，S_j是S_i的参考，记为S_i→S_j。

定义3：假设S_k=T_k,Pa_k,Pl_k,Og_k,Pn_k,On_k,Ve_k(k∈document ID)，现有 i，j∈document ID且i≠j，令n表示的个数，o表示S_i→S_j成立的个数， 令

$\frac{o}{n\times \delta }\ge 1,(0<\delta \le 1)$式IV

当式IV成立时，认为i→j，其中δ成为判定系数。

由定义2和定义3可知，评价文章内容是否重复或近似时，需要按词性类 别分类比较，当同一词性类别中有一个元素相同时，判定这一词性类别具有参 考性。当具有参考性的词性类别数与有效的词性类别数达到一定比例时，判定 文章内容是重复或是近似，所述比例根据实际情况自行设定，建议比例为80%。 上述方法同样能够用于其它行业的网页识别和分析。

下面以对比试验为例，将本发明算法和传统算法在召回率和准确率方面进 行对比：

从互联网上11家门户网站中随机收集了共578张网页，首先采用传统算法： 由人工对重复网页识别，这时网页以小类计算，共有重复和近似网页61类142 张。在算法正确性评价标准中，采用重复网页召回率（Recall）和去重准确率 （Precision），其定义如下：

如图2所示，通过实验数据的验证发现，本发明算法在准确率和召回率方 面有明显的提升，其中召回率能够提升10-20个百分点，效果显著。