lucene字典Finite State Transducers(FST)和Postings List_lucene postinglist-程序员宅基地
技术标签： ElasticSearch
下面内容转自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
️表示一种状态
-->表示状态的变化过程，上面的字母/数字表示状态变化和权重
将单词分成单个字母通过️和-->表示出来，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
智能推荐
机器学习模型评分总结（sklearn）_model.score-程序员宅基地
文章浏览阅读1.5w次，点赞10次，收藏129次。文章目录目录模型评估评价指标1.分类评价指标acc、recall、F1、混淆矩阵、分类综合报告1.准确率方式一：accuracy_score方式二：metrics2.召回率3.F1分数4.混淆矩阵5.分类报告6.kappa scoreROC1.ROC计算2.ROC曲线3.具体实例2.回归评价指标3.聚类评价指标1.Adjusted Rand index 调整兰德系数2.Mutual Informa..._model.score
Apache虚拟主机配置mod_jk_apache mod_jk 虚拟-程序员宅基地
文章浏览阅读344次。因工作需要，在Apache上使用，重新学习配置mod_jk1. 分别安装Apache和Tomcat：2. 编辑httpd-vhosts.conf： LoadModule jk_module modules/mod_jk.so #加载mod_jk模块 JkWorkersFile conf/workers.properties #添加worker信息 JkLogFil_apache mod_jk 虚拟
Android ConstraintLayout2.0 过度动画MotionLayout MotionScene3_android onoffsetchanged-程序员宅基地
文章浏览阅读335次。待老夫kotlin大成,扩展:MotionLayout 与 CoordinatorLayout,DrawerLayout,ViewPager 的 交互众所周知,MotionLayout 的 动画是有完成度的 即Progress ,他在0-1之间变化,一.CoordinatorLayout 与AppBarLayout 交互时,其实就是监听 offsetliner 这个 偏移量的变化 同样..._android onoffsetchanged
【转】多核处理器的工作原理及优缺点_多核处理器怎么工作-程序员宅基地
文章浏览阅读8.3k次，点赞3次，收藏19次。【转】多核处理器的工作原理及优缺点《处理器关于多核概念与区别 多核处理器工作原理及优缺点》原文传送门 摘要：目前关于处理器的单核、双核和多核已经得到了普遍的运用，今天我们主要说说关于多核处理器的一些相关概念，它的工作与那里以及优缺点而展开的分析。1、多核处理器 多核处理器是指在一枚处理器中集成两个或多个完整的计算引擎（内核），此时处理器能支持系统总线上的多个处理器，由总..._多核处理器怎么工作
个人小结---eclipse/myeclipse配置lombok_eclispe每次运行个新项目都需要重新配置lombok吗-程序员宅基地
文章浏览阅读306次。1. eclipse配置lombok 拷贝lombok.jar到eclipse.ini同级文件夹下，编辑eclipse.ini文件，添加: -javaagent:lombok.jar2. myeclipse配置lombok myeclipse像eclipse配置后，定义对象后，直接访问方法，可能会出现飘红的报错。 如果出现报错，可按照以下方式解决。 ..._eclispe每次运行个新项目都需要重新配置lombok吗
【最新实用版】Python批量将pdf文本提取并存储到txt文件中_python批量读取文字并批量保存-程序员宅基地
文章浏览阅读1.2w次，点赞31次，收藏126次。#注意：笔者在2021/11/11当天调试过这个代码是可用的，由于pdfminer版本的更新，网络上大多数的语法没有更新，我也是找了好久的文章才修正了我的代码，仅供学习参考。1、把pdf文件移动到本代码文件的同一个目录下，笔者是在pycharm里面运行的项目，下图中的x1文件夹存储了我需要转换成文本文件的所有pdf文件。然后要在此目录下创建一个存放转换后的txt文件的文件夹，如图中的txt文件夹。2、编写代码 （1）导入所需库# coding:utf-8import ..._python批量读取文字并批量保存
随便推点
Scala:访问修饰符、运算符和循环_scala ===运算符-程序员宅基地
文章浏览阅读1.4k次。http://blog.csdn.net/pipisorry/article/details/52902234Scala 访问修饰符Scala 访问修饰符基本和Java的一样，分别有：private，protected，public。如果没有指定访问修饰符符，默认情况下，Scala对象的访问级别都是 public。Scala 中的 private 限定符，比 Java 更严格，在嵌套类情况下，外层_scala ===运算符
MySQL导出ER图为图片或PDF_数据库怎么导出er图-程序员宅基地
文章浏览阅读2.6k次，点赞7次，收藏19次。ER图导出为PDF或图片格式_数据库怎么导出er图
oracle触发器修改同一张表,oracle触发器中对同一张表进行更新再查询时，需加自制事务...-程序员宅基地
文章浏览阅读655次。CREATE OR REPLACE TRIGGER Trg_ReimFactBEFORE UPDATEON BP_OrderFOR EACH ROWDECLAREPRAGMA AUTONOMOUS_TRANSACTION;--自制事务fc varchar2(255);BEGINIF ( :NEW.orderstate = 2AND :NEW.TransState = 1 ) THENBEG..._oracle触发器更新同一张表
debounce与throttle区别及其应用场景_throttle和debounce应用在哪些场景-程序员宅基地
文章浏览阅读513次。目录概念debouncethrottle实现debouncethrottle应用场景debouncethrottle场景举例debouncethrottle概念debounce字面理解是“防抖”，何谓“防抖”，就是连续操作结束后再执行，以网页滚动为例，debounce要等到用户停止滚动后才执行，将连续多次执行合并为一次执行。throttle字面理解是“节流”，何谓“节流”，就是确保一段时..._throttle和debounce应用在哪些场景
java操作mongdb【超详细】_java 操作mongodb-程序员宅基地
文章浏览阅读526次。regex() $regex 正则表达式用于模式匹配，基本上是用于文档中的发现字符串 （下面有例子）注意：若未加 @Field("名称") ，则识别mongdb集合中的key名为实体类属性名。也可以对数组进行索引，如果被索引的列是数组时，MongoDB会索引这个数组中的每一个元素。也可以对整个Document进行索引，排序是预定义的按插入BSON数据的先后升序排列。save: 若新增数据的主键已经存在，则会对当前已经存在的数据进行修改操作。_java 操作mongodb
github push 推送代码失败. 使用ssh rsa key. remote: Support for password authentication was removed._git push remote: support for password authenticati-程序员宅基地
文章浏览阅读1k次。今天push代码到github仓库时出现这个报错TACKCHEN-MB0:tc-image tackchen$ git pushremote: Support for password authentication was removed on August 13, 2021. Please use a personal access token instead.remote: Please see https://github.blog/2020-12-15-token-authentication_git push remote: support for password authentication was removed on august 1