搜索引擎应用技术(中級篇)

3 理解检索需求

如今，搜索引擎远远不是仅仅指类似于百度（和google）这类web 搜索引擎，它涵盖了大量行业，满足各种各样的需求。

笔者从小就坚信分析一个问题应该从来源开始，所以，分析搜索引擎，我们应该从现在人们对搜索引擎的需求开始。下图是信息检索的基本过程：

用户发出查询请求，然后搜索引擎从信息集合里面找出相关的信息集合返回给用户。
注意，这里所谓的相关有2 种含义：1）用户想看到的；2）系统想让用户看到的。


无论是信息还是查询，都不是一个绝对的结构。我们常见的信息检索中，信息一般是一个对象（文档），它由一组<属性，值>对表示。这点和数据库表示一条记录是一样的。而查询一般也是一个字符串。
下面看看常见的查询是什么样子的：
1）常规网页搜索引擎。查询可以是：“计算机”、“计算机OR 图片”、“计算机site:www.sina.com”；
2）常规数据库。查询可以是：“title= ’计算机’”、“title like ‘%计算机’”、“title=’计算机’ and content=’美女’”、“order by title ”、“group by 1”；搜索引擎的查询一般都属于数据库查询的一种。

注意到搜索引擎和数据库查询有几点不同：
1）速度很重要。搜索引擎一般通过网络服务于大众，用户众多，速度是十分重要的。大部分用户可以接受的时间在1s 左右；
2）最相关文档排前。和查询最接近的文档应该首先被返回。
3）文档类型单一。搜索引擎一般每次只能处理一种类型的文档。

考虑到这些不同，我们把常见的查询划分为以下几类：
1）元数据查询。文档的属性值必须满足某不等式，比如， (age-10)*(a ge-20)<=0；
2）全文检索。要求某个属性值（文本）包含的词语必须满足某个表达式，比如，“中国OR 美国”；

3）排序。首先，根据文档的各个属性值计算出权重来，其中，全文检索的权重与具体查询有关。然后根据选择的排序方式，计算文档的最终权重值，进行排序；
4）统计。统计文档在某个表达式上值的分布情况。比如，统计属性age 减10 之后，所有age 的平均值。

请注意，实际应用的需求可能涵盖了全文检索和数据库已有的所有功能。本处受到搜索引擎要求很高速度的约束，只能忽略常规的一些需求（比如，多表关联）。并不是说这些需求不能够快速实现，只是其实现技术暂时未被笔者了解到罢了。笔者也未曾见过或听说过这类实现。

多媒体需求：搜索引擎已经开始慢慢的支持对多媒体数据的处理。比如baidu图片搜索。
对于多媒体检索来说，常见的有2 种做法：1）基于文本检索；2）基于多媒体检索。
前者是通过给数据加上描述文本，然后基于描述文本检索。
后者是直接使用多媒体形式的查询进行检索，如给定一张图片，找和其相似的图片。本文暂时不涉及到后者。


3.1 实例介绍
简要的介绍几个实际网站搜索串的例子：
 Google：
Google 的语法基本上传统的搜索引擎一样，比如，要搜索“jerry 鼠”的
flash 文件的话，输入的串应为：jerry 鼠filetype:swf；
 Baid u：
百度的做法和Google 差不多，如果你要查询包含“tom 猫”的pdf 文件
的话，输入的串应该为：tom 猫filetype:pd f；
 淘宝：
电子商务底层搜索的功能比一般搜索引擎要强大很多。淘宝提供了根据
各种商品属性来搜索商品的功能，比如，价格范围。还有根据好几种方
式对结果进行排序；
 Ebay：
Ebay 除了提供比淘宝强大得多的那种近乎数据库式搜索外（比如，前缀
搜索），它还新推出了略微智能的搜索。比如，输入“Barbie red dress”，
会被解析为：搜索红色的Barbie dress。


4 开始分析

在需求明确之后，我们就可以开始分析如何实现这些需求了。

当然了，本文并不是简单的告诉你怎么完整一个项目。而是告诉你怎么分析实现搜索引擎。

5 预备知识
如果只是给一个普通项目提供搜索支持，你不需要多少预备知识，可以跳过本节。如果你想把搜索作好，建议你看本节。本节假定读者已经具备计算机专业本科水平。

本预备知识包含了搜索引擎一般需要使用的而普通课本上面又没有详细描述的数据结构和压缩算法。


5.1 数据结构

5.1.1 Hash函数
定义：Hash 函数把任意范围的key 映射到一个相对较小的整数范围内。比如，
md5 hash 算法就是把任意字节数组映射到128 位的整数上。
Hash 函数在很多领域都有应用，比如，模式匹配、密码学。它们都额外的定
义了Hash 函数的其他特点，如密码学要求Hash 函数接近于单向函数。我们这里
只讨论Hash 函数在Hash table 结构里面的应用。

5.1.1.1 常用Hash函数介绍
Hash 函数一般会分为2 种，即Hash table 用的hash 和密码学上面应用的Hash。
这里分开介绍。

5.1.1.1.1 Hash table的Hash函数
应用在Hash table 上的Hash 函数的一个主要特点是输出一般为32 或者64
位。常见的算法有很多种，有关这些Hash 算法的实现代码，可以参考笔者博客
上的文章：Hash 算法实现。

5.1.1.1.2 密码学上的Hash函数
密码学上的Hash 函数第一重要的是其伪单向性。故一般其计算都特别复杂，结果位数也很长。我们常见的Hash 函数有如下几个：

1. Adler-32：定义在rfc1950 里面，是一种乘法Hash 算法，结果是32 位整数；
2. CRC32：循环冗余码，结果是32 位整数；
3. MD 系列：md3, md4 等，结果都是128 位整数；考虑到md5 冲突的易构造性，建议不要用它做重要消息签名；
4. RipedMd 系列：有128/160/256/320 位4 种规范，但RipedMd-256/320 没有被认真设计，其安全度和128/160 这2 种规范一样；
5. SHA 系列：有160/256/384/512 位4 种规范；
6. Tiger：192 位，专门为64 位机器优化；
7. WhirlPool：512 位。

这里，需要注意的是，美国的国家标准推荐使用如下几个Hash 算法：Ripe dMd系列，SHA 系列，Tiger 和WhirlPool。具体的说明大家可以去看密码学相关书籍（推荐《密码学基础（英文版）》和《现代密码学理论与研究》）或者学习著名的开源库Crypto++或者参考笔者的博客：Hash 散列算法详细解析。


5.1.1.2 Hash table处理碰撞的技术

Open addressing（closed hashing）：探测方式。通过选择不同的位置来存放数据。
 线形探测：计算公式为next_pos = (cur_pos + m) mod N；其中m 为常数，N 为Hash table 数组长度；
 平方探测：常用计算公式为next_pos = (cur_pos + cur_pos^2) mod N；
 二次Hash：常用计算公式为next_pos = (cur_pos + Hash2(key)) mod N；Hash2 表示第二个Hash 函数。

Chaining：链表方式。即把冲突的key 串在一起。
以上两种碰撞处理技术很多数据结构书籍都详细描述过，本处不在赘述。下
面看看其他的方法：

Coalesced hashing：结合了Open addressing 和Chaining 方法，把Chaining的链表融合到Hash table 的数组里面，从而减少了空间使用。下面用一个例子说明这种方式。输入key 序列为{“qur”,“qrj”,“ofu”,“gcl”,“clq”,“ecd”,“aty”,“rhv”,“qus”}，左边图是基本Chaining 方式的结果，
右边图是本方式的结果：

Coalesced hashing 方式的处理方法为：利用线形探测找到一个空位，填入key，然后把这个空位链接到相同映射值组成的链表上面。需要注意的是，Coalesced hashing 对定长的key 才真正有用。


Cuckoo hashing：基本思想是使用2 个hash 函数来处理碰撞，从而每个key 都可以对应到2 个位置。
其具体的处理方式为：

• 如果key 对应的2 个位置中有一个为空，key 就可以插入到那个位置；
• 否则，任选一个位置，key 插入，把已经在那个位置的key 踢出来；
• 被踢出来的key 需要重新插入；
• 直到没有key 被踢出为止。

显然，这种方式是可能产生无限循环的，当出现无限循环的时候，就需
要重新选择hash 函数。

Cuckoo hashing 有2 个主要的变形：
1）增加hash 函数的个数；
2）每个位置可以放2 个key。
这2 个的目的都是为了增加Hash table 数组的利用率，因为基本的Cuckoo hashing 只有49%的利用率，而3 个Hash table可以利用91%的空间，每个位置保存2 个key 可以使利用率达到80%。有人分析Cuckoo hashing 比Chaining 的方式更好。基本Cuckoo Hashing的实现，参考笔者博客文章：Cuckoo Hash 介绍。







5.1.2 Trie树
也叫前缀数组，是一种key 为字符串的联合数组。下图是一个简单示例：

Trie 树的一个主要特点是查询字符串Key 很快。有关Trie 树的介绍可以参考一般的数据结构书籍。基本的Trie 树占用的内存很大，人们发明了基于数组的Trie 结构。双数组Trie 树其实是把Trie 树中的所有节点拼接在一起，减少占用的空间。以上图来说，这棵树可以用7 个（7 个节点，从上往下编号）数组表示：
 Node1[0:256]={null} ， Node1[‘t’]=Node2 ， Node1[‘i’]=Node3 ，isNodeHasData=false
 Node2[0:256]={null} ， Node2[‘o’]=Node4 ， Node2[‘e’]=Node5 ，isNodeHasData=false
 Node3[0:256]={null} ，isNodeHasData=true
 Node4[0:256]={null} ，isNodeHasData=true

 Node5[0:256]={null} ， Node5[‘a’]=Node6 ， Node5[‘n’]=Node7 ，isNodeHasData=true
 Node6[0:256]={null} ，isNodeHasData=true
 Node7[0:256]={null} ，isNodeHasData=true
注意到共有7 个256 个元素的数组，数组元素表示对应节点的孩子节点对应的数组，数组里面大部分都是Null 值，所以如果把它们组合在一起，可以大大减少空间占用。
在上面的这个例子中，可以简单的把所有数组混合起来，因为它们没有冲突；也可以把所有数组并排；前者组合后的数组大小为256，后者组合后的数组大小为256*7。实际中，直接混合数组会有很多冲突，而并排所有数组又十分浪费空间，故必须找一个好的办法来避免冲突同时减少空间浪费。文章“Fast and compact updating algorithms of a double-array structure”提出了一种基于空余空间链接的混合数组的算法，这是一种贪婪算法，能够较好地减少空间浪费。在实际应用中，我们发现这种算法的构建速度极慢，主要慢在贪婪算法上面。为了加快速度，我们在贪婪算法的基础上，跳过那些可能不匹配的位置，在多浪费一点空间的情况下，能够快速的构建双数组Trie 树。
下面是双数组Trie 树使用java 实现的一个版本：
Trie 结构支持下的Map sample code
 
其他例子：
http://blog.csdn.net/dingyaguang117/article/details/7608568
or
https://github.com/dingyaguang117/DoubleArrayTrie/tree/master/src


5.1.3　bit array(bitmap)
Bit 数组，里面的元素都是布尔值，而且，每个元素只占用1 位。Bit 数组一般基于普通的byte 或者word 数组。
Bit 数组在实现上面，有大量的小技巧。这些笔者相信大家在很多Bit 数组实现上都见过，此处不再赘述。
如果在这个方面有什么疑问，可以参考：
http://en.wikipedia.org/wiki/Bit_array。
Bit 数组也是一种重要的索引结构。它可以用来表示第n 个文本是否包含了某个词语（数据）。
有关它在索引上面的应用，在讲索引的章节会详细讨论。


5.1.4 Judy array
为什么要提及到Judy array 这个超过20000 行代码的咚咚？因为它在不降低速度的情况下，占用极小的额外空间！
Judy array 属于联合数组的范畴，看起来像一个Trie 结构（或者说256 叉树），即每个按照字节分层。它的主要目标是减少内存访问（官方说法是avoid cacheline fill）。
一般认为它有3 个有点：
1) 空间占用小。这点是因为它是一个Trie 结构，然后每层还利用了Bitmap；
2) 速度快。Judy array 的主要贡献也就在此了，它减少了内存访问，自然就加快了计算速度。实际测试的结果表明，它在add/update/delete 时的时间性能和hashtable 相当（略慢）；
3) 比较抗算法复杂性攻击（Algorithms complex attacks）。算法复杂性攻击的一个典型例子就是经典快速排序（ Intro QuickSort 的主要贡献就是解决了这个难题），如果你输入的是已经排序好了的数组，快排就变成噩梦了。同样，Hashtable 在输入的值的hash 结果都一样的时候，也变得一无是处。

有论文对比过Judy array 和Hashtable 的性能（<key,vale>=<int,int>），发现前者一般只需占用1.25 倍原始数据的空间，但Hashtable 经常占到3 倍-8 倍原始数据的空间。当然了，如果<key,value>对中的value 占用空间很大，那么Hashtable和Judy Array 占用的空间就差不多了。


5.1.5 Bloom filter
Bloom filter 是一个重要得没法说的结构。多年来，它都是大家研究的热点。Bloom filter 是一种高概率的Set 结构，其主要特点是空间占用小。对于搜索引擎来说，它在好几个地方都很有用处，比如URL 去重、单词拼写检查等等。Bloom Filter 是一个概率Set，只能以一定概率判断某个Key 是否在Set 里面出现。更准确的说，判断Key 不在Set 里面是精确的，判断Key 在Set 里面时不见得Key一定在Set 里面，即所谓的False Positive。
下图说明了它的基本结构：



Bloom Filter 由若干个Hash 函数和一个bitmap 数组组成。其操作过程如下：

• 加入Key：设置bitmap 的第Hashk(Key)位为1，这里i=1, 2,… k；
• 查询Key 是否存在：如果bitmap 的第Hashk(Key)位均为1，就认为Key在Set 中存在。这里i=1, 2,… k；
• 删除Key：没有办法。

设bitmap 有m 位，而Bloom Filter 集合有n 个元素，那么，当Bloom Filter报Key 存在而Key 实际不存在的概率为： (1-(1-1/m)^(kn))^k，在m 和n 都很大的时候，这个结果可以为(1-e^(-kn/m))^k。同时，这个结果最小的时候，k 等于 m*ln2/n = 0.7*m/n，最小的值为(1/2^ln2)^(m/n) = 0.62^(m/n)。这里的n 表示集合中元素的个数。这个式子表明，如果每个元素使用10 位来表示的话（在m 中，即m = 10*n）， bloom filter 出错的几率为0.62^10 = 1%。

为了达到p 的false positive，每个元素需要1.44log(base 2)1/p 位。
研究表明，当数据足够大时，如果用kn 位表示n 个数据的话，理论上，其false positive 为：P>=1/(2^k)-ε，其中 ε 为常数。这就说明，理论上，要达到p 的false positive，每个元素只需要log(base 2)1/p 位。可以看到，Bloom Filter 比理论值多用了44%的空间。

显然，Bloom Filter 存在2 个问题：
1）空间利用率较低 
2）需要使用很多独立分布的Hash 函数
3）bloom filter 不支持删除操作

研究人员对此有很多改进，对几个主要的改进介绍如下：
增加对删除操作的支持（Counting Bloom filter）：
如果数组的每个元素不是只有1 位，而是有t 位的话，这t 位就可以用来保存有多少个key 被映射到了这里。
下图是一个例子：

也就是说，当key 被添加到bloom filter 的时候，key 会被这k 个hash 映射到k 个位置pos1 到posk，把这k 个位置的值都加上1。
在删除key 的时候，key 会被这k 个hash 映射到k 个位置pos1 到posk，把这k 个位置的值都减1。
研究证明，对于数组中的元素来说，它最后大于24 的概率只有6.78E-17。即每个元素只需要4 位即可。


减少数组中为1的位（Choose Bloom Filter）：
已经知道Bloom filter 其实浪费了很多空间，在不减少它占用的空间的情况下，或许可以减少它false positive 的概率。Choose Bloom Filter 试图减少数组中元素值为1 的个数，它是这样计算key 是否在Set 中存在：计算key 的k 个has h值，设这k 个hash 值对应的bitmap 的位中，为1 的位数有t 个，为0 的位数为f个（这里k=t+f），当t>f 的时候，就认为key 在Set 中存在，否则认为不存在。
如何决定需要设置为0 的位（原来是1），比较困难。


增加压缩比率（Compressed Bloom Filter）：
Bloom Filter 常常需要保存在内存或者通过网络发送给客户端。但Bloom Filter 在信息模型上是随机的，直接对它的压缩不够理想。Compressed Bloom Filter 的思想如下：
1）分配大一点的bitmap；
2）按照基本bloom filter 方式进行插入操作；
3）仔细选择，把部分为0 的位设置为1，增加压缩率。
假设原始bitmap 为：
0000000100000010000000010000000000010000000
它可以被表示为：(7，6，8，11，7)，这里只保存连续的0 的个数。现在有
选择的把0 改为1，可以得到结果为（红色表示修改的位）：
0001000100010010001000010001000100010001000
即为：（ 3，3，3，2，3，4，3，3，3，3，3），十分方便压缩。需要注意的是，因为增加了为1 的位数，所以，Compressed Bloom Filter 比基本Bloom Filter更浪费空间。

Bloom Filter 的一种替代方案是直接使用Hash。可以用完美Hash（perfect hash）算法构建一个接近于理论值的概率Set。其思想可以简单的表示为下图：

即通过完美Hash，把输入的N 个Key，不冲突的映射到长度为N 的数组A，再把Key 用k 位表示即可。因为k 位可以表示2^k 种情况，故上述Hash 模式可以达到的false positive 为P >= 1/(2^k)。

上面的模式可以扩展到普通Hash 函数。比较有名的有2 个，一个是用多数组解决Hash 碰撞；一个就是Cukoo Hash 了。

上图是基于多数组的Hash Bloom Filter，其基本思想是，不碰撞的Hash 放到第一个数组，碰撞的放到第二个数组，还有碰撞的继续放到下个数组。

Cukoo Hash 本来就是一个没有碰撞的Hash，它不需要进行什么额外处理。唯一的问题在于如何在编程上更加节省空间。


5.2 压缩算法
压缩算法主要有2 种：无损压缩和有损压缩。前者用来压缩文本和普通文件；

后者一般用来压缩多媒体信息。因为搜索引擎很少用到有损压缩，我们将只谈论无损压缩。


(待續)