主题搜索策略

§3.1 导向词
§3.1.1 导向词及权值的配置
导向词就是一组关键词，它们会引导搜索器按照一定顺序搜索整个网络，使得搜索引擎可以在最短的时间里面得到最全面的跟某一个主题相关的信息。通过设置导向词以及它们对应的不同权值，所有标题、作者、正文或超连接文本中含有某一导向词的网页都会被赋予较高的权值，在搜索的时候会优先考虑。搜索器在向主控程序获得URL的时候也是按照权值由高到低的顺序。反之，搜索器在向主控程序提交新的URL和它的权值的时候，主控程序会按照权值预先排序，以便下一次有序的发给搜索器。
权值的设置有两种方法，第一种是根据管理员的经验手工设置，第二种是给定一个跟主题有关的网页集合，由程序自动提取这些网页里面共同的特征，在这些网页里面都出现的很多的关键词，它就被选作导向词。我们把第二种方法称为"特征提取"。手工设置的好处是实现简单，同时人的经验一般比较准确，跟实际情况不会出现大的偏差，缺点是导向词可能有缺漏，权值的量化定义不够精确；特征提取的优点是权值量化定义精确，但是它要求选取用来提取特征的网页集合必须是非常有代表性而且是全面概括的，否则导向词就可能实现很大的偏差。综合这两种方法的优缺点，我们的系统采用了这两种方法的结合策略：
1．   手工设置好一组导向词和它们对应的权值；
2．   用这组导向词到原搜索引擎中查找出对应的网页；
3．   按权值的比例选取一定数量的网页（比如权值是10，可以选10n个网页）；
4．   用这些网页组成的集合作为特征提取程序的输入，得到一组新的导向词。
以下是以"电影"为主题的一个例子的导向词及权值的配置:
导向词 权值
电影   10
影视   10
导演   10
编剧   10
监制   10
主角   8
配角   8
奥斯卡 5
影星   9
§3.1.2 根据导向词及权值改变搜索顺序
由上一章提到的URL优先级计算公式：
Pirority(URL) = a1 * domain_weight + a2 * link_popularity + a3 * priority(parent_url) + a4 * directory_depth
将导向词及其权值考虑在内，可以得到新的URL优先级计算公式：
Pirority(URL) = a1 * domain_weight + a2 * link_popularity + a3 * priority(parent_url) + a4 * directory_depth + a5 * ∑Oi
§3.2 网页评分(PageRank)
§3.2.1 引用计数(HIT NUMBER)
原系统中在搜索器搜集网页的时候，对于每一个网页数据库中都有一个指向该网页的其他网页总数，称为Hit Number。搜集器每访问一个新的网页，都会逐一检查这个网页的所有超连接，如果发现这些超连接里面有指向已经访问过的网页，那么这个已经访问过的网页的Hit Number将会被相应的加一。由此可见，等到搜索器已经访问过的网页集合足够大的时候（理想情况是整个网络），Hit Number越大，表示这个网页被别人引用得越多，由此可以估计这个网页也越重要。这种网页不论是在搜索器抓取网页这方面，还是在检索器最终给用户返回结构这方面，都应该放在优先处理的位置。
但是，单纯比较两个网页的Hit Number，有时候可能无法估计出这两个网页正确的重要性排序。比如有两个网页，它们在Internet上同样只是被引用了一次。一个是一份已经过时的个人简历，被一个个人网站所引用，除了作者以外基本没有其他人关心；另外一个是当天发生的重大国际新闻，被Yahoo！所引用，每一秒钟都被世界各地不同肤色的数以百计的人浏览。这时候你不能由两个网页的Hit Number一样（都是1）就得出两个网页在Internet上一样重要的结论。
这样，我们需要一个更加深入的指标来评测，这就是下面提到的网页评分（PageRank）。
§3.2.2 网页评分(PAGERANK)
在考虑一个网页被另一个网页的引用时候，不是单纯的将被引用网页的Hit Number加一，而是将引用网页的连接数作为权，同时将该引用网页的重要性也考虑进来（看看上面提到的例子，Yahoo！引用的网页显然比个人网站引用的网页重要，因为Yahoo！本身很重要），就可以得到扩展后的网页评分。
最早提出网页评分的计算方法是Google。它们提出了一个"随机冲浪"模型来描述网络用户对网页的访问行为。模型假设如下：
1)     用户随机的选择一个网页作为上网的起始网页；
2)     看完这个网页后，从该网页内所含的超链内随机的选择一个页面继续进行浏览；
3)     沿着超链前进了一定数目的网页后，用户对这个主题感到厌倦，重新随机选择一个网页进行浏览，并重复2和3。
按照以上的用户行为模型，每个网页可能被访问到的次数就是该网页的链接权值。如何计算这个权值呢？PageRank采用以下公式进行计算：
其中Wj代表第j个网页的权值；lij只取0、1值，代表从网页i到网页j是否存在链接；ni代表网页i有多少个链向其它网页的链接；d代表"随机冲浪"中沿着链接访问网页的平均次数。选择合适的数值，递归的使用以上公式，即可得到理想的网页链接权值。
该方法能够大幅度的提高简单检索返回结果的质量，同时能够有效的防止网页编写者对搜索引擎的欺骗。因此可以将其广泛的应用在检索器提供给用户的网页排序上，对于网页评分越高的网页，就排的越前。
§3.3 权威网页(Authority)和中心网页(Hub)
§3.3.1 什么是权威网页和中心网页
权威网页，顾名思义，是给定主题底下的一系列重要的权威的网页。其重要性和权威性主要体现在以下两点：
第一点，     从单个网页来看，它的网页内容本身对于这个给定主题来说是重要的；
第二点，     从这个网页在整个互联网重的地位来看，这个网页是被其他网页承认为权威的，这主要体现在跟这个主题相关的很多网页都有链接指向这个网页。
由此可见，权威网页对于主题搜索引擎的实现有很重大的意义。主题搜索引擎一个很关键的任务就是从互联网上无数的网页之中最快最准的找出这些可数的权威网页，并为他们建立索引。这也是有效区别主题搜索引擎和前三代传统通用搜索引擎的重要特征。
中心网页，是包含很多指向权威网页的超链接的网页。最典型中心网页的一个例子是Yahoo！，它的目录结构指向了很多主题的权威网页，使得它兼任了很多主题的中心网页。由中心网页出发，轻而易举的就会到达大量的权威网页。因此，它对于主题搜索引擎的实现也起了很大的意义。
权威网页和中心网页之间是一种互相促进的关系：一个好的中心网页必然要有超链接指向多个权威网页；一个好的权威网页反过来也必然被多个中心网页所链接；。他们的关系如图3.1所示。
§3.3.2 发掘权威网页的难度
前三代传统搜索引擎很大程度运用了单个网页内容（网页上出现的关键词）来发掘重要的网页，而忽略了网页在互联网中的地位。用这种方法要从互联网上无数的网页之中找出这些可数的权威网页，有较大的难度。再看一下上面的图3.1，如果每一个权威网页都像图上那样写着"权威"两个字来让你发现，那么我们的工作将会简单的多，可是现实却没有这么理想。
首先，根据关键词出现的频率很难判定这个网页的权威性。考察一下这个例子：比如你想找关于"北京大学"的权威网页。显然，北京大学的主页http://www.pku.edu.cn是互联网上关于"北京大学"最权威的网页之一。用基于关键词的传统的搜索引擎来查找，很自然的会输入"北京大学"或者"北大"。这时候的查询效果不一定很理想。因为互联网上有成千上万包含"北京大学"或"北大"作为关键词的网页（如"北大方正"，"北大在线"，"北京大学网络中心"等），而北大主页并不一定是"北京大学"或"北大"这两个关键词出现的最多最显著的网页。这样，不禁令人猜想到，根本没有一种方法可以从网页内在内容本身来判断这个网页的权威性。
其次，很多权威网页本身并没有包含跟它所属主题相关的关键词。比如你想找出网上"电脑销售"的大公司。如果你以"电脑销售"作为关键词，你很难找到"联想"或"方正"公司的主页，因为他们的主页上根本不会出现"电脑销售"的字眼。但他们的的确确是"电脑销售"的权威网页。
由此我们可以得出结论，要找出权威网页，必须将该网页的内在因素和外在因素都考虑在内，也就是说，除了要分析这个网页包含的关键词，还要分析互联网上其他网页指向这个网页的超链接。
§3.3.3 权威网页和中心网页的计算公式
虽然上面提到了发掘权威网页的难度，但根据权威网页和中心网页互相促进的关系，可用递推的方法循环计算出权威网页和中心网页。对于与某一个主题相关的网页集合中的每一个网页，我们都给他们定义两个参数：A（Authority）和H（Hub）。A值越高表示网页的权威度越高，H值越高表示网页的中心度越高。
将网页集合用有向图G=（V，E）表示，其中节点集V由网页组成，有向边集合E表示网页间的超链接。对于I∈V，A[I]、H[I]分别表示I对应的网页的权威度和中心度。为了控制A[]、H[]的范围，我们将A[]、H[]定义在[0，1]，并且规格化A[]、H[]使得：
∑I∈V(A[I])2 = 1
∑I∈V(H[I])2 = 1
对于每一个节点I，均有：
A[I] = ∑（i，j）∈E(H[J])   ……   （3.1）
H[I] = ∑（i，j）∈E(A[J])   ……   （3.2）
（本文只给出一个计算A值和H值的递推公式，有关该公式的收敛性证明，请参阅参考资料5）
§3.3.4 计算权威网页和中心网页的算法
根据上面提供的公式，我们很容易就得到计算权威网页和中心网页的算法：
计算权威网页和中心网页算法（G，k）
G: 网页集合对应的有向图；
k: 一个常数；
定义z ：向量(1，1， 1，……，1) ∈ R n ；
X0 := z；
Y0 := z；
For i = 1，2，……，k
用 (Xi-1，Yi-1)代入公式(3.1)得到新的Xi‘；
用 (Xi‘，Yi-1)代入公式(3.2)得到新的Xi‘；
规格化Xi‘得到新的Xi；
规格化Yi‘得到新的Yi；
End
Return (Xk，Yk).
§3.4 超链描述文本分析(Hyperlink Anchor Text Analysis)
互联网的魅力在于"互联"，从互联网上任何一个地方出发，就可以轻而易举的到达世界上其它的地方。实现互联是通过一系列的"超级文本链接"（Hypertext Link），可以这样说，没有了"超级文本链接"，互联网会变得不名一文。每一个超级链接都有一个描述文本（Anchor Text），这个文本反映了该网页与该链接所至网页的某种关系，是互联的关键所在。通过分析这个描述文本，就可以得到网页之间重要的关系。
原系统将这个描述文本与其所在的网页关联。我们在新系统的实现中，将描述文本与其所指向的网页相关联。这样做会对程序的编写带来一定的复杂性，因为搜索器在处理当前网页的时候，会遇到这个网页上很多的超链接描述文本，如果将它们都与当前网页关联，处理起来就很简单；否则，如果对于每一个超链接描述文本都将其与目标网页关联，就需要频繁的切换当前处理的网页，影响到了搜索器处理网页的速度。虽然这样做增添了程序的复杂度，但是却有它自身的很多好处：首先，描述文本通常比网页上的文本要更加精确的概括这个网页；其次，基于文本切词的搜索引擎并不能处理网络上的所有格式，比如一些图像，程序，数据库和多媒体等格式的文件，但是依靠超链接里面的描述文本与其关联，即使搜索器本身并没有真的抓取这些格式的文件，也可以索引这些搜索引擎无法直接索引的文件。但是这时候需要注意一个问题，就是通常说的"死链"问题。因为搜索器本身并没有真的抓取这些格式的文件，而只是记录了超链接描述文本，所以这些链接有可能只有描述文本，而它指向的文件根本不存在，这就是"死链"。
§3.5 小结
这一章从导向词、权威和中心网页、超链分析以及网页评分等多种搜集策略入手，阐述了主题搜索引擎的关键设计思想。在这个基础上，笔者将在下一章具体介绍天网主题搜索引擎的实现。
参考文献
[1]   CNNIC，中国互联网络发展状况统计报告，北京，2001年1月
http://www.cnnic.net.cn/develst/cnnic200101.shtml
[2]   Danny Sullivan. Fifth Annual Search Engine Meeting Report, Boston, MA, Apr. 2000.http://websearch.about.com/internet/websearch/library/blsem.htm
[3]   雷鸣 王建勇 赵江华 单松巍 陈葆珏，第三代搜索引擎与天网二期，北大学报，2000年
[4]   Oliver A. McBryan. GENVL and WWWW: Tools for Taming the Web. First International Conference on the World Wide Web. CERN, Geneva (Switzerland), May 25-26-27 1994.http://www.cs.colorado.edu/home/mcbryan/mypapers/www94.ps
[5]   Jon M. Kleinberg， Authoritative Sources in a Hyperlinked Environment
[6]   Krishna Bharata, Andrei Brodera, Monika Henzingera, Puneet Kumara, and Suresh Venkatasubramanianb，The Connectivity Server: fast access to linkage information on the Web，
[7]   Junghoo Cho, Hector Garcia-Molina and Lawrence Page，Efficient crawling through URL ordering,
[8]   L. Page and S. Brin, The anatomy of a search engine, in: Proc. of the 7th International WWW Conference (WWW 98), Brisbane, Australia, April 14-18, 1998.
[9]   北京大学计算机系网络与分布式实验室，"天网中英文搜索引擎概要设计书", 2000年4月8日