搜索引擎的核心内容的详细介绍

5.1 搜索引擎数据的索引---倒排表

参考文献：http://my.opera.com/lau_jia/blog/show.dml/408557

数据的索引分为三个步骤：网页内容的提取（网络蜘蛛）、词的识别（分词算法）、标引库的建立。目前主流的标引技术有三种，倒排文档、后缀数组和签名档。后缀的方法虽然快（超快），但是其维护困难，代价相当高，不适合搜索引擎的索引。签名档是一种很好的标引方式，但是目前据资料称倒排文档的速度和性能已经超过了签名档，因此也排除了。这里着重介绍倒排文档，这是一种在各大搜索引擎中被主要使用的标引方式，并且它也是搜索引擎中的一个很核心的技术。

在介绍前先要明确一下倒排文档所要面向的对象。我们所要标引的对象必须是处在半静态状态下这种方式才是有意义的，也就是说集合是在有规律的时间间隔内（每天，每月）进行更新的，如果每秒数千次，那么这种标引技术的收敛速度就差太多了。但是幸运的是web搜索引擎的文件是符合半静态条件的。

在进入正题前还要说明一点，我这里仅讨论中文的倒排方式，英语的倒排只要在排序结构前加一个trie树结构存放单词就可以了。

先，要知道倒排文档是一种面向单词的标引机制，它为文本集合建立标引，从而加快检索的速度。倒排文档通常由两部分组成：词汇表和事件表。词汇表就是放我们分词词典的地方，事件表就是放这个文档中对应于词汇表中词汇出现的位置，举个例子（举个英文的，可以少打点字），

上面的这种倒排方式称为完全倒排，现在有一种新的叫做块寻址技术（个人认为不适合高速的搜索引擎进行快速查找）。具体方法就是并不标出单词的具体位置，而是先将文本分块，然后再在事件表中标出单词在文本块中的块位置。
还是上面的例子，假设以标点符号为分块依据，

块的方法可以有效的降低倒排文档的体积，缺点是当需要确定某个词的具体位置时还是要打开文件进行查找，但是如果块够小的话，查找主要的开销是I/O操作，但是空间体积又会变大。所以在速度和占内存空间之间要进行权衡。这里要指出一点，I/O操作是很浪费时间的，通常块会取得比较大，如32k以上。

检索的方法

这一部分取决于在构造倒排文档时采用的结构，通常可以用散列（hash）技术，或者trie树或者B（二叉）树来构造倒排表的数据结构。个人推荐使用B树，因为它构造简单，查找效率也不错，但是如果你觉得自己有很强的编程能力的话（很伤身体的），可以考虑使用trie树或hash表。

索引的构筑

由于倒排文档一般很大，不压缩的话和文章本身差不多大（不采用块技术），压缩了也是变小的有限。
一般在建立索引时将索引表分成一个个的子索引，当内存不够时就将子索引合并然后写入硬盘，然后接着建立索引，每次内存不够了就将一部分子索引和硬盘上的文件合并然后存放在硬盘上。大致思想就是这么个过程，具体实现我还没有搞明白，需要慢慢尝试，还望高手执教。

5.2 分词算法

http://www.stlchina.org/twiki/bin/view.pl/Main/SESegment

基于字符串匹配的分词方法(机械分词)

基于理解的分词方法(人工智能，尚在研究中)

基于统计的分词方法

5.3 排序技术（page rank）

http://www.stlchina.org/twiki/bin/view.pl/Main/SESortTech

计算PageRank值有一个简单的公式:

其中：系数为一个大于0，小于1的数。一般设置为0.85。网页1、网页2至网页N表示所有链接指向A的网页。

HillTop算法

HillTop认为只计算 来自具有相同主题的相关文档(“专家”文档)链接对于搜索者的价值会更大：即主题相关网页之间的链接对于权重计算的贡献比主题不相关的链接价值要更高。

当前的搜索引擎的排序技术有两个不足：语意相关性和排序个性化。前者需要完善的自然语言处理技术，后者需要记录庞大访问者信息和复杂 的计算。

5.4网络蜘蛛

http://www.stlchina.org/twiki/bin/view.pl/Main/SECrawlerWeb

在抓取网页的时候，网络蜘蛛一般有两种策略：广度优先和深度优先（如下图所示）。

网站与网络蜘蛛的交互通过Robots.txt的语法和META Tag的语法进行。

内容提取：

搜索引擎建立网页索引，处理的对象是文本文件。

对于doc、pdf等文档，这种由专业厂商提供的软件生成的文档，厂商都会提供相应的文本提取接口。网络蜘蛛只需要调用这些插件的接口，就可以轻松的提取文档中的文本信息和文件其它相关的信息。

HTML等文档是主要的处理对象，要按照http协议来提取内容。

对于多媒体、图片等文件，一般是通过链接的锚文本（即，链接文本）和相关的文件注释来判断这些文件的内容。

动态网页要求网络蜘蛛需要有自己的脚本解释程序。通常这种最难被捉龋

更新周期：

对于大部分的网页，只需要判断网页的属性（主要是日期），把得到的属性和上次抓取的属性相比较，如果一样则不用更新。