开发者社区> 桃子红了呐> 正文
阿里云
为了无法计算的价值
打开APP
阿里云APP内打开

Lucene 4.X 倒排索引原理与实现: (3) Term Dictionary和Index文件 (FST详细解析)——直接看例子就明白了!!!

简介:
+关注继续查看
转自: http://www.cnblogs.com/forfuture1978/p/3945755.html 好好看看吧 倒排列表信息中词典相关存储的最关键格式 占倒排列表中文件大小的多数

我们来看最复杂的部分,就是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文件的指针。

 

下面咱们具体讨论,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的要求,给出一个字符串,我马上能找到倒排表的位置。

 

下面是FST的序列化:关心底层存储可以了解下。

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

image

 

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

image

 

 

默认情况下,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

image

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

image

 

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

image

 

 '












本文转自张昺华-sky博客园博客,原文链接:http://www.cnblogs.com/bonelee/p/6626984.html,如需转载请自行联系原作者


版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
Docker Swarm 集群部署笔记
Docker Swarm 集群部署笔记
38 0
js成员检查方式in、indexOf、includes、inArray
js成员检查方式in、indexOf、includes、inArray
99 0
Linux用户和组| 学习笔记
快速学习Linux用户和组
59 0
[python作业AI毕业设计博客]英文原版新书下载:Impractical Python Projects - 2019.Pdf
python测试开发项目实战-目录 python工具书籍下载-持续更新 python 3.7极速入门教程 - 目录 下载:Impractical Python Projects - 2019.Pdf Impractical Python Projects is a collection of...
1980 0
SAP Customer Data Cloud(Gigya)的用户搜索实现
我在Gigya前台根据email搜索,输入一个邮箱地址,回车,在Chrome开发者工具里观察到到后台的网络请求: 这是一个post请求: __RequestVerificationToken 请求体: {"query":"SELECT * FROM accounts WHERE (profile.
1324 0
Scrapy随机切换用户代理User-Agent
使用fake-useragent:https://github.com/hellysmile/fake-useragent 这是一个可以随机切换访问头的插件 安装方法: pip install fake-useragent 使用方法: from fa...
1315 0
ajax实现JSONP跨域
简单的说,出于安全方面的考虑,页面中的JavaScript无法访问其他服务器上的数据,即“同源策略”。而跨域就是通过某些手段来绕过同源策略限制,实现不同服务器之间通信的效果
3240 0
DOM4J 实现对XML文档的增、删、改、查
前言:首先谈一个小故事:当年Java准备做对XML的解析时,对解析器的实现方向在内部发生了争执,后来高层没有听从工程师建议,坚持开发出了JDOM,而主要的工程师选择离开Java 按照自己的方式实现,就是DOM4J 。后来结果表明,DOM4J 完胜了JDOM。下面,让我们来了解一下通过DOM4J 实现对XML文件进行增删改查的过程。 1、待解析的XML文件: <span styl
1718 0
4267
文章
0
问答
文章排行榜
最热
最新
相关电子书
更多
低代码开发师(初级)实战教程
立即下载
阿里巴巴DevOps 最佳实践手册
立即下载
冬季实战营第三期:MySQL数据库进阶实战
立即下载