晚上在网上看了腾讯大讲堂第三期的视频和ppt，是由腾讯搜搜首席架构朱老师主讲的搜索引擎，朱老师不愧是这方面的专家，讲的很到位，搜索技术的各个方面都有提及，从发展历史，到工作原理，再到未来发展方向，内容很详实，受教之余，也把自己了解的一些东西拿出来献献丑。 朱老师在工作原理部分讲到了索引技术，提到每个月要用一个星期的时间对抓下来的网页做成索引。这个索引是个什么东东呢？其实很像我们用的书本目录，或者是国外大部头教材后面的内容或者表格等的索引。其本质是对文本词汇的一个标记，在用户输入关键词时可以快速的定位该词汇在原文中的位置。可见，索引可算是搜索引擎工作的一个核心构成，其重要性自然不言而喻。 在早期的搜索技术中广泛适用了签名文档技术。这种技术就是朱老师提到的分类技术，因为其过于原始和简单，也不能提供很精准的搜索定位，现在已经基本被淘汰，不再适用。 目前主流的搜索引擎是基于一种称为 inverted file 的技术。这种技术的做法是建立了两个表，一个词汇表(vocabulary) ，一个事件表(occurrence)。词汇表中记录文本所有的关键词，时间表记录每一个关键词对应出现在文本中的位置。这样的两个表是比较大的，一般会占到原文的30%到40%（理论值）。有了这两个表，再对用户输入的关键词在词汇表中进行查找，可以很快定位关键字出现的位置。这是目前搜索引擎中索引的主流技术，查找性能很优越。 但 inverted file 技术的缺陷也比较明显，而且随着互联网技术的发展愈来愈彰显。其主要缺陷有以下几点：（1）无法对短语进行方便的检索。（2） inverted file 是一种词索引，其基本的索引单位是词。在英文等拉丁语环境中的表现较好。但在像汉语日语等没有明显的单词划分边界的语言中，表现就不尽如人意了。中文搜索中一个重要的技术就是“分词”技术，目的就是对抓下来的文本中的汉语词汇进行合适的划分，以利用 inverted file 技术做索引。这个分词技术到目前也没有很好的解决。想想也是，我们小时候学习阅读，很重要的一点就是合适的地方停顿，其实也就是分词。人都得学习才能做好，何况并不怎么聪明的机器~~ inverted file的缺陷本质上都是因为它是一种词索引。试想我们要是能做到对每个字母都建立索引，这样在查询的时候直接匹配关键词的字母和抓下来的网页中的字母，不是就能良好的解决上面的问题了？话虽如此，但具体实现起来是困难的。如果我们直接用inverted file技术，则对每个字符建立词汇表(vocabulary)（这样的话或许叫字符表合适~~），这个表倒是很小了，对应的拉丁语的话也就是26个字母，加上一些符号也不会超过300，但我们的事件表(occurrence)可就悲剧了，它会非常大以至于不能承受。想想记录一篇文章中每个字母的出现位置吧~~~ 但也并非就没有解决之道，我们的搜索技术也不可能一直停留在分词和词索引的层次上。上面的 inverted file技术之所以不再适用，是我们用旧瓶装新酿，结果自然不会好。好在各式各样的牛人们早就提出了各式各样的牛逼的新算法和数据结构。这些新方法都有一个名称叫 full text indexes （全文索引）。其中有效的方法之一就是suffix array或者suffix tree。这两者在本质上没有什么区别。用suffix array或者suffix tree 建立全文索引的时间和 inverted file 也没有太大的差距，还在我们的接受范围之内。但是，可悲的是suffix array和suffix tree都需要巨大的存储空间消耗~~~虽然相对于上文中提到的用 inverted file 基于单个字符建立全文索引的空间需求要小的多，但也足够大到无法实际应用的地步了，它需要至少占用原文本log(n)倍（n可以理解为原文的空间大小）的空间。毫无疑问，原文越大，这个倍数会越大，大到我们无法接受！ 对full text indexes(全文索引)算法的研究还有很多其他精致而有趣的算法，比如有牛人提出的CSA (compressed suffix array)算法已经能把全文索引压缩到原文的的1倍左右，而且不影响查询的时间。还有很多其他很有趣的算法也能做到类似的效果。实际应用中也有一些先驱者开发出了试验平台，忘记了是美国哪个大学的图书馆的搜索系统就是基于上述的CSA算法实现的。 未来的搜索引擎在索引技术上肯定是全文索引的，其好处不言而喻，相信不久的将来这将不在是实验室技术，而是应用到各大搜索引擎的的核心中，为我们的生活，学习提供更加精准，更加有效的搜索服务。 |
