null - 程序员宅基地

lucene字典Finite State Transducers(FST)和Postings List_lucene postinglist-程序员宅基地

下面内容转自http://www.cnblogs.com/LBSer/p/4119841.html

以及https://blog.csdn.net/AAA821/article/details/82014792

使用lucene进行查询不可避免都会使用到其提供的字典功能，即根据给定的term找到该term所对应的倒排文档id列表等信息。实际上lucene索引文件后缀名为tim和tip的文件实现的就是lucene的字典功能。

怎么实现一个字典呢？我们马上想到排序数组，即term字典是一个已经按字母顺序排序好的数组，数组每一项存放着term和对应的倒排文档id列表。每次载入索引的时候只要将term数组载入内存，通过二分查找即可。这种方法查询时间复杂度为Log(N)，N指的是term数目，占用的空间大小是O(N*str(term))。排序数组的缺点是消耗内存，即需要完整存储每一个term，当term数目多达上千万时，占用的内存将不可接受。

常用字典数据结构

很多数据结构均能完成字典功能，总结如下。

数据结构	优缺点
排序列表Array/List	使用二分法查找，不平衡
HashMap/TreeMap	性能高，内存消耗大，几乎是原始数据的三倍
Skip List	跳跃表，可快速查找词语，在lucene、redis、Hbase等均有实现。相对于TreeMap等结构，特别适合高并发场景（Skip List介绍）
Trie	适合英文词典，如果系统中存在大量字符串且这些字符串基本没有公共前缀，则相应的trie树将非常消耗内存（数据结构之trie树）
Double Array Trie	适合做中文词典，内存占用小，很多分词工具均采用此种算法（深入双数组Trie）
Ternary Search Tree	三叉树，每一个node有3个节点，兼具省空间和查询快的优点（Ternary Search Tree）
Finite State Transducers (FST)	一种有限状态转移机，Lucene 4有开源实现，并大量使用

FST原理简析

lucene从4开始大量使用的数据结构是FST（Finite State Transducer）。FST有两个优点：1）空间占用小。通过对词典中单词前缀和后缀的重复利用，压缩了存储空间；2）查询速度快。O(len(str))的查询时间复杂度。

下面简单描述下FST的构造过程（工具演示：http://examples.mikemccandless.com/fst.py?terms=&cmd=Build+it%21）。我们对“cat”、 “deep”、 “do”、 “dog” 、“dogs”这5个单词进行插入构建FST（注：必须已排序）。

1）插入“cat”

插入cat，每个字母形成一条边，其中t边指向终点。

2）插入“deep”

与前一个单词“cat”进行最大前缀匹配，发现没有匹配则直接插入，P边指向终点。

3）插入“do”

与前一个单词“deep”进行最大前缀匹配，发现是d，则在d边后增加新边o，o边指向终点。

4）插入“dog”

与前一个单词“do”进行最大前缀匹配，发现是do，则在o边后增加新边g，g边指向终点。

5）插入“dogs”

与前一个单词“dog”进行最大前缀匹配，发现是dog，则在g后增加新边s，s边指向终点。

最终我们得到了如上一个有向无环图。利用该结构可以很方便的进行查询，如给定一个term “dog”，我们可以通过上述结构很方便的查询存不存在，甚至我们在构建过程中可以将单词与某一数字、单词进行关联，从而实现key-value的映射。

也就是它这种压缩，就是让每个节点都不会放重复值，节省了大量的空间

假设我们现在要将mop, moth, pop, star, stop and top(term index里的term前缀)映射到序号：0，1，2，3，4，5(term dictionary的block位置)。最简单的做法就是定义个Map<string, integer="">，大家找到自己的位置对应入座就好了，但从内存占用少的角度想想，有没有更优的办法呢？答案就是：FST

Alt text

️表示一种状态

-->表示状态的变化过程，上面的字母/数字表示状态变化和权重

将单词分成单个字母通过️和-->表示出来，0权重不显示。如果️后面出现分支，就标记权重，最后整条路径上的权重加起来就是这个单词对应的序号。

FST以字节的方式存储所有的term Index，这种压缩方式可以有效的缩减存储空间(优点)，使得term index足以放进内存，但这种方式也会导致查找时需要更多的CPU资源(缺点,查找性能一般)。

FST存储的是如何通过term找到其对应的postings list（存储为一个bitset 标识了存在这些term的文档位置），其压缩形式为roaring map，具体可参考官网文档：https://www.elastic.co/cn/blog/frame-of-reference-and-roaring-bitmaps

本文链接：https://blog.csdn.net/im_cheer/article/details/89643121

原作者删帖不实内容删帖广告或垃圾文章投诉

智能推荐

稀疏编码的数学基础与理论分析-程序员宅基地

文章浏览阅读290次，点赞8次，收藏10次。1.背景介绍稀疏编码是一种用于处理稀疏数据的编码技术，其主要应用于信息传输、存储和处理等领域。稀疏数据是指数据中大部分元素为零或近似于零的数据，例如文本、图像、音频、视频等。稀疏编码的核心思想是将稀疏数据表示为非零元素和它们对应的位置信息，从而减少存储空间和计算复杂度。稀疏编码的研究起源于1990年代，随着大数据时代的到来，稀疏编码技术的应用范围和影响力不断扩大。目前，稀疏编码已经成为计算...

EasyGBS国标流媒体服务器GB28181国标方案安装使用文档-程序员宅基地

文章浏览阅读217次。EasyGBS - GB28181 国标方案安装使用文档下载安装包下载，正式使用需商业授权, 功能一致在线演示在线API架构图EasySIPCMSSIP 中心信令服务, 单节点, 自带一个 Redis Server, 随 EasySIPCMS 自启动, 不需要手动运行EasySIPSMSSIP 流媒体服务, 根..._easygbs-windows-2.6.0-23042316使用文档

【Web】记录巅峰极客2023 BabyURL题目复现——Jackson原生链_原生jackson 反序列化链子-程序员宅基地

文章浏览阅读1.2k次，点赞27次，收藏7次。2023巅峰极客 BabyURL之前AliyunCTF Bypassit I这题考查了这样一条链子：其实就是Jackson的原生反序列化利用今天复现的这题也是大同小异，一起来整一下。_原生jackson 反序列化链子

一文搞懂SpringCloud，详解干货，做好笔记_spring cloud-程序员宅基地

文章浏览阅读734次，点赞9次，收藏7次。微服务架构简单的说就是将单体应用进一步拆分，拆分成更小的服务，每个服务都是一个可以独立运行的项目。这么多小服务，如何管理他们？(服务治理注册中心[服务注册发现剔除])这么多小服务，他们之间如何通讯？这么多小服务，客户端怎么访问他们？(网关)这么多小服务，一旦出现问题了，应该如何自处理？(容错)这么多小服务，一旦出现问题了，应该如何排错?(链路追踪)对于上面的问题，是任何一个微服务设计者都不能绕过去的，因此大部分的微服务产品都针对每一个问题提供了相应的组件来解决它们。_spring cloud

Js实现图片点击切换与轮播-程序员宅基地

文章浏览阅读5.9k次，点赞6次，收藏20次。Js实现图片点击切换与轮播图片点击切换<!DOCTYPE html><html> <head> <meta charset="UTF-8"> <title></title> <script type="text/ja..._点击图片进行轮播图切换

tensorflow-gpu版本安装教程（过程详细）_tensorflow gpu版本安装-程序员宅基地

文章浏览阅读10w+次，点赞245次，收藏1.5k次。在开始安装前，如果你的电脑装过tensorflow，请先把他们卸载干净，包括依赖的包（tensorflow-estimator、tensorboard、tensorflow、keras-applications、keras-preprocessing），不然后续安装了tensorflow-gpu可能会出现找不到cuda的问题。cuda、cudnn。..._tensorflow gpu版本安装

随便推点

物联网时代权限滥用漏洞的攻击及防御-程序员宅基地

文章浏览阅读243次。0x00 简介权限滥用漏洞一般归类于逻辑问题，是指服务端功能开放过多或权限限制不严格，导致攻击者可以通过直接或间接调用的方式达到攻击效果。随着物联网时代的到来，这种漏洞已经屡见不鲜，各种漏洞组合利用也是千奇百怪、五花八门，这里总结漏洞是为了更好地应对和预防，如有不妥之处还请业内人士多多指教。0x01 背景2014年4月，在比特币飞涨的时代某网站曾经..._使用物联网漏洞的使用者

Visual Odometry and Depth Calculation--Epipolar Geometry--Direct Method--PnP_normalized plane coordinates-程序员宅基地

文章浏览阅读786次。A. Epipolar geometry and triangulationThe epipolar geometry mainly adopts the feature point method, such as SIFT, SURF and ORB, etc. to obtain the feature points corresponding to two frames of images. As shown in Figure 1, let the first image be and th_normalized plane coordinates

开放信息抽取(OIE)系统（三）-- 第二代开放信息抽取系统(人工规则, rule-based, 先抽取关系)_语义角色增强的关系抽取-程序员宅基地

文章浏览阅读708次，点赞2次，收藏3次。开放信息抽取(OIE)系统（三）-- 第二代开放信息抽取系统(人工规则, rule-based, 先关系再实体)一.第二代开放信息抽取系统背景第一代开放信息抽取系统(Open Information Extraction， OIE， learning-based, 自学习, 先抽取实体)通常抽取大量冗余信息，为了消除这些冗余信息，诞生了第二代开放信息抽取系统。二.第二代开放信息抽取系统历史第二代开放信息抽取系统着眼于解决第一代系统的三大问题: 大量非信息性提取（即省略关键信息的提取）、_语义角色增强的关系抽取