精华内容
下载资源
问答
  • 倒排表
    千次阅读
    2021-02-06 23:56:41

    搜索引擎最核心的技术, 倒排索引技术,倒排索引可能需要分成几篇文章才说得完,我们先会说说倒排索引的技术原理,然后会讲讲怎么用一些数据结构和算法来实现一个倒排索引,然后会说一个 索引器怎么通过 文档来生成一个倒排索引。

    什么是倒排索引呢?索引我们都知道,就是为了能更快的找到文档的数据结构,比如给文档编个号,那么通过这个号就可以很快的找到某一篇文档,而倒排索引不是根据文档编号,而是通过文档中的某些个词而找到文档的索引结构。

    倒排索引技术简单,高效,简直是为搜索引擎这种东西量身定做的,就是靠这个技术,实现一个搜索引擎才成为可能,我们也才能在海量的文章中通过一个关键词找到我们想要的内容。

    我们看个例子,有下面的几个文档:

    文档编号文档内容
    1这是一个Go语言实现的引擎
    2PHP是世界上最好的语言
    3Linux是C语言和汇编语言实现的
    4谷歌是一个世界上最好的搜索公司

    直观的看,我们通过编号1,2,3,4可以很快的找到文档,但是我们需要通过关键词找文档,那么把上面那个表格稍微变化一下,就是倒排索引了

    倒排表(倒排索引)【只列出了部分关键词】

    关键词文档编号
    Go1
    语言1,2,3
    实现1,3
    搜索4
    引擎1
    PHP2
    世界2,4
    最好2,4
    汇编3
    公司4
    这样就非常好理解了吧,实际上倒排索引就是把文档的内容切词以后重新生成了一个表格,通过这个表格,我们可以很快的找到每个关键词对应的文档,好了,没有了,到这里,就是倒排索引的核心原理,也是搜索引擎最基础的基石,不管是谷歌还是某度,最核心的东西就是这两个表格,没这两表格,啥都干不了。

    看上去很简单吧,好吧,我们现在来模拟搜索引擎进行一次搜索,比如,我们键入关键词:搜索引擎

    1. 首先将 “搜索引擎” 这个词进行分词:搜索/引擎;
    2. 我们在表格2中查到 “搜索” 这个词出现在第4行, “引擎” 这个词出现在第5行;
    3. 找到第4行的第2列、第5行的第2列,把文档编号找出来,是1和4
    4. 去第一个表格通过文档编号把每个文档的实际内容找出来
    5. 将1和4的结果显示出来
    6. 搜索完成

    上面就是搜索引擎的最基础的技术了,如果来设计一个数据结构和算法来实现表2就成了搜索引擎技术的关键。
    在这里插入图片描述
    在实现数据结构和算法之前,我们需要知道搜索引擎搜索的是海量的数据,一般的中型电商的数据都是几十上百G的数据了,所以这个数据结构应该是存储在本地磁盘的而不是在内存中的,基于以上的考虑,为了快速搜索,要么自己实现cache来缓存热数据,要么考虑使用操作系统的底层技术MMAP,鉴于我自己实现的cache不见得(基本上是不太可能)比操作系统做得好,所以我使用的是MMAP。




    参考资料:
    搜索之倒排索引

    更多相关内容
  • 004开业前营运工作倒排表.zip
  • 为了进一步缩短查询时间,通过对当前索引文件自索引结构的分析,设计了倒排链表的多层自索引结构。此结构以定长元组为单位,使用迭代的方法提取数据段同步点形成上层自索引;在此基础上,实现了索引压缩与查询系统。...
  • 倒排表讲解

    2021-12-02 17:19:10
    目录前言一、倒排表总结 前言 倒排表可以用来做过滤的相关操作。 一、倒排表 示例:pandas 是基于NumPy 的一种工具,该工具是为了解决数据分析任务而创建的。 总结 提示:


    前言

    在问答系统中,我们应该根据用户提出的问题,然后在知识库里找相关的问题以及返回概率最高的答案,我们遇到的问题是假设知识库里有n个问题,那么我们每次需要做n次的相似度计算,这样的话对计算机的负担是极大的,那么如何降低复杂度呢?核心思路是根据倒排表做一个层次过滤,过滤掉不相关的问题以及答案。

    一、倒排表

    1-1、基本概念

    文档:比如Word、PDF、Excell等不同格式的文件都可以称之为文档。
    文档集合:由若干文档构成的集合称之为文档集合。
    文档编号:每个文档都会被赋予一个唯一的编号当作标识。
    单词编号:与文档编号类似,作为单词的唯一表征。
    倒排索引:实现“单词-文档矩阵”的一种具体存储形式,通过倒排索引,可以根据单词快速获取包含这个单词的文档列表。倒排索引主要由两个部分组成:单词词典和倒排文件。
    单词词典:文档集合中出现的所有单词构成的字符串集合,单词词典内每条索引项记载单词本身的一些信息以及指向“倒排列表”的指针。
    倒排列表:记载了出现过某个单词的所有文档的文档列表以及单词在该文档中出现的位置信息,每条记录成为一个倒排项。根据倒排列表,即可以获知哪些文档包含某个单词。
    倒排文件(Inverted File):所有单词的倒排列表往往顺序地存储在磁盘的某个文件里,这个文件即被称之为倒排文件,倒排文件是存储倒排索引的物理文件。

    1-2、简单应用

    假设包含三个文档,对这三个文档建立倒排索引。
    在这里插入图片描述
    先对中文进行分词,然后再赋予每个单词唯一的编号,在倒排列表中记录下了哪些文档包含这个单词。除了记录哪些文档包含这个单词,还可以记录词频等信息。
    在这里插入图片描述

    参考文章:
    一文了解倒排表.
    NLP——倒排表.


    总结

    不知不觉就到12月了,今年可过的真快。

    展开全文
  • 给出了一个基于音节混淆网络的语音文档内容检索系统,提出了一种基于两阶段解码的查询自动扩展方法,首先通过Viterbi解码算法在混淆音节网格上计算混淆音节的似然得分,然后利用A*解码算法从音节格上产生易混淆的...
  • 查找——索引顺序表和倒排表

    千次阅读 2020-06-26 21:12:52
    查找8.3 索引顺序表和倒排表8.3.1 索引顺序表 8.3 索引顺序表和倒排表 当数据表中的数据元素个数n很大时,如果用顺序查找结构,则查找效率极低。如果采用有序表存储形式的折半查找,则为了维持数据表的有序性,时间...

    8.3 索引顺序表和倒排表

    当数据表中的数据元素个数n很大时,如果用顺序查找结构,则查找效率极低。如果采用有序表存储形式的折半查找,则为了维持数据表的有序性,时间开销很大;而且,当数据表很大时,计算机内存的容量可能不够。这时可采用索引方法来实现存储和查找。

    8.3.1 索引顺序表

    1. 索引顺序表一般由主表索引表两个部分组成,两者均采用顺序存储结构。
      主表中存放数据元素的全部信息索引表中存放数据元素的主键字和索引信息

    (1)完全索引

    1. 在图8-3所示的学生信息表的例子中,一个索引项对应数据表中一个数据元素,这时的索引结构叫作稠密索引也称完全索引。稠密索引结构适用于当数据元素在外存中按加入次序存放而不是按关键字有序存放的情形。
      在这里插入图片描述
    2. 完全索引表中关键字分块有序存放,即把所有n个索引项分为m个块 (子表),井且后一个子表中所有的关键字均大于前一个子表中所有的关键字,而在同一子表中所有关键字的次序任意。分块有序,索引按照关键字的大小建立,可知大于某个值或者小于某个值可以到哪个块里面去查找。经典的分块查找要求块间有序、块内也有序,如果块与块无序就无法建立索引。
    3. 分块查找的具体实现
      转载自:https://www.cnblogs.com/ciyeer/p/9067048.html
    #include <stdio.h>
    #include <stdlib.h>
    struct index {   //定义块的结构
      int key;
      int start;
    } newIndex[3];  //定义结构体数组
    int search(int key, int a[]);
    int cmp(const void *a,const void* b){
      return (*(struct index*)a).key>(*(struct index*)b).key?1:-1;
    }
    int main(){
      int i, j=-1, k, key;
      int a[] = {33,42,44,38,24,48, 22,12,13,8,9,20, 60,58,74,49,86,53};
      //确认模块的起始值和最大值
      for (i=0; i<3; i++)   {
        newIndex[i].start = j+1; //确定每个块范围的起始值
        j += 6;
        for (int k=newIndex[i].start; k<=j; k++)     {
          if (newIndex[i].key<a[k])       {
            newIndex[i].key = a[k];
          }
        }
      }
      //对结构体按照 key 值进行排序
      qsort(newIndex,3, sizeof(newIndex[0]), cmp);
      //输入要查询的数,并调用函数进行查找
      printf("请输入您想要查找的数:\n");
      scanf("%d", &key);
      k = search(key, a);
      //输出查找的结果
      if (k>0)   {
        printf("查找成功!您要找的数在数组中的位置是:%d\n",k+1);
      }  else  {
        printf("查找失败!您要找的数不在数组中。\n");
      }
      return 0;
    }
    int search(int key, int a[]){
      int i, startValue;
      i = 0;
      while (i<3 && key>newIndex[i].key)   {     // 确定在哪个块中,遍历每个块,确定key在哪个块中
        i++;
      }
      if (i>=3)   {     //大于分得的块数,则返回0
        return -1;
      }
      startValue = newIndex[i].start; //startValue等于块范围的起始值
      while (startValue <= startValue+5 && a[startValue]!=key)
      {
        startValue++;
      }
      if (startValue>startValue+5)   {     //如果大于块范围的结束值,则说明没有要查找的数
        return -1;
      }
      return startValue;
    }
    运行结果:
    
    请输入您想要查找的数:
    22
    查找成功!您要找的数在数组中的位置是:7
    
    1. 但是索引查找,块间有序,块内可以无序。查找过程是:
      首先根据索引查到块,然后如果块内有序就可以二分查找,如果无序就只能顺序查找。如下图,要查找38:
      在这里插入图片描述
      现在索引表看,38>22,而38<48,得到这个块的首地址6,直接找到6号位,(块内可以无序)并且从6号位开始顺序查找,直到9号位也是38,查找成功。

    (2)二级索引

    当完全索引表中关键字分块有序存放时,可以为完全索引表建立一个二级索引表,在二级索引表中一个索引项对应完全索引表中的一个子表,它记录了相应子表中最大关键字以及该子表在数据区中的起始位置,这种索引被称为二级索引,如图 8-4所示。
    在这里插入图片描述

    1. 对二级索引结构进行查找时,一般分为二次查找。其过程是:
      先在二级索引表中按给定值k进行查找,以确定待查子表的序号i,使得序号为i-1的子表中的最大关键字<k<=序号为i的子表中的最大关键字。然后再在第i个子表中给定值查找关健字等于k的索引项。如果找到关键字等于k的索引项,则可以根据索引项内的地址直接从外存中读取相应的数据元素;否则表示查找失败。
    2. 二级索引表是按关键字有序的,且长度一般不太大,可以用折半查找,也可以顺序查找。
    3. 二级索引查找平均查找长度:
      (1)查找成功
      ASL(IndexSeq)=ASL(Index)+ASL(SubList)
      其中,ASL(Index)是在二级索引表中查找成功的平均查找长度,ASL(SubList)是在子表内查找成功的平均查找长度。
      设完全索引表的长度为n,分成均等的m个子表,每个子表中有k个对象,则m=⌈n/k⌉(向上取整)。
      在等概率的情况下,每个子表的查找概率为1/m,子表内各对象的查找概率为1/k。
      ①若二级索引表和子表都用顺序查找,则二级索引查找成功时的平均查找长度为:
      ASL(IndexSeq)=(n+k2)/(2k)+1
      由此可见,二级索引查找的平均查找长度不仅与完全表索引表的长度n有关,而且与每个子表中所含的索引项个数k有关。那么,在给定n的情况下,当k=n1/2时,ASL(IndexSeq)取极小值n1/2+1
      ②若对二级索引表采用折半查找、对子表用顺序查找,则二级索引查找成功时的平均查找长度为:
      ASL(IndexSeq)=ASL(Index)+ASL(SubList)~log2(1+n/k)+k/2

    结论

    查找方法比较

    n个元素顺序查找折半查找分块查找
    ASL最大最小两者之间;顺序查找+顺序查找ASL=(n+k2)/(2k)+1;折半查找+顺序查找ASL~log2(1+n/k)+k/2
    表结构有序表、无序表有序表分块有序表
    存储结构顺序存储结构、线性链表顺序存储结构顺序存储结构、线性链表(块可以链式存储,但是要知道块的首地址)

    8.3.2 倒排表

    1. 对包含有大量数据元素的数据表或文件进行查找时,最常用的方法是针对数据元素的主关键字建立索引表,用主关键字建立的索引叫作主索引,主索引表的每个索引项给出数据元素的关键字及其在数据表或文件中的存放地址。但在实际应用中有时需要针对其他属性进行查找。
      因此,除主关健字外,可以把一些在查找时经常用到的属性设定为次关键字,并以每一个属性作为次关键字建立次索引表,称之为倒排索引表
    2. 倒排索引表有链式单元式两种结构。

    (1)链式倒排索引表

    1. 在链式倒排索引表中,列出了作为次关键字属性的所有取值,并对每一个取值建立有序链表把所有具有相同属性值的主关键字按其递增的顺序或按其在主索引表中的存储地址巡增的顺序链接在一起
      因此,链式倒排索引表包拓三个部分:次关键字、链表长度和有序链表
      在这里插入图片描述
    2. 由于主关键宁技大小依次有序存放上表的长度确定,因此在静态链表中可省去指针域。
    3. 在链式倒排索引表中各个属性链表的长度大小不一,管理起来比较困难。

    (2)单元倒排索引表

    1. 为此引入单元式倒排索引表,在单元式倒排表中,索引项中不存放对象的存储地址,存放该对象所在硬件区域的标识。硬件区域可以是磁盘柱面、磁道或一个页块,以一次I/O操作能存取的存储空间作为硬件区域为最好。为使索引空间最小,在索引中标识这个硬件区域时可以使用一个能转换成地址的二进制数,整个次索引形成一个(二进制数的)位矩阵。
      因此,在单元式例排索引表的各个索引项中存放表示各外存区域是否存有相应数据元素的标识(以0或1表示)。于是,整个单元式倒排索引表将形成一个(二进制数的)位矩阵。
      在这里插入图片描述
    2. 查找时,将相关索引项的二进制位串行进行按位“与”运算,求得所查数据元素在外存区域的区号。
      例如,求计算机系的上海籍男生:
      在这里插入图片描述

    特点

    倒排的优缺点和正排的优缺点整好相反。
    所有正排的【优点】易维护;【缺点】搜索的耗时太长。
    倒排【缺点】在构建索引的时候较为耗时且维护成本较高;【优点】搜索耗时短(在处理复杂的多关键字查询时,可在倒排表中先完成查询的交、并等逻辑运算,得到结果后再对记录进行存取。这样不必对每个记录随机存取,把对记录的查询转换为地址集合的运算,从而提高查找速度)。

    展开全文
  • Lucene倒排索引简述 之倒排表

    千次阅读 2018-10-09 20:31:55
    本篇博客将继续剖析Lucene关于倒排索引实现有另一个核心内容,倒排表(Postings)。我一直觉得Postings内容相对而言是比较简单,虽然内容很多,但是Lucene的官方文档讲得也非常详细了。如果对Lucene文档上的描述文件...

    一、前言

    上一篇《Lucene倒排索引简述 之索引表》,已经对整个倒索引的结构进行大体介绍,并且详细介绍了索引表(TermsDictionary)的内容。同时还详细介绍了Lucene关于索引表的实现,相关文件结构详解,以及对索引表采用的数据结构进行剖析解读。

    本篇博客将继续剖析Lucene关于倒排索引实现有另一个核心内容,倒排表(Postings)。我一直觉得Postings内容相对而言是比较简单,虽然内容很多,但是Lucene的官方文档讲得也非常详细了。如果对Lucene文档上的描述文件结构的表达方式不太熟悉的话,个人觉得可以参考前面的图自行画出文件结构示意图,或者直接在网络搜索相关的图,只要能整出索引文件的结构示意图,那么理解起来就应该不会太困难。

    二、Postings编码

    开始之前先介解Lucene在Postings采用了两个关键的编码格式,PackedBlock和VIntBlock。PackedBlock是在Lucene4.0引入,带来向量化优化。

    1. VIntBlock

    VIntBlock是能够存储复合数据类型的数据结构,主要通过变长整型(Variable Integer)编码达到压缩的目的。此外VIntBlock还能够存储byte[],比如.pay用VIntBlock存储了payloads数据等。

    值得一提的是,VIntBlock可以存储变长数据结构,如.doc用它存储DocID和TermFreq时,由于在特定条件下(TermFreq=1),Lucene会省略TermFreq以提高空间占用率。我知道Lucene用一个VInt来表示DocID,VInt则用每个Byte左边第一个Bit来表示是否需要读取顺续到下个Byte。也就是说一个VInt有效位是28bit,这就说明VInt头部是有特殊含义的,因此Lucene只能在VInt最右边的一个bit下功夫。让VInt的右边第一Bit来表示是否有下个数据。

    具体用法会在介绍.doc文件格式时介绍。

    2. PackedBlock

    PackedBlock只能存储单一结构,整数数组(Integer/Long)。这里主要是介绍PackedInts,即是将一个int[]打包成一个Block。PackedBlock只能能够存储固定长度的数组(Lucene规定其长度为128个元素),它压缩方式是将每个元素截断为预算的长度(length,单位是bit)压缩的。所以当长度length不是8的倍数时,会出现一个byte被多个元素占用。

    PackedBlock需要把整个int[]的所有条目指定长度编码,所以PackedBlock只能选择int[]最大的数还来计算长度,否则会让大数失真。反过来,PackedBlock都选择64位,则会浪费空间,不能达到压缩的目的。

    Lucene预先编译了64个PackedFormat编码器和解码器,即针对Long以内的每种长度都数据都有自己的解码和编码器,以提高编解码的性能。

    PackedPosDeltaBlock与PackedDocDeltaBlock和PackedFreqBlock一样采用PackedInts结构,它能存储的信息实际上是很有限的,只能存储Int的数组。所以在PackedPosDeltaBlock的时候,只能存储position信息,在VIntBlock则会存储更多必要的信息,减少搜索时的IO操作。

    这也是为什么需要将DocId和TermFreq拆分成PackedDocDeltaBlock和PackedFreqBlock两个Block存储的原因了。

    定长是指PackedBlock限定了一个Block仅允许存储长度128的整型数组,而不是限定Block用多少个Bytes来存储编码后的结果。另外Block存储占用的大小,是按数组中最大那个数的有效bits长度来计算整个Block需要占用多大的Bytes数组的。也就是Block的每个数据的长度都是一样,都按最长bits的来算。

    比如:(我们定义一个函数,bit(num)用来计算num占用多少个bits)

    1. 数组中最大的是1,那么PackedBlock的长度仅是16Bytes。bit(1) * 128 / 8 = 16
    2. 数组中最大的是128,PackedBlock长度则是144个Bytes。bit(128) * 128 / 8 = 144
    3. 数组中最大的是520,PackedBlock则需要160Bytes。bit(520) * 128 / 8 = 160

    小结,PackedBlock相当于是实现了向量化优化,Lucene通常会将整个PackedBlock加载到内在,既可以减少IO操作数,又能提高解码的性能。相对而言VIntBlock则能够更丰富数据类型,比较适合存储少量数据。

    三、Postings文件结构说明

    进入正题,我们知道整个Postings被拆成三个文件分别存储,实际上它们之间相对也是比较独立的。基本所有的查询都会用.doc,且一般的Query也仅需要用到.doc文件就足够了;近似查询则需要用.pox;.pay则是用于Payloads搜索(关于这个之前写一篇博客《Solr 迟到的Payloads》,介绍了Payloads用法和场景)。

    1. Frequencies And Skip Data(.doc文件)

    在Lucene倒排索引中,只有.doc是Postings必要文件,即是它是不能被省略。除此之外的两个文件都是通过配置,然后将其省略的。那么.doc到底是存储哪些不可告人的秘密呢?直接上图,开始剖析吧!

    这里画得不够清晰,每个Term都有成对的TermFreqs和SkipData的。换言之,SkipData是为TermFreqs构建的跳表结构,所以它们是成对出现的。

    1.1. TermFreqs – Frequencies

    TermFreqs存储了Postings最核心的内容,DocID和TermFreqs。分别表示文档号和对应的词频,它们是一一对应的,Term出现在文档上,就会有Term在文档中出现次数(TermFreqs)。

    Lucene早期的版本还没有PackedBlock结构,所以DocID与TermFreq是以一个二元组的方式存储的。这个结构非常好,是因为它好理解,之所以好理解是因为它贴近我们的心中的预想。但实际上这个结构并不太准确,只不过我们先简单这么理解也无伤大雅。既然是想深入剖析,还是有必要还原真相的。

    TermFreqs采用的是混合存储,由Packed Blocks和VInt Blocks两种结构组成。由于PackedBlock是定长的,当前Lucene默认是128个Integers。所以在不满128的时候,Lucene则采用VIntBlocks结构还存储。需要注意的是当用Packed Blocks结构时,DocID和TermFreq是分开存储的,各自将128个数据写入到一个Block。

    当用VIntBlocks结构时,还是沿用旧版本的存储方式,即上面描述的二元组的方式存储。所以说,将DocID和TermFreq当成一条数据的说法是不完全正确的。

    在Lucene4.0之前的版本,还没有引入PackedBlock时,DocID和TermFreq确定完全是成对出现,当时只有VIntBlock一种结构。

    Lucene尽可能优先采用PackedBlocks,剩余部分(不足128部分)则用VIntBlocks存储。引入PackedBlock之后,PackedDocDeltaBlock跟PackedFreqBlock是成对的,所以它的写出来的示意图应该是如下:

    每个PackedBlock由一个PackedDocDeltaBlock和一个PackedFreqBlock构成,它们都采用PackedInts格式。

    例如,在同一个Segment里,某一个Term A在259个文档同一个字段出现,那么Term A就需要把这259个文档的文档编号和Term A在每个文档出现的频率一同记下来存储在.doc。此时,Lucene需要用到2个PackedBlocks和3个VIntBlocks来存储它们。

    VIntBlock结构相对而言就高级很多了,它能够以一种巧妙的方式存储复杂的多元组结构。在.doc,用VIntBlock存储DocID和TermFreqs,是二元组。后面将介绍的Positions则用VIntBlock存储了Postition、Payload和Offset多元组,
    byte[]和VInt多种数据类型。

    这里每一个PackedBlock结构都包含了一个PackedDocDeltaBlock和一个PackedFreqBlock,如果没有省略Frequencies(TermFreq)的话;如果用户配置了不存储词频(TermFreq)的话,此时一个PackedBlock仅含有一个PackedDocDeltaBlock。PackedFreqBlock(TermFreq)的存储方式跟PackedDocDeltaBlock(DocID)完全一致,包括后面要讲的pos/pay也都一样的。也都是使用Packed Block这种编码方式。

    在VIntBlock上如何存储DocDelta和TermFreq的呢,当设置为不存储TermFreq时,Lucene将所有DocDelta以Variable Integer的编码方式直接写文件上。

    但当DocDelta和TermFreq两者都存储时,官方文档给出一个比较完整且复杂的计算说明。反正是我觉得有点复杂,所以没有用直接官方的上说明,我们来点简单的。

    首先需要换算的原因是,Lucene做一个小优化,即是当TermFreq=1时,TermFreq将不被存储。那么原本DocDelta(DocID的增量)后面紧跟一个Frequencies的情况变得不再确定,我压根就不知道我读的DocDelta后面有没有TermFreq的信息。

    那么问题就变成怎么标记存储还是没有存储TermFreq,Lucene先把数值向左移动一位,然后用最右的一个Bit的标记是否存储TermFreq。最后右边的一个bit1表示没有存储,0作为有存储TermFreq。实际上这已经是Lucene的惯用手段了。

    左移一位,实际上等同于X2,当最后一个bit是0,此时是一定是偶数,表示后面还存 储了TermFreq;
    左移一位再+1,相当于偶数+1,那就是奇数,此时最后一个bit是1,表示TermFreq=1,所以后面没有存储TermFreq。

    这基本上就是官方文档上的大体意思了。

    DocFreq=1时,Lucene做一个叫Singletion(仅出现在一个文档)的优化,当时就没有TermFreq和SkipData。因为TermFreq就等同于TotalTermFreq(上篇文章介绍过,存储在.tim的FieldMetadata上)。

    1.2. Multi-level SkipList – SkipData

    SkipData是.doc文件核心部件之一,Lucene采用的是多层次跳表结构,首先我们先预热一下了解SkipList的逻辑结构图,最后剖析Lucene存储SkipList的物理结构图。

    跳表的原理非常简单,跳表其实就是一种可以进行二分查找的有序链表。跳表在原有的有序链表上面增加了多级索引,通过索引来实现快速查找。首先在最高级索引上查找最后一个小于当前查找元素的位置,然后再跳到次高级索引继续查找,直到跳到最底层为止,这时候以及十分接近要查找的元素的位置了(如果查找元素存在的话)。由于根据索引可以一次跳过多个元素,所以跳查找的查找速度也就变快了。 ——— 来自百度百科

    将搜索时耗时转嫁给索引时,空间换时间是索引的基本思想。为此Lucene为Postings构建SkipList
    ,并把按层级将它系列化存储。第一个SkipLevel是最高,拥有最少的索引数。

    易知Lucene是在索引时构建了SkipList,在Segment中 每个Term都有自己唯一的Postings,每个Postings都有需要构建一个SkipList。这三者是一一对应的。所以画出来结构图如下:

    除了第0层之外所有SkipLevel的每个跳表数据块(SkipDatum)会存储了指向下一个SkipLevel的指针。图中SkipChildLevelFPg带?的原因是在Level 0时,SkipDatum没有下一级可以记录。如果Postings有存储positions、payloads和offsets的话,在跳表数据块中也会记录它们的Block所有文件指针。

    也就是说,通过SkipList可以找到DocID和TermFreq之外,还能找到Positions、Payloads和Offsets这三部分信息。所以在搜索时,通过SkipList的可以快速定位Postings的所有相关信息。

    关于Lucene如何构建SkipList的诸多细节,Lucene规定SkipList的层级不超过10层。

    1. 第0层,SkipList为每个Block增加索引,所以VIntBlock不在SkipList上。
    2. 第9层,SkipList的第一个节点是在第89 (227)Block。(这个数确实有点大)
    3. 第n层,SkipList的第m个节点的位置是第 8 n ∗ m 8^n * m 8nm个Block。

    跳表的第一层是最密的,越高层越稀疏。按层级从低到高依次系列化为写入.doc的SkipData部分。换言之,SkipDatum的个数越来越多,SkipLevelLength会越来越大。

    SkipLevelLength说明当前层次Skip系列化之后的长度,SkipLevel是包含该层的所有节点的数据SkipDatum。SkipDatum包含四部分信息,doc_id和term_freq、positions、payloads、以及下一层开始的位置(是第N层指向第N-1层的前一个索引)。

    SkipList主要是搜索时的优化,主要是减少集合间取交集时需要比较的次数,比如在Query被分词器分成多个关键词时,搜索结果需要同时满足这些关键词的。即是需要将每个Term对应的DocId集合进行析取操作,通过跳表能够有效有减少比较的次数。

    2. Postitions(.pos文件)

    .pos文件存储所有Terms出现文档中的位置信息。为更好的搜索性能,Lucene还在VIntBlock上存储了部分payloads和offsets的信息。实际上因为只有VIntBlock才有能力来存储复杂的数据结构,而PackedBlock是不具备这样的能力的。具体请参考下面的示意图:

    Lucene把同一个Term的所有position信息存储在同一个TermPositions上,并没有逻辑或者物理上的划分的。将在一个文档里出现的所有位置信息,按出现的先后顺序依次写入。
    关键在于,position与TermFreq并不是在一维度上,TermFreq的数值就是position的个数。也就是通过.pos文件,无法知道每个position的具体含义的,PostingsReader通过.doc文件的DocID和TermFreq信息才能算出Postition的是在哪个文档上的那个位置的。

    3. Payloads and Offsets(.pay文件)

    Payloads,可以理解为Term的附加信息,它实际上是跟Term成对出现的,类似于Map。在用法上也是如此,Payloads的信息需要用byte数组存储,所以在TermPayloads并不能用PackedBlock结构来存储。但是TermOffsets是由2个int来表示Offet的开始位置和长度的,即是能将它们拆成两个等size的int[],故可以用PackedBlock存储。故有如下图:

    四、总结

    开篇先学习了Lucene用于存储Postings的两种结构,或者说编码方式,PackedBlock和VIntBlock。PackedBlock是Lucene4.0引用的,它就是int[],给Postings向量化优化。除之外,还有一原著民VIntBlock,也是一种很巧妙且优雅的结构,能存储复杂的类型。

    而后,在介绍.doc文件格式的同时,又对上面的两大结构反复剖析。个人认为了解这两个结构之后,整个postings的理解应该不成问题。并且剖析了.doc文件上采用的SkipList数据结构,主要是搜索时集合间AND操作上的一个优化。所以在postings其它两个文件格式,仅用非常短的篇幅介绍。

    Lucene倒排索引部分内容到这里全部结束,其它很多优雅的设计和巧妙的结构,其中蕴含的Lucene之美,值得我们反复研读。

    展开全文
  • 一文了解倒排表

    千次阅读 2020-09-15 08:43:49
    倒排表 到排表是搜索引擎的核心架构 假设我们爬取了4个文档,里面的内容如下 基于4个文档,写出我们的词库 [我们,今天,运动,昨天,上,课,什么] 统计词库中的每个单词出现在哪些文档中,显然 我们 出现在[doc1,...
  • 针对当前在最频繁项集挖掘方面的不足,将集合论引入倒排表以对其进行改进,然后以此为基础提出了几个命题和推论,并结合最小支持度阈值动态调整策略,提出了一个基于改进的倒排表和集合理论的最频繁项集挖掘算法,...
  • 倒排表

    2020-03-26 12:01:42
  • NLP——倒排表

    2020-05-05 17:36:47
    倒排表 倒排表的核心思路是要知道某一个单词出现在哪一个文档中。 现在有一个知识库和词典库,词典库有所有出现的词,例如词典库是【我们,今天,运动,昨天,上,课】。 对于下面四个文档: doc1:我们今天运动; ...
  • 针对当前在最频繁项集挖掘方面的不足, 将集合论引入倒排表以对其进行改进, 然后以此为基础提出了几个命题和推论, 并结合最小支持度阈值动态调整策略, 提出了一个基于改进的倒排表和集合理论的最频繁项集挖掘算法, ...
  • 信息检索,倒排记录的合并算法实现,用户通过提示输入两个倒排记录,系统自动实现倒排记录的合并,并将合并结果输出。
  • 参考资料-004开业前营运工作倒排表.zip
  • 问-答系统简单的问答系统实现,利用TF-IDF,词向量,倒排表等方法数据集综合类中文词库.xlsx:包含了中文词,当做字典来用(用作PART1) dev-v2.0.json:这个数据包含了问题和答案的对,但是以JSON格式存在,需要...
  • 通过倒排表,我们无需在计算相似度时遍历库的所有问题,只需遍历包含用户问题关键词的问题即可。 result={} for i in range(len(file_txt)): left, rights = i,file_txt.iloc[i]['cut_review'].split() for right ...
  • 基于改进倒排表和集合论的TOP-N最频繁项集挖掘算法
  • 倒排索引 和 倒排表

    千次阅读 2015-06-09 14:45:18
    为什么我们要说倒排索引呢?   因为倒排索引是目前 搜索引擎公司最对搜索引擎最常用的存储方式.也是搜索引擎的核心内容!  在搜索引擎实际的引用之中,有时需要按照关键字的某些值查找记录,所以我们是按照关键字...
  • 倒排索引

    2016-02-09 01:07:59
    倒排索引的实现。 一个文件含有几个文件的名字,打开这个文件之后读其他文件的内容,将内容出现的文件号输出。
  • 所有索引项的集合构成该文件的索引。保存在磁盘上的索引又称索引文件。索引技术是组织大型数据库以及磁盘文件的一种重要技术。索引按照结构可以分为线性索引,树形索引和多级索引。所谓线性索引就是将索引项集合...
  • 倒排索引 倒排表

    2019-09-22 01:43:09
    为什么我们要说倒排索引呢? 因为倒排索引是目前 搜索引擎公司最对搜索引擎最常用的存储方式.也是搜索引擎的核心内容!在搜索引擎实际的引用之中,有时需要按照关键字的某些值查找记录,...那我想问下 什么是倒排表呢?...
  • 关于建立倒排表搜索的一点心得

    千次阅读 2015-05-03 14:36:53
    这几天刚刚用C写了一个关于倒排表搜索词条的程序,程序的效果还是可以,但是当词条数量增加后,算法的效率会大大降低。这里将对算法进行简述,并总结得失。一, 数据结构 将有两个文件作为索引的可持久化被保存。第...
  • 【简单理解】搜索引擎检索-倒排表(倒排索引) 简单介绍倒排索引 倒排索引(Inverted index),也常被称为反向索引、置入档案或反向档案,是一种索引方法,被用来存储在全文搜索下某个单词在一个文档或者一组文档...
  • 今天小编就为大家分享一篇python 实现倒排索引的方法,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧
  • 2.3 建立倒排表文件(引用刘鹏hadoop实战)  在分析完分词,Rank值得计算等问题的解决方案之后,就可以设计相应的MapReduce算法,来建立倒排表,计算,保存Rank和Position等附属信息。  首先定义倒排表存储...
  • 关于倒排索引的总结

    千次阅读 2019-12-18 17:05:54
    最近在研究elasticsearch的技术栈 ,发现ES底层是基于luence技术进行检索,检索的原理是倒排索引。那么什么是倒排索引呢?在知乎上看到一个讲解elasticsearch的倒排索引的帖子。 链接是:...
  • 小程序描述:输入两个倒排记录,求两个倒排记录的交集 跳表指针合并算法伪代码如下所示:   功能描述: ①运行程序,看到提示“请输入词项word1:”,输入某个倒排记录的词项。 ②运行程序,看到提示“请...
  • Frame Of Reference压缩算法对于倒排表来说效果很好,但对于需要存储在内存中的Filter缓存等不太合适,两者之间有很多不同之处:倒排表存储在磁盘,针对每个词都需要进行编码,而Filter等内存缓存只会存储那些经常...
  • 推荐系统实战:用户倒排索引的构建
  • ElasticSearch基础:从倒排索引说起,快速认知ES

    千次阅读 多人点赞 2021-06-27 10:01:48
    倒排表(Post list):一个文档通常由多个词组成,倒排表记录的是某个词在哪些文档里出现过及出现的位置。每个记录称为一个倒排项(Posting),倒排表记录的不单单是文档编号,还记录了词频等信息。 倒排文件...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 57,692
精华内容 23,076
关键字:

倒排表

友情链接: 人工势场法.zip