万维网WWW（World Wide Web）是一个巨大的，分布全球的信息服务中心，正在以飞快的速度扩展。1998年WWW上拥有约3.5亿个文档[14]，每天增加约1百万的文档[6]，不到9个月的时间文档总数就会翻一番[14]。WEB上的文档和传统的文档比较，有很多新的特点，它们是分布的，异构的，无结构或者半结构的，这就对传统信息检索技术提出了新的挑战。
传统的WEB搜索引擎大多数是基于关键字匹配的，返回的结果是包含查询项的文档，也有基于目录分类的搜索引擎。这些搜索引擎的结果并不令人满意。有些站点有意提高关键字出现的频率来提高自身在搜索引擎中的重要性，破坏搜索引擎结果的客观性和准确性。另外，有些重要的网页并不包含查询项。搜索引擎的分类目录也不可能把所有的分类考虑全面，并且目录大多靠人工维护，主观性强，费用高，更新速度慢[2]。
最近几年，许多研究者发现，WWW上超链结构是个非常丰富和重要的资源，如果能够充分利用的话，可以极大的提高检索结果的质量。基于这种超链分析的思想，Sergey Brin和Lawrence Page在1998年提出了PageRank算法[1] ，同年J. Kleinberg提出了HITS算法[5]，其它一些学者也相继提出了另外的链接分析算法，如SALSA，PHITS，Bayesian等算法。这些算法有的已经在实际的系统中实现和使用，并且取得了良好的效果。
文章的第2部分按照时间顺序详细剖析了各种链接分析算法，对不同的算法进行了比较。第3部分对这些算法做了评价和总结，指出了存在的问题和改进方向。
?
２．WEB超链分析算法
?
２.１ Google和PageRank算法
搜索引擎Google最初是斯坦福大学的博士研究生Sergey Brin和Lawrence Page实现的一个原型系统[2]，现在已经发展成为WWW上最好的搜索引擎之一。Google的体系结构类似于传统的搜索引擎，它与传统的搜索引擎最大的不同处在于对网页进行了基于权威值的排序处理，使最重要的网页出现在结果的最前面。Google通过PageRank元算法计算出网页的PageRank值，从而决定网页在结果集中的出现位置，PageRank值越高的网页，在结果中出现的位置越前。
２.１.１ PageRank算法
? PageRank算法基于下面2个前提：
前提1：一个网页被多次引用，则它可能是很重要的；一个网页虽然没有被多次引用，但是被重要的网页引用，则它也可能是很重要的；一个网页的重要性被平均的传递到它所引用的网页。这种重要的网页称为权威（Authoritive）网页。
前提2：假定用户一开始随机的访问网页集合中的一个网页，以后跟随网页的向外链接向前浏览网页，不回退浏览，浏览下一个网页的概率就是被浏览网页的PageRank值。
简单PageRank算法描述如下：u是一个网页， 是u指向的网页集合， 是指向u的网页集合， 是u指向外的链接数，显然=| | ，c是一个用于规范化的因子（Google通常取0.85），（这种表示法也适用于以后介绍的算法）则u的Rank值计算如下：
这就是算法的形式化描述，也可以用矩阵来描述此算法，设A为一个方阵，行和列对应网页集的网页。如果网页i有指向网页j的一个链接，则 ，否则 ＝0。设V是对应网页集的一个向量，有V=cAV，V为A的特征根为c的特征向量。实际上，只需要求出最大特征根的特征向量，就是网页集对应的最终PageRank值，这可以用迭代方法计算。
如果有2个相互指向的网页a，b,他们不指向其它任何网页，另外有某个网页c，指向a，b中的某一个，比如a，那么在迭代计算中，a，b的rank值不分布出去而不断的累计。如下图：
为了解决这个问题，Sergey Brin和Lawrence Page改进了算法，引入了衰退因子E(u)，E(U)是对应网页集的某一向量，对应rank的初始值，算法改进如下：
其中， ＝1，对应的矩阵形式为V’=c(AV’+E)。
另外还有一些特殊的链接，指向的网页没有向外的链接。PageRank计算时，把这种链接首先除去，等计算完以后再加入，这对原来计算出的网页的rank值影响是很小的。
Pagerank算法除了对搜索结果进行排序外，还可以应用到其它方面，如估算网络流量，向后链接的预测器，为用户导航等[2]。
２.１.２ 算法的一些问题
Google是结合文本的方法来实现PageRank算法的[2]，所以只返回包含查询项的网页，然后根据网页的rank值对搜索到的结果进行排序，把rank值最高的网页放置到最前面，但是如果最重要的网页不在结果网页集中，PageRank算法就无能为力了，比如在 Google中查询search engines，像Google，Yahoo，Altivisa等都是很重要的，但是Google返回的结果中这些网页并没有出现。 同样的查询例子也可以说明另外一个问题，Google，Yahoo是WWW上最受欢迎的网页，如果出现在查询项car的结果集中，一定会有很多网页指向它们，就会得到较高的rank值， 事实上他们与car不太相关。
在PageRank算法的基础上，其它的研究者提出了改进的PageRank算法。华盛顿大学计算机科学与工程系的Matthew Richardson和Pedro Dominggos提出了结合链接和内容信息的PageRank算法，去除了PageRank算法需要的前提2，增加考虑了用户从一个网页直接跳转到非直接相邻的但是内容相关的另外一个网页的情况[3]。斯坦大学计算机科学系Taher Haveliwala提出了主题敏感（Topic-sensitive）PageRank算法[4]。斯坦福大学计算机科学系Arvind Arasu等经过试验表明，PageRank算法计算效率还可以得到很大的提高[22]。
?
２.２ HITS算法及其变种
PageRank算法中对于向外链接的权值贡献是平均的，也就是不考虑不同链接的重要性。而WEB的链接具有以下特征：
1.有些链接具有注释性，也有些链接是起导航或广告作用。有注释性的链接才用于权威判断。
2.基于商业或竞争因素考虑，很少有WEB网页指向其竞争领域的权威网页。
3.权威网页很少具有显式的描述，比如Google主页不会明确给出WEB搜索引擎之类的描述信息。
可见平均的分布权值不符合链接的实际情况[17]。J. Kleinberg[5]提出的HITS算法中引入了另外一种网页，称为Hub网页，Hub网页是提供指向权威网页链接集合的WEB网页，它本身可能并不重要，或者说没有几个网页指向它，但是Hub网页确提供了指向就某个主题而言最为重要的站点的链接集合，比一个课程主页上的推荐参考文献列表。一般来说，好的Hub网页指向许多好的权威网页；好的权威网页是有许多好的Hub网页指向的WEB网页。这种Hub与Authoritive网页之间的相互加强关系，可用于权威网页的发现和WEB结构和资源的自动发现，这就是Hub/Authority方法的基本思想。
２.２.１ HITS算法
HITS（Hyperlink－Induced Topic Search）算法是利用Hub/Authority方法的搜索方法，算法如下：将查询q提交给传统的基于关键字匹配的搜索引擎．搜索引擎返回很多网页，从中取前n个网页作为根集(root set)，用S表示。S满足如下3个条件：
1．S中网页数量相对较小
2．S中网页大多数是与查询q相关的网页
3．S中网页包含较多的权威网页。
通过向S中加入被S引用的网页和引用S的网页将S扩展成一个更大的集合T．
以T中的Hub网页为顶点集Vl，以权威网页为顶点集V2，Vl中的网页到V2中的网页的超链接为边集E，形成一个二分有向图SG＝(V1，V2，E)。对V1中的任一个顶点v，用h(v)表示网页v的Hub值，对V2中的顶点u，用a(u)表示网页的Authority值。开始时h(v)＝a(u)＝1，对u执行I操作修改它的a(u)，对v执行O操作修改它的h(v)，然后规范化a（u），h（v），如此不断的重复计算下面的操作I，O，直到a（u），h（v）收敛。（证明此算法收敛可见 ）
I 操作： （1） O操作： （2）
每次迭代后需要对a(u),h(v)进行规范化处理：
式(1)反映了若一个网页由很多好的Hub指向，则其权威值会相应增加(即权威值增加为所有指向它的网页的现有Hub值之和)。式(2)反映了若一个网页指向许多好的权威页，则Hub值也会相应增加(即Hub值增加为该网页链接的所有网页的权威值之和)。
和PageRank算法一样，可以用矩阵形式来描述算法，这里省略不写。
HITS算法输出一组具有较大Hub值的网页和具有较大权威值的网页。
２.２.２ HITS的问题
HITS算法有以下几个问题：
1．实际应用中，由S生成T的时间开销是很昂贵的，需要下载和分析S中每个网页包含的所有链接，并且排除重复的链接。一般T比S大很多，由T生成有向图也很耗时。需要分别计算网页的A/H值，计算量比PageRank算法大。
2．有些时候，一主机A上的很多文档可能指向另外一台主机B上的某个文档，这就增加了A上文档的Hub值和B上文档的Authority，相反的情况也如此。HITS是假定某一文档的权威值是由不同的单个组织或者个人决定的，上述情况影响了A和B上文档的Hub和Authority值[7]。
3．网页中一些无关的链接影响A，H值的计算。在制作网页的时候，有些开发工具会自动的在网页上加入一些链接，这些链接大多是与查询主题无关的。同一个站点内的链接目的是为用户提供导航帮助，也与查询主题不甚无关，还有一些商业广告，赞助商和用于友情交换的链接，也会降低HITS算法的精度[8]。
4．HITS算法只计算主特征向量，也就是只能发现T集合中的主社区（Community），忽略了其它重要的社区[12]。事实上，其它社区可能也非常重要。
5．HITS算法最大的弱点是处理不好主题漂移问题（topic drift）[7,8]，也就是紧密链接TKC（Tightly-Knit Community Effect）现象[8]。如果在集合T中有少数与查询主题无关的网页，但是他们是紧密链接的，HITS算法的结果可能就是这些网页，因为HITS只能发现主社区，从而偏离了原来的查询主题。下面讨论的SALSA算法中解决了TKC问题。
6．用HITS进行窄主题查询时，可能产生主题泛化问题[5,9]，即扩展以后引入了比原来主题更重要的新的主题，新的主题可能与原始查询无关。泛化的原因是因为网页中包含不同主题的向外链接，而且新主题的链接具有更加的重要性。
２.２.３ HITS的变种
HITS算法遇到的问题，大多是因为HITS是纯粹的基于链接分析的算法，没有考虑文本内容，继J. Kleinberg提出HITS算法以后，很多研究者对HITS进行了改进，提出了许多HITS的变种算法，主要有：
２.２.３.１ Monika R. Henzinger和Krishna Bharat对HITS的改进
对于上述提到的HITS遇到的第2个问题，Monika R. Henzinger和Krishna Bharat在[7]中进行了改进。假定主机A上有k个网页指向主机B上的某个文档d，则A上的k个文档对B的Authority贡献值总共为1,每个文档贡献1/k，而不是HITS中的每个文档贡献1，总共贡献k。类似的，对于Hub值，假定主机A上某个文档t指向主机B上的m个文档，则B上m个文档对t的Hub值总共贡献1，每个文档贡献1/m。I，O操作改为如下
I 操作：
O操作：
调整后的算法有效的解决了问题2，称之为imp算法。
在这基础上，Monika R. Henzinger和Krishna Bharat还引入了传统信息检索的内容分析技术来解决4和5，实际上也同时解决了问题3。具体方法如下，提取根集S中的每个文档的前1000个词语，串连起来作为查询主题Q，文档Dj和主题Q的相似度按如下公式计算：
， ， ＝项i在查询Q中的出现次数，
＝项i在文档Dj中的出现次数，IDFi是WWW上包含项i的文档数目的估计值。
在S扩展到T后，计算每个文档的主题相似度，根据不同的阈值（threshold）进行刷选，可以选择所有文档相似度的中值，根集文档相似度的中值，最大文档相似度的分数，如1/10，作为阈值。根据不同阈值进行处理，删除不满足条件的文档，再运行imp算法计算文档的A/H值，这些算法分别称为med，startmed，maxby10。
在此改进的算法中，计算文档的相似度时间开销会很大。
２.２.３.２ ARC算法
IBM Almaden研究中心的Clever工程组提出了ARC（Automatic Resource Compilation）算法，对原始的HITS做了改进，赋予网页集对应的连结矩阵初值时结合了链接的锚（anchor）文本，适应了不同的链接具有不同的权值的情况。
ARC算法与HITS的不同主要有以下3点：
１．由根集S扩展为T时，HITS只扩展与根集中网页链接路径长度为1的网页，也就是只扩展直接与S相邻的网页，而ARC中把扩展的链接长度增加到2，扩展后的网页集称为增集（Augment Set）。
２．HITS算法中，每个链接对应的矩阵值设为1，实际上每个链接的重要性是不同的，ARC算法考虑了链接周围的文本来确定链接的重要性。考虑链接p－>q，p中有若干链接标记，文本1锚文本文本2，设查询项t在文本1，锚文本，文本2，出现的次数为n（t），则w（p，q）＝1+n（t）。文本1和文本2的长度经过试验设为50字节[10]。构造矩阵W，如果有网页i－>j ，Wi,j＝w（i，j），否则Wi,j＝0，H值设为1，Z为W的转置矩阵，迭代执行下面3个的操作：
（1）A＝WH （2）H＝ZA （3）规范化A，H
３．ARC算法的目标是找到前15个最重要的网页，只需要A/H的前15个值相对大小保持稳定即可，不需要A/H整个收敛，这样2中迭代次数很小就能满足，[10]中指出迭代5次就可以，所以ARC算法有很高的计算效率，开销主要是在扩展根集上。
２.２.３.３ Hub平均（ Hub－Averaging－Kleinberg）算法
Allan Borodin等在[11]指出了一种现象，设有M＋1个Hub网页，M＋1个权威网页，前M个Hub指向第一个权威网页，第M＋1个Hub网页指向了所有M＋1个权威网页。显然根据HITS算法，第一个权威网页最重要，有最高的Authority值，这是我们希望的。但是，根据HITS，第M＋1个Hub网页有最高的Hub值，事实上，第M＋1个Hub网页既指向了权威值很高的第一个权威网页，同时也指向了其它权威值不高的网页，它的Hub值不应该比前M个网页的Hub值高。因此，Allan Borodin修改了HITS的O操作：
O操作： ，n是(v,u)的个数
调整以后，仅指向权威值高的网页的Hub值比既指向权威值高又指向权威值低的网页的Hub值高，此算法称为Hub平均（Hub－Averaging－Kleinberg）算法。
２.２.３.４ 阈值（Threshhold—Kleinberg）算法
Allan Borodin等在[11]中同时提出了3种阈值控制的算法，分别是Hub阈值算法，Authority阈值算法，以及结合2者的全阈值算法。
计算网页p的Authority时候，不考虑指向它的所有网页Hub值对它的贡献，只考虑Hub值超过平均值的网页的贡献，这就是Hub阈值方法。
Authority阈值算法和Hub阈值方法类似，不考虑所有p指向的网页的Authority对p的Hub值贡献，只计算前K个权威网页对它Hub值的贡献，这是基于算法的目标是查找最重要的K个权威网页的前提。
同时使用Authority阈值算法和Hub阈值方法的算法，就是全阈值算法
２.３ SALSA算法
PageRank算法是基于用户随机的向前浏览网页的直觉知识，HITS算法考虑的是Authoritive网页和Hub网页之间的加强关系。实际应用中，用户大多数情况下是向前浏览网页，但是很多时候也会回退浏览网页。基于上述直觉知识，R. Lempel和S. Moran提出了SALSA（Stochastic Approach for Link-Structure Analysis）算法[8]，考虑了用户回退浏览网页的情况，保留了PageRank的随机漫游和HITS中把网页分为Authoritive和Hub的思想，取消了Authoritive和Hub之间的相互加强关系。
具体算法如下：
１．和HITS算法的第一步一样，得到根集并且扩展为网页集合T，并除去孤立节点。
２．从集合T构造无向图G’＝（Vh，Va，E）
Vh={ sh | s∈C and out-degree(s) > 0 } ( G’的Hub边).
Va={ sa | s∈C and in-degree(s) > 0 } (G’的Authority边).
E={ (sh , ra) | s－>r in T }
这就定义了2条链，Authority链和Hub链。
３．定义2条马尔可夫链的变化矩阵，也是随机矩阵，分别是Hub矩阵H，Authority矩阵A。
４．求出矩阵H，A的主特征向量，就是对应的马尔可夫链的静态分布。
５．A中值大的对应的网页就是所要找的重要网页。
SALSA算法没有HITS中相互加强的迭代过程，计算量远小于HITS。SALSA算法只考虑直接相邻的网页对自身A/H的影响，而HITS是计算整个网页集合T对自身AH的影响。
实际应用中，SALSA在扩展根集时忽略了很多无关的链接，比如
１．同一站点内的链接，因为这些链接大多只起导航作用。
２．CGI 脚本链接。
３．广告和赞助商链接。
试验结果表明，对于单主题查询java，SALSA有比HITS更精确的结果，对于多主题查询abortion，HITS的结果集中于主题的某个方面，而SALSA算法的结果覆盖了多个方面，也就是说，对于TKC现象，SALSA算法比HITS算法有更高的健壮性。
２.３.１ BFS（Backword Forward Step）算法
SALSA算法计算网页的Authority值时，只考虑网页在直接相邻网页集中的受欢迎程度，忽略其它网页对它的影响。HITS算法考虑的是整个图的结构，特别的，经过n步以后，网页i的Authority的权重是 ， 为离开网页i的 的路径的数目，也就是说网页j<>i，对i的权值贡献等于从i到j的 路径的数量。如果从i到j包含有一个回路，那么j对i的贡献将会呈指数级增加，这并不是算法所希望的，因为回路可能不是与查询相关的。
因此，Allan Borodin等[11]提出了BFS（Backward Forward Step）算法，既是SALSA的扩展情况，也是HITS的限制情况。基本思想是，SALSA只考虑直接相邻网页的影响，BFS扩展到考虑路径长度为n的相邻网页的影响。在BFS中， 被指定表示能通过 路径到达i的结点的集合，这样j对i的贡献依赖就与j到i的距离。BFS采用指数级降低权值的方式，结点i的权值计算公式如下：
＝ |B(i)|+ |BF(i)| + |BFB(i)|+……+| |
算法从结点i开始，第一步向后访问，然后继续向前或者向后访问邻居，每一步遇到新的结点加入权值计算，结点只有在第一次被访问时加入进去计算。
?
２.４ PHITS
D. Cohn and H. Chang提出了计算Hub和Authority的统计算法PHITS（Probabilistic analogue of the HITS）[12]。他们提出了一个概率模型，在这个模型里面一个潜在的因子或者主题z影响了文档d到文档c的一个链接，他们进一步假定，给定因子z，文档c的条件分布P(c|z)存在，并且给定文档d，因子z的条件分布P（z|d）也存在。
P(d) P(z|d) P(c|z) ，其中
根据这些条件分布，提出了一个可能性函数（likelihood function）L,
，M是对应的连结矩阵
然后，PHITS算法使用Dempster等提出的EM算法[20]分配未知的条件概率使得L最大化，也就是最好的解释了网页之间的链接关系。算法要求因子z的数目事先给定。Allan Borodin指出，PHITS中使用的EM算法可能会收敛于局部的最大化，而不是真正的全局最大化[11]。D. Cohn和T. Hofmann还提出了结合文档内容和超链接的概率模型[13]。
?
２.５ 贝叶斯算法
Allan Borodin等提出了完全的贝叶斯统计方法来确定Hub和Authoritive网页[11]。假定有M个Hub网页和N个Authority网页，可以是相同的集合。每个Hub网页有一个未知的实数参数 ，表示拥有超链的一般趋势，一个未知的非负参数 ，表示拥有指向Authority网页的链接的趋势。每个Authoritive网页j，有一个未知的非负参数 ，表示j的Authority的级别。
统计模型如下，Hub网页i到Authority网页j的链接的先验概率如下给定：
? P（i，j）＝Exp（ ＋ ）/（1＋Exp（ ＋ ））
Hub网页i到Authority网页j没有链接时，P（i，j）＝1/（1＋Exp（ ＋ ））
从以上公式可以看出，如果 很大（表示Hub网页i有很高的趋势指向任何一个网页），或者 和 都很大（表示i是个高质量Hub，j是个高质量的Authority网页），那么i－>j的链接的概率就比较大。
为了符合贝叶斯统计模型的规范，要给2M＋N个未知参数（ ， ， ）指定先验分布，这些分布应该是一般化的，不提供信息的，不依赖于被观察数据的，对结果只能产生很小影响的。Allan Borodin等在 中指定 满足正太分布N（μ， ）,均值μ＝0，标准方差δ＝10，指定 和 满足Exp（1）分布，即x>=0，P( >=x)＝P( >=x)＝Exp（－x）。
接下来就是标准的贝叶斯方法处理和HITS中求矩阵特征根的运算。
２.５.１ 简化的贝叶斯算法
Allan Borodin同时提出了简化的上述贝叶斯算法，完全除去了参数 ，也就不再需要正太分布的参数μ，δ了。计算公式变为：P（i，j）＝ /（1＋ ），Hub网页到Authority网页j没有链接时，P（i，j）＝1/(1＋ )。
Allan Borodin 指出简化的贝叶斯产生的效果与SALSA算法的结果非常类似。
?
２.６ Reputation
上面的所有算法，都是从查询项或者主题出发，经过算法处理，得到结果网页。多伦多大学计算机系Alberto Mendelzon, Davood Rafiei提出了一种反向的算法，输入为某个网页的URL地址，输出为一组主题，网页在这些主题上有声望（repution）[16]。比如输入，www.gamelan.com，可能的输出结果是“java”，具体的系统可以访问htpp://www.cs.toronto.edu/db/topic。
给定一个网页p，计算在主题t上的声望，首先定义2个参数，渗透率 和聚焦率 ，简单起见，网页p包含主题项t，就认为p在主题t上。
?
是指向p而且包含t的网页数目， 是指向p的网页数目， 是包含t的网页数目。结合非条件概率，引入 ， ， 是WEB上网页的数目。P在t上的声望计算如下：
指定 是既指向p有包含t的概率，即 ，显然有
我们可以从搜索引擎（如Altavista）的结果得到 ， , ,WEB上网页的总数估计值 某些组织会经常公布，在计算中是个常量不影响RM的排序，RM最后如此计算：
给定网页p和主题t，RM可以如上计算，但是多数的情况的只给定网页p，需要提取主题后计算。算法的目标是找到一组t，使得RM（p，t）有较大的值。TOPIC系统中是抽取指向p的网页中的锚文本的单词作为主题（上面已经讨论过锚文本能很好描述目标网页，精度很高），避免了下载所有指向p的网页，而且RM（p，t）的计算很简单，算法的效率较高。主题抽取时，还忽略了用于导航、重复的链接的文本，同时也过滤了停止字（stop word），如“a”，“the”，“for”，“in”等。
Reputation算法也是基于随机漫游模型的（random walk），可以说是PageRank和SALSA算法的结合体。
?
３.链接算法的分类及其评价
链接分析算法可以用来提高搜索引擎的查询效果，可以发现WWW上的重要的社区，可以分析某个网站的拓扑结构，声望，分类等，可以用来实现文档的自动分类等。归根结底，能够帮助用户在WWW海量的信息里面准确找到需要的信息。这是一个正在迅速发展的研究领域。
上面我们从历史的角度总结了链接分析算法的发展历程，较为详细的介绍了算法的基本思想和具体实现，对算法的存在的问题也做了讨论。这些算法有的处于研究阶段，有的已经在具体的系统实现了。这些算法大体可以分为3类，基于随机漫游模型的，比如PageRank，Repution算法，基于Hub和Authority相互加强模型的，如HITS及其变种，基于概率模型的，如SALSA，PHITS，基于贝叶斯模型的，如贝叶斯算法及其简化版本。所有的算法在实际应用中都结合传统的内容分析技术进行了优化。一些实际的系统实现了某些算法，并且获得了很好的效果，Google实现了PageRank算法，IBM Almaden Research Center 的Clever Project实现了ARC算法，多伦多大学计算机系实现了一个原型系统TOPIC，来计算指定网页有声望的主题。
AT&T香农实验室的Brian Amento在指出，用权威性来评价网页的质量和人类专家评价的结果是一致的，并且各种链接分析算法的结果在大多数的情况下差别很小[15]。但是，Allan Borodin也指出没有一种算法是完美的，在某些查询下，结果可能很好，在另外的查询下，结果可能很差[11]。所以应该根据不同查询的情况，选择不同的合适的算法。
基于链接分析的算法，提供了一种衡量网页质量的客观方法，独立于语言，独立于内容，不需人工干预就能自动发现WEB上重要的资源，挖掘出WEB上重要的社区，自动实现文档分类。但是也有一些共同的问题影响着算法的精度。
１．根集的质量。根集质量应该是很高的，否则，扩展后的网页集会增加很多无关的网页，产生主题漂移，主题泛化等一系列的问题，计算量也增加很多。算法再好，也无法在低质量网页集找出很多高质量的网页。
２．噪音链接。WEB上不是每个链接都包含了有用的信息，比如广告，站点导航，赞助商，用于友情交换的链接，对于链接分析不仅没有帮助，而且还影响结果。如何有效的去除这些无关链接，也是算法的一个关键点。
３．锚文本的利用。锚文本有很高的精度，对链接和目标网页的描述比较精确。上述算法在具体的实现中利用了锚文本来优化算法。如何准确充分的利用锚文本，对算法的精度影响很大。
４．查询的分类。每种算法都有自身的适用情况，对于不同的查询，应该采用不同的算法，以求获得最好的结果。因此，对于查询的分类也显得非常重要。
当然，这些问题带有很大的主观性，比如，质量不能精确的定义，链接是否包含重要的信息也没有有效的方法能准确的判定，分析锚文本又涉及到语义问题，查询的分类也没有明确界限。如果算法要取得更好的效果，在这几个方面需要继续做深入的研究，相信在不久的将来会有更多的有趣和有用的成果出现。
?
TheEdge推荐 [2007-9-2]
出处：奕天锐新
作者：Christine Churchill
作为搜索者或搜索引擎优化专业人士，你真的需要理解支持搜索引擎的算法和技术吗？在近来召开的一次搜索引擎战略会议上，搜索引擎算法和研究座谈小组专家的答复是肯定的：绝对有必要。
这是一份来自于2005年2月28到3月3日在美国纽约召开的搜索引擎战略会议中的特殊报道。
这个搜索引擎算法和研究座谈小组的成员包括：ASK Jeeves的产品管理和搜索技术副总裁Rahul Lahiri，Smart Interactive(近来被webSourced收购)的CEO，Mike Grehan以及来自于Mi Islita.com的Edel Garcia博士。
问题的来龙去脉是什么？
“我们真的需要了解搜索引擎技术层次上的所有内容吗？”Grehan问道。“是的！”他毫不含糊地进行了回答并继续解释当你理解了搜索引擎算法所带来的竞争优势。
“如果你知道是什么原因使得一个文档的 排名比另外一个要高，你可以有策略地优化并更好地为客户服务。而且，如果你的客户问道：‘为什么我的竞争对手总在前20名，而我却没有？搜索引擎的工作原理是什么？’如果你说‘我不知道——他们就那样——你认为他们还能让自己的账户存在多久？”
Grehan通过引用Brian Pinkerton——在1994年第一个开发出全文本检索搜索引擎的人的解释了自己的观点。“给它照相，”他解释说：“一个客户进入一个大型旅行用品商店，这个商店中什么都有，可用于世界各地的旅游，他看着在那里的小伙子，不加思索地问道 ‘旅游’。你想那个销售人员该从何讲起？”
搜索引擎用户想通过最小的感知和最大的快乐实现他们的目标。他们输入查询时不会仔细考虑的，他们采用不准确的3个词进行搜索，而且也没有学习正确的查询组成。这使得搜索引擎的工作更加困难。
搜索法、充裕问题和算法的演变
Grehan继续谈论搜索法在文件排名中的重要作用。“多种让人着魔事情的组合一道就产生了排名。我们应尽可能多地了解信息，因此，当我们谈论一篇文章的排名为什么要比另一篇高时，我们至少应能拿出一些证据说明正在发生什么。”
Grehan说明了随着时间的推移，搜索引擎算法的进程。早期的搜索引擎中，文本极其重要。但搜索研究家Jon Kleinberg发现了他所称之为的“充裕问题”。当输入一个搜索，然后返回包含适当文本的成千上万个网页时会出现充裕问题。你如何知道哪个是最重要的或者最合适的网页？搜索引擎如何确定哪个网页应出现在搜索结果列表的顶部？搜索引擎算法必须不断地向复杂性方面发展，以便适应过于充裕的问题。
来自于ASK Jeeves的看法
根据来自于ASK Jeeves Rahul Lahiri的说法，在网络上，ASK Jeeves财产 排名第七，在 搜索引擎中排名第四，Lahiri列举了对ASK Jeeves搜索引擎来讲是关键因素的几项内容，包括索引大小、内容的新鲜程度和数据结构。ASK Jeeves对数据结构的关注是很独特的，且通过这种方法与其他搜索引擎进行区分。
在网络搜索中有两种关键的驱动因素：内容分析和链接分析。Lahiri确认ASK Jeeves将网络视为一幅图画并将查看它们之间的链接关系，并尝试绘制相关信息之间的簇。
通过将网络分成不同的信息区块，ASK Jeeves可以根据来自于每个区块的权威“知识”来更好地理解一个查询并将更适应主题的查询结果提供给搜索者。如果你有一个较小的站点，但在你的区块中非常相关，你的站点可能比有些提供相关信息的区块之外大站点排名更好一些。
为什么共现非常重要
Edel Garcia博士被耽误了，未能在座谈小组中给大家作报告，但他准备了一份具有配音说明的PowerPoint文件。主持人Chris Sherman告诉大家，就当幻灯片是由Garcia博士给大家解说的。
Garcia博士是一位对人工智能和信息检索具有特殊兴趣的专家。他解释到，共现的短语更会倾向于被认为是相关的或者“相互联系的”。另外，语义联合影响我们对一个词语的理解。当我们看到“aloha（夏威夷人问候语：欢迎，再见）”一词时，我们想到的是“Hawaii（夏威夷）”，为什么？这是因为词语之间语义的联合。根据Garcia的观点，共现理论可以用来理解词语、商标和产品和服务等等之间的语义联合。
Garcia博士然后提出了一个问题。为什么我们必须关注搜索引擎中的词语联合？他的答案是：考虑一下关键词商标联合。这对搜索市场营销含义非常重要。
如果想了解Garcia博士更多的理论，请访问搜索引擎观察论坛Keywords Co-occurrence and Semantic Connectivity。
座谈会以气氛活跃的问答形式结束。搜索引擎算法的演变趋势如何？Grehan已经有了现成的答案：他期望能引入概率性潜在语义索引和概率性超文本导引主题搜索。那些满口的行话是什么意思？你必须参加下次搜索引擎会议才能找到答案。
（二）
最近一直在研究sphinx的工作机制，在［搜索引擎］Sphinx的介绍和原理探索简单地介绍了其工作原理之后，还有很多问题没有弄懂，比如底层的数据结构和算法，于是更进一步地从数据结构层面了解其工作原理。在网上搜了很多资料，发现没有很多介绍这方面的文章，后来找到了一本书，《这就是搜索引擎》，拜读了本书的第三章，介绍了主流搜索引擎用的数据结构及其工作原理，sphinx使用的数据结构也是一样的，用的也是倒排索引。
注：本文不会对sphinx和搜索引擎严格区分开，同一作搜索引擎看待。
先附图一枚：
先介绍与搜索引擎有关的一些基本概念，了解这些概念对后续了解工作机制非常重要。
单词-文档矩阵是表达两者之间所具有的一种包含关系的概念模型。如下图所示，每列代表一个文档，每行代表一个单词，打对钩的位置代表包含关系。
?
从纵向看，可以得知每列代表文档包含了哪些单词；从横向看，每行代表了哪些文档包含了某个单词。搜索引擎的索引其实就是实现单词-文档矩阵的具体数据结构。可以有不同的方式来实现上述概念模型，比如倒排索引、签名文件、后缀树等方式。但实验数据表明，倒排索引是单词到文档映射关系的最佳实现方式。
文档（Document）：以文本形式存在的存储对象。如：网页、Word、PDF、XML等不同格式的文件。
文档集合（Document Collection）：若干文档构成的集合。如：大量的网页。
文档编号（Document ID）：搜索引擎内部，唯一标识文档的唯一编号。
单词编号（Word ID）：搜索引擎内部，唯一标识单词的唯一编号。
倒排索引（Inverted Index）：实现单词--文档矩阵的一种具体存储形式。倒排索引主要有单词词典和倒排文件组成。
单词词典（Lexicon）：文档集合中出现过的所有单词构成的字符串集合，单词词典内每条索引项记载单词本身的一些信息及指向倒排列表的指针。
倒排列表（PostingList）：出现了某个单词的所有文档的文档列表及单词在该文档中出现的位置信息。列表中每条记录称为一个倒排项（Posting）。
倒排文件（Inverted File）：保存所有单词的倒排列表的文件，倒排文件是存储倒排索引的物理文件。
概念之间的关系如图：
?
下面举一个实例，这样对倒排索引有一个更直观的感受。
假设文档集合包含5个文档，每个文档内容如下图所示：
?
建立的倒排索引如下图：
?
?
单词ID：记录每个单词的单词编号；
单词：对应的单词；
文档频率：代表再文档集合中有多少个文档包含某个单词
倒排列表：包含单词ID及其他必要信息
TF：单词在某个文档中出现的次数
POS：单词在文档中出现的位置
以单词“加盟”为例，其单词编号为8，文档频率为3，代表整个文档集合中有三个文档包含这个单词，对应的倒排列表为{(2;1;<4>),(3;1;<7>),(5;1;<5>)}，含义是在文档2，3，5出现过这个单词，在每个文档的出现过1次，单词“加盟”在第一个文档的POS是4，即文档的第四个单词是“加盟”，其他的类似。
这个倒排索引已经是一个非常完备的索引系统，实际搜索系统的索引结构基本如此。
?
单词词典用来维护文档集合中出现过的所有单词的相关信息，同时用来记载某个单词对应的倒排列表在倒排文件中的位置信息。在查询时到单词词典里查询，就能获得相应的倒排列表，并以此作为后序排序的基础。
?
常用数据结构：哈希加链表和树形词典结构。
下图是哈希加链表词典结构的示意图。主体是哈希表，每个哈希表项保存一个指针，指针指向冲突连表，相同哈希值的单词形成链表结构。
构建过程：
对文档进行分词；
对于做好的分词，利用哈希函数获取哈希值；
根据哈希值对应的哈希表项找到对应的冲突链表；
如果冲突链表已经存在该单词
不处理
否则
加入冲突连表
使用B树或者B+树的结构。与哈希表不同的是，需要字典项能按照大小排序，即使用数字或字符序。
树形结构中，使用层级查找，中间节点保存一定顺序范围的词典项目存储在哪个子树中，最底层的叶子节点存储单词的地址信息。
倒排列表用来记录哪些文档包含了某个单词。倒排列表由倒排索引项组成，每个倒排索引项由文档ID，单词出现次数TD以及单词在文档中哪些位置出现过等信息。包含某单词的一些列倒排索引项形成了某个单词对应的倒排列表。下图是倒排列表示意图：
前面介绍了索引结构，那么，有了数据之后索引是怎么建立的呢？主要有三种建立索引的方法。
此方法在内存里完成索引的创建过程。要求内存要足够大。
第一遍
收集一些全局的统计信息。包括文档集合包含的文档个数N，文档集合内所包含的不同单词个数M，每个单词在多少个文档中出现过的信息DF。
将所有单词对应的DF值全部相加，就可以知道建立最终索引所需的内存大小是多少。
获取信息后，根据统计信息分配内存等资源，同事建立好单词相对应倒排列表在内存中的位置信息。
第二遍
逐个单词建立倒排列表信息。获得包含某个单词的每个文档的文档ID，以及这个单词在文档中的出现次数TF，然后不断填充第一遍扫描时所分配的内存。当第二遍扫描结束的时候，分配的内存正好被填充满，每个单词用指针所指向的内存区域“片段”，其起始位置和终止位置之间的数据就是这个单词对应的倒排列表。
在建立索引过程中，始终在内存中分配固定大小的空间，用来存放词典信息和索引的中间结果，当分配的空间被消耗光的时候，把中间结果写入磁盘，清空内存里中间结果所占空间，以用做下一轮存放索引中间结果的存储区。参考下图：
上图是排序法建立索引中间结果的示意图。建立过程：
读入文档后，对文档进行编号，赋予唯一的文档ID，并对文档内容解析；
将单词映射为单词ID；
建立（单词ID、文档ID、单词频率）三元组；
将三元组追加进中间结果存储区末尾；
然后依次序处理下一个文档；
当分配的内存定额被占满时，则对中间结果进行排序（根据单词ID->文档ID的排序原则）；
将排好序的三元组写入磁盘文件中。
注：在排序法建立索引的过程中，词典是一直存储在内存中的，由于分配内存是固定大小，渐渐地词典占用内存越来越大，那么，越往后，可用来存储三元组的空间越来越少。
建立好索引后，需要合并。
合并时，系统为每个中间结果文件在内存中开辟一个数据缓冲区，用来存放文件的部分数据。将不同缓冲区中包含的同一个单词ID的三元组进行合并，如果某个单词ID的所有三元组全部合并完成，说明这个单词的倒排列表已经构建完成，则将其写入最终索引中，同事将各个缓冲区中对应这个单词ID的三元组内容清空。缓冲区继续从中间结果文件读取后续的三元组进行下一轮合并。当所有中间结果文件都依次被读入缓冲区，并合并完成后，形成最终的索引文件。
归并法与排序法类似，不同的是，每次将内存中数据写入磁盘时，包括词典在内的所有中间结果都被写入磁盘，这样内存所有内容都可以被清空，后续建立索引可以使用全部的定额内存。归并法的示意图如下所示：
?
与排序法的差异：
1、排序法在内存中存放的是词典信息和三元组数据，词典和三元组数据并没有直接的联系，词典只是为了将单词映射为单词ID。归并法则是在内存中建立一个完整的内存索引结构，是最终文章索引的一部分。
2、在将中间结果写入磁盘临时文件时，归并法将这个内存的倒排索引写入临时文件，随后彻底清空所占内存。而排序法只是将三元组数据排序后写入磁盘临时文件，词典作为一个映射表一直存储在内存中。
3、合并时，排序法是对同一单词的三元组依次进行合并；归并法的临时文件则是每个单词对应的部分倒排列表，所以在合并时针对每个单词的倒排列表进行合并，形成这个单词的最终倒排列表。
在真实环境中，搜索引擎需要处理的文档集合内有些文档可能被删除或者内容被修改。如果要在内容被删除或修改之后马上在搜索结果中体现出来，动态索引可以实现这种实时性需求。动态索引有三个关键的索引结构：倒排索引、临时索引和已删除文档列表。
临时索引：在内存中实时建立的倒排索引，当有新文档进入系统时，实时解析文档并将其追加进这个临时索引结构中。
已删除列表：存储已被删除的文档的相应文档ID，形成一个文档ID列表。当文档被修改时，可以认为先删除旧文档，然后向系统增加一篇新文档，通过这种间接方式实现对内容更改的支持。
当系统发现有新文档进入时，立即将其加入临时索引中。有新文档被删除时，将其加入删除文档队列。文档被更改时，则将原先文档放入删除队列，解析更改后的文档内容，并将其加入临时索引。这样就可以满足实时性的要求。
在处理用户的查询请求时，搜索引擎同时从倒排索引和临时索引中读取用户查询单词的倒排列表，找到包含用户查询的文档集合，并对两个结果进行合并，之后利用删除文档列表进行过滤，将搜索结果中那些已经被删除的文档从结果中过滤，形成最终的搜索结果，并返回给用户。
动态索引可以满足实时搜索的需求，但是随着加入文档越来越多，临时索引消耗的内存也会随之增加。因此要考虑将临时索引的内容更新到磁盘索引中，以释放内存空间来容纳后续的文档，此时就需要考虑合理有效的索引更新策略。
对所有文档重新建立索引。新索引建立完成后，老的索引被遗弃释放，之后对用户查询的响应完全由新的索引负责。在重建过程中，内存中仍然需要维护老的索引对用户的查询做出响应。如图所示
有新文档进入搜索系统时，搜索系统在内存维护临时倒排索引来记录其信息，当新增文档达到一定数量，或者指定大小的内存被消耗完，则把临时索引和老文档的倒排索引进行合并，以生成新的索引。过程如下图所示：
更新步骤：
1、当新增文档进入系统，解析文档，之后更新内存中维护的临时索引，文档中出现的每个单词，在其倒排列表末尾追加倒排列表项，这个临时索引可称为增量索引
2、一旦增量索引将指定的内存消耗光，增量索引和老的倒排索引内容需要进行合并。
高效的原因：在对老的倒排索引进行遍历时，因为已经按照索引单词的词典序由低到高排好顺序，所以可以顺序读取文件内容，减少磁盘寻道时间。
缺点：因为要生成新的倒排索引文件，所以老索引中的倒排列表没发生变化也需要读出来并写入新索引中。增加了I/O的消耗。
原地更新策略的出发点是为了解决再合并策略的缺点。
在索引合并时，并不生成新的索引文件，而是直接在原先老的索引文件里进行追加操作，将增量索引里单词的倒排列表项追加到老索引相应位置的末尾，这样就可达到上述目标，即只更新增量索引里出现的单词相关信息，其他单词相关信息不变动。
为了能够支持追加操作，原地更新策略在初始建立的索引中，会在每个单词的倒排列表末尾预留出一定的磁盘空间，这样，在进行索引合并时，可以将增量索引追加到预留空间中。如下图：
实验数据证明，原地更新策略的索引更新效率比再合并策略低，原因：
1、由于需要做快速迁移，此策略需要对磁盘可用空间进行维护和管理，成本非常高。
2、做数据迁移时，某些单词及其对应倒排列表会从老索引中移出，破坏了单词连续性，因此需要维护一个单词到其倒排文件相应位置的映射表。降低了磁盘读取速度及消耗大量内存（存储映射信息）。
将单词根据其不同性质进行分类，不同类别的单词，对其索引采取不同的索引更新策略。常见做法：根据单词的倒排列表长度进行区分，因为有些单词经常在不同文档中出现，所以其对应的倒排列表较长，而有些单词很少见，则其倒排列表就较短。根据这一性质将单词划分为长倒排列表单词和短倒排列表单词。长倒排列表单词采取原地更新策略，而短倒排列表单词则采取再合并策略。
因为长倒排列表单词的读/写开销明显比短倒排列表单词大很多，所以采用原地更新策略能节省磁盘读/写次数。而大量短倒排列表单词读/写开销相对而言不算太大，所以利用再合并策略来处理，则其顺序读/写优势也能被充分利用。
建立好索引之后，如何用倒排索引来响应用户的查询呢？主要有下面三种查询处理机制。
以倒排列表中包含的文档为单位，每次将其中某个文档与查询的最终相似性得分计算完毕，然后开始计算另外一个文档的最终得分，直到所有文档的得分计算完毕为止。然后根据文档得分进行大小排序，输出得分最高的K个文档作为搜索结果输出，即完成了一次用户查询的响应。实际实现中，只需在内存中维护一个大小为K的优先级队列。如下图所示是一次一文档的计算机制示意图：
虚线箭头标出查询处理计算的前进方向。查询时，对于文档1而言，因为两个单词的倒排列表中都包含这个文档，所以可以根据各自的TF和IDF等参数计算文档和查询单词的相似性，之后将两个分数相加得到文档1和用户查询的相似性得分Score1。其他的也是类似计算。最后根据文档得分进行大小排序，输出得分最高的K隔文档作为搜索结果输出。
与一次一文档不同，一次一单词采取“先横向再纵向”的方式，首先将某个单词对应的倒排列表中的每个文档ID都计算一个部分相似性得分，也就是说，在单词-文档矩阵中首先进行横向移动，在计算完某个单词倒排列表中包含的所有文档后，接着计算下一个单词倒排列表中包含的文档ID，即进行纵向计算，如果发现某个文档ID已经有了得分，则在原先得分基础上累加。当所有单词都处理完毕后，每个文档最终的相似性得分计算结束，之后按照大小排序，输出得分最高的K个文档作为搜索结果。 下图是一次一单词的运算机制。
虚线箭头指示出了计算的前进方向，为了保存数据，在内存中使用哈希表来保存中间结果及最终计算结果。在查询时，对于文档1，根据TD和IDF等参数计算这个文档对”搜索引擎“的相似性得分，之后根据文档ID在哈希表中查找，并把相似性得分保存在哈希表中。依次对其他文档计算后，开始下一个单词（此处是”技术“）的相似性得分的计算。计算时，对于文档1，计算了相似性得分后，查找哈希表，发现文档1以及存在得分，则将哈希表对应的得分和刚刚计算得到的得分相加作为最终得分，并更新哈希表1中文档1对应的得分，这样就得到文档1和用户查询最终的相似性得分，类似的计算其他文档，最后将结果排序后输出得分最高的K个文档作为搜索结果。
基本思想：将一个倒排列表数据化整为零，切分为若干个固定大小的数据块，一个数据块作为一组，对于每个数据块，增加元信息来记录关于这个块的一些信息，这样即使是面对压缩后的倒排列表，在进行倒排列表合并的时候也能有两个好处：
1、无须解压所有倒排列表项，只解压部分数据即可
2、无须比较任意两个文档ID。
下图是将“Google”这个查询词对应的倒排列表加入跳跃指针后的数据结构。
假设对于“Google”这个单词的倒排列表来说，数据块的大小为3。然后在每块数据前加入管理信息，比如第一块的管理信息是<<5,Pos1>>，5表示块中第一个文档ID编号，Pos1是跳跃指针，指向第2块的起始位置。假设要在单词“Google"压缩后的倒排列表里查找文档ID为7的文档。首先，对倒排列表前两个数值进行数据解压缩，读取第一组的跳跃指针数据，发现其值为<5,Pos1>，其中Pos1指出了第2组的跳跃指针在倒排列表中的起始位置，于是可以解压缩Pos1位置处连续两个数值，得到<13,Pos2>。5和13是两组数据中最小的文档ID（即每组数据的第一个文档ID），我们要找的是7，那么如果7号文档包含在单词”Google“的倒排列表中的话，就一定会出现在第一组，否则说明倒排列表中不包含这个文档。解压第1组数据后，根据最小文档编号逆向恢复其原始的文档编号，此处<2,1>的原始文档ID是：5+2=7，与我们要找的文档ID相同，说明7号文档在单词”Google“的倒排列表中，于是可以结束这次查找。
从上面的查找过程可知，在查找数据时，只需要对其中一个数据块进行解压缩和文档编号查找即可获得结果，而不必解压所有数据，很明显加快查找速度，并节省内存空间。
缺点：增加指针比较操作的次数。
实践表明：假设倒排列表的长度为L（即包含L个文档ID），使用根号L作为块大小，则效果较好。
即对文档的多个字段进行索引。
实现多字段索引的方式：多索引方式、倒排列表方式和扩展列表方式。
针对每个不同的字段，分别建立一个索引，当用户指定某个字段作为搜索范围时，可以从相应的索引里提取结果。当用户没有指定特定字段时，搜索引擎会对所有字段都进行查找并合并多个字段的相关性得分，这样效率较低。多索引方式示意图如下：
将字段信息存储在某个关键词对应的倒排列表内，在倒排列表中每个文档索引项信息的末尾追加字段信息，这样在读出用户查询关键词的倒排列表的同时，就可以根据字段信息，判断关键词是否在某个字段出现，以此来进行过滤。倒排列表方式示意图如下：
这是用得比较多的支持多字段索引的方法。为每个字段建立一个列表，该列表记录了每个文档这个字段对应的出现位置信息。下图是扩展列表的示意图：
为方便起见，只针对”标题“字段所建立扩展列表。比如第一项<1,(1,4)>，代表对于文档1而言，其标题的位置为从第一个单词到第4个单词这个范围，其他项含义类似。
对于查询而言，假设用户在标题字段搜索”搜索引擎“，通过倒排列表可以知道文档1、3、4包含这个查询词，接下来需要判断这些文档是否在标题字段中出现过查询词？对于文档1，”搜索引擎“这个查询词的出现位置是6和10。而通过对应的标题扩展列表可知，文档1的标题范围是1到4，说明文档1的标题内不包含查询词，即文档1不满足要求。对于文档3，”搜索引擎出现的位置是2、8、15，对应的标题扩展列表中，标题出现范围为1到3，说明在位置2出现的这个查询词是在标题范围内的，即满足要求，可以作为搜索结果输出。文档4也是类似的处理。
短语查询的本质是如何在索引中维护单词之间的顺序关系或者位置信息。较常见的支持短语查询技术包括：位置信息索引、双词索引和短语索引。也可将三者结合使用。
在索引中记录单词位置信息，可以很方便地支持短语查询。但是其付出的存储和计算代价很高。示意图如下：
<5,2,[3,7]>的含义是，5文档包含“爱情“这个单词，且这个单词在文档中出现2次，其对应的位置为3和7，其他的含义与此相同。
查询时，通过倒排列表可知，文档5和文档9同时包含两个查询词，为了判断在这两个文档中，用户查询是否以短语的形式存在，还要判断位置信息。”爱情“这个单词在5号文档的出现位置是3和7，而”买卖“在5号文档的出现位置是4，可以知道5号文档的位置3和位置4分别对应单词”爱情“和”买卖“，即两者是一个短语形式，而根据同样的分析可知9号文档不是短语，所以5号文档会被作为搜索结果返回。
统计数据表明，二词短语在短语中所占比例最大，因此针对二词短语提供快速查询，能解决短语查询的问题。但是这样做的话倒排列表个数会发生爆炸性增长。双词索引的数据结构如下图：
由图可知，内存中包含两个词典，分别是”首词“和”下词“词典，”首词“词典有指向”下词“词典某个位置的指针，”下词“词典存储了紧跟在”首词“词典的常用短语的第2个单词，”下词“词典的指针指向包含这个短语的倒排列表。比如”我的“这个短语，其倒排列表包含文档5和7，”的父亲“这个短语，其倒排列表包含文档5，其余词典也是类似的含义。
对于查询，用户输入”我的父亲“进行查询，搜索引擎将其进行分词得到”我的“和”的父亲“两个短语，然后分别查找词典信息，发现包含”我的“这个短语的是文档5和文档7，而包含”的父亲“这个短语的有文档5。查看其对应的出现位置，可以知道文档5是符合条件的搜索结果，这样就完成了对短语查询的支持。
双词索引会使得索引急剧增大，一般实现并非对所有单词都建立双词索引，而是只对计算代价高的短语建立双词索引。
直接在词典中加入多次短语并维护短语的倒排列表。缺点就是不可能事先将所有短语都建好索引。通用做法就是挖掘出热门短语。下图是加入短语索引后的整体索引结构：
对于查询，当搜索引擎接收到用户查询后，现在短语索引里查找，如果找到，则计算后返回给用户搜索结果，否则仍然利用常规索引进行查询处理。
将三者结合起来，接收到用户查询后，系统首先在短语索引中查找，如果找到则返回结果，否则在双词索引中查找，如果找到则返回结果，否则从常规索引中对短语进行处理，充分发挥各自的优势。3种方式的混合索引结构如下图所示：
短语查询用来对热门短语和高频短语进行索引，双词索引对包含停用词等高代价短语进行索引。
对于查询，系统首先在短语索引中查找，如果找到则返回结果，否则在双词索引中查找，如果找到则返回结果，否则从常规索引中对短语进行处理，这样就充分发挥各自的优势。
当搜索引擎需要处理的文档集合太多的时候，就需要考虑分布式解决方案。每台机器维护整个索引的一部分，有多台机器协作来完成索引的建立和对查询的响应。
将整个文档集合切割成若干个子集合，而每台机器负责对某个文档子集合建立索引，并响应查询请求。按文档划分示意图如下：
工作原理：查询分发服务器接收到用户查询请求后，将查询广播给所有索引服务器。每个索引服务器负责部分文档子集合的索引维护和查询响应。当索引服务器接收到用户查询后，计算相关文档，并将得分最高的K个文档送返查询分发服务器。查询分发服务器综合各个索引服务器的搜索结果后，合并搜索结果，将得分最高的m个文档作为最终搜索结果返回给用户。
每个索引服务器负责词典中部分单词的倒排列表的建立和维护。按单词划分示意图如下：
工作原理：一次一个单词。假设查询包含A、B、C三个单词，查询服务器接收到查询后，将查询转发到包含单词A倒排列表的索引服务器节点1，索引服务器节点1提取A的倒排列表，并累计计算搜索结果的中间的分，然后将查询和中间结果传递给包含单词B倒排列表的索引服务器节点，索引服务器节点2也是类似处理，并继续到索引服务器节点3。然后将最终结果返回给查询分发服务器，查询分发服务器计算得分最高的K个文档作为搜索结果输出。
按文档比较常用，按单词划分只在特殊应用场合才使用。
按单词划分的不足：
可扩展性
搜索引擎处理的文档是经常变动的。如果按文档来对索引划分，只需要增加索引服务器，操作起来很方便。但如果是按单词进行索引划分，则对几乎所有的索引服务器都有直接影响，因为新增文档可能包含所有词典单词，即需要对每个单词的倒排列表进行更新，实现起来相对复杂。
负载均衡
常用单词的倒排列表非常庞大，可能会达到几十M大小。如果按文档划分，这种单词的倒排列表会比较均匀地分布在不同的索引服务器上，而按单词进行索引划分，某个常见单词的倒排列表全部内容都由一台索引服务器维护。如果该单词同时是一个流行词汇，那么该服务器会成为负载过大的性能瓶颈。
容错性
假设某台服务器出现故障。如果按文档进行划分，那么只影响部分文档子集合，其他索引服务器仍然能响应。但如果按单词进行划分，若索引服务器发生故障，则某些单词的倒排列表无法访问，用户查询这些单词的时候，会发现没有搜索结果，直接影响用户体验。
对查询处理方式的支持
按单词进行索引一次只能查询一个单词，而按文档划分的不受此限制。
通过了解搜索引擎使用的数据结构和算法，对其工作原理有了进一步的认识。对于sphinx来说，在线上环境可以考虑增量索引和一次全量索引结合达到实时性的效果。
由于底层基础比较差，花了大半个月重复读了几遍才能弄懂第三章讲的内容，真正体会到数据结构和算法真的很重要。虽然日常工作很少会直接用到数据结构和算法，但是知道了常用的数据结构和算法之后，在遇到问题时就会有更多解决方案的思路，厚积薄发。
到此本文结束，如果还有什么疑问或者建议，可以多多交流，原创文章，文笔有限，才疏学浅，文中若有不正之处，万望告知。
文章来源：https://blog.csdn.net/JackLiu16/article/details/79285438
这是水淼·帝国CMS站群文章更新器的试用版本更新的文章，故有此标记(2020-06-23 09:53:31)
几种搜索引擎算法 SEO
文章版权声明：除非注明，否则均为个人博客原创文章，转载或复制请以超链接形式并注明出处。