精华内容
下载资源
问答
  • 查找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. 查找时,将相关索引项的二进制位串行进行按位“与”运算,求得所查数据元素在外存区域的区号。
      例如,求计算机系的上海籍男生:
      在这里插入图片描述

    特点

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

    展开全文
  • 【简单理解】搜索引擎检索-倒排表(倒排索引) 简单介绍倒排索引 倒排索引(Inverted index),也常被称为反向索引、置入档案或反向档案,是一种索引方法,被用来存储在全文搜索下某个单词在一个文档或者一组文档...

    【简单理解】搜索引擎检索-倒排表(倒排索引)

    简单介绍倒排索引

           倒排索引(Inverted index),也常被称为反向索引、置入档案或反向档案,是一种索引方法,被用来存储在全文搜索下某个单词在一个文档或者一组文档中的存储位置的映射。它是文档检索系统中最常用的数据结构。

    常见应用:搜索引擎、问答系统、对话系统。

    图说倒排索引

            这里首先引出一个例子来详细介绍倒排索引的思想和实现。

    内容简化

    假设用户有个搜索query:“苹果手机2020发布会时间”。百度的搜索结果如下:

    现在我们把这个问题具体化。我们除了有要查询的query:“苹果手机2020发布会时间”。还有被查询的网页数据库。这里我们做个简化,假设我们的网页数据库内容只有如下4条:

    网页1:

    2020苹果手机第一场发布会时间确定
    

    网页2:

    苹果手机2020出什么机型

    网页3:

    2020新机发布会时间

    网页4:

    苹果在2020将推出四款新iPhone

    关键词匹配

    为了选取最理想的查询结果,最容易想到的方法就是关键词匹配了,简单的来说,就是网页中包含查询的关键词越多,网页和查询query的相关度也就越大。
    在做关键词查询前,一般文本会先进行预处理。这里的预处理主要包括去停用词和分词。
    去停用词
    去除和查询不相关的内容,比如本例子中的标点符号。在其他场景中,除了标点符号也会去除一些特别的字或词。
    分词
    分词主要目的是将句子切长短语或关键字,这样才利于查询匹配。比如“苹果手机2020发布会时间”可以分词成:

    苹果手机/2020/发布会/时间

    当然网页也需要这样进行分词:
    网页1:

    2020/苹果手机/第一场/发布会/时间/确定

    网页2:

    苹果手机/2020/出什么/机型

    网页3:

    2020/新机/发布会/时间

    网页4:

    苹果/在/2020/将/推出/四款/新/iPhone/

    分词是一项专门的技术,在实际工程中可以至今借助工具来完成,比如jieba分词
    分词处理后,我们用查询query中的关键词在网页数据库中进行关键词匹配,并统计匹配数目:

    网页序号 匹配关键词 匹配个数
    网页1 2020,苹果手机,发布会,时间 4
    网页2 苹果手机,2020 2
    网页3 2020,发布会,时间 3
    网页4 2020 1

    从上述表格中容易确定,网页序号1就是和查询query最匹配的网页。

    倒排索引

    仔细考虑上面的关键词查询过程,会发现这种方法有个很大的效率问题:我们的例子中只有4个待查询的网页,而实际的互联网世界的网页数目是非常巨大的。假设互联网世界的网页数据为N,那么使用关键词查询的时间复杂度就是O(N),显然,这样的时间复杂度还是太大了,而倒排索引就很好的优化了这个问题。
    从倒排索引这个名字很容易联想出它的实现,关键就是“倒排”的“索引”。在前面的讲解中,我们的索引(key)是网页,内容(value)是关键字。倒排索引就是反过来:内容关键字作为索引(key),所在网页作为内容(value)。前面的表格就可以改写成,

    关键词 包含关键词的网页
    苹果手机 网页1,网页2
    2020 网页1,网页2,网页3,网页4
    发布会 网页1,网页3
    时间 网页1,网页3

    通过上面的表格,很明显网页1是包含最多关键词的网页,也是和查询query相关度最高的网页。采用倒排索引的方法,搜索的时间复杂度得到了明显的降低。

    展开全文
  • 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个节点的位置是第8nm8^n * m个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之美,值得我们反复研读。

    展开全文
  • 2.3 建立倒排表文件(引用刘鹏hadoop实战)  在分析完分词,Rank值得计算等问题的解决方案之后,就可以设计相应的MapReduce算法,来建立倒排表,计算,保存Rank和Position等附属信息。  首先定义倒排表存储...
    2.3 建立倒排表文件(下面原理引用刘鹏hadoop实战)
        在分析完分词,Rank值得计算等问题的解决方案之后,就可以设计相应的MapReduce算法,来建立倒排表,计算,保存Rank和Position等附属信息。
        首先定义倒排表存储信息格式,这是算法的输出目标,也是查询程序从倒排表中获取信息的接口。本系统倒排表的存储格式定义如下:
        (1)倒排表文件(INVERTED_INDEX_FILE)有若干索引词记录组成,每个索引词记录(TERM_RECORD)是有一个索引词(TERM)和包含该词的所有帖子的信息(MULTI_INFO)组成,其中TERM和MULTI_INFO之间用空格隔开。索引词记录按照顺序追加的方式存放,之间用换行符分隔,例如:
        TERM+'\t'+MULTI_INFO+'\r\n'
        (2)在每条索引词记录中,TERM是用分词软件切分出来的一个词。而MULTI_INFO则由多个单条帖子信息(SINGLE_INFO)组成。其中SINGLE_INFO和SINGLE_INFO之间用分号隔开。表示如下:
        MULTI_INFO=SINGLE_INFO1;SINGLE_INFO2;……;SINGLE_INFONn
        (3)单条帖子信息SINGLE_INFO,由帖子ID(DID),索引词语该帖子的Rank值(Rank),索引词在该帖子中出现的位置(POSITIONS)组成,其间用冒号隔开。表示格式如下:
        SINGLE_INFO=DID:RANK:POSITIONS
        (4)SINGLE_INFO中的DID是唯一指定某个帖子的值。本系统选择原文件中帖子行首在原文件中的偏移量(offset)作为帖子ID(DID)。每个帖子的源文件中有唯一的偏移量,且给定一个偏移量offset后,可以通过在源文件中定位offset,并执行readline操作(帖子和帖子之间用换行符间隔的),即可读出这条帖子的信息。
        (5)SINGLE_INFO中的RANK用一个浮点类型的数值表示。
        (6)SINGLE_INFO中的POSITIONS由多个单个位置信息(POSITIONS)组成,之间用百分号隔开。表示格式如下:
        POSITIONS=POSITIONS1%POSITIONS2%……%POSITIONSn
        (7)对于单个位置信息(POSITION),其有标题记标识(ISTITLE),起始位置(START),结束为止(END)组成。之间用竖线隔开,表示格式如下:
        POSITIONS=ISTITLE|START|END
        下面给出一个索引词记录的存储实例
        黑莓    4852292:162.6:1|2|4%0|804|806;42910773:106.26:0|456|458%0|560|562
        该实例说明关键词“黑莓”在ID号为“48522292”和“42910773”的两个帖子中出现。在"48522292"中出现了两次,第一次的位置是在标题中,具体出现在第2-4位;第二次出现在正文中,具体出现在第804-806;该词相对于这个帖子的Rank值为162.6
        由于倒排表的信息来自于每条帖子,这些帖子可以并行地被处理,因此设计了基于MapReduce的并行算法来建立倒排表。算法描述如下

    图1-1 MapReduce建立倒排表的流程图
        
    建立倒排表的算法流程如下:
        (1)采用Hadoop默认的文件分给方式,将源文件分成若干个小文件,每个Mapper节点一次只处理一个小文件。
        (2)在Map阶段,对于每个小文件采用按行切分的方法输入。每个map函数的输入<key,value>分别是offset和line.其中offset作为key是指输出的这一行的行首相对于整个源文件的偏移量,也就是帖子的DID;line作为value是指输入的一行,在本系统也就是一条帖子,可以从中切分出帖子的TITLE和CONTENT。
        (3)对于输入的每条line(一条帖子),在map函数中切分出TITLE和CONTENT中的每个词(TERM)。对于每个词,根据其出现的情况计算出RANK和POSITIONS,将这些信息封装成一个SINGLE_INFO.输出阶段要发送k次(k是切分出来的TERM的个数),每次发射的key和value是TERM及其对应的SINGLE_INFO。
        (4)经过分区(Partion)阶段,从Map发射出来具有相同的key(TERM)的<key,value>对会分别发到同一个Reducer端,每个reduce函数会处理具有相同TERM的<key,value>对。
        (5)输入到每个reduce函数的相同TERM对应的SINGLE_INFO的数目就是包含这个TERM的帖子的数目,记为num.根据前面介绍的IT-IDF算法,在reduce函数里更新每个SINGLE_INFO里面的Rank值,更新的的公式为RANK=RANK/num.更新后的RANK值就是TERM相对于某个帖子的最终RANK值。
        核心代码如下:
     public static class InvertedIndexerMapper extends
                Mapper<LongWritable, Text, Text, RecordWritable> {
            public final static Text WORD = new Text();
            public final static RecordWritable RECORD = new RecordWritable();
            public final static Gson gson = new Gson();
            @Override
            protected void map(LongWritable key, Text value, Context context)
                    throws IOException, InterruptedException {
                BBS bbs = gson.fromJson(value.toString(), BBS.class);
                HashMap<String, RankPosition> map = new HashMap<String, RankPosition>();
                StringReader title = new StringReader(bbs.getTitle());
                IKSegmenter ik_title = new IKSegmenter(title, true);
                Lexeme lex_title = new Lexeme(0, 0, 0, 0);
                while ((lex_title = (ik_title.next())) != null) {
                    if (lex_title.getLength() >= 2) {
                        String token = lex_title.getLexemeText();
                        int start = lex_title.getBeginPosition();
                        int end = lex_title.getEndPosition();
                        if (!map.containsKey(token)) {
                            map.put(token, new RankPosition(5, true, start, end));
                        } else {
                            map.put(token, map.get(token).add(5, true, start, end));
                        }
                    }
                }
                StringReader content = new StringReader(bbs.getContent());
                IKSegmenter ik_content = new IKSegmenter(content, true);
                Lexeme lex_content = new Lexeme(0, 0, 0, 0);
                while ((lex_content = ik_content.next()) != null) {
                    if (lex_content.getLength() >= 2) {
                        String token = lex_content.getLexemeText();
                        int start = lex_content.getBeginPosition();
                        int end = lex_content.getEndPosition();
                        if (!map.containsKey(token)) {
                            map.put(token, new RankPosition(1, false, start, end));
                        } else {
                            map.put(token, map.get(token).add(1, false, start, end));
                        }
                    }
                }
                EmitMapValue(map, key.get(), context);
                map.clear();
            }
            public void EmitMapValue(HashMap<String, RankPosition> map,
                    long DID, Context context) throws IOException,
                    InterruptedException {
                for (Map.Entry<String, RankPosition> entry : map.entrySet()) {
                    WORD.set(entry.getKey());
                    RECORD.set(DID, entry.getValue());
                    context.write(WORD, RECORD);
                }
            }
        }
        public static class InvertedIndexerReducer extends
                Reducer<Text, RecordWritable, Text, Text> {
            private final static Text OUT=new Text();
            @Override
            protected void reduce(Text key, Iterable<RecordWritable> values,
                    Context context) throws IOException, InterruptedException {
                StringBuilder info = new StringBuilder();
                List<RecordWritable> list=new ArrayList<RecordWritable>();
               
                while(values.iterator().hasNext()){
                    RecordWritable record=values.iterator().next();
                    RecordWritable recordWritable=new RecordWritable(record.getDID(), record.getRank(), record.getPositions());
                    list.add(recordWritable);
                }
                int sum=list.size();
                for(int i=0;i<list.size();i++){
                    info.append(resetFinalRank(list.get(i), sum)+";");
                }
                OUT.set(info.toString());
                context.write(key,OUT);
            }
            public String resetFinalRank(RecordWritable value, long num) {
                value.setRank((float) (value.getRank().get() / num));
                return value.toString();
            }
        }


    具体实现代码可以查看:
    参考文献:
    1.刘鹏,hadoop实战,电子工业出版社,2011.9
    展开全文
  • 关于建立倒排表搜索的一点心得

    千次阅读 2015-05-03 14:36:53
    这几天刚刚用C写了一个关于倒排表搜索词条的程序,程序的效果还是可以,但是当词条数量增加后,算法的效率会大大降低。这里将对算法进行简述,并总结得失。一, 数据结构 将有两个文件作为索引的可持久化被保存。第...
  • 理解倒排表

    2009-04-02 14:29:00
    这次查看倒排表,突然想起来,08年春,我就查过是咋回事了,估计是当时理解的不够透彻,再加上年老体衰,竟然怎么也想不顺了。 下面举个例子: 案例1:普通文档存在形式: PPT (从头看起.....)==> keywords1,keywords...
  • 倒排索引 和 倒排表

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

    2012-11-11 21:23:43
    为什么我们要说倒排索引呢?   因为倒排索引是目前 搜索引擎公司最对... 在搜索引擎实际的引用之中,有时需要按照关键字的某些值查找记录,所以我们是按照关键字建立索引,这个索引我们就称之为: 倒排索引, 而带
  • Lucene 合并倒排表算法之并集

    千次阅读 2010-09-25 13:39:00
    本文继续对倒排表求并集的算法:lucene处理交集时采用的数据结构是一个倒排表的数组,数组的元素是一个个的迭代器来表现每个倒排表.而在求并集的时候则是采用了队列数据结构.在DisjunctionSumScorer类的构造函数中对...
  • 倒排表交集的计算

    千次阅读 2009-05-16 23:43:00
    1. 对倒排表进行排序2. 对排序后的倒排表进行求交集的时间复杂度是o(n + m)3. 两两合并和多路同时合并的效果差不多4.可以采用跳表来加速合并过程,所谓跳表即是 因此在查询时可以根据快表进行跳转,但快表的长度...
  • 一文了解倒排表

    2020-09-15 08:43:49
    倒排表 到排表是搜索引擎的核心架构 假设我们爬取了4个文档,里面的内容如下 基于4个文档,写出我们的词库 [我们,今天,运动,昨天,上,课,什么] 统计词库中的每个单词出现在哪些文档中,显然 我们 出现在[doc1,...
  • Lucene 合并倒排表算法之交集

    千次阅读 2010-09-25 10:16:00
    lucene在搜索时,需要对多个倒排表进行merge操作:计算两者间的交集 并集和差集.
  • Frame Of Reference压缩算法对于倒排表来说效果很好,但对于需要存储在内存中的Filter缓存等不太合适,两者之间有很多不同之处:倒排表存储在磁盘,针对每个词都需要进行编码,而Filter等内存缓存只会存储那些经常...
  • Lucene倒排表原理

    千次阅读 2010-08-14 10:53:00
    Lucene倒排索引原理  Lucene是一个高性能的java全文检索工具包,它使用的是倒排文件索引结构。该结构及相应的生成算法如下: <br /> 0)设有两篇文章1和2  文章1的内容为:Tom lives in ...
  • 所有索引项的集合构成该文件的索引。保存在磁盘上的索引又称索引文件。索引技术是组织大型数据库以及磁盘文件的一种重要技术。索引按照结构可以分为线性索引,树形索引和多级索引。所谓线性索引就是将索引项集合...
  • 通过倒排表,我们无需在计算相似度时遍历库的所有问题,只需遍历包含用户问题关键词的问题即可。 result={} for i in range(len(file_txt)): left, rights = i,file_txt.iloc[i]['cut_review'].split() for right ...
  • 倒排文件

    千次阅读 2017-07-20 08:12:53
    1.倒排文件的组织方式和特点   倒排文件和多重表文件不同。...倒排表的主要优点是:在处理复杂的多关键字查询时,可在倒排表中先完成查询的交、并等逻辑运算,得到结果后再对记录进行存取。这样不必对每
  • 倒排索引

    2017-08-26 12:27:33
    对于一个单词,它的倒排表的内容为出现这个单词的文档编号。 输入第一行包含一个数N,1 接下来N行,每行第一个数ci,表示第i个文档的单词数。接下来跟着ci个用空格隔开的单词,表示第i个文档包含的单词。文

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 49,385
精华内容 19,754
关键字:

倒排表