Lucene学习总结之Lucene的索引文件格式

当我们真正进入到Lucene源代码之中的时候，我们会发现:

  • Lucene的索引过程，就是按照全文检索的基本过程，将倒排表写成此文件格式的过程。
  • Lucene的搜索过程，就是按照此文件格式将索引进去的信息读出来，然后计算每篇文档打分(score)的过程。

一、基本概念

下图就是Lucene生成的索引的一个实例：

image

Lucene的索引结构是有层次结构的，主要分以下几个层次：

  • 索引(Index)：
    • 在Lucene中一个索引是放在一个文件夹中的。
    • 如上图，同一文件夹中的所有的文件构成一个Lucene索引。
  • 段(Segment)：
    • 一个索引可以包含多个段，段与段之间是独立的，添加新文档可以生成新的段，不同的段可以合并。
    • 如上图，具有相同前缀文件的属同一个段，图中共两个段 "_0" 和 "_1"。
    • segments.gen和segments_5是段的元数据文件，也即它们保存了段的属性信息。
  • 文档(Document)：
    • 文档是我们建索引的基本单位，不同的文档是保存在不同的段中的，一个段可以包含多篇文档。
    • 新添加的文档是单独保存在一个新生成的段中，随着段的合并，不同的文档合并到同一个段中。
  • 域(Field)：
    • 一篇文档包含不同类型的信息，可以分开索引，比如标题，时间，正文，作者等，都可以保存在不同的域里。
    • 不同域的索引方式可以不同，在真正解析域的存储的时候，我们会详细解读。
  • 词(Term)：
    • 词是索引的最小单位，是经过词法分析和语言处理后的字符串。

Lucene的索引结构中，即保存了正向信息，也保存了反向信息。

所谓正向信息：

  • 按层次保存了从索引，一直到词的包含关系：索引(Index) –> 段(segment) –> 文档(Document) –> 域(Field) –> 词(Term)
  • 也即此索引包含了那些段，每个段包含了那些文档，每个文档包含了那些域，每个域包含了那些词。
  • 既然是层次结构，则每个层次都保存了本层次的信息以及下一层次的元信息，也即属性信息，比如一本介绍中国地理的书，应该首先介绍中国地理的概况，以及中国包含多少个省，每个省介绍本省的基本概况及包含多少个市，每个市介绍本市的基本概况及包含多少个县，每个县具体介绍每个县的具体情况。
  • 如上图，包含正向信息的文件有：
    • segments_N保存了此索引包含多少个段，每个段包含多少篇文档。
    • XXX.fnm保存了此段包含了多少个域，每个域的名称及索引方式。
    • XXX.fdx，XXX.fdt保存了此段包含的所有文档，每篇文档包含了多少域，每个域保存了那些信息。
    • XXX.tvx，XXX.tvd，XXX.tvf保存了此段包含多少文档，每篇文档包含了多少域，每个域包含了多少词，每个词的字符串，位置等信息。

所谓反向信息：

  • 保存了词典到倒排表的映射：词(Term) –> 文档(Document)
  • 如上图，包含反向信息的文件有：
    • XXX.tis，XXX.tii保存了词典(Term Dictionary)，也即此段包含的所有的词按字典顺序的排序。
    • XXX.frq保存了倒排表，也即包含每个词的文档ID列表。
    • XXX.prx保存了倒排表中每个词在包含此词的文档中的位置。

在了解Lucene索引的详细结构之前，先看看Lucene索引中的基本数据类型。

二、基本类型

Lucene索引文件中，用一下基本类型来保存信息：

  • Byte：是最基本的类型，长8位(bit)。
  • UInt32：由4个Byte组成。
  • UInt64：由8个Byte组成。
  • VInt：
    • 变长的整数类型，它可能包含多个Byte，对于每个Byte的8位，其中后7位表示数值，最高1位表示是否还有另一个Byte，0表示没有，1表示有。
    • 越前面的Byte表示数值的低位，越后面的Byte表示数值的高位。
    • 例如130化为二进制为 1000, 0010，总共需要8位，一个Byte表示不了，因而需要两个Byte来表示，第一个Byte表示后7位，并且在最高位置1来表示后面还有一个Byte，所以为(1) 0000010，第二个Byte表示第8位，并且最高位置0来表示后面没有其他的Byte了，所以为(0) 0000001。

clip_image002[1]

  • Chars：是UTF-8编码的一系列Byte。
  • String：一个字符串首先是一个VInt来表示此字符串包含的字符的个数，接着便是UTF-8编码的字符序列Chars。

三、基本规则

Lucene为了使的信息的存储占用的空间更小，访问速度更快，采取了一些特殊的技巧，然而在看Lucene文件格式的时候，这些技巧却容易使我们感到困惑，所以有必要把这些特殊的技巧规则提取出来介绍一下。

在下不才，胡乱给这些规则起了一些名字，是为了方便后面应用这些规则的时候能够简单，不妥之处请大家谅解。

1. 前缀后缀规则(Prefix+Suffix)

Lucene在反向索引中，要保存词典(Term Dictionary)的信息，所有的词(Term)在词典中是按照字典顺序进行排列的，然而词典中包含了文档中的几乎所有的词，并且有的词还是非常的长的，这样索引文件会非常的大，所谓前缀后缀规则，即当某个词和前一个词有共同的前缀的时候，后面的词仅仅保存前缀在词中的偏移(offset)，以及除前缀以外的字符串(称为后缀)。

prefixsuffix

比如要存储如下词:term，termagancy，termagant，terminal，

如果按照正常方式来存储，需要的空间如下：

[VInt = 4] [t][e][r][m]，[VInt = 10][t][e][r][m][a][g][a][n][c][y]，[VInt = 9][t][e][r][m][a][g][a][n][t]，[VInt = 8][t][e][r][m][i][n][a][l]

共需要35个Byte.

如果应用前缀后缀规则，需要的空间如下：

[VInt = 4] [t][e][r][m]，[VInt = 4 (offset)][VInt = 6][a][g][a][n][c][y]，[VInt = 8 (offset)][VInt = 1][t]，[VInt = 4(offset)][VInt = 4][i][n][a][l]

共需要22个Byte。

大大缩小了存储空间，尤其是在按字典顺序排序的情况下，前缀的重合率大大提高。

2. 差值规则(Delta)

在Lucene的反向索引中，需要保存很多整型数字的信息，比如文档ID号，比如词(Term)在文档中的位置等等。

由上面介绍，我们知道，整型数字是以VInt的格式存储的。随着数值的增大，每个数字占用的Byte的个数也逐渐的增多。所谓差值规则(Delta)就是先后保存两个整数的时候，后面的整数仅仅保存和前面整数的差即可。

delta

比如要存储如下整数：16386，16387，16388，16389

如果按照正常方式来存储，需要的空间如下：

[(1) 000, 0010][(1) 000, 0000][(0) 000, 0001]，[(1) 000, 0011][(1) 000, 0000][(0) 000, 0001]，[(1) 000, 0100][(1) 000, 0000][(0) 000, 0001]，[(1) 000, 0101][(1) 000, 0000][(0) 000, 0001]

供需12个Byte。

如果应用差值规则来存储，需要的空间如下：

[(1) 000, 0010][(1) 000, 0000][(0) 000, 0001]，[(0) 000, 0001]，[(0) 000, 0001]，[(0) 000, 0001]

共需6个Byte。

大大缩小了存储空间，而且无论是文档ID，还是词在文档中的位置，都是按从小到大的顺序，逐渐增大的。

3. 或然跟随规则(A, B?)

Lucene的索引结构中存在这样的情况，某个值A后面可能存在某个值B，也可能不存在，需要一个标志来表示后面是否跟随着B。

一般的情况下，在A后面放置一个Byte，为0则后面不存在B，为1则后面存在B，或者0则后面存在B，1则后面不存在B。

但这样要浪费一个Byte的空间，其实一个Bit就可以了。

在Lucene中，采取以下的方式：A的值左移一位，空出最后一位，作为标志位，来表示后面是否跟随B，所以在这种情况下，A/2是真正的A原来的值。

ab

如果去读Apache Lucene - Index File Formats这篇文章，会发现很多符合这种规则的：

  • .frq文件中的DocDelta[, Freq?]，DocSkip,PayloadLength?
  • .prx文件中的PositionDelta,Payload? (但不完全是，如下表分析)

当然还有一些带?的但不属于此规则的：

  • .frq文件中的SkipChildLevelPointer?，是多层跳跃表中，指向下一层表的指针，当然如果是最后一层，此值就不存在，也不需要标志。
  • .tvf文件中的Positions?, Offsets?。
    • 在此类情况下，带?的值是否存在，并不取决于前面的值的最后一位。
    • 而是取决于Lucene的某项配置，当然这些配置也是保存在Lucene索引文件中的。
    • 如Position和Offset是否存储，取决于.fnm文件中对于每个域的配置(TermVector.WITH_POSITIONS和TermVector.WITH_OFFSETS)

为什么会存在以上两种情况，其实是可以理解的：

  • 对于符合或然跟随规则的，是因为对于每一个A，B是否存在都不相同，当这种情况大量存在的时候，从一个Byte到一个Bit如此8倍的空间节约还是很值得的。
  • 对于不符合或然跟随规则的，是因为某个值的是否存在的配置对于整个域(Field)甚至整个索引都是有效的，而非每次的情况都不相同，因而可以统一存放一个标志。
文章中对如下格式的描述令人困惑：

Positions --> <PositionDelta,Payload?> Freq

Payload --> <PayloadLength?,PayloadData>

PositionDelta和Payload是否适用或然跟随规则呢？如何标识PayloadLength是否存在呢？

其实PositionDelta和Payload并不符合或然跟随规则，Payload是否存在，是由.fnm文件中对于每个域的配置中有关Payload的配置决定的(FieldOption.STORES_PAYLOADS) 。

当Payload不存在时，PayloadDelta本身不遵从或然跟随原则。

当Payload存在时，格式应该变成如下：Positions --> <PositionDelta,PayloadLength?,PayloadData> Freq

从而PositionDelta和PayloadLength一起适用或然跟随规则。

4. 跳跃表规则(Skip list) 

为了提高查找的性能，Lucene在很多地方采取的跳跃表的数据结构。

跳跃表(Skip List)是如图的一种数据结构，有以下几个基本特征：

  • 元素是按顺序排列的，在Lucene中，或是按字典顺序排列，或是按从小到大顺序排列。
  • 跳跃是有间隔的(Interval)，也即每次跳跃的元素数，间隔是事先配置好的，如图跳跃表的间隔为3。
  • 跳跃表是由层次的(level)，每一层的每隔指定间隔的元素构成上一层，如图跳跃表共有2层。

skiplist

需要注意一点的是，在很多数据结构或算法书中都会有跳跃表的描述，原理都是大致相同的，但是定义稍有差别：

  • 对间隔(Interval)的定义： 如图中，有的认为间隔为2，即两个上层元素之间的元素数，不包括两个上层元素；有的认为是3，即两个上层元素之间的差，包括后面上层元素，不包括前面的上层元素；有的认为是4，即除两个上层元素之间的元素外，既包括前面，也包括后面的上层元素。Lucene是采取的第二种定义。
  • 对层次(Level)的定义：如图中，有的认为应该包括原链表层，并从1开始计数，则总层次为3，为1，2，3层；有的认为应该包括原链表层，并从0计数，为0，1，2层；有的认为不应该包括原链表层，且从1开始计数，则为1，2层；有的认为不应该包括链表层，且从0开始计数，则为0，1层。Lucene采取的是最后一种定义。

跳跃表比顺序查找，大大提高了查找速度，如查找元素72，原来要访问2，3，7，12，23，37，39，44，50，72总共10个元素，应用跳跃表后，只要首先访问第1层的50，发现72大于50，而第1层无下一个节点，然后访问第2层的94，发现94大于72，然后访问原链表的72，找到元素，共需要访问3个元素即可。

然而Lucene在具体实现上，与理论又有所不同，在具体的格式中，会详细说明。

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.xdnf.cn/news/148921.html

如若内容造成侵权/违法违规/事实不符，请联系一条长河网进行投诉反馈，一经查实，立即删除！

相关文章

Android开源 Skeleton 骨架屏 V1.3.0

Android开源 Skeleton 骨架屏 V1.3.0

目录 一、简介 二、效果图 三、引用 Skeleton 添加jitpack 仓库 添加依赖: 四、新增 “块”骨架屏 1、bind方法更改和变化&#xff1a; 2、load方法更改和变化&#xff1a; 五、关于上一个版本 一、简介 骨架屏的作用是在网络请求较慢时&#xff0c;提供基础占位&…
阅读更多...
Android LitePal byte[]类型字段不被创建

Android LitePal byte[]类型字段不被创建

我创建了以下实体类&#xff0c;主要是用户分享的内容、分享的照片、分享的标题&#xff0c;然后百度了一下LitePal可以识别byte[]&#xff0c;因为需要文件的上传与读取&#xff1a; public class Context extends LitePalSupport {private Integer ContextId;private String…
阅读更多...
LLMs 用强化学习进行微调 RLHF: Fine-tuning with reinforcement learning

LLMs 用强化学习进行微调 RLHF: Fine-tuning with reinforcement learning

让我们把一切都整合在一起&#xff0c;看看您将如何在强化学习过程中使用奖励模型来更新LLM的权重&#xff0c;并生成与人对齐的模型。请记住&#xff0c;您希望从已经在您感兴趣的任务上表现良好的模型开始。您将努力使指导发现您的LLM对齐。首先&#xff0c;您将从提示数据集…
阅读更多...
用向量数据库Milvus Cloud 搭建AI聊天机器人

用向量数据库Milvus Cloud 搭建AI聊天机器人

加入大语言模型（LLM） 接着，需要在聊天机器人中加入 LLM。这样，用户就可以和聊天机器人开展对话了。本示例中，我们将使用 OpenAI ChatGPT 背后的模型服务：GPT-3.5。 聊天记录 为了使 LLM 回答更准确，我们需要存储用户和机器人的聊天记录，并在查询时调用这些记录，可以用…
阅读更多...
软件设计模式系列之二十五——访问者模式

软件设计模式系列之二十五——访问者模式

访问者模式&#xff08;Visitor Pattern&#xff09;是一种强大的行为型设计模式&#xff0c;它允许你在不改变被访问对象的类的前提下&#xff0c;定义新的操作和行为。本文将详细介绍访问者模式&#xff0c;包括其定义、举例说明、结构、实现步骤、Java代码实现、典型应用场景…
阅读更多...
软件工程从理论到实践客观题汇总(头歌第九章至第十七章)

软件工程从理论到实践客观题汇总(头歌第九章至第十七章)

九、软件体系结构设计 1、软件体系结构设计概述 2、软件体系结构模型的表示方法 3、软件体系结构设计过程 4、设计初步的软件体系结构 5、重用已有软件资源 6、精化软件体系结构 7、设计软件部署模型 8、文档化和评审软件体系结构设计 十、软件用户界面设计 1、用户界面设计概…
阅读更多...
Ae 效果：CC Page Turn

Ae 效果：CC Page Turn

扭曲/CC Page Turn Distort/CC Page Turn CC Page Turn &#xff08;CC 翻页&#xff09;主要用于模拟书页翻动的效果。通过使用该效果&#xff0c;用户可以创建出像书页或杂志页面翻动的视觉效果&#xff0c;增强影片的交互性和视觉吸引力。 ◆ ◆ ◆ 效果属性说明 Contro…
阅读更多...
Is This The Intelligent Model（这是智能模型吗）

Is This The Intelligent Model（这是智能模型吗）

Is This The Intelligent Model 这是智能模型吗 Ruoqi Sun Academy of Military Science Defense Innovation Institute, Beijing, 100091, China E-mail: ruoqisun7163.com The exposed models are called artificial intelligent models[1-3]. These models rely on knowled…
阅读更多...
第2篇 机器学习基础 —（1）机器学习方式及分类、回归

第2篇 机器学习基础 —（1）机器学习方式及分类、回归

前言&#xff1a;Hello大家好&#xff0c;我是小哥谈。机器学习是一种人工智能的分支&#xff0c;它使用算法和数学模型来使计算机系统能够从经验数据中学习和改进&#xff0c;而无需显式地编程。机器学习的目标是通过从数据中发现模式和规律&#xff0c;从而使计算机能够自动进…
阅读更多...
Leetcode 231.2的幂

Leetcode 231.2的幂

给你一个整数 n&#xff0c;请你判断该整数是否是 2 的幂次方。如果是&#xff0c;返回 true &#xff1b;否则&#xff0c;返回 false 。 如果存在一个整数 x 使得 n 2x &#xff0c;则认为 n 是 2 的幂次方。 示例 1&#xff1a; 输入&#xff1a;n 1 输出&#xff1a;tr…
阅读更多...
【重拾C语言】二、顺序程序设计（基本符号、数据、语句、表达式、顺序控制结构、数据类型、输入/输出操作）

【重拾C语言】二、顺序程序设计（基本符号、数据、语句、表达式、顺序控制结构、数据类型、输入/输出操作）

目录 前言 二、顺序程序设计 2.1 求绿化带面积——简单程序 2.2基本符号&#xff1a; 2.2.1 字符集 可视字符 不可视字符 2.2.2 C特定符 关键字 分隔符 运算符 2.2.3 标识符 2.2.4 间隔符 2.2.5 注释 2.3 数据 2.3.1 字面常量&#xff08;Literal Constants&am…
阅读更多...
【RP-RV1126】烧录固件使用记录

【RP-RV1126】烧录固件使用记录

文章目录 烧录完整固件进入MASKROM模式固件烧录升级中&#xff1a;升级完成&#xff1a; 烧录部分进入Loader模式选择文件切换loader模式 烧录完整固件 完整固件就是update.img包含了所有的部件&#xff0c;烧录后可以直接运行。 全局编译&#xff1a;./build.sh all生成固件…
阅读更多...
SDL2绘制ffmpeg解析的mp4文件

SDL2绘制ffmpeg解析的mp4文件

文章目录 1.FFMPEG利用命令行将mp4转yuv4202.ffmpeg将mp4解析为yuv数据2.1 核心api: 3.SDL2进行yuv绘制到屏幕3.1 核心api 4.完整代码5.效果展示 本项目采用生产者消费者模型&#xff0c;生产者线程&#xff1a;使用ffmpeg将mp4格式数据解析为yuv的帧&#xff0c;消费者线程&am…
阅读更多...
单层神经网络

单层神经网络

神经网络 人工神经网络&#xff08;Artificial Neural Network&#xff0c;ANN&#xff09;&#xff0c;简称神经网络&#xff08;Neural Network&#xff0c;NN&#xff09;&#xff0c;是一种模仿生物神经网络的结构和功能的数学模型或计算模型。1943年&#xff0c;McCulloc…
阅读更多...
计数排序（Counting Sort）详解

计数排序（Counting Sort）详解

计数排序&#xff08;Counting Sort&#xff09;是一种非比较排序算法&#xff0c;其核心思想是通过计数每个元素的出现次数来进行排序&#xff0c;适用于整数或有限范围内的非负整数排序。这个算法的特点是速度快且稳定&#xff0c;适用于某些特定场景。在本文中&#xff0c;我…
阅读更多...
多层神经网络和激活函数

多层神经网络和激活函数

多层神经网络的结构 多层神经网络就是由单层神经网络进行叠加之后得到的&#xff0c;所以就形成了层的概念&#xff0c;常见的多层神经网络有如下结构&#xff1a; 1&#xff09;输入层&#xff08;Input layer&#xff09;&#xff0c;众多神经元&#xff08;Neuron&#xff…
阅读更多...
电商项目常用的五个设计模式场景及分析实现

电商项目常用的五个设计模式场景及分析实现

电商设计模式总结 1 单点登录模 1 业务介绍 单点登录&#xff08;Single Sign-On, SSO&#xff09;模块允许用户在多个相关应用系统之间进行无缝的身份验证。用户只需登录一次&#xff0c;然后可以访问所有连接的应用程序而无需重新登录。在电商应用中&#xff0c;这对于提供…
阅读更多...
互联网Java工程师面试题·Dubbo篇·第一弹

互联网Java工程师面试题·Dubbo篇·第一弹

目录 1、为什么要用 Dubbo&#xff1f; 2、Dubbo 的整体架构设计有哪些分层? 3、默认使用的是什么通信框架&#xff0c;还有别的选择吗? 4、服务调用是阻塞的吗&#xff1f; 5、一般使用什么注册中心&#xff1f;还有别的选择吗&#xff1f; 6、默认使用什么序列化框架&…
阅读更多...
堆排序——向下调整

堆排序——向下调整

之前我们要想实现堆排序&#xff0c;是运用建堆代码来实现的&#xff1a; 向上调整建堆——向下调整排序 那么去我们可不可以只适用一种调整方法&#xff08;向下调整&#xff09;就能实现这样的功能呢&#xff1f; 向要只使用向下调整就实现堆排序 首先就是把数组里的值使用…
阅读更多...
uboot启动流程-uboot内存分配工作总结

uboot启动流程-uboot内存分配工作总结

一. uboot 启动流程 _main 函数中会调用 board_init_f 函数&#xff0c;本文继续简单分析一下 board_init_f 函数。 本文继续具体分析 board_init_f 函数。 本文继上一篇文章的学习&#xff0c;地址如下&#xff1a; uboot启动流程-uboot内存分配_凌肖战的博客-CSDN博客 二…
阅读更多...
最新文章

Copyright @ 2022~2023