索引系统-倒排索引文件的创建过程

2019-12-12 11:15:27  浏览:205  作者:老王

  倒排索引文件的创建过程更像是一个工程建设,其中大量应用了批量计算及流水计算的技巧,完成如此大规模的倒排索引文件的创建一直是搜索引擎的核心难点。

  创建倒排表


  首先通过一个例子完整地体会单个索引结点倒排文件的创建过程,如图5-22所示。

  这里的网页库支持顺序访问模式(参见第三章第五节),能够顺序读取存放在其中的文档。为了简化,我们假定读取的文档按照顺序分别为文档1、文档2和文档3,其正文内容分别为"ratdog"、" dog cat”和" rat dog"。通过在内存中完成正排得到索引词出现的文档和位置信息,例如,rat(1,1)表示在文档1的第1个位置出现“rat"这个索引词。接下来通过对字母排序(汉字可以按照汉字词汇编号排序)得到一个临时的按照索引词有序的结构,这有助于顺序写入各个索引词对应的记录表。在图5-22所示的倒排表达到一定大小(例如100MB)时,将倒排表顺序写入到临时倒排文件中。完成全部网页库的索引工作后,将产生的多个临时倒排文件归并为一个最终倒排文件(图5-22中忽略临时倒排文件归并的过程)。

索引系统-倒排索引文件的创建过程

  从计算的角度上讲,临时倒排文件创建的全过程包含了磁盘读取( loading)计算( processing)和写入磁盘( flushing)这3个过程,磁盘读取从网页库中读取一个个的文档;计算过程包括了正排计算、排序及归并等;写入磁盘主要是写入临时倒排文件如果采用多道并行处理,则可大大提高索引创建的效率。

  如果将整个临时倒排文件创建过程抽象为L( loading)、p( processing)和F( flushing)3个顺序的操作,即到写入临时倒排文件为止,则L操作和F操作是磁盘密集型操作;而P操作是CPU密集型操作。为了简化,采用两个线程并发操作的处理方法,如图5-23所示。

索引系统-倒排索引文件的创建过程

  这里线程1首先开始执行L操作在执行P操作时磁盘空闲这时线程2使用磁盘执行L操作。理论上最佳的效果是无论在什么时间点上,总是一个线程占用CPU;另一个线程占用磁盘,这样相互配合可以高效地完成索引创建过程。这里还有一个问题就是一次L操作读取多少文档才是最佳的,可以使得这种合作能够最少出现互相等待的情况。对于两道线程并发,一个L操作读取的文档规模应该满足。使得P操作执行的时间与执行一次L操作的时间相当,即线程1的P操作能够和线程2的L操作重叠。当然实际处理中还有很多技巧,读者可以参阅文献[ Arvind arasu etal,.200]获取更加详细的技术细节。

  计算统计信息


  计算统计信息在上一节中提到,这里给出两种计算方法,两种方法各有优劣。第1种方法从排序后的正排表开始统计;第2种方法从临时倒排文件统计。分别来看这两种方法的区别。首先通过图5-24来理解第1种方法。

索引系统-倒排索引文件的创建过程

  内存中经过排序的正排结果在转换为倒排表之前,发给统计员一份拷贝。统计员为每个索引结点建立一个哈希表,这个哈希表用来进行计数。在全部网页库中的文档被处理完后,统计员将各个哈希表中的词进行综合统计,把相应的结果发给各个索引结点。注意这里发给索引结点A的统计结果和发给索引结点B的统计结果是不同的,因为索引结点B不包含"rat"这个索引词,因此没有必要把"rat"的信息发给它。这种方法由于需要维护哈希表的代价,因此需要耗费一定的内存空间,这是其主要缺点。

  第2种统计方法主要采用基于已经计算好的倒排表数据来进行综合统计,整个过程相对简单。相当于对各个索引结点自身的统计结果进行综合统计,然后回传给各个索引结点。这种方法的主要缺点是需要等待最慢的索引结点做完索引后才能开始进行计算。

  在完成了创建最终倒排文件和词典后,全部倒排索引文件创建工作完毕。从某种角度上看,这些都是一种预先计算( precomputation)这种预先计算都是在为查询时节省时间,海量数据完成一次最终倒排索引文件的制作是非常耗时的,这些尽可能预先完成的计算为查询争取了宝贵的时间。

  现在离搜索越来越近了,下一章我们来到搜索引擎最直接面对用户的查询系统,继续了解有关搜索及查询的知识。

评论区

共0条评论
  • 这篇文章还没有收到评论,赶紧来抢沙发吧~

【随机新闻】

返回顶部