Talk is Cheap, Show me the Code! <<网站首页文章列表

  • 搜索引擎进阶——Lucene链表操作解析

    说到搜索引擎,大家都不会陌生,尤其是互联网从业者更是如此。而大部分程序员都能对其基本原理说个七七八八,比如分词、倒排链表、空间向量模型、余弦定理、Top-N......。而且对于全文检索的两个过程索引和查询也都知道个大概。+ 索引:对数据进行分词,然后按照分词结果生成倒排链表(包含词频、位置等信息),最后生成索引文件。+ 查询:对查询语句进行分词,综合其他查询条件生成查询树并优化;对查询树进行倒排链表匹配,将匹配到的链表按照查询语义进行操作(交集、并集、差集等);最后按照打分规则进行排序并分页返回结果。当然真正的实现细节会复杂许多,比如数据结构、数据类型定义、索引存储、数据压缩、相关链表操作算法、跳跃表、打分模型、内存索引切换等等,都是需要考虑的地方。 链表操作前面介绍的那些内容中,有一个是非常重要而且相对来说比较容易看懂和说明白的就是链表操作。何为链表操作?每个Term后面都挂有一个链表,链表的元素主要包含的内容有元素的DocId(这是Lucene给每个文档的自增编号)、Frequency(这是分词在对应文档中出现的频率)。实际上,每个链表元素就对应一篇当初索引的文档,所以链表操作就是对这些文档进行交集、差集、并集的操作。例,有如下几篇文档: A:机器学习最通俗的解释就是让机器学会决策。 B:支持向量机(SVM)是90年代中期发展起来的基于统计学习理论的一种机器学习方法。 C:随机森林的基本单元是决策树。 D:分类和回归是机器学习解决的两大主要问题。 E:古典决策理论盛行于20世纪初到50年代期间。 F:分类树(决策树)是一种十分常用的分类方法,是一种有监督的机器学习方法。现在我们只考虑其中几个分词,而且暂时忽略分词的歧义性,那么简易

    链表   交集   并集   差集   Lucene   Java   搜索引擎   2019-08-13 浏览(723) 阅读原文>>
  • 应用算法学习(一)—— TopN算法

    零、应用场景最早接触这个算法,是在看Lucene实现原理相关代码的时候。搜索返回查询结果就是一个很典型的TopN算法应用,获取综合分数最高的前N个结果。搜索场景,通常数据量会在百万级、千万级甚至更多,因此,获取分数最高的前N个结果的性能好坏直接影响搜索体验。获取前N个得分最高的结果,可以有不同的方法:1. 直接对数据(Item)集进行排序,然后截取前N个Item;那么,排序算法会对性能有较大影响。例如快排的时间复杂度在O(n)到O(nn)之间,平均复杂度是O(nlog(n))。2. 对所有Item进行一次遍历,对于遍历每个Item的时候,始终有一个临时结果集来保存当前情况下的可能结果集,当遍历结束时,临时结果集就是最终结果,只要按顺序输出即可。本身遍历比较简单,那么选择临时结果集的数据结构就是算法的关键。我们对临时结果集的数据结构有几个要求: 1. 数据结构本身可以有序输出Item。 2. 可以快速新增一个Item,而且可以保持i中的特性。 3. 可以快速判断是否需要替换Item,且替换之后可以保持i中的特性。--- 一、算法简介Lucene中使用的最小二叉堆,就是满足了上面第二点中提出的要求(堆特性)。 最小二叉堆:父节点不大于其两个子节点,两个子节点直接的大小比较没有要求。堆顶是所有节点中最小的,但是最终整个堆返回的就是前N个最大值。解释: 堆顶最小的目的是,在遍历时,如果发现某个Item的值大于堆顶(找出前N个最大的要求就是,用某个Item替换掉临时结果集中最小的,堆顶始终最小的话就可以很方便判断Item是否可以入堆,而且直接删除被替换的堆顶),则可以替换掉当前堆顶,然后执行节点沉降,以便保持特性。它的时间复杂度为 O(nlog(n))。 主要过程1. 遍历目标集,每次遍历的数据节

    topN   二叉堆   Lucene   搜索引擎   2018-09-20 浏览(2311) 阅读原文>>
  • 1 
    blogTest
    分享文章
     
    使用APP的"扫一扫"功能,扫描左边的二维码,即可将网页分享给别人。
    你也可以扫描右边本博客的小程序二维码,实时关注最新文章。