倒排文件与搜索算法

l       什么是倒排文件    

   文件检索里面已经有了很多方法，让我们很容易根据一个记录的关键码查找到该记录全部信息的存放位置，从而能拿到该记录的全部其他属性值。但是在实际检索应用中，我们还经常需要根据记录中的其他一些非关键码的数据项来作查找，也就是根据属性的值来查找记录。所以我们也要对属性值建立索引，即索引表中的每一项均由一个具体可能出现的属性值，和出现给该值的记录的地址两部分组成。这样，我们可以通过记录的某一项属性值反过来查找到这个记录的存放地址，或者记录对应的关键码。我们称这种索引为倒排索引（inverted index）。拥有倒排索引的文件被称为倒排索引文件，简称倒排文件（inverted file）。

l       倒排文件应用举例

1、  基于属性的倒排

   在一个带结构的记录文件中，如数据库文件等。文件里存放的都是一条接着一条的整齐的记录，每个记录又可分为一个个的属性。检索过程往往要求找出，在某个或者某些属性上满足一定条件的记录集合。像这一类的检索我们称为基于属性的检索。

   比如北大里某次活动的学生报名登记表文件，部分信息如下：

编号(关键码)	学号	姓名	性别	年龄	院系
001	xxx142	张三	男	18	元培
002	xxx205	李四	女	17	哲学
003	xxx187	王五	男	19	生物
004	xxx325	赵六	女	18	元培
……	……	……	……	……	……

表1 主文件 

   对这类文件的往往会进行这样的一些查询，如：找出院系为“元培”的所有学生（简单查询），找出年龄在18到20之间的所有学生（范围查询），找出年龄在19岁以上的所有男生（逻辑查询）等等。如果没有倒排表，我们则只能顺序从头到尾的一条一条检查记录，判断是否符合条件。这样当文件很大的时候，往往要多次读写磁盘会耗费相当大的时间。就算之前我们把记录按照关键码排序，也仍无法使用普通的检索方式来提高效率，因为查找的条件不是和关键码相关的。

   而我们利用倒排文件来实现上述非关键码的查询，就能大大提高速度。对于前面的情况设计倒排表如下：

性别倒排表	编号#
男	001，003
女	002，004
年龄倒排表	编号#
16
17	002
18	001，004
19	003
20
……	……
院系倒排表	编号#
元培	001，004
生物	003
哲学	002
……	……

表2 倒排表文件

   有了这样的倒排表后，前面的查询就很容易了。如找出院系为“元培”的所有学生（简单查询），可以在院系倒排表中，取出属性值为“元培”的那一行倒排表，它里面包含的所有编号对应的记录就是所求的记录。又如找出年龄在18到20之间的所有学生（范围查询），我们可以把年龄倒排表中18，19和20这三行所对应的三个编号集合做并运算，最后结果就是我们要找的。而找出年龄在19岁以上的所有男生（逻辑查询），这个我们找出19岁以上的所有编号集合，用并运算合在一起，再同性别倒排表中的男生那一行的集合做与运算，最后就能得到正确结果。

   由此可见，有了倒排文件，我们就可以将查询变成几个集合之间的交，并等运算，得到的最后结果即时我们要求的，这样不用挨个读取记录，且参与运算的数据大大减少，基本可以不用多次读写磁盘而直接在内存里进行运算，大大提高了检索速度。

2、  基于文本的倒排

   倒排文件也可以应用于非结构化的信息检索里面，如大量正文的文本索引。尤其当今搜索引擎需要对海量的正文文本信息进行检索的情况下，倒排文件的使用尤其重要。

   对多个正文文本建立索引的基本思想就是，把正文看成一个一个的关键词的集合，然后用这些词组成一些适合快速检索的数据结构。一个倒排文件就是一个已经排好序的关键词的列表，其中每个关键词指向一个倒排表，该表中记录了该关键词出现的文档集合以及在该文档中的出现位置。如北大某院图书馆论文集的部分倒排表：

关键词	倒排表（所在文档编号，出现次数， 出现位置）
KMP	（#3307, 2, 5, 43）（#4615, 3, 0, 19, 34, 70, 143）
最小支撑树	（#2519, 1, 267）（#6742, 3, 19, 322, 526）……
贪心算法	（#2948, 3, 45, 267, 587）（#3693, 5, 39, 423, 765,809,1024）……
……	……

表3 基于文本的倒排文件

   这样一来，当要检索关于KMP方面的文章时，可直接取出其倒排表即可得知，编号为3307和4615的文章都是包含KMP这个关键词的，且能知道包含了多少次，以及在各个文档中的具体出现位置。如果同时需要“最小支撑树”和“贪心算法”两方面的文章，则可以直接将两个倒排表取交集，就能得到所有符合条件的集合。如此可以免去在整个图书馆里每一篇文档里去逐个查找的代价，从而可以轻松快捷的得到结果。

   对于这样一个正文倒排文件的建立通常需要如下几个步骤。首先是文本切词，即以人工或者机器自动的方式把一篇文档里的可能成为关键词的词组划分出来。在汉语等东方语言中，因为词与词之间没有空格，所以怎样把词组从句子中完整的切分出来，需要专门的研究。这需要自然语言理解技术(natural language processing,属人工智能研究的一个分支)的支持。然后是得到各个关键词的集合，对于每个关键词建立它的倒排表，然后把所有倒排表按关键词排序存入文件，形成倒排文件。文件中除了记录那个关键词对应哪些文档外，还应该有关键词在文档中的出现位置和出现次数等。然而最后得到的倒排文件往往还是很大，关键词很多，所以还需要对倒排文件里的关键词再次建立索引结构。对关键词进行索引的常用技术有散列和B+树等，当然如果关键词能全部放入内存，也可以使用二叉查找树来建立索引。

   由于倒排索引支持高效检索，所以应用相当广泛。当然，对倒排表进行集合运算也需要一些运算空间，更大的缺点在于，当文件发生变化时，要同时维护更新这些索引，而这种更新的工作量会很大，所以它比较适合于当大文件里面内容比较稳定的情况下。尤其像光盘上的数据检索等就会是它最理想的应用场所之一。