『搜索引擎』索引数据结构与算法.docx

最近一直在研究 sphinx 的工作机制,在[搜索引擎] Sphinx 的介绍和原理探索简单地介绍了其工作原理之后,还有很多问题没有弄懂,比如底层的数据结构和算法,于是更进一步地从数据结构层面了解其工作原理。在网上搜了很多资料,发现没有很多介绍这方面的文章,后来找到了一本书,《这就是搜索引擎》,拜读了本书的第三章,介绍了主流搜索引擎用的数据结构及其工作原理, sphinx 使用的数据结构也是一样的,用的也是倒排索引。注:本文不会对 sphinx 和搜索引擎严格区分开,同一作搜索引擎看待。先附图一枚索引基础先介绍与搜索引擎有关的一些基本概念,了解这些概念对后续了解工作机制非常重要。单词-文档矩阵单词- 文档矩阵是表达两者之间所具有的一种包含关系的概念模型。如下图所示,每列代表一个文档,每行代表一个单词,打对钩的位置代表包含关系。从纵向看, 可以得知每列代表文档包含了哪些单词; 从横向看, 每行代表了哪些文档包含了某个单词。搜索引擎的索引其实就是实现单词- 文档矩阵的具体数据结构。可以有不同的方式来实现上述概念模型, 比如倒排索引、签名文件、后缀树等方式。但实验数据表明, 倒排索引是单词到文档映射关系的最佳实现方式。倒排索引基本概念?文档( Document ): 以文本形式存在的存储对象。如: 网页、 Word 、 PDF 、 XM L 等不同格式的文件。?文档集合( Document Collection ):若干文档构成的集合。如:大量的网页。?文档编号( Document ID ):搜索引擎内部,唯一标识文档的唯一编号。?单词编号( Word ID ):搜索引擎内部,唯一标识单词的唯一编号。?倒排索引( Inverted Index ): 实现单词–文档矩阵的一种具体存储形式。倒排索引主要有单词词典和倒排文件组成。?单词词典( Lexicon ): 文档集合中出现过的所有单词构成的字符串集合, 单词词典内每条索引项记载单词本身的一些信息及指向倒排列表的指针。?倒排列表( PostingList ): 出现了某个单词的所有文档的文档列表及单词在该文档中出现的位置信息。列表中每条记录称为一个倒排项( Posting )。?倒排文件( Inverted File ):保存所有单词的倒排列表的文件,倒排文件是存储倒排索引的物理文件。概念之间的关系如图倒排索引简单实例下面举一个实例,这样对倒排索引有一个更直观的感受。假设文档集合包含 5 个文档,每个文档内容如下图所示: 建立的倒排索引如下图: ?单词 ID :记录每个单词的单词编号; ?单词:对应的单词; ?文档频率:代表再文档集合中有多少个文档包含某个单词?倒排列表:包含单词 ID 及其他必要信息? TF :单词在某个文档中出现的次数? POS :单词在文档中出现的位置以单词“加盟”为例, 其单词编号为 8, 文档频率为 3, 代表整个文档集合中有三个文档包含这个单词,对应的倒排列表为{(2;1;<4>),(3;1;<7>),(5;1;<5>)} 含义是在文档 2,3,5 出现过这个单词,在每个文档的出现过 1 次,单词“加盟”在第一个文档的 POS 是4 ,即文档的第四个单词是“加盟”,其他的类似。这个倒排索引已经是一个非常完备的索引系统,实际搜索系统的索引结构基本如此。单词词典单词词典用来维护文档集合中出现过的所有单词的相关信息, 同时用来记载某个单词对应的倒排列表在倒排文件中的位置信息。在查询时到单词词典里查询, 就能获得相应的倒排列表, 并以此作为后序排序的基础。常用数据结构:哈希加链表和树形词典结构。哈希加链表下图是哈希加链表词典结构的示意图。主体是哈希表, 每个哈希表项保存一个指针, 指针指向冲突连表,相同哈希值的单词形成链表结构。构建过程: 对文档进行分词; 对于做好的分词,利用哈希函数获取哈希值; 根据哈希值对应的哈希表项找到对应的冲突链表; 如果冲突链表已经存在该单词不处理否则加入冲突连表树形结构使用 B 树或者 B+ 树的结构。与哈希表不同的是, 需要字典项能按照大小排序, 即使用数字或字符序。树形结构中,使用层级查找,中间节点保存一定顺序范围的词典项目存储在哪个子树中,最底层的叶子节点存储单词的地址信息。倒排列表倒排列表用来记录哪些文档包含了某个单词。倒排列表由倒排索引项组成, 每个倒排索引项由文档 ID ,单词出现次数 TD 以及单词在文档中哪些位置出现过等信息。包含某单词的一些列倒排索引项形成了某个单词对应的倒排列表。下图是倒排列表示意图: 建立索引前面介绍了索引结构, 那么, 有了数据之后索引是怎么建立的呢?主要有三种建立索引的方法。两遍文档遍历法此方法在内存里完成索引的创建过程。要求内存要足够大。第一遍收集一些全局的统计信息。包括文档集合包含的文档个