Lucene学习笔记之-核心数据结构PriorityQueue的实现原理 精选 原创 sbp810050504 2019-01-06 22:43:20 博主文章分类:搜索引擎 ©著作权 文章标签 Lucene PriorityQueue HitQueue 优先队列 堆 文章分类 数据结构与算法 人工智能 ©著作权归作者所有:来自51CTO博客作者sbp810050504的原创作品,请联系作者获取转载授权,否则将追究法律责任 Luene的核心应用场景是全文检索。简单来说,就是通过用户输入的关键词来匹配相关文档,然后根据匹配程度返回TopN的查询结果给用户。 这里需要解决的一个核心问题就是如何快速返回TopN的结果,这本质上是一个排序的问题。说起排序,我们有很多选择,冒泡,快排,归并...。 这些排序算法在数据量小的时候,不是问题。一旦数据量过大,就成为问题了。 例如对1000万的数组排序: Integer[] a = new Integer[10000000]; for(int i=0;i<10000000;i++){ a[i] = (int) (Math.random()*10000000); } long start = System.currentTimeMillis(); Arrays.sort(a); System.out.println((System.currentTimeMillis() - start) +" 毫秒"); 在我的电脑耗时需要5秒左右, 这个等待时间对于用户体验来说,就不那么feeling good了。 这时候,该考虑优化了。优化基本上是一个做减法的过程。再回到我们的核心需求: 基于搜索关键词返回TopN的结果。 也就是说,我们只需要TopN的结果有序就可以了。 基于上述需求,我们引入一个新的数据结构: 堆(Heap)。 堆是一种特殊的二叉树。所谓二叉树就是每个节点最多有两个子节点: 最多生二胎,超生不被允许的。 对于二叉树这种树形结构,最核心的关系就是父子节点关系。 定义不同的节点关系,我们就能得到丰富多彩的数据结构,以应对不同场景的业务问题。比如: 规定“子节点不能大于父节点”, 我们可以得出根节点是最大的节点, 得到大顶堆。 规定“子节点不能小于父节点”, 我们可以得出根节点是最小的节点, 得到小顶堆。 规定“根节点大于左子树,小于右子树;子树亦是如此”, 我们得到二叉搜索树;为了使二叉搜索树的左右尽量平衡,我们又得到了“红黑树”,“AVL树”,Treap等不同策略的平衡树。 这些概念性的东西,能理解就OK. 理解了堆的来龙去脉, 我们可能会有点困惑,它并没有直接维护一个有序的结构。 是的,它没有直接维护有序的结构,它是通过删除数据实现排序功能的。理解这一点特别重要。 以大顶堆为例: 由于堆顶是最大的元素,所以我们能确信,对于一个堆: 我们只要不断地删除堆顶的数据,直至空堆,就能得到一个有序的结果。这就是堆排序的思想。 那么如何利用堆实现TopN的有序输出呢? 以搜索的打分作为排序项,我们希望输出得分最高的N个结果。 我们先遍历N个结果,得到有N个元素的小顶堆。由于堆顶的元素最小, 遍历剩下的打分结果,只需要跟堆的根节点对比即可。如果打分结果小于堆的根节点,弃之;如果打分结果大于堆的根节点,删除根节点;然后使用该打分结果更新到堆中。 这样最后这个堆就维护了我们想要的TopN。 例如对1000万的数据,我们给出最大的前100个数,代码如下: Integer[] a = new Integer[10000000]; for(int i=0;i<10000000;i++){ a[i] = (int) (Math.random()*10000000); } long start = System.currentTimeMillis(); PriorityQueue<Integer> pq = new PriorityQueue<Integer>(100) { @Override protected boolean lessThan(Integer t1, Integer t2) { return t1 < t2; } }; for(int i=0;i<10000000;i++){ pq.insertWithOverflow(a[i]); } Integer[] b = new Integer[100]; for(int i=99;i>=0;i--){ b[i] = pq.pop(); } System.out.println((System.currentTimeMillis() - start) +" 毫秒"); System.out.println(Arrays.asList(b)); 这个耗时只需要50多毫秒。 这个性能差距几乎是100倍。可见堆这种数据结构在TopN这个场景下是多么适合。 其实JDK有自己基于堆实现的优先队列PriorityQueue, 为啥Lucene要再造一遍轮子呢? JDK默认的PriorityQueue是可以自动扩展的,Lucene需要定长的。 JDK默认的PriorityQueue将数据结构封装得比较紧密,而Lucene需要一定的灵活性,比如调整堆顶。 小顶堆是一种二叉树,所以其逻辑结构大致如下: 1 3 2 5 8 7 6 如果观察,可以发现这个一个规律,就是第一层只有1个元素;第二层最多有2个元素; 第三层最多有4个元素, 即第N层有2^(n-1)个元素。 这个规律后面有用。 那么怎么编码实现一个堆呢? 最简单的实现方式是基于数组,以Lucene的实现为例,学习一下: public abstract class PriorityQueue<T> { private int size; private final int maxSize; private final T[] heap; 定义了一个数组。 只需要做如下的规定,那么就能满足對的逻辑结构: 1. heap[0]位空置不用。 2. heap[1]为根节点。 3. heap[2~3]为第二层,heap[4~7] 为第三层 ... heap[2^n ~ 2^(n+1)-1]为第n+1层 这样,元素在数组的哪个位置,我们就能知道它属于哪一层了。 接下来要解决的问题是: 如何插入一个元素到堆中? 假设前面有N个元素了, 那么代码很简单 public final T add(T element) { ++this.size; this.heap[this.size] = element; this.upHeap(this.size); return this.heap[1]; } 两步走: s1 将元素添加到尾巴上。 s2: 由于这个元素有可能比其父节点小,所以递归地跟其父节点比较,换位置即可,这里有点冒泡的感觉。即想象把乒乓球按入水中,松手后就会上浮。 如何从堆中删除一个元素? public final T pop() { if (this.size > 0) { T result = this.heap[1]; this.heap[1] = this.heap[this.size]; this.heap[this.size] = null; --this.size; this.downHeap(1); return result; } else { return null; } } 两步走: s1: 用数组尾巴上的元素覆盖跟节点元素。 s2: 由于这个元素是否能胜任根节点这个位置还不确定,因此需要跟两个子节点比较,调整位置。这里有丝下沉的感觉。即想象把铁球丢入水中,自己就沉了下去。 这里,堆的插入和删除操作还是思路还是比较轻奇的,值得好好揣摩一番。 在Lucene中,PriorityQueue有那些应用场景呢? HitQueue, 搜索打分的核心。 FieldValueHitQueue, 按字段排序的核心。 .... 总之,该数据结构在Lucene中有30~40个子类,应用十分广泛。了解其实现机制,对于了解其他的功能大有裨益。 赞 收藏 评论 分享 举报 上一篇:ES学习笔记之-集成测试的简单学习 下一篇:ES学习笔记之--ES的集群是如何组建起来的 提问和评论都可以,用心的回复会被更多人看到 评论 发布评论 全部评论 () 最热 最新 相关文章 Calico实现原理 前言本文主要会介绍笔者在学习Calico时所总结的知识点,其中会涉及到Calico的架构、通信过程细节、环境要求以及各种工作模式的细节等方面的相关内容。笔者也会将自己的理解在文中进行阐述,这也算是在和大家交流心得的一个过程。若文中有错误的理解和概念,请大家及时纠正;吸纳大家的建议,对于我来说也是很重要的学习过程之一。1.概述Calico是纯三层的SDN实现,它基于BPG协议和Linux自 calico kubernetes docker 容器网络 BGP Flannel原理解析 前言本文主要会介绍笔者在学习Flannel时所总结的知识点,其中会涉及到Flannel的架构、各种Backend的实现原理等方面的相关内容。笔者也会将自己的理解在文中进行阐述,这也算是在和大家交流心得的一个过程。若文中有错误的理解和概念,请大家及时纠正;吸纳大家的建议,对于我来说也是很重要的学习过程之一。1.概念Flannel是CoreOS开发的容器网络解决方案。在Flannel中,每 flannel Flannel 容器网络 overlay underlay Kubernetes Controller实现原理 前言本文主要会介绍笔者在学习Kubernetes中的控制器模式以及Controller实现原理时所总结的知识点,其中会涉及到控制器模式设计思想以及实现原理、Controller对象实现原理以及自定义Controller的实现方式等方面的相关内容。笔者也会将自己的理解在文中进行阐述,这也算是在和大家交流心得的一个过程。若文中有错误的理解和概念,请大家及时纠正;吸纳大家的建议,对于我来说也是很重要 controller 控制循环 informer control loop 自定义控制器 lucene原理 Lucene的概述: Lucene(发音为 ['lusen] )是一个非常优秀的开源的全文搜索引擎,我们可以在它的上面开发出各种全文搜索的应用来。Lucene在国外有很高的知名度,现在已经是Apache的顶级项目,在国内,Lucene的应用也越来越多。Lucene的算法原理: Lucene是一个高性能的java全文检索工具包,它使用的是倒排文件索引结构。该结构及相应的生成算法如下: 职场 休闲 LUCENE lucene的原理 想想我们生活中的字典 前面有相关的索引,然后索引对应具体的内容,lucene也是一样。创建索引分为5步,原始文档 spring.txt springmvc.txt获取文档创建文档对象 Document 对象 文件名称 文件内容 文件路径 文件大小分析文档 Term file_content spring Term file_content frame lucene教程 lucene学习 Lucene的工作原理 以下就是我记录了他们关于Lucene的资料,我总结如下:(在文章最后我会标明出处!)Lucene的概述: Lucene(发音为 ['lusen] )是一个非常优秀的开源的全文搜索引擎,我们可以在它的上面开发出各种全文搜索的应用来。Lucene在国外有很高的知名度,现在已经是Apache的顶级项目,在国内,Lucene的应用也越来越多。Lucene的算法原理: Lucen lucene 工作 全文检索 数据库 语言 lucene基本操作及原理 把实体对象Article保存到文件中进行查找public class Article { private Long id; private String title; private String content; public Long getId() { return id; } public void setId( lucene 深入理解lucene原理 文章链接 其它 [转]Lucene倒排索引原理 Lucene是一个高性能的java全文检索工具包,它使用的是倒排文件索引结构。该结 lucene 索引 字符串 倒排索引 lucene原理及java实现 lucene原理 全文搜索 lucene 搜索 数据 lucene字典实现原理——FST 1 lucene字典 使用lucene进行查询不可避免都会使用到其提供的字典功能,即根据给定的term找到该term所对应的倒排文档id列表等信息。实际上lucene索引文件后缀名为tim和tip的文件实现的就是lucene的字典功能。 怎么实现一个字典呢?我们马上想到排序数组,即term字典是一个已经按字母顺序排序好 搜索引擎 数据结构 lucene 数组 【转】Lucene工作原理——反向索引 【转】Lucene工作原理——反向索引 - 佛光剑 - 博客园 秋石车神随笔 - 59, 文章 - 0, 评论 - 1, 引用 - 0 【转】Lucene工作原理——反向索引 lucene 倒排索引 属性值 【ElasticSearch】lucene字典实现原理——FST 一、参考资料lucene字典实现原理——FST - bonelee elasticsearch lucene 搜索引擎 参考资料 实现原理 lucene索引查看 lucene索引原理 基于Lucene检索引擎我们开发了自己的全文检索系统,承担起后台PB级、万亿条数据记录的检索工作,这里向大家分享下Lucene底层原理研究和一些优化经验。 从两个方面介绍: 1. Lucene简介和索引原理 2. Lucene优化经验总结Lucene简介和索引原理 该部分从三方面展开:Lucene简介、索引原理、Lucene索引实现。1.1 Lucene简介 Lucen lucene索引查看 跳跃表 倒排索引 理论基础 Lucene 工作原理 Lucene是一个高性能的java全文检索工具包,它使用的是倒排文件索引结构。该结构及相应的生成算法如下: 0)设有两篇文章1和2 文章1的内容为:Tom lives in Guangzhou,I liv... lucene 倒排索引 字符串 后缀 Lucene索引查看工具 lucene索引原理 Lucene:基于传统全文检索引擎的倒排索引,并实现了分块索引。与倒排所引相对立的是正排索引,也成为正向所引。Lucene:简单的说,可以认为是围绕索引展开的,索引包含的内容比较广且复杂。接下来,将简单介绍。1 正排索引(forward index)由key查询实体的过程,是正排索引.在搜索引擎中每个文件都对应一个文件ID,文件内容被表示为一系列关键词的集合 Map< id,list< Lucene索引查看工具 正排索引 倒排所引 Lucene 倒排索引 lucene索引null lucene建立索引原理 Lucene是全文检索,全文检索是计算机程序通过扫描文章中的每一个词,对每一个词建立索引,并指明该词在文章中出现的次数和位置。当用户查询时根据建立的索引进行查找,就好像我们使用字典的检索来查字一样。Lucene的原理先来讲一讲Lucene的原理先是根据对象文件或数据创建索引库,索引库中是二进制形式的文件。索引库中分为目录区域和数据区域。比如: 这个分词是根据所使用的分词器来决定的。索引库 lucene索引null Lucene lucene apache analyzer lucene 批量更新索引 lucene建立索引原理 一.lucene原理 Lucene 是apache软件基金会一个开放源代码的全文检索引擎工具包,是一个全文检索引擎的架构,提供了完整的查询引擎和索引引擎,部分文本分析引擎。它不是一个完整的搜索应用程序,而是为你的应用程序提供索引和搜索功能。lucene 能够为文本类型的数据建立索引,所以你只要能把你要索引的数据格式转化的文本的,Lucene 就能对你的文档进行索 lucene 批量更新索引 lucene 搜索 apache lucene在内存里创建索引 lucene索引原理 背景都知道lucene使用倒排索引来搜索文档,哪倒排索引究竟是个什么呢?倒排索引是区分于正排索引的概念正排索引:以文档的唯一id作为索引,以文档的内容作为记录的结构 倒排索引:以文档中内容的单词作为的索引,以文档的id作为内容的结构相比关系数据库使用的“like %XX%”查询,倒排索引有什么优点搜索效率更高,like“%xx%”,无法使用索引,会走全表扫描,效率差可以实现更复杂的搜索场景,lik lucene在内存里创建索引 elasticsearch 性能优化 搜索引擎 lucene Lucene底层原理和优化经验分享(1)-Lucene简介和索引原理 Lucene底层原理和优化经验分享(1)-Lucene简介和索引原理2017年01月04日 08:52:12阅读数:18366 基于Lucene检索引擎我们开发了自己的全文检索系统,承担起后台PB级、万亿条数据记录的检索工作,这里向大家分享下Lucene底层原理研究和一些优化经验。 从两个方面介绍: 1. Lucene简介和索引原理 2. Lucene优化经验 lucene 后缀 elasticsearch 跳跃表 倒排索引