test_input.txt

这是一个小的中文术语提取工具

0.3973996608
0.3973996608
︸    404143424445
当然，由于整个网络的页面数量巨大，采用普通的迭代计算方式将会非常耗
时， L~ncePage和 sergcyBrin提出改进后的算法则大大降低了运算量，并成
功将其投入到实际的运用中。
.PageRank的不足
PageRank值较好地反映网页之间的相互引用关系，被引用较多的网页重要性
也较大，所以能较好地反映页面权威性。但它和主题是相互独立的，没有考虑到
网页和主题之间的相关性，容易造成“主题漂移”现象，即搜索到的网页虽然具有
较高的权威性，但与用户想要的主题无关。
此外，PageRank往往无法正确判断刚刚放到互联的网页的重要性，因为刚放
入W七b的网页有可能没有任何的链接指向它，这时，即便是非常重要的网页
PageRank值也会非常低。
.TOpic一sensitivepageRank算法
斯坦福大学计算机科学系口l’  aherHaveliwala【101提出了一种主题敏感
(Topi~sensitive)的PageRank算法解决了“主题漂流”问题。该算法考虑到有些页
面在某些领域被认为是重要的，但并不表示它在其它领域也是重要的。
算法先根据O伴 nDirectory列出16个基本主题向量，并对每个网页离线计
算出对这些基本主题向量的PageRank值。
在用户查询时，算法根据用户输入的查询主题或查询的上下文，计算出该主
题与已知的基本主题的相似度，在基本主题中选择一个最接近的主题代替用户的
查询主题，并用该基本主题向量的PageRank值对结果进行排序。该算法可以有
效地避免一些明显的主题漂移现象。浙江大学硕士学位论文第2章相关技术的研究现状
 2.3.2HITS算法
HITs(H即eriink一  IndueedTopiesearch)算法[22]是由习einbe嗯在90年代末
提出的一种链接分析算法，它更为精确的分析了页面权威性“Authority’’，Kleinberg
认为页面的重要性应该建立在用户查询条件的基础上，每一页面都分别有
Authority值和Hub值。通常，好的Hub是指向许多好的权威页面;好的权威页
面有许多好的Hub页面所指向。这种Hub和Authority之间的相互作用可用于权
威页面的挖掘和高质量W七b结构和资源的自动发现，这就是HrrS方法的基本思
想。
为便于理解，心einberg用图来表示链接关系，设超链页面的集合v为一个
有向图G二(v，E)，图中的一个节点对应一张网页，有向边印， q)EE表示网页p
链接指向网页q，节点p的出度 (out-degree)指节点p链出的网页数量，而节点p
的入度(in一degree)则指的是链接指向节点p的网页数量。如果集合w是v的一个
子集，则用G[明来表示由w组成的有向图，它的节点包含在w中，边对应于
W中的所有链接。现在假设给定一个泛指主题检索提问。，需要通过链接分析确
定该提问的权威页。HITS算法的流程如下:
l)获得 RootSet用基于文本的搜索引擎如AltaVista或Hotbot来得到。
的查询结果集，取排名最高的前t(t值通常设为200)位作为结果集R(称Root
Set)。
2)扩充 RootSet扩充R分为两个方面，一是将所有R中页所指向的页
面扩充进去;二是将指向R中的每一页面的链接页面取其中任意d(d值通常设定
为50，如果d不大于50，则取其所有页面)个页面扩充到原来的R中形成s(称为
 BaseSet)。S的数量范围一般在 1000至5000。
3)排除干扰为了提高计算效果，幻einberg还将S作了进一步的处理，
他将链接分为两种情况:一是指有链接关系的两个页面处在不同域名之间，这样
的链接称为横向链接;还有一种情况是指有链接关系的两个页面处于同一域名之
下，这样的链接称为内在链接。幻einberg认为内在链接只具有网站内部的导航
功能，它几乎不能传递网页间的authority，因此需要将这种内在链接从s中删去，
形成G。
4)计算hubs和authorities的值对于每一个页面p，用a印)表示页面p
的 authorityweight(权威权重)，用h的表示页面p的 hubweight(中心权重)，使
用下列公式进行迭代计算。
a(尸)=艺h(r，)i=l
n
h(，)一艺a(。，)
 (2.9)
 (2.10)浙江大学硕士学位论文第2章相关技术的研究现状
其中ri是链接到p的页面，qi是页面p链接出去的页面。
5)规范化处理每次迭代计算完之后都需要进行规范化处理，使其能收
敛，页面p经规范化处理后满足以下条件:
艺。(，)2=l
炸S
艺，(，)，=1
作S
 (2.11)
 (2.12)
6)重复过程4)一5)，直到a印)和h印)收敛为止。
 2.33PageRank和HITS算法比较
PageRank和Hrrs均为基于链接分析的搜索引擎排序算法。但两者也存在较
大的差别:
 1)PageRank算法与主题无关，HITS算法同用户的检索主题相关。PageRank
算法独立于检索主题，因此也常被称为query一indePendeni算法。PageRank借鉴
了引文分析的思想，并利用网络自身的超链接结构给所有的网页确定一个重要性
的等级数即PageRank值。HrrS的原理如前所述，其authority值只是相对于某个
检索主题的权重，因此HrrS算法也常被称为query一dePendent算法。
2)权重的传播模型HITS是首先通过基于文本的搜索引擎来获得最初
的处理数据，网页重要性的传播是通过hub页向authority页传递，而且Kleinberg
认为，hub与authority之间是相互增强的关系;而PageRank基于随机冲浪 (random
surfer)模型，可以认为它将网页的重要性从一个authority页传递给另一个authority
页。
3)查询响应时间表面上看，由于authority和hub值的计算是在获得用
户的查询关键字后进行的，虽然网页数量一般为1000至5000个，但由于需要从
基于内容分析的搜索引擎中提取根集并扩充基本集，这个过程需要耗费相当的时
间;在PageRank算法中，PageRar正值计算工作在用户查询时己经由服务器端独
立完成，不需要用户端等待，因此，PageRank算法要比HrrS具有更高的反应速
度。
2.4本章小节
本章首先介绍了三大类的中文分词方法:机械分词、基于统计的分词和基于
规则的分词方法，然后介绍了用于主题相关度判别的计算模型:布尔模型和向量
空间模型，最后介绍了两种较为出名的基于链接的分析技术PageRank和HrrS算
法，并对两者做一个对比。浙江大学硕士学位论文第3章中文分词和主题预测算法
第3章中文分词和主题预测算法
垂直搜索引擎中的关键技术包括中文分词、网络蜘蛛、索引、分布式存储等，
本文重点研究前两项技术。
中文分词是搜索引擎的基础组成部分，分词的好坏直接影响了搜索引擎的各
个环节的工作。中文分词技术有机械分词、基于统计的分词方法和基于规则的统
计方法三种基本类型。结合垂直搜索引擎的特点，本文提出了基于主题的自适应
的分词技术，使用候选词典来指导分词和歧义的消除。
垂直搜索引擎的网络蜘蛛即专业网络蜘蛛的目标是在尽量少地遍历WEB的
前提下，发现尽量多的主题相关的网页。专业网络蜘蛛使用‘， BestFirst’’策略遍历
M触b，因此，需要对网页的主题相关度做预测。本文提出了基于链入网页计算模
型、基于父网页的计算模型和TPR预测算法。
3.1基于主题的自适应的分词方法
基于字符串匹配的分词方法需要使用分词词典，词典的大小和质量直接决定
了分词的效率和质量，为此，维护一个数量适度、更新及时词典具有较大的价值
与意义。结合搜索引擎的特点，本文提出了一种基于主题的自适应的分词方法，
该方法主要包括利用候选词典进行分词、基于专业词库和统计方法消除歧义现
象。
3.1.1候选词典
一般认为，用户提交给搜索引擎的汉字串都是以词的形式存在的，在真心想
通过搜索引擎查找资料的前提下，很少有用户会提交不构成词的汉字串作为搜索
条件提交给搜索引擎，例如，某用户想查找数据库方面关于“数据挖掘”方面的资
料，他可能会提交形如“数据挖掘”、“ datamining”等关键词进行搜索，而不会提
交一些不构成词的字符串给搜索引擎，如“掘挖据数”等乱码。
对提交给搜索引擎的关键词进行统计，当某些关键词的频度超过一定阀值
后，将其纳入候选词典中，另外一方面，当关键词的频度下降到某一阀值时，将
其从候选分词典中移除，及时更新候选词典。
使用候选词典的优势是能保证分词系统与时俱进，能正确地识别某一时间段
特别热门的词如“超女”、‘，PK’，等，这些词往往具有昙花一现的特点，即原先在词
典中不存在这样的词，由于某种原因一段时间非常火暴，在这个时间内它往往作
为一个独立存在的词而存在，分词系统需要将其作为一个词条处理，但是随着时
间的推移，这些词将慢慢谈出人们的视线。
为了正确处理这样的情况，候选词典提供了一个很好的解决方案，候选词典1)1.“洲项士学位论文第3章中文分词和主题预测算法
统计终端用户输入的关键词，并将频度高出一定阀值的入选为候选词典中的词
条，在分词出现未登词串时，将参考候选词典中的词条，如果有匹配成功，则利
用候选词典分词。
此外，如果某些候选词条持续一段相当长的时间仍处于活跃的状态，则将该
词条入选为正式分词词典中的词条。
增加了候选词典后，用户提交的数据流程如图3一1所示:
用用用用用用用用户孰入练仁嘴点点瘫瘫瘫瘫瘫瘫瘫瘫瘫瘫瘫瘫瘫瘫瘫瘫选词典典典                典降降圈;粉翔‘娜娜械徽沈娜叨 叨        叨叨                叨
连询控制器
图3一1用户提交的关键词的数据流程
 3.1.2Aging技术
由于客户端的输入行为是无法控制的，各种各样的输入结果都有可能被提交
给搜索引擎，如果存储每一种可能的输入，那需要极高的代价，同时也是没有必
要的，为此，为了防止候选词典无限制地扩张，必须控制控制候选词典在某一合
理的范围内。
为了解决这个问题，本文提出了aging技术，该技术使候选词典中的所有词
条都在不停地衰老(aging)，另外一方面，用户的输入又让相应的词汇增加生命力。
aging技术移除那些提交的次数不多，不被人们所认可的词汇，由于这些词
条生命力的增长速度(跟被提交的频度成正比)没有衰老速度快，最终会被系统
移除，而另外一些热门词汇，反复地被用户提交，增长速度远快于衰老速度，因
此能长久地保持在候选词典中。
当一个新词条进入候选词典时，我们将该词条的age初始化为。，系统每隔
一段时间(如每天)对候选词典中的所有的词条的age更新一次，使所有词条的
age增加一定的步长(如l)。当发现候选词典中的某些词条的频度被age追赶上
时，即有词条的频度 frequency<=age，则该词条将从候选词典中被移除。
当候选词典中的词条的age超过某一阀值时，我们认定，该词已经生存了相
当长的时间了，可以作为正式的词条进行分词词典中，当然进入分词词典的过程浙江大学硕士学位论文第3章中文分词和主题预测算法
需要人工的干预，以保证分词词典的完整性与正规性。相应地，如果发现某一词
条的生命力不足时，可以将其从正式的分词词典中移除。
3.1.3基于主题的自适应分词算法
分词算法往往分成词串的切分和歧义消除两部分，在词串的切分过程中往往
使用机械分词方法进行初分，然后利用基于统计的方法和其它方法相结合来消除
歧义。这样既发挥了机械分词效率高，又发挥了统计方法能识别新词的优点。
分词工作中最难的部分是歧义和未登词的识别，中文分词问题中歧义字段切
分是影响分词系统切分精度的重要因素，它是中文分词系统设计中的一个最困难
也是最核心的问题。特别是在科技发展日新月异的今天，某些新兴行业的专业术
语层出不穷，这给分词工作带了挑战。
中文分词中存在交集型歧义和多义型歧义两种:
l)交集型歧义字段:在字段ABC中， ABow并且 BCow，则称ABC为
交集型歧义字段。其中A，B，C为字串，W为词典。
2)多义型字段:在字段AB中， ABEW， Aow， BCow，W为词