此文已由作者刘超授权网易云社区发布。

欢迎访问网易云社区，了解更多网易技术产品运营经验

词典中所保存的信息主要是三部分：

• Term字符串

• Term的统计信息，比如文档频率(Document Frequency)

• 倒排表的位置信息

其中Term字符串如何保存是一个很大的问题，根据上一章基本原理的表述中，我们知道，写入文件的Term是按照字典顺序排好序的，那么如何将这些排好序的Term保存起来呢？

1. 顺序列表式

一个直观的想法就是顺序列表的方式，即每个Term都占用相同的空间，然后大家依次排列下来，如图所示：

这种方式查找起来也很方便，由于Term是排好序的，而且每一项占用空间相同，就可以采取二分查找，较快的定位Term的位置。比如在文件中，词典的起始地址是FP，共保存了N个Term，每个Term占用固定大小M个Byte，则中间的Term的位置为，将此位置的M个Byte读取出来，转换为字符，如果是要找的Term则完毕，如果大于要找的Term，则在前半段二分查找，如果小于要找的Term，就在后半段二分查找。

这种方法的一个最大的缺点，从图中我们也可以看出，就是对空间的浪费，我们必须按照最长的词所占的空间来决定每一个Term的空间，有的Term很长，如图中的counterrevolutionary，有的Term则很短，如cab，对于短的Term来讲，是空间的巨大浪费。而且另一个棘手的问题是，我们很难知道最长的字符串到底有多长。

2. 指针列表式

有人要说了，这样空间太浪费，像我们八辈贫农，可不能浪费一点空间，咱们要排列就紧密排列，一个挨一个：

就算Term与Term之间有分隔符号，可是茫茫辞海，我去那里找我的Term啊，总不能每找一个Term都从头开始扫描吧，我倒是想二分查找，可是每个Term的空间都不相同，偏移量我可怎么算呢？

有了，虽然每个Term的长度不同，可是指针(文件中的指针也即偏移量)的长度是相同的，我们将指针放成一个列表，不是就可以二分查找了么？。

这种指针列表方式在Lucene中我们也会经常看到，而且不仅仅用在词典的格式设计中，到时候大家不要忘记它，为方便记忆，我们称之为指针列表规则。

3. 前端编码式

如果细心观察的同学会发现，Term按照字典顺序排序，有一个好处，就是相邻的Term很大可能性上会有相同的前缀，比如上面的例子中，共8个Term，其中字符“c”被保存了8遍，字符“a”保存了4遍，字符“l”保存了3遍，能不能将相同的前缀提取出来，只保存一份呢？

对于某个Term和前一个Term有相同的前缀的，后者仅仅保前缀在Term中的偏移量，外加后缀的部分，一般来说偏移量作为数字所占用的空间比字符要小得多，所以这种方式会进一步节约存储空间，这种方式成为前端编码(front coding)。

空间是节约了，那么如何快速的查找呢？二分法估计是不行了，而且解压缩也成了问题，因为要想知道一个Term的全貌，必须把前一个Term也解压缩出来，难不成每次查找都把整个词典都解压缩？当然不是，我们可以将Term分块，每一块都有一个排头兵，整个快是基于排头兵进行前端编码，每次解压缩，仅仅解压缩一个块就可以了:

对于排头兵，由于数量相对于整个词典数量少的多，可以使用指针列表方式存储从而可以进行二分查找，甚至可以全部加载到内存中，使得查找更加方便。这种前端编码加词典分块的方式在Lucene中也会被用到，我们姑且称之前缀分块规则。

4. 最小完美哈希

该省的空间都省了，下面该考虑一下查询速度的问题了，在每次查询的时候，为了定位倒排表，首先需要定位词典中Term的位置，就算是使用前端编码加词典分块的方式，也需要尽快的定位排头兵的位置，那么怎么才能找得快呢？

很多人首先想到的应该是哈希表，如果词典能够全部放在内存中，用哈希表O(1)就能定位Term的位置。但是哈希函数不好选啊，弄不好就有冲突，当然我们有各种方法来解决冲突，一种常用的方法就是后面挂个链表，冲突的都挂在一个位置就可以了。可要是冲突的多了，都堆在一个链表中，那不又成了顺序扫描了，哈希表的优势荡然无存。那么如何减少冲突呢？当然是哈希表越稀疏越好，哈希表有一个概念叫做装载因子(Load Factor)，装的越满因子越大，只要装载因子比较小，冲突的概率自然就小，可是随之而来的一个问题就是空间的浪费。

就没有一个既节省空间，又不发生冲突的方法么？好让咱多快好省的建设社会主义嘛。别说，还真有，听名字就很牛，叫最小完美哈希。我们一般所说的哈希函数，就是将m个字符串，映射到k个位置上去，一般需要稀疏，所以k大于等于m，还有可能冲突，而这个算法设计的哈希函数一个都不会冲突，这就是所谓的完美，而且k=m，也即一个空间也不浪费，这就是所谓的最小。当然在实际应用中，一般不要求那么的最小而且完美，为了查询效率，一般都倾向于牺牲一点空间来保证完美，有一些工具可以帮助我们来生成这样的哈希函数，比如Gperf(http://www.gnu.org/software/gperf/)，根据你的输入的字符串列表而生成哈希函数，再如CMPH(C Minimal Perfect Hashing Library，http://cmph.sourceforge.net/index.html)，它支持多种算法，可以快速处理大量的字符串，我们来介绍其中一种CHM算法，也即无环图的方法，为啥叫CHM呢？这种算法是根据Z.J. Czech, G. Havas, B.S. Majewski这三位老兄发表的一篇论文《An optimal algorithm for generating minimal perfect hash functions., Information Processing Letters, 43(5):257-264, 1992.》来的，所以借用三位名字中的首字母CHM来命名了这个算法。

按照最小完美哈希的定义，我们先假设有三个字符串String1, String2, String3，它们经过哈希运算后，String1映射为0，String2映射为1，String3映射为2，正好没有一个空间浪费，也没有一个哈希值冲突，这是我们想最后实现的结果，如图.

 

那么哈希函数是什么样子的，才能达到这种效果呢？我们先来看公式：

W表示需要哈希的字符串，m是字符串的个数。我们可以看出，这个哈希函数嵌套了两层，第一层先用两个函数f1和f2将字符串分别映射成为两个数字，f1和f2需要是独立的，因而映射出来的两个数字也是不同的，这两个数字的取值范围[0, n-1]，姑且认为n是一个比m大的数，至于n多大后面还会提到。

接着上面的例子，m=3，n假设为4，如图所示：

 

然后就进入第二层，g函数将f1和f2计算出的两个数字进行处理，得到最终的哈希值[0, m-1]。还是上面的例子，g函数如何设计才能使得

设计g 函数，我们就使用无向图的方式，如图，将f1和f2计算出的数字作为顶点，而最终的哈希值作为连接两个顶点的边，我们想求的是

各是什么，也即g函数的映射方式。

 

我们先假设

，既然g 函数要求

，从而可以推出

也是0，由

，则推出

，依此类推，。

这个算法最后能够成功，还有一个关键点，就是这个图必须是无环的，如果有环算法就会失败。还是上面的例子，比如

，便产生了如图的有环图。

搜索引擎的设计(1)：词典的设计 下篇

11.1—11.15云计算基础服务全场5折起

免费体验云安全(易盾)内容安全、验证码等服务

更多网易技术、产品、运营经验分享请点击。