倒排索引

倒排索引在逻辑结构和基本思想上非常简单。下面通过具体的例子来说明一下，让大家对倒排指数有一个宏观直接的感受。

中文和英文不一样，单词之间没有明确的分隔符。所以首先要用分词系统把一个文档自动分割成词序列，这样每个文档就可以转换成由词序列组成的数据流。

为了方便系统的后续处理，需要给每个不同的单词分配一个唯一的单词编号，并记录哪些文档包含这个单词。经过处理后，我们可以得到最简单的倒排索引(参见图4)。

在图4中，“单词ID”一列记录了每个单词对应的数字，第二列是对应的单词，第三列是每个单词对应的倒排表。例如，单词“Google”，其中单词编号为1，倒排表为{1，2，3，4，5}，表示文档集合中的每个文档都包含该单词。

图4中的倒排索引最简单的原因是因为这个索引系统只记录哪些文档包含某个单词。事实上，索引系统可以记录更多的信息。

图5是相对复杂的倒排索引。与图4所示的基本索引系统相比，在对应于该单词的倒排表中不仅记录了文档号，还记录了词频信息，即该单词在某个文档中出现的次数。之所以要记录这些信息，是因为在搜索结果中对词频信息进行排序时，查询与文档的相似度是一个非常重要的计算因素，所以将其记录在倒排表中，方便后续排序时的评分计算。

在图5所示的例子中，单词“founder”的字数为7，对应的倒排表内容为(3；1)，其中3表示文档号为3的文档中包含该词，数字1表示词频信息，即该词在3号文档中只出现过1次，其他词对应的倒排表具有相同的含义。

实用的倒排索引还可以记录更多的信息。除了文档号和词频信息，图6所示的索引系统还记录了两种信息，即每个单词对应的文档频率信息(图6中的第三列)和该单词在某个文档中出现位置的信息。

文档频率信息表示文档集合中有多少文档包含一个单词。之所以记录这些信息，和词频信息是一样的，词频信息是搜索结果排名计算中非常重要的因素。

然而，词在文档中的位置信息不一定被索引系统记录，而是可以包括或不包括在实际的索引系统中。之所以这样，是因为这些信息对于搜索系统来说并不是必须的，位置信息只有在支持短语查询的情况下才能派上用场。

以“Lars”这个词为例:它的字数为8，文档频率为2，意味着整个文档集合中有两个文档包含这个词，对应的倒排表为{(3；1;& lt4 & gt),(5;1;& lt4 & gt)}，表示该词在文档3和文档5中均有出现，词频为1，两个文档中“Lars”一词的出现位置均为4，即文档中的第四个词为“Lars”。

图6所示的倒排索引已经是非常完整的索引体系，实际搜索引擎的索引结构也基本相同。唯一不同的是采用什么具体的数据结构来实现上述逻辑结构。

有了这个索引系统，搜索引擎可以方便地响应用户的查询。例如，当用户输入查询词“脸书”时，搜索系统会寻找倒排索引，从中可以读取包含该词的文档，这些文档就是提供给用户的搜索结果。

使用词频信息和文档频率信息，可以对这些候选搜索结果进行排序，计算文档与查询的相似度，并根据相似度得分从高到低对输出进行排序，这是搜索系统内部过程的一部分。

词词典是倒排索引中非常重要的一部分，用于维护文档集合中出现过的所有词的相关信息，记录一个词在倒排文件中对应的倒排表的位置信息。支持搜索时，根据用户的查询词，在词词典中查找就可以得到对应的倒排表，并以此作为后续排序的依据。

对于一个大规模的文档集合，它可能包含几十万甚至几百万个不同的单词。能否快速定位一个词，会直接影响搜索时的响应速度。因此，需要有效的数据结构来构建和查找单词词典。常用的数据结构有哈希加链表结构和树形字典结构。

B树(或B+树)是另一种高效的搜索结构，图8是B树结构示意图。b树搜索不同于哈希搜索，哈希搜索要求字典条目按大小排序(数字或字符顺序)，而哈希搜索不要求数据满足这一要求。

b树是一种分层的搜索结构。中间节点用来表示某个排序范围内的字典项存放在哪个子树中，根据字典项的比较大小起到导航的作用。最底层的叶子节点存储单词的地址信息，可以根据这个地址提取单词串。

详情请看[/黑客ose 1994/article/details/5093396？location num = 11 & amp；fps=1)