互联网搜索引擎工作原理的报告
一、搜索引擎的结构
基本结构：
二、主要功能模块
1
．网络爬虫：
搜索引擎的搜索器又被称为网络爬虫，它日夜不停的在互联网中搜索，不断的访问页面、按超链接跳转、发现新页面，并且1）对页面的信息进行提取、网页快照；2）把页面的地址连同页面信息返回给搜索引擎，交由分析器分析整理。
网络爬虫的任务就是要尽可能多和尽可能快地搜集各种类型的新信息，同时因为互联网上的信息更新很快，所以它还要定期更新已经搜集过的旧信息，以避免死连接和无效连接。比如说打开摆渡搜索某个关键字，在关键字的每个匹配项的最后，就注明了对这个网页的更新日期。
2
．分析器：
分析器的功能是对搜集端数据库中的数据进行筛选和分析。首先对数据量不足的无用网页和非正常页面进行过滤，然后按特定格式将网页压缩成文档，并存于信息数据库内。文档的格式一般包括a.DocID b.url长度 c.页面数据长度 d.url地址 e.页面数据。其中DocID是与通过url换算出的校验值相对应的。
信息数据库保存了所有这些网页的文档信息，按照DocID进行排序。
3
．字典：
字典是一个散列表，它包含大约一千万个关键字和词语，与之对应的是这个字或词唯一的WordID，以及它所在的桶的位置。由于这个字典无论在建立索引还是检索关键字过程中都要频繁使用，所以它被存放在一个内存中。
4
．索引端数据库：
是存储索引的地方，是有很多桶组成的。它分为前向索引桶和后向索引桶两类，其中后向索引桶又分为短索引桶(short barrel)和全索引桶(full barrel)。
5
．索引器和前向索引：
索引器对信息数据库中的文档进行索引，首先对一个文档中的每个有用词汇建立一个采样，把这个文档中相同的词汇的采样归为一组建立一个采样表，并查询字典得到这个词的WordID。当分析完一个文档的全部信息后，然后按照前向索引的方式（DocID->n个WordID+采样表，其中的n数量级应该在1000之下）把这个文档作为索引项加入桶中，这样对信息库的所有文档进行分析，做成一个很庞大的索引。
6
．排序器和后向索引：
排序器把前向索引库重新排列，做成了后向索引库（WordID->m个DocID+采样表，这里的m有可能很小，但也有可能上千万）。因为这样是以WordID为索引关键字，就可以让用户的检索获得很快的相应。另外，从效率和匹配率的双重角度考虑，还把后索引库分为了短索引和全索引，短索引用来存放关键字在标题、锚信息、meta标签中的文档，而关键字在普通文本中的文档放在全索引中，这是因为一般在前一种情况下网页信息对用户更重要一些。
7
．检索器
检索器就是在用户输入关键字后，以尽量快的速度和尽量高的精确率做出反馈。检索器要完成的步骤是：1）解析输入字串，过滤掉无用词汇，提取关键字；2）查找字典，得到WordID和它所在的桶的位置；3）在索引端数据库中进行检索，得到一个匹配网页的集合；4）用权威值算法对网页加权，然后按权值排列这些网页，把权值高的排在考前的位置。
一般检索器考虑先到一类桶（短索引）中查找，如果找到的匹配项不足够多时，再去二类桶进行第二次检索。至于权威值的算法，差不多所有的搜索引擎都在用PageRank算法，或它的改进版本。
三、网页排序与PageRank算法
Google
使用PageRank算法排列网页，这个算法的提出者是九几年斯坦福大学的博士研究生Sergey Brin和Lawrence Page，他俩也就是Google的创始人。别的搜索引擎的排序方法略有变化，但实际上也是以PageRank为原型的。
1
．确定问题域：
当检索算法返回一个对关键字匹配的网页集合V后。返回的页面数量可能非常大，对其完全排序是很难的。这时，首先按照关键字出现频率、出现位置、集中度还有网页本身的权威值筛选出一个较小的集合S，叫做根集root set。然后加入S集所引用的页面和引用了S集的页面，扩展为集合T，这个集合就是排序的问题域。接下来对T使用PageRank方法排序。
2
．PageRank的前置条件：
PageRank
算法所作的假设是
1
）网页的主体之间有相关性，并且体现在他们的相互超链接上。
2
）用户的大部分浏览具有相关性，或者说连贯性，当然也不排除用户直接跳转到无关网页的可能性。
3
）用户顺序浏览网页，忽略了他们后退的情况，也不怎么考虑在网页上驻留的时间。（实际上如果用户在一个页面驻留时间长，那应该付给这个页面更大的权值，可惜很难找到办法计量）
3
．PagePank算法的理论表述：
PageRank
为每个页面制定一个权威值(Authority)。这个权威值的计算方法基本是依据以下的三条:
1
）对于某一个主题，如果一个页面被很多别的页面引用，那么表示这个页面比较重要，要获得较高的权威值：
2
）如果一个页面被很重要的页面（比如说知名的网站Yahoo、sohu）引用，表示这个页面比较重要，也要获得较高的权威值；
3
）页面引用了别的页面，则它把自己的权威值等分后传递给它所引用的其他页面（其实不一定是等分，还要看链接的质量）；
4
．算法实现：
网页集合T加上相互的链接构成了一个有向图，由输出的节点集合为V，又输入的节点集合为U，图的有向边集合为E：
最初，每个输出点有相同的hub值且 ∑hub(v)=1，v∈V；
----------------------------
对每个u∈U执行I操作：Authority(u)=∑hub(v)*1/Nv 其中v∈{v|(v,u) ∈E},Nv是v的链接数；
接下来对v∈V执行O操作：hub(v)= ∑Authority(u)*1/Nu 其中u∈{u|(v,u) ∈E},Nu是u的被链接数；
然后分别对U和V集合的节点规格化，使∑hub(v)=1，∑Authority(u)=1。
----------------------------
循环对其总的节点作以上的操作，直到u和v趋于稳定（可以证明u、v值在多次循环后处于收敛）
5
．一些改进：
有很多人对这个原始算法作了改进和补充，其中比如说：
这个算法没有考虑搜索的主题关键字对排序的影响，所以经常出现的一个问题是出题迁移，排出来的最高权值者可能不是最相关于用户做要搜索的主题了。所以就引入了文档相似度的一个辅助量Similarity(Q,Dj)；
在实际的情况中，一个页面中的很多连接完全可能有一些很重要，与主题密切相关、另一些不重要，只是一些广告什么的，所以有人就提出了ARC算法按不同重要性（锚文本左右相邻的关键字的密度）对权值进行分割，比较准确；
另外，还设立一个阀值，不再把权值低的网页的贡献计入∑hub(v)；
其实还有很多对PageRank的改进算法。
四、之后的工作与研究方向
如何建立便捷与易于维护的索引是我一直在看的。可惜相关的文献都是久远年代的东西了，关于倒排表、后缀树、签名档以及他们衍生物的性能比较也是可能的方向。另外这些东西不单是搜索引擎网站关心的，也是图书馆学的研究课题（一份期刊：Journal of the American Society for Information Science and Technology JASIST）
相关性排序是一个有意思的东西，将pagerank权值引入对网页的相关性排序是Sergey Brin和Lawrence Page的杰作。而这么多年对于算法的准确性和效率的改进一直没有停止，很多人都对如何把搜索结果排的更整齐有自己的看法（所以说它有意思）。有一篇文章：Google の秘密 - PageRank 徹底解説 by Hajime BABA / 馬場肇