搜索引擎

技术架构

网络爬虫：搜索引擎的信息源来自于互联网网页，通过网络爬虫将整个互联网获取到本地。 网页去重：互联网页面中有相当大比例的内容是完全相同或者近似重复的，网页去重模块会对此做出检测，并去除重复内容。 倒排索引：网页内容通过倒排索引这种高效查询数据结构来保存，网页之间的链接关系也会保存。 链接分析：链接关系在网页相关性排序阶段是可利用的，通过链接分析可以判断页面的相对重要性，对于为用户提供准确的搜索结果帮助很大。

云存储与云计算平台：网页数量非常多，搜索引擎不仅需要保存网页原始信息，还需要保存一些中间结果，单台或少量机器是不现实的。优秀的云存储和云计算平台已经称为大型商业搜索引擎的核心竞争力。 查询分析：当搜索引擎接收到用户的查询词后，首先需要对查询词进行分析，推导用户的真正搜索意图。 Cache系统：搜索引擎的缓存系统存储了不同的查询意图对应的搜索结果，如果能够在缓存系统中找到满足用户需求的信息，则可以直接将搜索结果返回给用户。

网页排序：根据用户的查询实时实时计算哪些网页满足用户信息需求，并排序输出作为搜索结果。网页排序最重要的两个参考因素：内容相似性因素、网页重要性因素。 反作弊：作弊将网页的搜索排名提高到与其网页质量不相称的位置，这会严重影响用户的搜索体验。自动发现作弊网页并对其处罚，是搜索引擎非常重要的一部分。

网络爬虫

网络爬虫是通过网页的链接地址来寻找网页，从网站某一个页面开始，读取网页的内容，找到在网页中的其他链接地址，然后通过这些链接地址寻找下一个网页，如此循环下去，直到把这个网站所有网页抓取完为止。

作用：为搜索引擎抓取大量数据；
对象：整个互联网上的网页；

工作原理

基本过程：

为爬虫输送表示起始位置的URL列表；
从种子列表出发，不断爬行发现新的URL
根据某种抓取策略爬行发现新的URL，如此重复

类型：

批量性爬虫：有明确的抓取范围和目标，当爬虫达到这个抓取目标之后，即停止抓取过程。
增量型爬虫：会保持持续不断的抓取，对于抓取到的网页，定期更新
垂直型爬虫：关注特定主题内容或者特定行业的网页

抓取策略

深度优先

依据深度优先的原则，先下载当前网页所链接的URL，追加到待抓取URL队列末尾。

宽度优先

将新下载的网页包含的链接直接追加到待抓取URL队列末尾。

Partial PageRank

对于已经下载的网页，加上待抓取URL队列中的URL一起，形成网页集合
在此集合内进行PageRank计算，将待抓取URL队列里的网页按照PageRank得分降序排列
形成的序列就是爬虫接下来应该依次抓取的URL列表。
一个性能折衷方案是每新下载个网页时，将所有网页重新计算非完全PageRank，对产生的新网页赋临时Pagerank值，若值比较大则优先下载；

OPIC策略(Online Page Importance Computation)

每个互联网页面都给予相同的现金，每当下载了某个页面P之后，P将自己拥有的现金平均分配给P所包含的链接页面，把自己的现金清空。

对于待抓取的URL队列中的网页，则根据手头拥有的现金金额进行排序，优先下载现金最充裕的网页。

不同于Pagerank的迭代计算，OPIC是在线策略，适合实时计算，
PageRank需要考虑无连接关系的网页远程跳转的过程，OPIC没有这一计算因子

大站优先策略(Lager Sites First)

以网站为单位来衡量网页重要性，对于待抓取的URL队列中的网页，如果哪个网站等待下载的页面最多，则优先下载这些链接

网页更新策略

互联网的内容具有动态性，网页更新策略的任务就是决定何时重新抓取已经下载过的网页，使得本地下载的网页和互联网的原始网页内容保持一致；

历史参考策略

假设：过去频繁更新的网页，那么将来也会频繁更新。该策略通过参考其历史更新情况来预估某个网页何时进行更新。

利用泊松过程对网站的变化建模，通过历史的变动情况，利用模型进行预测网页内容何时发生变化；

用户体验策略

更新网页取决于网页的内容变化带来的搜索质量变化；

影响越大的网页，则越快更新；

用户体验策略保存网页的多个历史版本，并根据过去每次内容变化对搜索资料的影响，得出一个平均值，以此作为判断爬虫更新该网页时机的参考依据，影响越大的网页则优先调度进行更新。

聚类抽样策略

具有相似属性的网页，其更新周期也是类似的，只需计算某个类别的更新周期；

对同一类别的网页进行采样，以被采样的网页更新周期作为其他网页的更新周期；

无需保留网页的历史信息。对于新网页也只需要找到其聚类就能进行更新；

与网页更新周期相关的属性有两大类：

静态：页面内容，链接深度，PageRank；
动态：图片数量的变化情况，入链出链的变化情况；

分布式爬虫

分布式技术将抓取任务分布到不同的节点以提高抓取的性能和可拓展性；

层级划分：分布式数据中心，分布式抓取服务器。分布式爬虫程序；

主从式分布爬虫

不同服务器承担不同的角色分工。

URL服务器维护待抓取URL队列，获得待抓取网页的URL，分配给不同的抓取服务器，分配使得各抓取服务器负载均衡。
抓取服务器之间没有通信联系，每个抓取服务器只和URL服务器进行消息传递。

URL服务器承担很多管理任务，同时，待抓取队列数量巨大，因此，URL服务器容易成为整个系统的瓶颈。

对等式分布爬虫

在对等式分布爬虫体系中，服务器之间不存在分工差异，每台服务器承担相同的功能，各自负担一部分URL的抓取工作。该架构中没有URL服务器，则需要服务器自己判断某个URL是否需要自己抓取，或者将读取到的URL传递给其他服务器。

许多对等式分布爬虫通过哈希取模的方法进行任务的分工；

暗网抓取

暗网：目前搜索引擎按常规方式很难抓取到的互联网页面

典型的暗网是垂直领域的网站，通常是网站提供组合查询界面，用户输入查询才能获取数据的页面；

难点：模拟人的行为，填写内容并提交表单，获取数据；

技术：组合查询问题，文本框填写问题；

组合查询问题

查询模板：如果在向搜索引擎提交查询的时候，部分属性被赋予值，其他属性不赋值，则这几个赋值的属性称为查询模板。

对于固定的查询模板，如果给模板内的每个属性都赋值，形成不同的查询组合，提交给搜索引擎，获得的返回结果，如果内容相差甚大，则这个查询模板是富含信息的查询模板。

对于一个固定的垂直搜索来说，其查询模板组合起来有很多，抓取的任务是找到富含信息的查询模板。

ISIT算法：减少提交的查询模板数量

先从1维开始，判断是否是富含信息模板，如果是的话，将该1维模板拓展到2维，再次依次考察对应的二维模板；
如此类推，逐渐增加维数，直到再也找不到富含信息模板为止。

文本框填写问题

对于输入中的文本框，需要爬虫自动生成查询。

可以通过人工观察对网站进行定位，提供一个初始种子查询关键词表，以此作为爬虫工作的基础条件。
通过人工启发结合递归迭代的方式，尽可能覆盖数据库里的记录。

网络协议

URL规范：统一资源定位符,<协议>://<主机>:<端口>/<路径>;
HTTP协议:超文本传输协议,定义了浏览器怎样向万维网服务器请求万维网文档，以及服务器怎样把文档传送给浏览器。
Robots协议:是Web站点和搜索引擎爬虫交互的一种方式，robots.txt是存放在站点根目录下的一个纯文本文件。该文件可以指定搜索引擎爬虫只抓取指定的内容，或者禁止搜索引擎爬虫抓取网站的部分或全部内容。

索引技术

基础

搜索引擎索引是实现单词-文档矩阵的具体的数据结构；

术语	概念
文档	以文本形式存在的存储对象
文档集合	由若干文档构成的集合
文档编号	作为文档的唯一标识
单词编号	作为单词的唯一标识
倒排索引	实现单词—文档矩阵的一种具体存储形式
单词词典	文档集合中出现过的所有单词构成的字符串集合
倒排列表	记载出现过某个单词的所有文档的文档列表、以及单词在该文档中出现的位置信息
倒排文档	顺序存储倒排列表的文件

单词词典

单词词典：用来维护文档集合中出现过的所有单词相关信息，记载某个单词对应的倒排列表在倒排文件中的位置信息；

哈希+链表

主体部分是哈希表，每个哈希表项保存一个指针，指针指向冲突链表，在冲突链表里，相同哈希值的单词形成链表结构。

冲突链表：两个不同单词获得相同的哈希值，这在哈希方法里称为一次冲突，可将相同哈希值的单词存储在链表里，以供后续查找。

建立词典：

对于某个文档出现的单词T，利用Hash函数获取其哈希值；
根据哈希值对应的哈希表项读取并保存其中的指针，找到对应的冲突链表；
若冲突链表中已经存在单词T，则说明该单词之前解析的文档中已经出现过；若未发现该单词，则将其加入冲突链表中。

响应用户请求：

先计算请求的哈希值
定位对应的哈希槽中，获取冲突链表
将查询和链表中的每一个单词进行比较；

树形词典结构

利用B树可以进行高效的查找，前提是字典项具有顺序；

倒排列表

一个倒排索引项描述一个单词和文档相关的信息,形成列表结构，也就是倒排列表；

每一个文档维护一个文档编号DocID
单词在在这个文档出现的次数TF
单词在文档出现的位置...

在实际实现中，并不存储实际的文档编号，二十存储文档编号差值(D-Gap)

相邻两个倒排索引项文档编号的插值
文档编号一般是大数值，这样的作法可以增加数据的压缩率；
文档通常递增，因此通常为大于0的整数；

倒排文档

倒排文档的组成：

关键字（作者，主题词，分类号）
目长：含有关键字记录的条数
记录号集合：所有和该关键字有关的记录号；

倒排文档建立在顺排文档的基础上，它是从主文档中提取可检索字段内容，也有采取自动从标题、文摘或全文中提取关键词，利用所得到的这些属性词来建立倒排文档。

索引建立

两遍遍历文档法

在内存里完成索引的创建过程的，需要对文档进行两遍扫描。

第一次遍历：获得统计信息，根据统计信息分配内存，建立好单词的倒排列表在内存的位置；
第二遍文档遍历：建立每个单词的倒排列表信息；

一个空间上的优化是：始终在内存中分配固定大小的空间，用来存放词典信息和索引的中间结果，当分配的空间消耗完时，把中间结果写进磁盘，清空内存里中间结果所占空间，以用做下一轮存放索引中间结果的存储区。

排序法

排序法是指对中间结果在内存中排序；

基本步骤：

读入一个文档后，给文档进行编号，赋予唯一的文档ID，并对文档内容解析；
对于文档中出现的单词，通过查词典将单词转换为对应的单词ID，如果词典中没有这个单词，说明是第一次检测到，则赋予单词唯一的单词ID并插入词典中。
对该文档内每个单词建立一个（单词ID，文档ID，单词频率）三元组，这个三元组就是单词对应文档的倒排列表项，将这个三元组追加进入中间结果存储区末尾。
对文档内的所有单词都经过如此处理，形成三元组序列的形式，处理完成以后，开始依次序处理下一文档，如此循环。
当分配的内存空间被占满时，对三元组中间结果进行排序。排序的原则：
- 主键是单词ID，即首先要按照单词ID由小到大排序；
- 次键是文档ID，即在相同单词ID的情况下，按照文档ID由小到大排序。
然后将排好序的三元组写入临时文件中，空出内存来进行后续文档的处理。

注意，在建立索引的过程中，词典一直存储在内存中，每次清空内存只是将中间结果写入磁盘；

最终的文档处理完毕后，需要对中间结果进行合并，由于每个中间结果都是有序的

在合并中间结果的过程中，系统为每个中间结果文件在内存中开辟一个数据缓冲区，用来存放文件的部分数据。
将不同缓冲区中包含的同一个单词ID的三元组进行合并。
如果某个单词ID的所有三元组全部合并完成，说明这个单词的倒排列表已经构建完成，则将其写入最终索引中，同时将各个缓冲区中对应这个单词ID的三元组内容清空，这样缓冲区就可以继续从中间结果文件中读入后续的三元组来进行下一个单词的三元组合并。

归并法

分两个阶段进行

在内存中维护中间结果，当内存占满后，将内存数据写入磁盘临时文件
对临时文件进行归并，形成最终索引，

需要在内存建立索引结构，描述目前处理的文档子集；

在将中间结果写入磁盘临时文件时，将整个内存的倒排索引写入临时文件。依次将单词和对应的倒排列表写入磁盘文件，随后彻底清空所占内存。

动态索引

组成：

倒排索引：在磁盘中已经存在的索引；
临时索引：在内存中实时建立的倒排索引
已删除文档列表：用来存储已被删除的文档的相应的文档ID，形成一个文档ID列表。

动态索引的处理办法：

当系统发现有新文档进入时，立即将其加入到临时索引结构中。
当文档被删除时，则将其加入删除文档队列。
当文档被更改时，则将原始文档放入已删除队列，解析更改后的文档内容，并将其加入临时索引中。

对于查询请求，如何形成准确的搜索结果？

同时从倒排索引和临时索引中读取对应的倒排列表；
找到的文档集合进行合并；
在文档删除列表过滤；

索引更新

完全重建策略

当新增文档达到一定数量，将新增文档和原先的老文档进行合并，然后利用建立静态索引的方式，对所有文档重新建立索引。

新索引建立完成后，老的索引被遗弃释放，之后对用户查询的相应完全由新的索引来负责。

由于重建索引需要较长的时间，在进行索引重建过程中，内存中仍然需要维护老的索引来应对用户的查询请求。只有当新索引建立完成后，才能释放旧的索引，将用户查询请求切换到新索引上。

再合并策略Re-Merge

当新增文档进入搜索系统时，搜索系统在内存维护临时倒排索引来记录信息，当新增文档达到一定数量，或者指定大小的内存被消耗完，则把临时索引和老文档的倒排索引进行合并，以生成新的索引。

步骤如下：

当新增文档进入系统，解析文档，之后更新内存中的临时索引，文档中出现的每个单词，在其倒排列表末尾追加倒排列表项，这个临时索引可称为增量索引。
增量索引将指定的内存消耗光后，此时需要进行一次索引合并，即将增量索引和旧文档的倒排列表索引进行合并。
在合并过程中，需要一次遍历增量索引和老索引单词词典中包含的单词及其对应的倒排列表，可以用两个指针分别指向两套索引中的目前需要合并的单词：
- 如果这个单词在词典序中小于老索引的单词指针指向的单词，说明这个单词在旧索引中未出现过，则直接将这个单词对应的倒排列表写入新索引的倒排文件中，同时增量索引单词指针后移指向下一个单词。
- 如果两个单词指针指向的单词相同，说明这个单词同时在增量索引和旧索引中同时出现，则将老索引中这个单词的倒排列表写入新索引的倒排列表，然后把增量索引中这个单词的倒排列表追加到其后，这样就完成了这个单词所有倒排列表的合并。
- 如果某个单词仅在老索引中出现过，即发现老索引的单词指针指向的单词，其词典序小于增量索引单词指针指向的单词，则直接将老索引中对应的倒排列表写入新索引倒排文件中。新索引的单词指针后移指向下一个单词，继续合并。

由于在磁盘的老索引(倒排文档对应的倒排列表，保存为文件)是顺序的，增量索引在遍历词典的时候也按照字典顺序由低到高排列，可以只对倒排文件进行一遍扫描，顺序读取，减少了IO开销(文件操作中比较耗时的磁盘寻道时间)，提高合并效率。

这个再合并策略类似于归并排序；

优点：老的倒排索引是顺序结构，遍历时可以顺序读取文件内容，减少磁盘寻道时间，高效更新。
缺点：需要生成新的倒排索引文件，但是老索引很多单词的倒排列表其实没发生什么变化，也需要从老索引中读取出来并写入新索引文件中，这一操作非常耗时，带来大量的IO开销；

原地更新策略In-Place

在索引合并时，并不生成新的索引文件，而是直接在老的索引文件里进行追加操作，将增量索引里单词的倒排列表项追加到老索引相应位置的末尾。即只更新增量索引里出现的单词相关信息，其他单词相关信息不做变动。

策略步骤如下：

老索引中每个单词的倒排列表末尾都预留出空余磁盘空间，以作为信息追加的存储区域。
在对新增索引进行合并时，按照词典序，依次遍历新增索引中包含的单词，并对新增倒排列表的大小和老索引中相应预留空间大小进行比较：
- 如果预留空间足够大，则将新增列表追加到老索引后面即可；
- 如果预留空间不足以容纳新增倒排列表，则在磁盘中找到一块完整的连续存储区，这个存储区足以容纳这个单词的倒排列表，然后，将老索引中的倒排列表读出并写入新的磁盘位置，并将增量索引对应的倒排列表追加到其后。

缺点：

对于倒排文件中的相邻索引单词，其倒排列表顺序一般是按照相邻单词的词典序存储的，但是由于原地更新策略对单词的倒排列表做数据迁移，某些单词及其对应倒排列表会从老索引中移出

这样就破坏了这种单词连续性，导致在进行索引合并时不能进行顺序读取，必须维护一个单词到其倒排文件相应位置的映射表
一方面降低了磁盘读取速度，另外一方面需要大量的内存来存储这种映射信息。

混合策略

混合策略的出发点是能够结合不同索引更新策略的长处，将不同的索引更新策略混合，以形成更高效的方法。常用的混合策略是根据单词的倒排列表长度进行区分：

对于经常在不同的文档中出现的单词，其对应的倒排列表较长，称为长倒排列表单词，采取原地更新策略；
对于少见的一些单词，其倒排列表较短，称为短倒排列表单词，则采取再合并策略。

查询处理

一次一文档(Doc at a time)

以倒排列表中包含的文档为单位，每次将其中某个文档与查询的最终相似性得分计算完毕，然后开始计算另外一个文档的最终得分，直到所有的文档的得分都计算完毕为止。

步骤

找到和查询相关的所有文档；
按照文档顺序，计算每个文档和用户查询的相似性得分
- 对每个查询单词，若文档包含单词，计算文档和单词的相似性得分
- 将查询出现的单词对应的得分，累加得到最终相似性得分；
根据文档得分进行大小排序，输出得分Top K作为搜索结果输出，即可完成一次用户查询的响应。

一次一单词(Term at a Time)

将某个单词对应的倒排列表中的每个文档ID，都计算一个部分相似性得分，在计算完毕某个单词倒排列表中包含的所有文档之后，接着计算下一个单词的倒排列表中包含的文档。若发现某个文档ID已经有了得分，则在原先得分上进行累加。

步骤

找到和查询相关的所有文档；
按照查询单词顺序，计算每个文档和用户查询的相似性得分
- 对每个文档，若文档包含单词，计算文档和单词的相似性得分
- 将文档的所有部分得分累加得到最终相似性得分；
根据文档得分进行大小排序，输出得分Top K作为搜索结果输出，即可完成一次用户查询的响应。

跳跃指针(Skip Pointer)

对于某些搜索引擎，认为文档必须包含所有的查询词，才认为文档是相关的；

文档ID是以文档编号差值（D-Gap）形式存储，且这个差值是以压缩后的方式编码的；

note: 若倒排列表直接包含文档ID，而不是差分，只需要通过归并排序能获得倒排列表集合的交集；

跳跃指针基本思想：将一个倒排列表数据化整为零，切分为若干个固定大小的数据块，一个数据块为一组，对于每个数据块，增加元信息来记录关于这个块的一些信息。

设置数据块大小，将一个倒排列表分成若干块
每个块前加入管理信息<idx, Pos j>表示第j个块的首个文档ID为idx

在一个具有跳跃指针的倒排列表中查找某个文档(已知文档ID)：

先根据跳跃指针，确定文档在哪一个块中；
连续顺序解压，恢复该块中所有的文档ID，进行比较；

数据块的大小一般设置为,其中倒排列表长度为,效果比较好

数据块越小，则使用跳跃指针向后进行跳跃的可能性越大，其缺点是增加了比较操作的次数；
数据块越大，则可以有效减少指针比较次数，其缺点是使用跳跃指针向后跳跃的可能性越小。

获得查询词的对应的倒排列表交集：反复在两个倒排列表中查找某个文档是否存在，将同时存在两个倒排列表中的文档ID作为计算结果。

跳跃指针的优点

相对不包含跳跃指针的索引来说，只需对其中一个数据块进行解压缩和文档编号查找即可获得结果，不用将所有索引数据都进行解压缩和比较操作。这明显加快了查找速度，并节省内存空间。

索引压缩

索引压缩则可以利用数据压缩算法，有效减少数据量，并且可以减少磁盘读/写数据量，加快用户查询的响应速度。

倒排索引包含两个部分：单词词典、单词对应的倒排列表。

词典压缩

词典组织方式，一般存储单词+DF+指向倒排列表的指针

哈希加链表
B树形词典结构

结构优化

将单词连续存储在某个内存区域，原来存储单词内容的部分由指向这个存储区对应单词起始位置的指针代替；
单词结尾可以采用下一个单词的指针所指向位置判断。

进一步的优化技术：

将连续词典分块，动态调整分块大小，以获取最优压缩效果；
原来每个词典项需保留一个指向连续词典区的指针，分块之后，每个块中的词典项共享同一个指针。
每个分块内包含多个单词，则为每个单词增加单词长度信息，以在提取单词时对块内不同单词予以区分。

倒排列表压缩

采用二进制编码：由二进制数字0和1表示实际数据，不同的比特宽度代表了不同的数字表示范围。

倒排列表压缩算法举例：

Elias Gamma算法:利用分解函数将待压缩的数字分解为两个因子，然后分别用一元编码和二进制编码来表达这两个因子。

将分解数字表示为,因子用一元编码表示，因子采用长度为的二进制编码表示
Elias Delta算法：利用了两次Elias Gamma算法，将待压缩的数字分解为3个因子，之后利用一元编码和二进制编码来进行数值压缩。

将分解数字表示为,因子用Elias Gamma算法继续分解为个因子，因子采用长度为的二进制编码表示
PForDelta算法：PForDelta算法是目前解压速度最快的一种倒排文件压缩算法，其主要思想是尽可能一次性压缩和解压多个数值。设定连续压缩个数值，取一定比例作为异常大数；

压缩的数据分为3部分：异常数据存储区、常规数据存储区、异常链表头。

压缩过程
1. 确定小数的最大者，进而确定比例宽度；
2. 对原始数据循环遍历，处理异常大数。遇到大数则逆序放置到静态数据尾端，并将异常大数转换为链表结构。
3. 将小数一次性快速压缩，存入常规数据存储区，压缩按照先前得到的比例宽度
解压过程

一次性将常规存储区的数据进行解压，根据异常链表头、依次顺序读出异常大数的位置，结合尾部存储的异常大数恢复原始数值序列。

文本处理

一般来说，名词是最能表达文档内容的。因此，对文档进行预处理是必要的。

文本处理过程：

文本的词法分析：主要是对文本中的数字、连接符、标点符号和字符的大小写进行处理；
无用词汇的删除：主要是过滤掉那些对于信息获取过程来说区分能力低的词汇；
词干提取：主要是去除词缀（前缀和后缀），这样可以允许所获取的文档包含一些查询词条的变换形式；
索引词条/词干的选择：在选择时，通常按照单词的习惯用法，实际上名词往往要比形容词、副词和动词包含更多的语义；
构造词条的分类结构：例如词典或者结构抽取，利用它可以进行查询的扩展。

词法分析

将字符串（文档中的文本）转换成词条的过程，这些词条可能被用来作为索引词条。因此词法分析的主要目的是识别文本中的词条。

英文：在对英文进行分词的过程中，除了空格分隔符，还需要处理：数字、连字符、标点符号和字母的大小写。
数字：数字一般不适合用作索引词条，因为对于数字来说，如果不参考上下文，它就没有明确的含义。
连字符：对于连字符的处理，目前常用的是方法是，首先采用一定的规则选出那些对词义有影响的连字符号，然后将其他的连字符都过滤掉。
标点符号：在词法分析过程中，标点符号将被全部去除。但是，对于那些成为单词中一部分的标点符号来说，一般不可以去除。字母的大小写：可以将文本中的所有词条都转换成大写或者小写。但是在某些特殊情况下，也需要对大小写进行区分。

中文分词技术

对于中文来说，词与词之间没有分隔符，且存在许多歧义现象；

单字切分：是指按照中文一个字、一个字地进行分词。按此方式切分出来的词进入索引，称为字索引。
二分法：是指每两个字进行一次切分。
词库分词：是指用一个已经建立好的词的集合去匹配目标，当遇上集合中已经存在的词时，就将之切分出来。

系统评价：

用户相应度：主要指用户对这项技术的满意度。
兼容性：要求能在不同的系统中都可以毫无障碍地使用，而且能给各行各业都带来方便。
准确率：是分词系统性能的核心指标，系统的准确率越高越好，应尽可能接近100%。
运行效率：在分词系统中分词的工作消耗的时间应尽量少，使用户没有等待的感觉。
适用性：好的分词系统具有良好的适用性，可以方便地集成在各种各样的汉语信息处理系统中。
通用性：中文分词系统必须具有很好的通用性。应能适应不同地区的不同用字、用词，不同的语言风格，不同的专用名构成方式等；支持不同的应用目标，包括语音合成、校对、翻译等；支持不同领域的应用，包括社会科学、新闻、办公等。

中文分词算法：基于字符串匹配的分词方法、基于理解的分词方法、基于统计的分词方法。

中文分词难题：

歧义识别：歧义是指同样的一句话，可能有两种或者更多的切分方法。
新词识别：在字典中都没有收录过，但又确实能称为词的那些词。

基于字符串匹配的分词

机械分词方法，它是按照一定的策略将待分析的汉字串与一个“充分大的”机器词典中的词条进行配，若在词典中找到某个字符串，则匹配成功（识别出一个词）。

最大匹配法（Forward Maximum Matching method, FMM）:FMM算法是正向最大匹配算法，它是基于字符串匹配的一种分词方法。

算法思想：选取包含6~8个汉字的符号串作为最大符号串，把最大符号串与词典中的单词条目相匹配，如果不能匹配，就削掉一个汉字继续匹配，直到在词典中找到相应的单词为止。匹配的方向是从左向右。

**逆向最大匹配法（Backward Maximum Matching method，BMM）：基于字符串匹配的一种分词方法，基本算法和正向最大匹配法相似，只是匹配的方向是从右到左，该算法比FMM的精确度高一些。

双向匹配法（Bi-direction Matching method，BM）：将FMM法和BMM法结合起来的算法称为双向匹配法，这种算法通过比较两者的切分结果，来决定正确的切分，而且可以识别出分词中的交叉歧义。

最少匹配算法（Fewest Words Matching，FWM）：FWM实现的分词结果中含词数最少，它和在有向图中搜索最短路径很相似。控制首先要对所选的语料进行分段，然后逐段计算最短路径，得到若干个分词结果，最后进行统计排歧，确定最理想的分词结果。

网格分词算法：基于统计性的一种分词算法，它的算法思想是：首先构造候选词网格，利用词典匹配，列举输入句子所有可能的切分词语，并且以词网格形式保存；然后计算词网格中的每一条路径的权值，权值通过计算图中每一结点得一元统计概率和结点之间的二元统计概率的相关信息；最后根据搜索算法在图中找到一条权值最大的路径，作为最后的分词结果。

基于理解的分词方法

基于理解的分词方法是通过让计算机模拟人对句子的理解，达到识别词的效果。基本思想：在分词的同时进行句法、语义分析，利用句法信息和语义信息来处理歧义现象。通常包括三个部分：分词子系统、句法语义子系统、总控部分。在总控部分的协调下，分词子系统可以获得有关词、句子等的句法和语义信息来对分词歧义进行判断，即它模拟了人对句子的理解过程。

基于统计的分词技术

从形式上看，词是稳定的字的组合，因此在上下文中，相邻的字同时出现的次数越多，就越有可能构成一个词。因此字与字相邻共现的频率或概率能够较好的反映成词的可信度。可以对语料中相邻共现的各个字的组合的频度进行统计，计算它们的互现信息。基本思想：定义两个字的互现信息，计算两个汉字X、Y的相邻共现概率。互现信息体现了汉字之间结合关系的紧密程度。当紧密程度高于某一个阈值时，便可认为此字组可能构成了一个词。这种方法只需对语料中的字组频度进行统计，不需要切分词典。

无用词汇删除

在信息库的文档中太频繁出现的单词将不会成为具有良好区分能力的词汇。实际上，如果一个单词出现在信息库中80％的文档中，该单词对于信息获取过程来说没用，这些词统称为无用词汇。在选择索引词条的时候，这些词条常常被过滤掉。一般来说，冠词、介词、连词都可以算作无用词汇。删除无用词汇对于信息获取来说具有重要意义，它可以大大缩小索引空间的大小，而且空间的缩小一般可以在40％左右。

信息获取系统通常会设置一个无用词汇列表。删除无用词汇将影响系统的查全率，因此，一些搜索引擎采用了全文索引，对无用词汇也会建立索引。

英文词干提取

用户输入词汇是信息库中某个相关文档中词汇的一种变形，词汇的变形可以是该词的复数、动名词或过去分词形式等。在这种情况下，则可以将文档中的词汇用它们的词干来代替。词干：是单词的一部分，是去除词的前缀和后缀后剩下的部分。

波特算法基本思想：对文本中单词的后缀应用一系列的规则，是目前公认最好的算法。该算法使用了560个后缀，上千条规则。

索引词选择

一些名词常常是两个或者三个同时出现，可以将这些词汇作为一个整体建立索引。在实际操作中，可以先设置一个阈值，计算文本中词汇之间的距离，如果该距离小于阈值，则将这些词汇放在一起构成名词词组。

搜索排序

搜索结果排序是搜索引擎最核心的构成部分，很大程度上决定了搜索引擎的质量好坏与用户接受与否。

机器学习排序

利用机器学习技术对搜索结果进行排序，是非常热门的一个研究领域。基本思路：提供训练数据，机器自动学习获得排序公式（传统检索模型由人工拟合排序公式）。

人工标注训练数据：对于某个查询Q，人工标出哪些文档是和这个查询相关的，并标出相关程度，或者利用用户点击记录来模拟这种人工打分机制。
文档特征抽取：每个文档是由若干特征构成的，通过特征抽取算法抽取文档特征，常用特征有文档长度、网页PageRank值、网页入链数量等。
学习分类函数：通过多个训练实例，采用机器学习技术对系统进行训练，生成分类函数。
在实际搜索系统中采用机器学习模型：利用生成的分类函数对与查询相关的网页进行排序。

机器学习排序可分为三类方法：单文档方法（Pointwise Approach）、文档对方法（Pairwise Approach）、文档列表方法（Listwise Approach）。

检索质量评价

混淆矩阵如下：

	相关文献	不相关文献	总计
被检出文献	A	C	A+C
未检出文献	B	D	B+D
总计	A+B	C+D	A+B+C+D

查全率：衡量系统在实施某一作业时检出相关文献能力的一种测度指标，是对检索遗漏程度的度量。

查准率：衡量系统在实施某一检索作业时检索精度的一个测度指标，是对检索噪音程度的度量。

链接分析

搜索引擎在查找能够满足用户请求的网页时，主要考虑两方面的因素：一方面是用户发出的查询与网页内容的内容相似性得分，即网页和查询的相关性，另一方面是通过链接分析方法计算获得的得分，即网页的重要性。

PageRank算法

取万维网链接结构图，的规模为;

对于中的每一个节点，设是其PageRank值，而向量为G对应的PageRank结果向量,分量和为1,预先设定参数;

Simplified Version

初始化向量;

每一步迭代，向量获得更新如下：

算法充分迭代，直到向量收敛；

Standard Version

初始化向量;

遍历每一个结点:

若,则遍历的出度顶点,更新
若,则对所有顶点更新：

遍历完成后，更新向量;算法充分迭代，直到向量收敛；

HITS算法

HITS是Hyperlink-Induced Topic Search（基于超链接推演的主题搜索算法）的简称，其核心思想是对网页两个方面的权威程度进行评价，一个是内容权威度（Authority Value），即网页本身内容的受欢迎程度，另一个是链接权威度（Hub Value），即网页链接到其他受欢迎资源的程度。

对用户输入的查询的主题而言，首先是通过文本搜索过程与此查询主题内容相关的网页集合，并适当扩展该网页集合，以包括尽可能多的结果候选网页，同时使结果集合网页间的链接结构关系更加完整；

随后则是通过一个“迭代-收敛”的过程计算网页集合中每个页面对应的链接权威度与内容权威度数值，算法最后输出的是分别按照链接权威度与内容权威度排序的结果列表，用户可以根据需求的不同，选择其中的结果页面进行浏览。

记为网络信息检索结果集合，找到和有关链接的网页形成结构图

对于图中每一个结点，维护为其链接权威度和内容权威度；

初始化;

每一步迭代，进行I操作和O操作，对每一个结点

I操作：
O操作：
规范化处理：每个分量除以某数，使得

算法充分迭代直到收敛，或者到达迭代次数上限；

P的内容权威度与链向P网页的链接权威度相关（O操作）。链向P的网页的链接权威度越高，说明P的内容权威度越高。链接权威度与内容权威度之间具有相互增强的关系。

缺点：

计算效率较低：HITS是与查询相关的算法，所以必须在接收到用户查询后实时进行计算，而其本身需要进行很多轮迭代计算才能获得最终结果，导致计算效率变低。
主题漂移问题：如果在扩展网页集合里包含部分与查询主题无关的页面，而且这些页面之间有较多的相互链接指向，那么使用HITS算法很可能会给予这些无关网页很高的排名，导致搜索结果发生主题漂移，这种现象称为紧密链接社区现象。
易被作弊者操纵结果：HITS算法从机制上很容易被作弊者操纵，比如作弊者可以建立一个网页，页面内容增加很多指向高质量网页或者著名网站的网址，这就是一个很好地Hub页面，之后再将这个网页链接指向作弊网页，于是可以提升作弊网页的内容权威度。
结构不稳定：如果在原有的扩展网页集合内，添加删除个别网页或者改变少数链接关系，则HITS算法的排名结果会有非常大的改变。

比较

HITS	PageRank
与用户输入的查询请求密切相关	与查询请求无关
必须在接收到用户查询后进行实时计算，计算效率较低	在爬虫抓取完成后离线计算，在线直接使用计算结果，计算效率高
计算对象数量较少，只需计算扩展集合内网页之间的链接关系	全局性算法，需要对所有页面节点进行处理
适合部署在客户端	适合部署在服务器端
更易受到链接作弊的影响	从链接反作弊的角度来说机制更优
结构不稳定	后者计算时的远程跳转，表现更稳定

网页去重

搜索引擎是在网络爬虫阶段进行近似重复检测（网页去重）的。

框架

特征提取：对于给定文档，首先需要进行特征抽取，从文档中抽取出一系列能够表征文档主体内容的特征集合。
文档指纹生成：在将文档转换为特征集合后，对信息进一步压缩，采用信息指纹相关算法，将特征集合压缩为新的数据集合。
相似性计算：通过相似性计算来判断哪些网页是近似重复页面。

Shingling算法

Shingling算法以Shingles作为文档的特征。

Shingles，即将文档中出现的连续单词作为一个整体，对这个单词片段进行哈希计算，形成一个数值，每个单词片段对应的哈希值称为一个Shingle。文档的特征集是由多个Shingle构成的。

以一个固定大小的移动窗口从文档第一个单词（单字）开始依次移动，每次向后移动一个单词（单字），直到文本末尾。

步骤：

从文档中抽取出能代表文档内容的特征
根据两个文档对应的特征集合的重叠程度来判断是否近似重复；

用Jaccard相似性计算文档特征集的重合程度：

对于特征集合,Jaccard相似性计算为

Shingling算法在运用过程中，计算效率不高，如果网页数量大，运行时间会过长。

原因在于把一个文档转换为以Shingles表示的特征集合形式后，这个文档对应的特征集合很大。

SuperShingle Trick

对于不同的网页，将其转换为固定大小的特征集合，这个特征集合的大小远小于原始Shingling算法转换后特征集合的大小，以此方法来提高运算效率。

一个改进的Shingleing算法步骤如下：

将文档转换为由shingles构成的特征集合；
通过引入m个不同的哈希函数，将文档映射为固定大小，形成哈希函数簇；
对于某个特定的哈希函数F，对每个shingle都计算出一个对应的哈希数值，取最小的那个哈希值作为代表；
m个哈希函数便获得了m个哈希值，如此便将文档的特征集合转换为了固定大小m。

在SuperShingle Trick中，取,对84个数值进一步压缩，以14个连续数值作为一块，即分为6块，在采用另一个哈希函数对每一块的14个数值进行哈希计算，进一步将文档转换为6个哈希值；若任意两个文档有两个以上的哈希值是相同的，即可认为是近似重复文档；

SimHash算法

实践表明，SimHash是目前最优秀的去重算法之一,属于局部敏感哈希算法(Locality-Sensitive Hashing)的一种；

文档指纹计算：将一篇文本文档转换为固定大小的二进制数值，以此作为文档的信息指纹；
文档指纹计算：将一篇文本文档转换为固定大小的二进制数值，以此作为文档的信息指纹；

文档指纹计算是指：通过适当的抽取方法，从文档中抽取一批能表征文档的特征，获得文档的特征及其权值w，利用一个哈希函数将每个特征映射成固定长度的二进制表示，利用权值改写特征的二进制向量，将权重融入向量中，形成一个实数向量。对每个特征向量完成改写之后，累加所有实数向量，获得一个文档整体的实数向量。累加规则，即将对应位置的数值相加即可，最后将得到的实数向量重新妆化成二进制向量。

这里二进制向量和实数向量转换规则是

若二进制的某个比特位是数值1，则实数向量中对应位置改写为w；反之，若实数向量位对应大于0，则二进制向量的比特位为1；若二进制的某个比特位是数值0，则实数向量中对应位置改写为-w，即权值的负数；反之，若实数向量位对应小于等于0，则二进制向量的比特位为0；

在实践中一般文档转换为64比特的二进制数值，内容相似性通过海明距离的大小衡量；

对于64位二进制数来说，判断两个文档是否近似重复的标准是：海明距离是否小于等于3，若两个文档的二进制数值小于等于3位不同，则判定为近似重复文档。

对于动态出现新网页，找出其近似重复的内容，可采用以下分组算法，将索引网页根据文档指纹进行分组，新网页只在部分分组内进行匹配，以减少新文档和索引网页的比较次数。

对64位长度的二进制数值进行分块，没16位为一块，则每个二进制数值被划分为4块，分别以A、B、C、D命名。
对于海量的索引网页，依据分块进行聚类：对于A块来说，根据该块内16位二进制聚类，若16位二进制都相同，则将这些网页看作一个聚类，依据此规则，可将索引网页分为若干组数据。对B、C、D按照相同方法聚类。
对于新抓取的网页，同样将64比特二进制数据分为4块：Q1、Q2、Q3、Q4。
在索引网页的分组中，找到对应A块16位和Q1完全相同的分组，然后与分组内的网页一一匹配，查找哪些网页是近似重复的。对Q2、Q3、Q4作同样处理。

将新网页与分组内的索引网页一一匹配：若两者二进制数值的海明距离小于等于3，则判定为近似重复文档。

网页反作弊

作弊方法

内容作弊

内容作弊是指通过精心更改或者调控网页内容，使得网页在搜索引擎中获得与其网页不相称的高排名。

搜索引擎排名包含了内容相似性和链接重要性计算，内容作弊针对的是内容相似性计算部分。

内容作弊方式：关键词重复、无关查询词作弊、图片alt标签文本作弊、网页标题作弊、网页重要标签作弊、网页元信息作弊。

链接作弊

链接作弊是指网站拥有者通过操纵页面之间的链接关系，或者操纵页面之间的链接锚文字，以此来增加链接排序因子的得分，影响结果排名。

链接作弊方式：链接农场、Google轰炸、交换友情链接、购买链接、购买过期域名、“门页”作弊

页面隐藏作弊

页面隐藏作弊是指通过一些手段欺骗搜索引擎爬虫，使得搜索引擎抓取的页面内容和用户点击查看到的页面内容不同，从而影响搜索引擎的搜索结果。

页面隐藏作弊方式：IP地址隐形作弊、HTTP请求隐形作弊、网页重定向、页面内容隐藏。

Web2.0作弊

Web2.0作弊是指通过以用户为中心的一些应用产品来作弊。 Web2.0作弊方式：博客作弊、点评作弊、标签作弊、SNS作弊、微博作弊。

反作弊技术

信任传播模型

在海量的网页数据中，通过一定的技术手段或者人工半人工手段，从中筛选出部分完全值得信任的页面，也就是一定不会作弊的页面（可理解为白名单）；

算法以这些白名单内的页面作为出发点，赋予白名单内的页面节点较高的信任度分值，其他页面是否作弊，根据其和白名单内节点的链接关系来确定。

白名单内节点通过链接关系将信任度分值向外扩散传播，如果某个节点最后得到的信任度分值高于一定阈值，则认为没有问题，而低于这一阈值的网页则被认为是作弊网页。

不信任传播模型

从技术框架上来讲，不信任传播模型和信任传播模型是相似的，两者区别在于：初始的页面子集不是值得信任的页面节点，而是确认存在作弊行为的页面集合，即不值得信任的页面集合（可理解为黑名单）。

赋予黑名单内节点不信任分值，通过链接关系将这种不信任关系传播出去，如果最后页面节点的不信任分值大于设定的阈值，则会被认为是作弊网页。

异常发现模型

异常发现模型基本假设：作弊网页必然存在有异于正常网页的特征，这种特征有可能是内容方面的，也有可能是链接关系方面的。

该模型具有两种子模型：一种是直接从作弊网页包含的独特特征来构建算法；另一种是将不正常的网页视为作弊网页。

反内容作弊

针对内容作弊，通常采用一些启发规则或者内容统计分析地方式进行识别。对于重复出现关键词这种作弊方式，可以判断文本内一定大小的窗口中是否连续出现同一关键词，如果是，则消除重复出现的内容。

对于标题关键词作弊，可以判断标题词在文本正文出现的比例和权重，如果达到一定条件，则判断为标题关键词作弊。

反链接作弊

通用链接反作弊方法，是指这种反作弊方法不需要针对某种具体的作弊方式来做特征分析，并根据分析结果构建有针对性的算法。

例如TrustRank算法属于信任传播模型中的反链接作弊技术：采取信任分值均分策略：即将网页获得的信任分值按照出链个数平均分配，如果一个网页有K个出链，则每个出链分配得到1/K的信任分值，并将这个分值传递给出链指向的页面。

BadRank属于不信任传播模型的反链接作弊技术：首先构建作弊网页集合，之后利用链接关系来将不信任分值传递到其他网页，和TrustRank计算类似；

SpamRank算法是一种符合异常发现模型的反作弊方法。计算思路：

计算网页的PageRank值；
计算出网页的支持页面；
判断支持页面的PageRank分布是否违反Power-Law统计分布，若违反则作为作弊页面处理。

反隐藏作弊

常见的隐藏作弊方式有页面隐藏、网页重定向。

识别页面隐藏：对网页进行两次抓取，第一次是正常的搜索引擎爬虫抓取，第二次以模拟人工访问页面的方式抓取，如果两次抓取到的内容差异较大，则认为是作弊页面。

识别网页重定向：收集一批作弊页面，据其进行扩展，检测到经常与这些作弊页面链接一起出现的链接，则扩充进可疑页面集合。依次访问这些页面，若某个页面被诸多可疑链接重定向指向，或者重定向到作弊网页的可疑链接，均被认为作弊网页。