正排索引和倒排索引简单介绍.docx

《正排索引和倒排索引简单介绍.docx》由会员分享，可在线阅读，更多相关《正排索引和倒排索引简单介绍.docx（2页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、正排索引和倒排索引简洁介绍在搜寻引擎中，数据被爬取后，就会建立index,便利检索。在工作中常常会听到有人问，你这个index是正排的还是倒排的？那么什么是正排呢？ 什么又是倒排呢？下面是一些简洁的介绍。网页A中的内容片段：Tom is a boy.Tom is a student too.网页B中的内容片段：Jon works at school.Toms teacher is Jon.正排索引：正排索引是指文档ID为key,表中纪录每个关键词消失的次数，查找时扫描表中的每 个文档中字的信息，直到找到全部包含查询关键字的文档。假设网页A的局部文档ID是TA,网页B的局部文档ID是TB。那么对

2、TA进行正排 索引建立的表结构是下面这样的：内容：TooisnboyTgisastudenttoo分诩Tooisaboystudenttoo正排：Indexwordword hit（词出现的次数）ord offset （词在文柬中出现的位置）TAToo21.5is22.6a23,7boy14student18too19NULL出现的位置进行筮分序列Docidwordword”（词出现的次数）ord_offset （词在文章中出现的位置）位置解释：TAToo21,4第一个Ton出现 在第一个位置 上，第二个Torn 出现在以1为4偏 移量的位置上. 即1+泡is22.4同理，第一个1$ 出现在第

3、二个位 置上，第二个i* 出现在以4为偏 移fit的位上.HP. 2M位a23,4boy4student18too9根据位置任原字符审，123456789TomTonisisaaboystudenttooTonisaboy Tomisastudenttoo从上面的介绍可以看出，正排是以docid作为索引的，但是在搜寻的时候我们基本上都 是用关键词来搜寻。所以，试想一下，我们搜一个关键字（Tom）,当100个网页的10个网 页含有Tom这个关键字。但是由于是正排是doc id作为索引的，所以我们不得不把100个 网页都扫描一遍，然后找出其中含有Tom的10个网页。然后再进行rank, sort等

4、。效率就 比较低了。尤其当现在网络上的网页数已经远远超过亿这个数量后，这种方式现在并不适合 作为搜寻的依靠。不过与之相比的是，正排这种模式简洁维护。由于是采纳doc作为key来存储的，所以 新增网页的时候，只要在末尾新增一个key,然后把词、词消失的频率和位置信息分析完成 后就可以使用了。全部正排的优点是：易维护；缺点是搜寻的耗时太长；倒排索引：由于正排的耗时太长缺点，倒排就正好相反，是以word作为关键索引。表中关键字 所对应的纪录表项纪录了消失这个字或词的全部文档，一个表项就是一个字表段，它纪录该 文档的ID和字符在该文档中消失的位置状况。倒排包含两部分：1、由不同的索引词（index t

5、erm）组成的索引表，称为“词典（lexicon）。其中包 含了各种词汇，以及这些词汇的统计信息（如消失频率nDocs）,这些统计信息可以直接用 于各种排名算法。2、由每个索引词消失过的文档集合，以及命中位置等信息构成。也称为“纪录表。 就是正排索引产生的那张表。当然这部分可以没有。详细看自己的业务需求了。下面是一个简洁的倒排索引构建，只包含第一部分的。倒排演示：docl：itiswhatitisdoc2:whatisitdoc3:itisabanana倒排：Termitdocl, doc2, doc3)isdocl, doc2, doc3)whatdocl,doc2)adoc3)bananadoc3当我们搜索、haJ, is,it*的时候，docl, doc2 A docl, doc2, doc3 A (docl, doc2, doc3),得到的文章就是 docl, doc2带位置的倒挂：Terrait(docl, 1), (docl, 4), (doc2, 3), (doc3, 1)is(docl,2), (dcol,5), (doc2,2), (doc3,2)what(docl, 3), (doc2, 1)a(doc3,3)banana(doc3, 4)倒排的优缺点和正排的优缺点整好相反。倒排在构建索引的时候较为耗时且维护 成本较高，但是搜寻耗时短。