在工作中,经常听到Feed相关的产品和研发谈及正排库和倒排库,那么究竟什么是正排和倒排呢。
正排索引(正向索引)
正排表是以文档的ID为关键字,表中记录文档中每个字的位置信息,查找时扫描表中每个文档中字的信息直到找出所有包含查询关键字的文档。
正排表结构如图1所示,这种组织方法在建立索引的时候结构比较简单,建立比较方便且易于维护;因为索引是基于文档建立的,若是有新的文档加入,直接为该文档建立一个新的索引块,挂接在原来索引文件的后面。若是有文档删除,则直接找到该文档号文档对应的索引信息,将其直接删除。但是在查询的时候需对所有的文档进行扫描以确保没有遗漏,这样就使得检索时间大大延长,检索效率低下。
正排索引也称为“前向索引”。它是创建倒排索引的基础,具有以下字段。
(1)Localld字段(表中简称“Lid”):表示一个文档的局部编号。
(2)Wordld字段:表示文档分词后的编号,也可称为“索引词编号”。
(3)NHits字段:表示某个索引词在文档中出现的次数。
(4)HitList变长字段:表示某个索引词在文档中出现的位置,即相对于正文的偏移量。
由于一篇文章中的某些词可能出现多次,而且位置不同,而全文检索的本质要求是把这些位置标识出来,因此HitList中的每个命中都表示索引词在文档的某个位置中出现了一次,这个序列为单调递增序列。基于游程编码的方法,变升序序列为差分序列,采用前文提到的Variable Byte Coding方法编码可以大大压缩正排索引的HitList字段。
事实上,文档编号在不同的计算过程里,分别称为局部编号和全局编号,它们在编号长度上稍有不同,为了便于理解,不区别这些区别,认为Localld和Docld完全一致,都表示一个文档的唯一编号。在正排索引中Localld采用升序序列编号(假定编号采用自增1的方式递增),这为下面的计算创造条件。进行倒排索引的转化时,由于正排索引中Lid天然的有序性,因此在正排索引转化为倒排索引的创建过程中,自然可以保证倒排索引中每个词汇对应的文档编号也是有序的.
本质上说,正排索引以文档编号为视角看待索引词,也就是通过文档编号去找索引词。任给一个文档编号,能够知道它包含了哪些索引词、这些索引词分别出现的次数,以及索引词出现的位置。然而全文索引是通过关键词来检索,而不是通过文档编号来检索,因此正排索引不能满足全文检索的要求。
虽然正排索引不能满足全文检索的需要,但是正排索引为创建倒排索引创造了有利条件,是计算倒排索引的不可缺少的一环。
尽管正排表的工作原理非常的简单,但是由于其检索效率太低,除非在特定情况下,否则实用性价值不大。
倒排索引(反向索引)
倒排表以字或词为关键字进行索引,表中关键字所对应的记录表项记录了出现这个字或词的所有文档,一个表项就是一个字表段,它记录该文档的ID和字符在该文档中出现的位置情况。
由于每个字或词对应的文档数量在动态变化,所以倒排表的建立和维护都较为复杂,但是在查询的时候由于可以一次得到查询关键字所对应的所有文档,所以效率高于正排表。在全文检索中,检索的快速响应是一个最为关键的性能,而索引建立由于在后台进行,尽管效率相对低一些,但不会影响整个搜索引擎的效率。
倒排表的结构图如图2:
正排索引是从文档到关键字的映射(已知文档求关键字),倒排索引是从关键字到文档的映射(已知关键字求文档)。
本文转自CSDN
正排索引和倒排索引简单介绍,什么是搜索引擎的正排索引,正排索引和倒排索引的区别
One comment
感谢楼主精彩内容分享