侧边栏壁纸
  • 累计撰写 98 篇文章
  • 累计创建 20 个标签
  • 累计收到 3 条评论

Lucene学习笔记

林贤钦
2020-12-05 / 0 评论 / 0 点赞 / 732 阅读 / 5,985 字
温馨提示:
本文最后更新于 2021-03-03,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

Lucene学习笔记

说明:本文只针对Lucene原理探究,不针对luceneAPI进行研究

一、Lucene简介

Lucene是一个全文搜索框架,不是应用产品,并不包含搜索引擎系统,它包含了索引结构、读写索引工具、相关性工具、排序等功能。因此在使用Lucene时仍需要关注搜索引擎系统,例如数据获取、解析、分词等方面的东西。而solr和elasticsearch都是基于该工具包做的一些封装。

(1)为什么要学习Lucene

我们都知道全文搜索,我了解到lucene也是通过ElasticSearch,因为es就是基于lucene工具包进行分装成一个以Restful风格的全文检索服务器,我们以我们平时搜索百度浏览器的情况进行分析。

如果不使用Lucene或者基于lucene封装的es,solr,那么我们的搜索可能是这样的,这就是原始搜索引擎技术,如果用户比较少而且数据库的数据量比较小,那么这种方式实现搜索功能在企业中是比较常见的。

image-20201205135901178

如果使用lucene库查询数据,那么请求将会是这样,那么为什么使用lucene查询数据会比mysql的快?

image-20201205140309662

全文索引到底是什么,底层又是通过什么样的技术实现的或者说是通过什么原理能够让百度那么大的一个索引库快速的将数据展示到用户面前?而且我们搜索的内容不一定全是数据库能存储的,有些数据是mysql无法存储的,比如非结构化数据。

(2)什么是全文检索技术

全文搜索引擎就是通过从互联网上提取的各个网站的信息(以网页文字为主)而建立的数据库中,检索与用户查询条件匹配的相关记录,然后按一定的排列顺序将结果返回给用户。《百度百科》

从计算机的角度来讲,就是计算机索引程序通过扫描文章的每个词,对每个词建立一个索引,指明该词在文章中出现的次数和位置,当用户查询的时候,检索程序就根据事先建立的索引进行查找,并将查找的结果反馈给用户的检索方式。

是如何建立索引,如何记录,又是怎么返回,lucene通过倒排索引的技术思想

(3)什么是倒排索引

非结构化数据的查询方法有两种,顺序扫描法和倒排索引

  • 顺序扫描法:所谓的顺序扫描,就是从上到下一个一个检索查找

    比如我们要查找内容包含某个字符串的文件,那么就需要一个一个文件从头到尾的查找遍历,这样的好处是查找的准确率高,但是这会随着查找数据量的增大,越来越慢

  • 倒排索引:倒排索引就是文件在存储的时候,会按照我们设定的规则进行存储,查询前会先将查询的内容提取出来组成文档(正文),对文档进行切分词组成目录(索引),查询的时候会先查询索引,通过索引查找文档,这个过程就叫全文检索。

    例如我们使用新华字典查询汉字,新华字典有偏旁部首的目录(索引),我们查字首先查这个目录,找到这个目录中对应的偏旁部首,就可以通过这个目录中的偏旁部首找到这个字所在的位置(文档)。

倒排索引的优点就是查询的准确率高,而且查询速度非常快,不会因为数据量的增大,而使得查询数据变慢,但是会额外占用一些磁盘的空间来维护索引等数据。

说这么多,还是没说lucene的原理,细节是怎么实现这个过程的。

二、lucene的索引文件结构

(1)索引文件结构

lucene的索引结构包括:索引(index)、段(segment)、文档(document)、域(Field)、词(Term),那么它们之间又有什么关系呢?

image-20201205152341953

  • 索引(Index):Lucene的索引由多个文件组成,这些文件放在同一个目录下,同一文件夹的所有文件构成一个Lucene索引
  • 段(Segment):一个索引可以包含多个段,段与段之间是相互独立的,添加新文档可以生成新的段,不同段可以合并。
  • 文档(document):文档是我们建立索引的基本单位,不同的文档保存在不同的段中,一个段又可以包含多个文档,新添加的文档是单独保存在一个新生成的段中,随着段的合并,不同的文段又会合并到同一个段中。
  • 域(Field):一篇文档包含不同类型的信息,可以分开索引,比如标题,时间,正文,作者等信息,都可以保存到域中,域你甚至可以比喻成数据库中的列。
  • 词(Term):词是索引的最小单位,是经过词法分析和语言处理后的字符串。

(2)结构的信息

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

  • 正向信息:也就是按图一般,从索引到词的包含关系:索引(index)->段(segment)->文档(document)->域(Field)->词(Term),也就是索引包含了哪些段,段由保存了哪些文档的位置,文档又包含了域,而域就包含了切分词后词的位置。
  • 反向信息:体现了倒排索引的精髓,保存了词典倒排表的映射。比如我们全文检索的时候,是如何通过词查找到文档的过程,关键字->文档号->出现的位置。

这里还是有个问题,关键字那么多,中文加英文相当于中华大词典+英文牛津词典的目录,我们查找的时候将查找词切分词后,总不能从头到位一个一个遍历查找吧?这样效率就太差了,那么是通过什么算法实现的呢?

(3)词典数据结构对比

倒排索引中的词典位于内存,其结构尤为重要,有很多种词典结构,各有各的优缺点,最简单如排序数组,通过二分查找来检索数据,更快的有哈希表,磁盘查找有B树、B+树,但一个能支持TB级数据的倒排索引结构需要在时间和空间上有个平衡,下图列了一些常见词典的优缺点:

跳跃表占用内存小,且可调,但是对模糊查询支持不好
排序列表Array/List使用二分法查找,不平衡
字典树查询效率跟字符串长度有关,但只适合英文词典
哈希表性能高,内存消耗大,几乎是原始数据的三倍
双数组字典树适合做中文词典,内存占用小,很多分词工具均采用此种算法
Finite State Transducers (FST)一种有限状态转移机,Lucene 4有开源实现,并大量使用
B树磁盘索引,更新方便,但检索速度慢,多用于数据库

Lucene3.0之前使用的也是跳跃表结构,后换成了FST,但跳跃表在Lucene其他地方还有应用如倒排表

合并和文档号索引。

3.1、跳跃表的原理

优点 :结构简单、跳跃间隔、级数可控,Lucene3.0之前使用的也是跳跃表结构,但跳跃表在

Lucene其他地方还有应用如倒排表合并和文档号索引。 缺点 :模糊查询支持不好

image-20201205154413067

在顺序单链表中,我们要找到49这个节点,那么我们需要遍历这个有序链表,从7找到49,如果数据量非常大,那么速度将非常慢。

image-20201205154957732

而在跳跃表中,我们从7找到49的节点,7->28->42->49,就跟我们查找词典一样,先找到第几章,然后第几节,再查找具体的位置。数据量越大,跳跃表的优势越强大,比如牛津词典。

3.2、FST原理简析

lucene从4开始大量使用的数据结构是FST(Finite State Transducer)。

FST有两个优点

  • 空间占用小。通过对词典中单词前缀和后缀的重复利用,压缩了存储空间;

  • 查询速度快。O(len(str))的查询时间复杂度。

我们对“cat”、 “deep”、 “do”、 “dog” 、“dogs”这5个单词进行插入构建FST(注:必须已排序)。

image-20201205160532048

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

三、Lucene全文检索的流程

知道了索引文件的结构,知道了跳跃表以及FST的原理,那么Lucene检索数据的流程是怎么样的?

索引和搜索流程图

image-20201205162919505

索引整个流程可以分析为:原始内容->获得文档->创建文档->分析文档->索引文档

  • 原始内容:索引和搜索的内容,包括互联网上的网页、数据库中的数据、磁盘上的文件等。

  • 获得文档:从互联网上、数据库、文件系统中等获取需要搜索的原始信息,这个过程就是信息采集,采集数据的目的是为了对原始内容进行索引

  • 创建文档:获取原始内容的目的是为了索引,在索引前需要将原始内容创建成文档(Document),文档中包括一个一个的域(Field),域中存储内容。

  • 分析文档:将原始内容创建为包含域(Field)的文档(document),需要再对域中的内容进行分析,分析成为一个一个的单词。

  • 索引文档:对所有文档分析得出的语汇单元进行索引,索引的目的是为了搜索,最终要实现只搜索被索引的语汇单元从而找到Document(文档)。

搜索流程可以分析为:用户搜索关键字->创建索引->执行搜索->渲染结果返回用户界面

  • 用户搜索关键字:用户输入查询关键字
  • 创建查询:用户输入查询关键字执行搜索之前需要先构建一个查询对象,查询对象中可以指定查询要查询关键字、要搜索的Field文档域等,查询对象会生成具体的查询语法
  • 执行搜索:根据查询语法在倒排索引词典表中分别找出对应搜索词的索引,从而找到索引所链接的文档链表。
  • 渲染结果返回用户界面:将查询到的文档数据经过服务器渲染结果后返回用户界面

四、Lucene使用注意事项

  • 关键词区分大小写 OR AND TO等关键词是区分大小写的,lucene只认大写的,小写的当做普通单词。
  • 读写互斥性 同一时刻只能有一个对索引的写操作,在写的同时可以进行搜索
  • 文件锁 在写索引的过程中强行退出将在tmp目录留下一个lock文件,使以后的写操作无法进行,可以将其手工删除
  • 时间格式 lucene只支持一种时间格式yyMMddHHmmss,所以你传一个yy-MM-dd HH:mm:ss的时间给lucene它是不会当作时间来处理的
  • 设置boost 有些时候在搜索时某个字段的权重需要大一些,例如你可能认为标题中出现关键词的文章比正文中出现关键词的文章更有价值,你可以把标题的boost设置的更大,那么搜索结果会优先显示标题中出现关键词的文章.

《参考文献》

0

评论区