词性分类优先在搜索引擎中的应用

摘要：该论文首先介绍了搜索引擎的三种基本排序算法，然后介绍了中文词性标注的原理和算法，本文重点是将词性标注原理引入到了搜索引擎的应用中，从输入的索引词着手，提出了运用词性分类优先的方法来影响索引文档的排序，即不同词性给予不同的优先级，根据优先级大小依次筛选文档，进而提高索引精度。该方法是在牺牲有效性的基础上提高索引可靠性的。

关键词：排序算法；搜索引擎；词性标注

中图分类号：TP311.1 文献标识码：A文章编号：1007-9599 (2011) 05-0000-03

Speech Classification Priority Application in the Search Engine

Zhang Jingchun1,Guan Shixue1,2,Ma Yuan1

(1.Lanzhou University,College of Information Science and Engineering,Lanzhou730000,China;2.PLA 66483 Troops,Beijing100093)

Astract:The paper first introduces three basic search engine ranking algorithms, and then introduces the principle and algorithms of Chinese part of speech tagging. This paper focus on the index words and puts emphasis on the introduction of the speech tagging principle to a search engine application, and makes use of part of speech classification method to influence the ranking of indexed documents, that is, different parts of speech are given different priority. According to the priority order of the indexed words the documents are selected in order, and then the indexing accuracy is improve. This method is based on the expense of speed to improve the reliability of index.

Keywords:Sorting algorithm;Search engine;Part of speech mark

一、引言

搜索引擎的功能实现分为两大部分，搜集子系统和检索子系统[1]，检索子系统主要对抓取来的网页进行索引，并为用户提供高质量的检索服务。其中输出列表采用的排序算法直接影响着检索的质量，是检索能力的决定性因素。十几年间人们一直在不断探索各种文档的排序算法，有基于词频与位置加权的排序，基于超链分析的排序，基于文档结构的排序，以及多种算法的改进与融合。但总体上看，目前的排序算法主要是在被索引文档方面展开研究的，用户输入关键词仅作为一次搜索的引子。

本文在以上考虑的基础上，引入词性标注和权值门限两个概念。从索引词的输入端着眼，提出了关键词词性分类优先的方法，旨在进一步影响检索系统的网页输出列表。

二、排序算法

（一）基于词频与位置加权的排序算法

基于词频与位置加权的排序算法源自于传统的信息检索中的文本文档加权标引算法[2]，关键词在文档中的地位由两个方面决定，一个是词频因子，指词在文档中出现的频次，频次越高，该词的权重越高；二是逆文档频率因子，指的是包含该关键词的网页越多，这个词就越不重要。同时由于关键词在Web文档中出现的位置不同，对文档的影响力也是截然不同的。一般来说，处于标题(title)、摘要(summary)、头段与尾段以及每段段首句的词更能准确地表达整个文档的主旨，自然它们的权重设置也要适当提高，我们把这种调整称为位置加权。综合考虑以上因素，通过合理的计算就可以得出关键词在网页的权值。在检索过程中，系统会分析用户输入的索引词与系统内所存文档中关键词的匹配程度，从而得出整个Web文档集的排序[3]。

（二）PageRank算法

PageRank算法是由Google创始人之一Larry Page，于1998年在斯坦福大学就读博士研究生期间和SergeyBrin 提出的基于网络链接分析的排序算法[4]。PageRank不是简单地计算一个网页的链接数量（包括链向此网页和由此网页链出的超链数量）来确定网页重要程度的，而是采用了如下算法：

假设A为一个网页，链向它的网页分别为T1、T2、…Tn，从A链出的网页仅计算其链接数量设为C(A)；参数d是取值0到1的阻尼系数(也叫规范化因子，通常取0.85较为合适)，网页A的PageRank值是：

PR(A) = (1-d) + d (PR(T1)/C(T1) + ... + PR(Tn)/C(Tn)) =(1-d)+ （1）

PageRank算法被提出后，人们在此基础上又提出了多种改进的算法。有Topic-sensitive PageRank[5]、加速评估算法[6]和其它一些改进算法，分别对PageRank算法的不足进行了相应的修改补充。

（三）Hits 算法

Hites(hyperlink-induced topic search)算法是与PageRank算法同期由康奈尔大学的Kleinberg提出的[7]，它是一种基于Web结构挖掘的算法。算法认为网页页面有两个方面的属性，一个是权威性(Authority)，被其它网页指向的属性，用A(T)表示；另一个是中心性(Hub)，指向其它网页的属性，用H(T)表示。权威性A(T)用指向自己的网页Ta的中心性H(Ta)衡量，中心性H(T)用自己指向的网页Tb的权威性A(Tb)衡量，a、b为自然数。如下：

（2）

（3）

其中，m、n分别为对应的网页数量。由公式可以得出，权威性和中心性是相互作用的，高权威性网页是由很多高中心性网页所链接的，同时高中心性网页也必然链向很多高权威性网页。

用户查询过程中，系统首先根据输入的关键词得到最相关的一组网页集合形成根集，再对其进行上下扩展，增加它所链接的和链向它的网页地址。然后通过根集特征与扩展集特征的对比，完成对扩展集内网页的筛选，去掉不相关和差别较大的网页。最后计算扩展集内网页的权威值和中心值，并依据此值进行排序[8―9]。

从总体上看，上述排序算法无论是基于内容或是基于链接，还是从结构上考虑，都是从网页角度分析计算来提高排序质量的。那么我们是否可以换一个方向，从关键词词性上分析能否提高排序质量呢?

三、词性标注

词性标注指在给定句子中判定每个词的语法范畴，确定词性并加以标注的过程[10]。具体指的是，在机器对自然文本分词处理后，根据每个词所在文本中的位置和上下文的关系，分析、计算并确定所得词的词性，为信息检索提供基础。词性标注过程对于非兼类词（单性词）容易实现，对于兼类词（一个词在不同的语境中呈现不同的词性）则存在着一定的难度。词性标注的方法主要有基于规则【Greene and Rubin，1971】【Brill，1993】和基于统计【Bahl and Mercer，1976】【Kempe，1993】两大类，在基于统计的方法中，隐马尔可夫模型（Hidden Markov Model 简称HMM）是最主要的算法模型之一【11】。

（一）基于规则方法

核心思想是计算机根据具体的上下文结构框架，套用语言学家总结的语言学规律来判定兼类词的词性【12】。例如，对“作风整顿”中的“整顿”一词进行分析，整顿在词典中判定为兼类词――名词、动词。依据语言规律，在“作风整顿”中，名词后跟名词，“整顿”为名词；在“整顿作风”中，名词前为动词，所以“整顿”为动词。这种方法所依赖的规则库是封闭的系统，所以正确率比较低，只能达到77%[13]。

（二）基于统计方法

在统计的方法中，计算机是在对大量自然语料的统计计算基础上自动生成的规则。其基本思想是，制定词的标志集，选取部分自然语料进行人工词性标注，再利用统计理论进行运算得出统计规律，然后依据统计规律建立统计模型，计算机根据统计模型进行词性标注[12]。其中应用较为广泛、效果较好的是隐马尔可夫模型。

隐马尔可夫模型是在马尔可夫模型的基础上发展起来的，属于马尔可夫链的一种。此模型是一个双重随机过程，可观察事件的随机过程是隐蔽的状态转换过程的随机函数[14]。

在词性标注应用中，隐马尔可夫模型应用十分广泛。假设词的序列W=｛w1，w2，……wn｝作为观察序列，可能的词性序列T=｛t1，t2，……tn｝，作为隐含的状态序列。目的是得到一个T使得P(T|W)最大，用T*表示。根据贝叶斯定理：

（4）

（5）

（6）

上式中 表示词性为 的词 的概率， 表示词性 到词性 的转移概率。

四、词性分类优先的应用

当用户输入的索引词为多个，或者输入一个句子并完成分词后，传统的搜索引擎默认关键词之间是AND关系，多个关键词之间不存在主次。那些对用户来说不重要的关键词可能会在输出文档列表顺序中产生了重要作用，干扰了整体的排列顺序。

本文提出了通过区分词性的方法对得到的所有关键词进行比较，在文档排序过程中，凡是涉及到关键词的部分，不再采用简单地关键词权值相加，而是根据关键词词性的优先级逐层析出的方法来干预排列。

设用户输入的索引词为q1，q2，q3……。搜索引擎根据索引词得到了一个网页集合为P=｛p1，p2，p3，……pn｝，第i个网页内关键词集合为Ki={ki1，ki2，ki3……kin}，因此Ki中至少包含以上索引词中的一个。

根据词性标注算法标注以上所有索引词的词性，在汉语中词性包括：名词、动词、形容词与副词、介词、代词、数词、量词，其它如叹词、拟声词、助词不列为关键词。这里人为设置词性优先顺序为：名词、动词、形容词与副词、数词、量词、代词、介词。把相同词性的关键词作为一个训练项T（各同性词的权值相加作为训练项的权值），因此可以得到七个训练项。当不包含某个词性的关键词时，就没有这个词性的训练项。

在得到的网页集合P内，判断每个网页内关键词是否包含全部索引词，将全部包含的网页作为一个子集S=｛p1，p2，……pm｝，部分包含索引词的网页作为一个子集S’={p1，p2，……pr}，其中m+r=n。在S内，计算每个网页中训练项各自的权值，并做归一化处理（此处理在现有的搜索引擎中已经得到成熟应用），记为W1pi，W2pi，W3pi……Wnpi（ ），分别对应着T1，T2，T3……Tn在网页pi内的权值。算法中，依据词性的优先级别进行分层计算，并在每一层中设置阀值V（0

图1：词性优先的二叉树排列算法

从图1可以得出，S1，S2，……S10是集合S经过四次权值大小的判断细分出来的子集，所有子集网页数量和仍然是集合S内网页数量m。10个子集的优先级是从左到右排列的，S1内网页优先级最高，在输出的列表中排在最前面。

网页集合S’内，由于每个网页包含的关键词略有不同，则会得到不同的处理结果。有的网页可能缺少核心的关键词，有的网页可能仅缺少那些不重要的关键词。对于前者，参考的价值非常小，肯定是要排到最后，或者直接删掉。但对于后者，可能包含重要的网页，如何处理就变得非常重要了。在这里，我们同样选择和S大体上相同的方法。不同之处是在没有某个关键词的节点上，直接跳过，进入下一个节点判断。假设也得到了若干子集，记为：S’1，S’2，S’3……，对于前面几个子集肯定包含了多个重要的关键词，并且权值在门限以上，所以应当把它们也排列在用户容易得到的地方。方法是将S’1，S’2插入到S4与S5之间，因为S4和S5是两个核心关键词训练项（名词、动词）的区分线。

根据上述内容，本文在某搜索引擎的基础上，通过对语句“成为强者的三个基本条件”组成的一组关键词进行两种不同的搜索方式（一个是未区分词性的搜索，一个是区分词性优先级的搜索）。重点针对列表中前20个网页进行人工分析（由于用户在索引过程中关注度主要集中在第一页或者前两页结果上，所以后面众多网页可不作重点处理），并得出了图2所示结果。其中浅色线条为未区分词性时索引列表前20个网页不同词性关键词的权值，深色线条为区分词性后得到的索引列表前20个网页有关词性的权值大小（所有值均作归一化处理）。

图2未区分词性时与区分词性后得到的网页列表前20个网页各词性权值的对比表

从图2可以看出，图Final Result 中两种索引方式所得关键词权值和有一定差距，区分词性后比区分词性前略高一些，前20个网页总体趋势都是从高到低发展。但是结合前面各词性的图表分析会发现，在整体的文档排列中，数量词和形容词在未区分词性的结果起了重要作用，而区分词性后，起决定作用的主要是名词、动词和形容词，数量词不起决定作用。

五、结论

通过以上描述，可以发现，加入词性优先级的分析后，索引列表产生了良性的变化。同时也要注意，算法采用了二叉树形式，门限值V的大小直接影响着排列效果。V值越接近1，所得子集S1内网页数量就越少，结果可能更精确，但精确之余有可能漏掉了重要的网页。所以V的值不能简单的设置，而应该采取统计模型与质量回馈相结合的方法来灵活确定。

通过模拟和理论分析，我们还可以看到在S1到S10十个子集中，不是前面集合的所有网页的权值都大于后面集合内网页的权值。可能存在着这样的情况：pi属于S2，pj属于S3，pj内关键词权值和大于pi内关键词权值和。因为pi(W3>V3，W4