文档章节

Lucene 4.X 倒排索引原理与实现: (3) Term Dictionary和Index文件 (FST详细解析)

火力全開
 火力全開
发布于 2016/10/06 01:14
字数 3138
阅读 72
收藏 1
点赞 0
评论 0

我们来看最复杂的部分,就是Term Dictionary和Term Index文件,Term Dictionary文件的后缀名为tim,Term Index文件的后缀名是tip,格式如图所示。

image

Term Dictionary文件首先是一个Header,接下来是PostingsHeader,这两个的格式一致,但是保存的是不同的信息。SkipInterval是跳跃表的跳的幅度,MaxSkipLevels是跳跃表的层数,SkipMinimun是应用跳跃表的最小倒排表长度,接下来就是Term的部分了。

在tim文件中,Term是分成Block进行保存的,如何将Term进行分块,则需要和tip文件配合。Term Index文件对于每一个Field都保存一个FSTIndex来帮助快速定位tim文件中属于这个Field的Term的位置,由于FSTIndex的长度不同,为了快速定位某个Field的位置,则应用指针列表规则,为每一个Field保存了指向这个Field的FSTIndex的指针。

这里比较令人困惑的一点就是,FST是什么,如何利用他来分块呢?

FST全程是Finite State Transducers,是一个带输出的有限状态机,看过前面有限状态机规则的可以知道,有限状态机逻辑上来讲就是一颗树,就像图3-71中的那棵树,从初始状态输入字符a到达状态a,输入字符b到达状态b,输入字符d到达状态d,不同的是状态d有输出,所谓的输出就是一个指针,指向tim文件中的位置。

Tim文件中Term的分块就是按照FST来的,图3-71中,Block 0中的所有的Term都是以abd为前缀的,Block 1中所有的Term都是以abe为前缀的。每一个Block都有一个Block Header,里面指明这个Block包含几个Term,假设个数为N,Suffix里面包含了N个后缀,比如Block 0中包含Term “abdi”和”abdj”,则这里面保存”i”和”j”。Stats里面包含了N个统计信息,每个统计信息包含docFreq和totalTermFreq。Metadata里面包含了指向倒排表文件frq和prx文件的指针。

Tim和tip文件的写入是由org.apache.lucene.codecs.BlockTreeTermsWriter来负责的,在它的构造函数中,生成了两个OutputStream,并且写入除了Block和FSTIndex之外的所有信息。

image

Lucene40PostingsWriter的start函数如下:

image

image

下面咱们具体讨论,Term如何分块,Block如何写入,FSTIndex如何构造。

我们首先通过一个简单的例子,来看一下一个普通的FST是如何构造的,Lucene的文档里面给了类似下面这样一个例子。

image

这里InputValues是构造FST的输入,是根据这些字符串,构造出图3-71中的那棵树。

OutputValue是有限状态机的输出,由于在实际应用中,输出是一个指向tim文件的一个指针,一般是byte[]类型,所以我们也在这里弄了三个byte[]作为输出。

Builder就是有限状态机的构造器,它支持多种输出类型,我们这里用byte[]作为输出,所以输出类型我们选择BytesRef,这是对byte[]的一个封装。

下一步就是用Builder的add函数将输入和输出关联起来,由于builder的输入必须是IntsRef类型,所以需要从字符串转换成为IntsRef类型,输出也要将byte[]封装为BytesRef。

Builder的finish函数真正构造一个FST,在内存中形成一个二进制结构,通过它可以通过输入,快速查询输出,例如程序中的给出输入”acf”就能得到输出[5 6]。

从表面现象来看,我们甚至可以决定FST就是一个hash map,给出输入,得到输出。这就满足了作为Term Dictionary的要求,给出一个字符串,我马上能找到倒排表的位置。

Builder里面一个很重要的成员变量UnCompiledNode<T>[] frontier,在FST的构造过程中,它维护整棵FST树,其中里面直接保存的是UnCompiledNode,是当前添加的字符串所形成的状态节点,而前面添加的字符串形成的状态节点通过指针相互引用。

Builder.add函数主要包括四个部分:

image

当第一个字符串abd加入之后,frontier的结构如图3-72所示,图中蓝色的节点都是。

image

当新的字符串abe之后,首先(1)找出公共前缀ab,则prefixLenPlus1=3。然后调(2)用freezeTail将尾节点Sd进行冰封。为什么要进行冰封(一个形象的说法)呢?因为Sd节点不会再改变了。在实际应用中,字符串都是按照字母顺序依次处理的,上一次的字符串是abd,下一个字符串可能是abdm,再下一个字符串可能是abdn,这都会导致Sd这个节点的变化。然而当abe出现后,说明abd*都不可能出现了,状态Sd也不可能再有新的子节点了,所以Sd也就确定下来了,需要冰封。那么Sb节点要不要冰封呢?当然不行了,因为这次来了abe,下次还可能有abf, abg等等新的Sb的子节点出现,这就是为什么要计算公共前缀了,公共前缀之后的状态节点都是可以冰封的了,而这些冰封的节点都从尾部开始,所以这一步的函数叫freezeTail。

freezeTail的实现如下:

image

freezeTail主要有两个分支,在Builder构造的时候,用户可以传进自己的freezeTail,如果用户指定了,则调用它的freeze函数,如果没有指定,则执行else部分默认的行为。在这里,我们使用默认行为,在后面的代码分析中,我们还能看到使用自己的freezeTail的情况。

默认行为中,从尾部到公共前缀节点,对于每个状态节点,调用compileNode函数。在这之前,frontier里面保存的都是UnCompiledNode,经过compileNode函数后,就变成了CompiledNode,并从frontier摘下来,parent.replaceLast函数将父节点的指针指向新的CompiledNode。所谓compile过程,就是将内存中的数据结构变成二进制。

compileNode最终调用org.apache.lucene.util.fst.FST.addNode(UnCompiledNode<T>),代码如下:

image

image

然后(3)将新的input添加到frontier之后,变成如图3-73的数据结构。

image

依次类推,当添加acf之后,frontier变成如下的数据结构。

image

最后调用Builder的finish函数生成FST,代码如下:

image

image

形成的二进制数组如图3-75所示,由于有内容翻转,所以解析的时候需要从右向左解析。

image

了解了最基本的FST的原理之后,让我们来一步一步通过代码,了解tim和tip文件的block和FSTIndex是如何生成的。

我们以下图3-76为例子。默认情况下,BlockTreeTermsWriter有两个静态变量,DEFAULT_MIN_BLOCK_SIZE=25,DEFAULT_MAX_BLOCK_SIZE=48,MIN的意思是当某个状态节点的子节点个数超过25个的时候,可以写成一个Block,MAX的意思是当个数超过48的时候,则写成多个Block,多个Block构成一个层级Block。为了能够清晰的解析代码,我们设DEFAULT_MIN_BLOCK_SIZE=2,DEFAULT_MAX_BLOCK_SIZE=4。我们仅仅添加一篇文档,里面的Term依次为 abc abdf abdg abdh abei abej abek abel abem aben。所形成的状态树如图所示,根据MIN和MAX的设置,f, g, h会写成一个Block,i, j, k, l, m, n写成一个层级Block,c, d, e写成一个Block。我们之所以把从a到n的十进制和十六进制列在这里,是因为在eclipse中,有时候字符显示的是十进制,有时候是十六进制,当看到这些数值的时候,知道是这些字符即可。

image

写tim和tip文件的过程纷繁复杂,下面的流程图3-77作为一个线索

image

每来一个新的Term,都调用finishTerm。

image

image

finishTerm的blockBuilder是没有output的,这个blockBuilder是用来进行Term分块的,而不是用来生成FSTIndex的。blockBuilder.add函数的流程和上面的叙述过的FST基本原理中的过程基本一致,不同的是blockBuilder是被用户指定了freezeTail的,为org.apache.lucene.codecs.BlockTreeTermsWriter.TermsWriter.FindBlocks,所以freezeTail调用的是FindBlocks.freeze函数。这个freeze函数仅仅处理子节点的个数大于min的节点,调用writeBlocks函数将子节点写成block,对于不满足这个条件的节点,仅仅从frontier上摘下来,不做其他操作。

在整个过程中,维护两个成员变量,一个是List<PendingEntry> pending保存尚未处理的Term或者block,对于Term,里面保存这个Term的text,docFreq,totalTermFreq信息。另一个是pendingTerms,保存尚未处理的Term的freqStart和proxStart信息。

当加入abc,abdf,abdg,abdh之后,frontier成为如下的结构,在这个过程FindBlock.freeze什么都不做。这个时候的pending和pendingTerms也如图所示。

image

加入abei的时候,对Sd进行freeze的时候,发现Sd的出度为3,大于min,则开始调用BlockTreeTermsWriter.TermsWriter.writeBlocks(IntsRef, int, int)函数。

image

由于出度小于max,所以写成一个non floor的block。

写入一个Block的函数如下:

image

image

image

对于每一个写成的block,都要为这个block生成一个FSTIndex,这个过程由函数BlockTreeTermsWriter.PendingBlock.compileIndex实现。

image

image

Block也写入了,FSTIndex也生成了,这个时候frontier,pending和pendingTerms的结果如下图所示。

image

这里需要解释一下的BLOCK:abd的FSTIndex里面的映射关系[-38,2]是如何得出来的?这是由下面这个函数计算出来的。fp=86, hasTerm=true, isFloor=false,则二进制位101011010,表示成为VInt为11011010, 00000010,为[-38,2],其实-38是补码。

image

接下来添加abei, abej, abek, abel, abem, aben之后,这个时候frontier,pending和pendingTerms的结果如下图3-80所示。

image

当所有的Term添加完毕后,BlockTreeTermsWriter.TermsWriter.finish被调用。

image

image

调用freezeTail(0)的时候,还是调用FindBlocks.freeze函数,在freeze状态Se的时候,出度为6>min,所以调用writeBlocks,由于6>max,因而写入floor block。

image

image

image

写入firstBlock和floorBlocks的函数还是上面写non floor block时调用的writeBlock函数,下面列出一些主要的变量的值。

image

写入了层级block并且生成FSTIndex之后,frontier,pending和pendingTerms的结果如下图所示。

image

这里需要解释的是[-77,3,1,107,33]代表的什么呢?首先abe指向的是层级Block,其中firstBlock的起始地址为108,fp=108, hasTerm=true, isFloor=true,则二进制为110110011,表示成为VInt为 [10110011, 00000011],为[-77,3],接下来是floorblock信息。

在函数BlockTreeTermsWriter.PendingBlock.compileIndex中,有这样一段:

image

接着写入floorBlock的个数,为1。接着写这个floorBlock的首字符k(107)。最后写floorBlock的首地址和firstBlock的首地址的差,sub.fp=124, fp=108, sub.hasTerms=true,所以为33。所以[abe]的output为[-77,3,1,107,33]。

在freeze状态Se之后,下面应该freeze状态Sb了,它的出度为3,所以先调用writeBlock写入一个non floor block的,然后调用compileIndex来为这个block产生新的FSTIndex。

写入Block的时候,一些重要的变量如下表所示。

表3-17 freeze状态Sb时writeBlock的变量

image

在compileIndex生成当前block的FSTIndex的时候,除了添加prefix=ab所对应的output之外,还会将子block,BLOCK:abd和BLOCK:abe的FSTIndex都添加过来,形成一个整的FSTIndex。

Freeze完状态Sb之后,frontier,pending和pendingTerms的结果如下图所示。

image

这里pending只有一项,所有子Block的FSTIndex都合并到BLOCK:ab中来,多了一个[ab]的output为[-30,4],这是由fp=152, hasTerm=true, isFloor=false编码出来的。

接下来对于状态Sa,出度为1,并不做什么。对于初始状态S0,出度也为1,按说不做什么,但是在FindBlocks.freeze函数中,有这样的代码:

image

这里除了判断出度是否>min,还有idx==0,对于状态S0,还是需要调用writeBlocks,将BLOCK:ab写入tim中。

BlockTreeTermsWriter.TermsWriter.finish函数的blockBuilder.finish()就此结束。接下来从pending.get(0)得到根节点的FSTIndex,由于在compileIndex中,所有的子节点的FSTIndex都会加入到父节点中,最终根节点的FSTIndex是整个状态机的FSTIndex,然后将它写入在indexOut,也即tip文件中。

最终,tip和tim文件中Block和FSTIndex的格式和关系如图3-83所示。

image

最后我们再看一下FSTIndex的二进制内容,如下图3-84所示。

image

本文转载自:http://www.cnblogs.com/forfuture1978/p/3945755.html

火力全開
粉丝 19
博文 199
码字总数 17966
作品 0
卢湾
高级程序员
Lucene解析 - IndexWriter

前言 在上一篇文章我们介绍了Lucene的基本概念,在本篇文章我们将深入Lucene中最核心的类之一IndexWriter,来探索Lucene中数据写入和索引构建的整个过程。 IndexWriter 先看下Lucene中如何使...

木洛 ⋅ 04/17 ⋅ 0

Elasticsearch是如何做到快速索引的

最近在参与一个基于Elasticsearch作为底层数据框架提供大数据量(亿级)的实时统计查询的方案设计工作,花了些时间学习Elasticsearch的基础理论知识,整理了一下,希望能对Elasticsearch感兴趣...

浮躁的码农 ⋅ 05/30 ⋅ 0

Apache LuceneTM5.0.0 版本即将发布

Apache LuceneTM5.0.0 版本即将发布 源文地址:http://blog.mikemccandless.com/2014/11/apache-lucene-500-is-coming.html 最后,在密集发布一系列4.x版本的特性后,最近发布的是4.10.2版本...

sbp810050504 ⋅ 2015/01/09 ⋅ 0

lucene4.7 索引文件(九)

下图是一个典型的Lucene4.x的索引结构图: Lucene4.x之后的所有索引格式如下所示: 文件名 后缀 描述 Segments File segments.gen, segments_N 存储段文件的提交点信息 Lock File write.lock...

一枚Sir ⋅ 2014/04/11 ⋅ 1

Apache Lucene - Index File Formats V7.3.0

Apache Lucene - Index File Formats(索引文件格式) Introduction(引言) This document defines the index file formats used in this version of Lucene. If you are using a different ver......

囧雪啥都不知道 ⋅ 05/10 ⋅ 0

Lucene索引文件组成

Lucene的索引里面存了些什么,如何存放的,也即Lucene的索引文件格式,是读懂Lucene源代码的一把钥匙。 当我们真正进入到Lucene源代码之中的时候,我们会发现: Lucene的索引过程,就是按照全...

曾杰 ⋅ 2012/03/05 ⋅ 0

Lucene学习总结之三:Lucene的索引文件格式(1)

【转载 http://www.cnblogs.com/forfuture1978/archive/2009/12/14/1623597.html】 Lucene的索引里面存了些什么,如何存放的,也即Lucene的索引文件格式,是读懂Lucene源代码的一把钥匙。 当...

ruanjun ⋅ 2016/04/12 ⋅ 0

lucene 原理及代码解析

一、简介 lucene是一个全文检索类库,提供结构化以及非结构化文本检索。 全文检索的概念与传统数据库的模糊查询不同。 lucene将文本切分词后建立成倒排索引,当用户查询时lucene将用户输入的...

吴卫_Mars ⋅ 2013/09/27 ⋅ 1

Elasticsearch 2.2.0 基础篇:Lucene倒排索引

1.简介 倒排索引源于实际应用中需要根据属性的值来查找记录。这种索引表中的每一项都包括一个属性值和具有该属性值的各记录的地址。由于不是由记录来确定属性值,而是由属性值来确定记录的位...

赛克蓝德 ⋅ 2016/02/19 ⋅ 0

Lucene的索引文件格式(1)

Lucene学习总结之三:Lucene的索引文件格式(1) Lucene的索引里面存了些什么,如何存放的,也即Lucene的索引文件格式,是读懂Lucene源代码的一把钥匙。 当我们真正进入到Lucene源代码之中的时...

nubo ⋅ 03/05 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

Netweaver和SAP云平台的quota管理

Netweaver 以需要为一个用户上下文(User Context)能够在SAP extended memory区域中分配内存尺寸创建quota为例。 对于Dialog工作进程,使用事务码修改参数 ztta/roll_extension_dia. 对于非D...

JerryWang_SAP ⋅ 10分钟前 ⋅ 0

IDEA提示编码速度

焦点移动 将焦点冲代码编辑窗口移动到菜单栏:Alt+菜单栏带下划线字母 将焦点从工具窗口移动到代码编辑窗口 Esc或Shift+Esc 将焦点从代码编辑移动到最近使用的工具窗口 F12 模板提示 Ctrl+J...

bithup ⋅ 19分钟前 ⋅ 0

180623-SpringBoot之logback配置文件

SpringBoot配置logback 项目的日志配置属于比较常见的case了,之前接触和使用的都是Spring结合xml的方式,引入几个依赖,然后写个 logback.xml 配置文件即可,那么在SpringBoot中可以怎么做?...

小灰灰Blog ⋅ 43分钟前 ⋅ 0

冒泡排序

原理:比较两个相邻的元素,将值大的元素交换至右端。 思路:依次比较相邻的两个数,将小数放在前面,大数放在后面。即在第一趟:首先比较第1个和第2个数,将小数放前,大数放后。然后比较第...

人觉非常君 ⋅ 49分钟前 ⋅ 0

Vagrant setup

安装软件 brew cask install virtualboxbrew cask install vagrant 创建project mkdir -p mst/vmcd mst/vmvagrant init hashicorp/precise64vagrant up hashicorp/precise64是一个box......

遥借东风 ⋅ 今天 ⋅ 0

python3.6 安装pyhook_3

我的是在win下的,忙了半天老是安装不了, pip install 也不行。 那么可以看出自己的版本是32bit 一脸懵逼 没办法 只好下载32版本的来安装 我一直以为 是 对应32 位的 。 下面是 小例子 http...

之渊 ⋅ 今天 ⋅ 0

004、location正则表达式

1、location的作用 location指令的作用是根据用户请求的URI来执行不同的应用,也就是根据用户请求的网站URL进行匹配,匹配成功即进行相关的操作。 2、location的语法 = 开头表示精确匹配 ^~...

北岩 ⋅ 今天 ⋅ 0

CentOS7 静默安装 Oracle 12c

环境 CentOS7.5 最小安装 数据库软件 linuxx64_12201_database.zip 操作系统配置 关闭 SELinux sed -i '/^SELINUX=/cSELINUX=disabled' /etc/selinux/config 关闭防火墙 systemctl disable ......

Colben ⋅ 今天 ⋅ 0

Yii2中findAll()的正确使用姿势/返回为空的处理办法

从一次错误的操作开始 $buildingObject = Building::findAll("status=1"); 1 这个调用看着没有任何毛病,但是在使用时返回的结果却是一个空数组。再回过头来看看数据表中: 按照套路来讲,查...

dragon_tech ⋅ 今天 ⋅ 0

如何优雅的编程——C语言界面的一点小建议

我们鼓励在编程时应有清晰的哲学思维,而不是给予硬性规则。我并不希望你们能认可所有的东西,因为它们只是观点,观点会随着时间的变化而变化。可是,如果不是直到现在把它们写在纸上,长久以...

柳猫 ⋅ 今天 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部