网络信息检索（七）搜素引擎体系结构与排序算法

• 密集并行（Embarrassingly parallel）
  无状态（Stateless） -查询只是一次性的
  大量的只读（Read-only）操作

• 需要很大的存储-索引库的数据甚至比网页的数据还多

• 需要很多的计算-即使我们可以将很多东西预处理，对大量的查询操作而言，我们的任务量仍然很重。

• 需要极短的响应时间-考虑一下打开个百度用一天？

---

• 系统的设计目标：能耗小、性能比高 （尽可能用便宜，普通的设备）
  便宜的 PC集群

• 软件的可靠性–追求便宜就不一定可靠了，但是可靠性又必须得到保证，某个设备宕机系统仍然可以运行。
  容错（Fault tolerance）

• 解决方案：高度的（High degree of replication）–数据冗余，放在不同的地方。

Google：英文含义，“体现了整合网上海量信息的远大目标”。

Google将数以千计的低成本计算机联网到一起，制造出了一部超高速搜索引擎。超过80亿索引页面、超过10亿索引图像、超过80种语言、112 个国际域名 (2008年的统计数据）下面红线是Google的市场占有量。

Implemented in C and C++ on Solaris and Linux

（1）采集数据

（2）建立索引

命中表是前向索引和倒排索引的核心部分。

• 前向索引：每篇文档都有一个对于它的所有词的前向索引。
• 每个文档包含很多词，每个词都有其对应的wordID，按照wordID分到桶里，也就是说桶将词表分成好多份，保存在他范围内的所有词信息。
• 前向索引是以文档为主的索引，我们使用sorter建立倒排索引，利用桶里放置的词直接对每个word ID的词进行排序，就能生成倒排索引。

（3）提供检索服务

• 网页分成几个域比较重要，包括title，anchor等。因此barrels分为两类，短桶存放比较重要的域的词，长桶存放所有的词。

（4）数据结构

优化的数据结构，使得海量文档可以较低的开销被抓取、索引和检索

• 文件系统BigFiles
• 网页库（Repository）
• 文档索引（Document index）
• 词典（Lexicon）
• 命中表（Hit lists）
• 前向索引（Forward index）
• 倒排索引（Inverted index）

---

操作系统提供的文件系统通常不能满足搜索引擎的要求，Google用了很多时间来开发自己的BigFiles文件系统

• 在建在多个文件系统之上，以64位整数进行寻址的虚拟文件系统
• 文件系统之间的分配由系统自动完成
• 一般操作系统不提供足够的描述符号，所以BigFiles文件系统要自己处理文件描述符的分配与回收
• BigFiles文件系统还直接支持文件的压缩功能

---

网页库（Repository）包含了每个网页的完整HTML文档，每个网页都是用zlib进行压缩的（压缩要综合考虑存储和速度）

---

文档索引按照一定的次序来保存关于每个文档的信息，它是按docID组织的，每个条目包含

• 指向repository中文档的指针
• 文档校验和（checksum）
• 统计信息
• 当前文档统计信息
• URL指针
  • 如果该网页已经被抓取下来了，则它还包含一个指针，指向一个可变宽度、被称为docinfo的文件，该文件中包含文档的URL及标题
  • 如果该网页未被抓取，指针只是指向一个仅仅包含URL的URLlist

在设计时，要考虑压缩数据结果以减少存储

---

• 不同搜索引擎采用的词典不一样，在Google中，词典可以驻留在内存中，占大约256M内存，包含14,000,000个单词（一些稀有的单词没有加入到词典中）
• 由两部分组成
   其一是通过空格分隔的单词表（a list of the words, concatenated together but separated by nulls）
   其二是由指针组成的散列表（ a hash table of pointers ）–每个单词映射到一个wordID。
• 为了提高性能，除了基本词典，每个索引器（indexer）还维护一个额外的文件，因为我们有多个机器，每个机器都要独立维护一个词典。

---

命中表的每一项包含某词在某文档中的出现信息：
 位置
 字体大小
 大小写信息等
 描述子类型（ descriptor type ），如title、anchor等

anchor的表示最特殊，用4bit表示值，这个值其实是document ID的hash值，因为anchor是自己外链包含的文本，这个文本不是对当前网页重要，而是对指向网页比较重要，因此这个docid是链接链向网页的docID，此时的位置也不是词的位置，而是表示这是第几个链接（超出16个链接就不计了）

---

前向索引是文档到词的索引，每个桶容纳一定范围内的wordID，如果一个文档包含的单词（用wordID表示）属于某个桶的话，那么该桶首先记录该文档的docID，紧接其后的是文档中的一串单词、对应于这些单词的命中列表。

---

提高文档检索的速度，要建立词到文档的索引，即倒排索引。倒排索引也包含与前向索引一样的存储桶（无论是前向还是倒排，命中表都在桶里，命中表都是核心）

---

（5）Google检索算法

（1）单个检索词的查询排序

• 对每个词提取命中列表（Hitlist）
• 每个命中可以是以下几种类型之一：题目，锚文本， URL，大字体，小字体等
• 每个命中类型赋予一定的权重，类型－权重构成一个权重的矢量（weight vector）
• 每个类型命中个数被计算，并构成频率矢量（count vector）
• 两个矢量的点积（dot product）用来计算IR（Information Retrieval）的得分（内容相关度）
• IR分数与PageRank（网页重要性）结合起来计算最后的得分

（2）多个检索词的查询排序

• 与单个检索词的排序类似，只是必须分析相近性（proximity）  匹配词越接近，权重越高
• 每个邻近关系被赋予1到10的权重，从“词组关系”到“毫无关系”
• 对每个类型的命中和相近度计算出现的次数

（3）扩展性与关键的优化技术

采用高可扩展的集群架构，当时（1998年）：
大约2400万文档，在一个星期内索引完成
索引了大约5亿多个超链
4个crawlers每秒抓取100个文档

---

• 每个crawler维护一个自己的 DNS查找缓存
• 用flex来产生 词法分析器（lexical yzer）以解析文档
• 并行化索引
• 词典的内存管理（In-memory lexicon）
• 网页库的压缩（Compression of repository）
• 对命中表（hitlists）的编码压缩可节省很大的存储空间
• 索引器优化的很好，比crawler略快，因此crawler是瓶颈
• 文档索引批量更新（updated in bulk）
• 关键的数据结果放在本地硬盘
• 全局化的架构设计，尽可能避免磁盘扫描

---

• 系统设计
  存储和计算的配置
  分布式系统的挑战：可扩展性（Scalability）、可靠性（Reliability）、安全（Security）、协商（Consensus）

• 编程模型：关于管理的资源的简单的、全局视图

---

---

• 文件系统是建立在廉价通用主机平台上的，文件系统必须能够一直监视自己的状态并从灾难中恢复过来
• 文件系统存储着许多大文件。数目大概是几百万个，大小为100M或者更大，几G
• 需要支持两种类型的读取方式：大规模流读取方式和小规模随机读取方式。在大规模流读取中，一个操作通常会从一个连续的文件区域中读取几百K或者更多的数据。随机读取则可能在任意位置读取几K的数据
• 写的方式和读的方式也类似。大量的数据通常以追加的方式添加到文件最后，因为这些数据一次写入后通常就不再更改了（改一般也是批量更改）
• 系统必须能够保证多个客户端能并发地对同一个文件进行追加记录
• 稳定的高带宽比低延时更重要。大多数应用程序，需要在高传输速率下，大块地操作数据。

（1）简介与典型应用

 一个成熟的Apache开源项目；
 提供文本索引和搜索的Java 类库/包；
 也有C/Python语言接口；
 http://lucene.apache.org

---

（2）得分算法-类向量空间模型

不同之处在于

• 对于查询的向量构造，权重种使用了权重，而不是tf因子。
• idf的计算公式也有点不太一样，首先用的是，并且给分母+1。tf因子开根号。

---

• 表示查询所在的域的长度，或者简单理解为某篇文档中查询范围内词汇的数量
• 和值与文档无关，不影响排名
• 是人为赋予的经验值，缺省为1.0
• 因此排名因子：
  单位长度的文档包含的关键词个数的平方根

（3）BooleanQuery的得分公式:多个词

BooleanQuery是一种复合式查询，支持多种不同查询词的逻辑组合，

 BooleanQuery例子
＋俄罗斯 恐怖 事件 －美国
＋（俄罗斯 美国) 恐怖 事件

可以对不同的查询词赋予不同的boost值表示该查询词在整个BooleanQuery中的重要程度
例如: 俄罗斯3.0 恐怖2.0 事件1.0

---

• Nutch的创始人Doug Cutting，也是Lucene和Hadoop的创始者
• Nutch 1.2是基于Lucene的开源搜索引擎，增加了面向web的处理模块
  crawler
  链接图（link graph） • 链接分析 • 锚文本
  HTML和其他文档格式的识别和解析
  语言、字符集的识别和处理
  扩展的索引和检索功能
• Nutch 1.2版本之后，从搜索引擎演化为网络爬虫，进行分布式多任务抓取和分析存储。
• Solr是基于Lucene的搜索系统，提供索引和搜索服务

---

---

---

他对停止词的处理别具一格，不会直接把所有的停止词去掉，比如都是停止词，但是连起来还是蛮有用的，所以Nutch选择将停止词和附近的词连起来组成新的词，以防漏掉重要信息。

• 页面包含的匹配的检索词的个数
• 匹配词的邻近程度
• 词在页面的位置
• 词在某些tag的位置，如
• 指向该页面的锚文本
• 在页面中出现的检索词的频率，以及检索词在整个中出现的频率（TF*IDF）
• 链接分析：哪些页面指向该页面
• 点击分析：该页面被访问的频率
• 网页的“崭新”程度

设计复杂的公式将以上各因素综合起来