test_input.txt

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

从几个可选择的问题中进行再选择。用户只需输入简单的疑问句，如“  What15the
 meaningor…?”，“   Howeanxdo…?”、“ whereeanl五nd…?”等句式就能直接
获得结果。
垂直搜索引擎的关键技术有中文分词和网络蜘蛛等。中文分词技术是中文搜
索引擎重要的组成部分，自从80年代初中文信息处理领域提出中文分词以来，
中文分词研究全面兴起，取得了一些重要的进展和一些实用性的成果。
目前分词的方法主要可分成三大类:机械分词方法、基于统计的分词方法和
基于理解的分词方法。机械分词方法需要分词词典的支持，具有效率高，算法简
单的特点;基于统计的分词方法根据词的频度来判断成词的概率，这种方法能有
效地识别新词，但效率往往没有机械分词方法高;基于理解的分词方法通过让计
算机模拟人对句子的理解，达到识别词的效果，由于语言知识和语言规则过于复
杂，因而这种方法尚处于研究的阶段。
专业网络蜘蛛技术(FocusedC~ler)是垂直搜索引擎的关键部分，直接决
定了垂直搜索引擎的质量。专业网络蜘蛛从90年代中期的文本分类工作发展而
来，到90年代末已经成为一个热点的研究领域。
专业网络蜘蛛技术的研究成果有:Chal“  abartietal.实现了一个免定制和存储
管理的专业爬行器[3];Rennie和McCalluln[4]将巩固学习(reinforeement
leaming)【51引入网络蜘蛛的学习过程，通过训练发掘出链接文本中“隐含”的结构浙江大学硕士学位论文第1章绪论
信息来指导爬行器工作;Diligenti[6』提出了基于语境图的搜索策略，它通过构建
典型页面的Web’’语境图”来估计离目标页面的距离;为避免PageRank算法的“主
题漂移”问题，斯坦福大学计算机科学系1’a】 lerHaveliwala提出了主题敏感ToPi。
 sensitivePageR毗算法[10]等等。
1.4本文的工作和组织
在中文分词技术方面，本文提出了基于主题的自适应分词技术，使用候选词
典和关键词库来指导分词和歧义消除过程，为了合理地控制候选词典的规模和质
量，提出了Aging技术，使得一部分关键词由于过于衰老而退出候选词典。将基
于主题的分词方法和基于统计的方法相结合具有较高的查全率和查准率。
在专业网络蜘蛛技术方面，提出了基于父网页的主题相关度预测、基于链入
网页的主题相关度预测和TPR算法。基于父网页的主题相关度预测利用了锚文本
和父网页的主题相关度等信息进行预测;基于链入网页的主题相关度预测算法则
综合考虑了链接进入网页的数量和质量;TPR算法将网页的主题相关性和权威性
相结合，从而有效地防止“主题漂流”现象。
此外，为了克服基于“隧道技术”的网络蜘蛛效率低下的Ib1题，本文改进了
“隧道技术”的算法，改进后的隧道技术能在整个Web中拉网式地探索未知网页，
从而发现新 webCo~ity的概率大大得到提高。
下面是本文的章节结构:
第一章绪论
介绍了本文的研究背景及搜索引擎的历史、分类、工作原理和发展趋势。对
比了通用搜索引擎和垂直搜索引擎的优缺点，介绍了垂直搜索引擎，总括全篇的
研究目标和各章内容。
第二章相关技术的研究现状
本章首先介绍三大类的中文分词方法:机械分词、基于统计的分词和基于规
则的分词方法，然后介绍用于主题相关度判别的计算模型:布尔模型和向量空间
模型，最后介绍两种较为出名的基于链接的分析技术PageRank和HrrS算法。
第三章中文分词和主题预测关键算法
本章主要介绍了本文提出的几个主要算法:基于主题的自适应的分词方法、
基于父网页主题预测方法、基于链入网页的主题预测方法和TPR主题预测算法。
第四章基于稀疏隧道技术的 FocusedCrawler
本章首先介绍 FocusedCrawler技术，为了解决 FocusedCrawler的缺点，弓I
进了隧道(Tunneling)技术，最后介绍本文提出的稀疏隧道技术。
第五章系统设计与实现
介绍了系统的设计原型，以及系统的相关技术实现细节。浙江大学硕士学位论文第l章绪论
第六章总结与展望
总结全文，提出了一些不足之处，并对下一步的研究和应用做出展望。
最后是参考文献及致谢。浙江大学硕士学位论文第2章相关技术的研究现状
第2章相关技术的研究现状
本章主要对中文分词技术、专业网络蜘蛛技术和链接分析技术的研究现状做
一个概述，并对其中一些实现细节做探讨。
2.1中文分词技术
汉语以字为基本的书写单位，而作为能够独立活动的有意义的最小语言成分
的却是词。中文信息处理中一个重要的基础课题就是词的切分，也称中文分词，
与拉丁语系的语言以空格作为词界不同，在汉语中词与词之间没有明显的区分标
记【7]，因而中文分词的意义显得格外重要。众所周知，词在中文信息处理的诸多
环节起着重要的作用，当然也包括了搜索引擎。
现有的分词算法可分为三大类:基于字符串匹配的分词方法、基于统计的分
词方法和基于理解的分词方法。机械分词方法需要分词词典的支持，具有效率高，
算法简单的特点，但难以排除机械切分产生的歧义，准确率较差【8];基于统计的
分词方法根据词的频度来判断成词的概率，这种方法能有效地识别新词，时空开
销大，效率有限;基于理解的分词方法通过让计算机模拟人对句子的理解，达到
识别词的效果，由于语言知识和语言规则过于复杂，因而这种方法尚处于研究的
阶段。
2.1.1基于字符串匹配的分词方法
基于字符串匹配的分词方法，又叫做机械分词方法，它是按照一定的策略将
待切分的汉字串与分词词库中的词条进行匹配，若在词库中找到相应的词条，则
匹配成功。目前实用的分词系统基本上都是以基于字符串匹配的分词方法为主，
辅之以少量的词法、语法和语义信息。
按照扫描的方向不同，基于字符串匹配的分词方法可分为正向匹配分词方法
和逆向匹配分词方法;按照优先匹配的长度不同，又可分为最大匹配分词方法和
最小匹配分词方法。总的来说，机械分词方法中共有三种基本的分词方法，分别
是最大正向匹配法、最大逆向匹配法和逐词遍历法。除了这三种基本的方法外，
还可以在分词的过程中使用一些其它技巧，形成新的分词方法，主要有双向扫描
法、设立切分标志法、最佳匹配法和二次扫描法等等。
.最大jE向匹配法(Max如  umMatehingMethod)
该算法通常称为MM法，其基本思想为:设Max为词典中的词条长度的最
大值，str为待切分的句子或字串。如图2一1所示，首先，令Length等于Max，
MM法每次从Str中取出长度为Length的一个子串，把该子串与词典中的词条进
行匹配。若成功，则该子串为词。指针后移Length个汉字后继续匹配下一个词。浙江大学硕士学位论文第2章相关技术的研究现状
若不成功，则把该字串最后一个字去掉，再与词典中的词条进行匹配。如此匹配
下去，直至匹配成功或该子串只剩一个字为止(表示该字可以当作词，可在该字后
面开始切分)。
翼翼熬翼蒸                蒸            
戮戮羹落姗薰薰矛谧娜胭草闭翔翔资召豁  豁黔】级落落            .....娜日刁伫召四 四咬峨戏著著班砍跳蒸蒸  当          当              当        当当蟹必  必  贬          贬              贬贬气粼获获        获  
馨馨鬓藻】                            】
图2一 1MM算法流程
MM分词算法优点是算法简单，不需要任何的词法、句法和语义知识，没有
很复杂的数据结构。唯一的要求就是必须有一个很强大的分词词典，缺点是不能
很好地解决歧义问题，不能认识新词。有统计表明，单纯使用该方法的匹配错误
率为1/169，这种精度还远远不能满足实际的需要。实际使用的分词系统，都是
把机械分词作为一种初分手段，还需通过利用其它的语言信息来进一步提高切分
的准确率。
.逆向最大匹配法   (ReverseMaximtunMatehingMethod)
该算法通常称为RMM算法，它的基本原理与MM算法一样，不同的是分
词的扫描方向，RMM算法从词尾开始切分。根据统计分析，RMM分词算法比
MM算法有更高的切分准确率，切分错误率为1/245。
.逐词遍历法
逐词遍历分词方法是将词典中的词条由长到短递减的顺序，逐个在待处理的
字串或句子中搜索，直到切分出所有的词为止。不论分词词典多大，都得把整个
分词词典匹配一遍。故这种方法的时间复杂度比较高，分词的速度慢、效率不高。
.双向扫描法
双向扫描法的基本原理是分别用MM法和RMM法进行初步的切分，并将浙江大学硕士学位论文第2章相关技术的研究现状
MM法切分的结果与RMM法切分的结果进行比较，如果两种结果一致，则判定
切分正确;如果两种结果不一致，则采用人工干预的方式，或者记频度的算法，
或者结合上下文相关信息选取一种切分。该算法能发现所有的交集型歧义字段，
但对于正、逆向的扫描结果一致但实际切分不正确的字串仍然不能正确处理。
.设立切分标志法
该方法首先在待切分字符串中识别出一些带有明显特征的词，并以这些词作
为断点，可将原字符串切分为较小的串再进行机械分词，从而减少匹配的错误率。
.最佳匹配法
最佳匹配法的原理:在词典中按词的出现频率大小排列词条，高频率的词排
在前，低频率的词排在后，从而缩短分词词典的检索时间，达到最佳效果，加快
分词速度。
.二次扫描法
有统计表明，汉语中词的平均长度为1.83。因此，每次从待切分的字符串中
取两个字符比取最大长度的子串进行匹配的方法相比，前者的效率更高。
该方法的基本做法是:首先从待切分的字符串中取两个汉字记为str，检查分
词词典中是否有这样一个词，它前两个汉字和str相同，若有的话，则取待切分
的字符串中的前三个汉字记为str，重新在分词词典中查找前三个字相同的词条，
如果匹配成功则继续上述过程，直到进行了n个汉字为止(设n为词典中最长词所
含汉字的个数)，则切分出一个n字词;如果匹配不成功则完成了一次扫描;把
str中最后一个汉字去掉，使用MM方法或RMM方法进行第二次切分。
二次扫描法只是改变了MM分词法从词条的最大长度开始匹配的做法，而是
从长度为2的词条开始匹配，这样可以大量地减少匹配失败的次数，从而提高了
分词的效率。
2.1.2基于统计的分词方法
基于统计的分词方法的基本原理:从形式上看，词是稳定的字的组合，因此
在上下文中，相邻的字同时出现的次数越多，就越有可能构成一个词。因此字与
字相邻共现的频率或概率能够较好地反应成词的可信度。
当紧密程度高于某一个闭值时，便可认为此字组可能构成了一个词。这种方
法只需对语料中的字组合的频度进行统计，不需要切分词典，因而又叫做无词典
分词法。但这种方法也有一定的局限性，会经常抽出一些共现频度高、但并不是
词的常用字组，例如“这一”、“之一”、“有的”、“我的”、“许多的”等，并且对常用
词的识别精度差，时空开销大。实际应用的统计分词系统都要使用一部基本的分
词词典(常用词词典)进行串匹配分词，同时使用统计方法识别一些新的词，即
将串频统计和串匹配结合起来，既发挥机械分词切分速度快、效率高的特点，又浙江大学硕士学位论文第2章相关技术的研究现状
利用了基于统计分词方法结合上下文识别生词、自动消除歧义的优点。
计算汉字间紧密程度的统计模型主要有:互信息、t测试两种。
.互信息
定义1:对一包含汉字X和Y的字符，X和Y之间的互信息定义为
，(X，Y)一fogZ彩纂升
式中:了陇Y)—汉字X和Y的互信息;
尸代刀—汉字X和Y联合出现的概率;
尸闪—汉字X出现概率;
尸田—汉字Y出现概率。
 (2.1)
互信息体现了汉字之间结合关系的紧密程度，当紧密程度高于某一个阐值
时，便可认为此字组可能构成了一个词。在公式 (2.1)中，P(x，Y)表示汉字串xy
联合出现的概率，P(X)为X出现的概率，P(Y)为Y出现的概率，可以通过以下公
式计算得出:
P(x，均里〔笙业，P(x)一丝旦，P(均一必
 nnn
 (2.2)
公式(2.2)中，汉字串x、Y和xy出现的次数分别计为n(X)、n(Y)、n(XY)，
汉字串总长度为n。
sProat等最早将互信息用于定量估计两个汉字间的结合力:两汉字间互信息
越大，两个汉字结合的紧密程度越高;互信息越小，结合的紧密程度越低。并给
出了两个相邻汉字断连与否(即是否能够构成词，连则能构成词，断则不能构成词)
的判别规则:互信息超过某一闽值，则连;否则断。
.t测试原理
定义2:对有序汉字串xyz，汉字Y相对于x及z的t测试定义为