精华内容
下载资源
问答
  • Lucene 倒排索引原理

    2021-02-04 10:51:17
    1 前言 Lucene 作为 Apache 开源的一款搜索工具,一直以来是实现搜索...因此,本文将介绍一下倒排索引的概念以及倒排索引Lucene 中的实现。 2 基本原理 2.1 什么是倒排索引 搜索的核心需求是全文检索,全文检索简单

    1 前言

    Lucene 作为 Apache 开源的一款搜索工具,一直以来是实现搜索功能的神兵利器,现今火热的 Solr 和 Elasticsearch 均基于该工具包进行开发,我们搜索召回组这边也是基于 Lucene 实现了一套索引构建机制,用于酒店搜索、门票搜索、大搜等搜索相关业务。

    而 Lucene 之所以能在搜索中发挥至关重要的作用正是因为倒排索引。

    因此,本文将介绍一下倒排索引的概念以及倒排索引在 Lucene 中的实现。

    2 基本原理

    2.1 什么是倒排索引

    搜索的核心需求是全文检索,全文检索简单来说就是要在大量文档中找到包含某个单词出现的位置,在传统关系型数据库中,数据检索只能通过 like 来实现,例如需要在酒店数据中查询名称包含公寓的酒店,需要通过如下 sql 实现:

    select * from hotel_table where hotel_name like '%公寓%';
    

    这种实现方式实际会存在很多问题:

    • 无法使用数据库索引,需要全表扫描,性能差
    • 搜索效果差,只能首尾位模糊匹配,无法实现复杂的搜索需求
    • 无法得到文档与搜索条件的相关性

    搜索的核心目标实际上是保证搜索的效果和性能,为了高效的实现全文检索,我们可以通过倒排索引来解决。

    倒排索引是区别于正排索引的概念:

    • 正排索引:是以文档对象的唯一 ID 作为索引,以文档内容作为记录的结构。
    • 倒排索引:Inverted index,指的是将文档内容中的单词作为索引,将包含该词的文档 ID 作为记录的结构。

    在这里插入图片描述
    下面通过一个例子来说明下倒排索引的生成过程。
    假设目前有以下两个文档内容:

    苏州街维亚大厦

    桔子酒店苏州街店

    其处理步骤如下:

    1、正排索引给每个文档进行编号,作为其唯一的标识。
    在这里插入图片描述
    2、生成倒排索引:

    • a.首先要对字段的内容进行分词,分词就是将一段连续的文本按照语义拆分为多个单词,这里两个文档包含的关键词有:苏州街、维亚大厦…
    • b.然后按照单词来作为索引,对应的文档 id 建立一个链表,就能构成上述的倒排索引结构。

    在这里插入图片描述
    有了倒排索引,能快速、灵活地实现各类搜索需求。整个搜索过程中我们不需要做任何文本的模糊匹配。

    例如,如果需要在上述两个文档中查询 苏州街桔子 ,可以通过分词后通过 苏州街 查到 12,通过 桔子 查到 2,然后再进行取交取并等操作得到最终结果。

    在这里插入图片描述

    2.2 倒排索引的结构

    根据倒排索引的概念,我们可以用一个 Map来简单描述这个结构。这个 Map 的 Key 的即是分词后的单词,这里的单词称为 Term,这一系列的 Term 组成了倒排索引的第一个部分 —— Term Dictionary (索引表,可简称为 Dictionary)。

    倒排索引的另一部分为 Postings List(记录表),也对应上述 Map 结构的 Value 部分集合。

    记录表由所有的 Term 对应的数据(Postings) 组成,它不仅仅为文档 id 信息,可能包含以下信息:

    • 文档 id(DocId, Document Id),包含单词的所有文档唯一 id,用于去正排索引中查询原始数据。
    • 词频(TF,Term Frequency),记录 Term 在每篇文档中出现的次数,用于后续相关性算分。
    • 位置(Position),记录 Term 在每篇文档中的分词位置(多个),用于做词语搜索(Phrase Query)。
    • 偏移(Offset),记录 Term 在每篇文档的开始和结束位置,用于高亮显示等。
      在这里插入图片描述

    3 Lucene 倒排索引实现

    全文搜索引擎在海量数据的情况下是需要存储大量的文本,所以面临以下问题:

    • Dictionary 是比较大的(比如我们搜索中的一个字段可能有上千万个 Term)
    • Postings 可能会占据大量的存储空间(一个Term多的有几百万个doc)

    因此上面说的基于 Map 的实现方式几乎是不可行的。

    在海量数据背景下,倒排索引的实现直接关系到存储成本以及搜索性能。

    为此,Lucene 引入了多种巧妙的数据结构和算法。其倒排索引实现拥有以下特性:

    • 以较低的存储成本存储在磁盘 (索引大小大约为被索引文本的20-30%)
    • 快速读写

    下面将根据倒排索引的结构,按 Posting List 和 Terms Dictionary 两部分来分析 Lucene 中的实现。

    3.1 Posting List 实现

    PostingList 包含文档 id、词频、位置等多个信息,这些数据之间本身是相对独立的,因此 Lucene 将 Postings List 被拆成三个文件存储:

    • .doc后缀文件:记录 Postings 的 docId 信息和 Term 的词频
    • .pay后缀文件:记录 Payload 信息和偏移量信息
    • .pos后缀文件:记录位置信息

    基本所有的查询都会用 .doc 文件获取文档 id,且一般的查询仅需要用到 .doc 文件就足够了,只有对于近似查询等位置相关的查询则需要用位置相关数据。

    三个文件整体实现差不太多,这里以.doc 文件为例分析其实现。

    .doc 文件存储的是每个 Term 对应的文档 Id 和词频。每个 Term 都包含一对 TermFreqs 和 SkipData 结构。

    其中 TermFreqs 存放 docId 和词频信息,SkipData 为跳表信息,用于实现 TermFreqs 内部的快速跳转。

    在这里插入图片描述

    3.1.1 TermFreqs

    TermFreqs 存储文档号和对应的词频,它们两是一一对应的两个 int 值。Lucene 为了尽可能的压缩数据,采用的是混合存储 ,由 PackedBlock 和 VIntBlocks 两种结构组成。

    PackedBlock

    其采用 PackedInts 结构将一个 int[] 压缩打包成一个紧凑的 Block。它的压缩方式是取数组中最大值所占用的 bit 长度作为一个预算的长度,然后将数组每个元素按这个长度进行截取,以达到压缩的目的。

    例如:一个包含128个元素的 int 数组中最大值的是 2,那么预算长度为2个 bit, PackedInts 的长度仅是 2 * 128 / 8 = 32个字节,然后就可以通过4个 long 值存储。
    在这里插入图片描述
    VIntBlock

    VIntBlock 是采用 VInt 来压缩 int 值,对于绝大多数语言,int 型都占4个字节,不论这个数据是1、100、1000、还是1000,000。VInt 采用可变长的字节来表示一个整数。数值较大的数,使用较多的字节来表示,数值较少的数,使用较少的字节来表示。每个字节仅使用第1至第7位(共7 bits)存储数据,第8位作为标识,表示是否需要继续读取下一个字节。

    举个例子:

    整数130为 int 类型时需要4个字节,转换成 VInt 后仅用2个字节,其中第一个字节的第8位为1,标识需要继续读取第二个字节。

    在这里插入图片描述
    根据上述两种 Block 的特点,Lucene 会每处理包含 Term 的128篇文档,将其对应的 DocId 数组和 TermFreq 数组分别处理为 PackedDocDeltaBlock 和 PackedFreqBlock 的 PackedInt 结构,两者组成一个 PackedBlock,最后不足128的文档则采用 VIntBlock 的方式来存储。

    在这里插入图片描述

    3.1.2 SkipData

    在搜索中存在将每个 Term 对应的 DocId 集合进行取交集的操作,即判断某个 Term 的 DocId 在另一个 Term 的 TermFreqs 中是否存在。TermFreqs 中每个 Block 中的 DocId 是有序的,可以采用顺序扫描的方式来查询,但是如果 Term 对应的 doc 特别多时搜索效率就会很低,同时由于 Block 的大小是不固定的,我们无法使用二分的方式来进行查询。因此 Lucene 为了减少扫描和比较的次数,采用了 SkipData 这个跳表结构来实现快速跳转。

    跳表

    跳表是在原有的有序链表上面增加了多级索引,通过索引来实现快速查找。

    实质就是一种可以进行二分查找的有序链表。
    在这里插入图片描述
    SkipData结构

    在 TermFreqs 中每生成一个 Block 就会在 SkipData 的第0层生成一个节点,然后第0层以上每隔 N 个节点生成一个上层节点。

    每个节点通过 Child 属性关联下层节点,节点内 DocSkip 属性保存 Block 的最大的 DocId 值,DocBlockFP、PosBlockFP、PayBlockFP 则表示 Block 数据对应在 .pay、.pos、.doc 文件的位置。
    在这里插入图片描述

    3.1.3 Posting 最终数据

    Posting List 采用多个文件进行存储,最终我们可以得到每个 Term 的如下信息:

    • SkipOffset:用来描述当前 term 信息在 .doc 文件中跳表信息的起始位置。
    • DocStartFP:是当前 term 信息在 .doc 文件中的文档 ID 与词频信息的起始位置。
    • PosStartFP:是当前 term 信息在 .pos 文件中的起始位置。
    • PayStartFP:是当前 term 信息在 .pay 文件中的起始位置。

    3.2 Term Dictionary 实现

    Terms Dictionary(索引表)存储所有的 Term 数据,同时它也是 Term 与 Postings 的关系纽带,存储了每个 Term 和其对应的 Postings 文件位置指针。
    在这里插入图片描述

    3.2.1 数据存储

    Terms Dictionary 通过 .tim 后缀文件存储,其内部采用 NodeBlock 对 Term 进行压缩前缀存储,处理过程会将相同前缀的的 Term 压缩为一个 NodeBlock,NodeBlock 会存储公共前缀,然后将每个 Term 的后缀以及对应 Term 的 Posting 关联信息处理为一个 Entry 保存到 Block。
    在这里插入图片描述

    在上图中可以看到 Block 中还包含了 Block,这里是为了处理包含相同前缀的 Term 集合内部部分 Term 又包含了相同前缀。

    举个例子,在下图中为公共前缀为 a 的 Term 集合,内部部分 Term 的又包含了相同前缀 ab,这时这部分 Term 就会处理为一个嵌套的 Block。

    在这里插入图片描述

    3.2.2 数据查找

    Terms Dictionary 是按 NodeBlock 存储在.tim 文件上。当文档数量越来越多的时,Dictionary 中的 Term 也会越来越多,那查询效率必然也会逐渐变低。

    因此需要一个很好的数据结构为 Dictionary 建构一个索引,这就是 Terms Index(.tip文件存储),Lucene 采用了 FST 这个数据结构来实现这个索引。

    FST

    FST, 全称 Finite State Transducer(有限状态转换器)。

    它具备以下特点:

    • 给定一个 Input 可以得到一个 output,相当于 HashMap
    • 共享前缀、后缀节省空间,FST 的内存消耗要比 HashMap 少很多
    • 词查找复杂度为 O(len(str))
    • 构建后不可变更

    如下图为 mon/1,thrus/4,tues/2 生成的 FST,可以看到 thrus 和 tues 共享了前缀 t 以及后缀 s。
    在这里插入图片描述
    根据 FST 就可以将需要搜索 Term 作为 Input,对其途径的边上的值进行累加就可以得到 output,下述为以 input 为 thrus 的读取逻辑:

    • 初始状态0
    • 输入t, FST 从0 -> 3, output=2
    • 输入h,FST 从3 -> 4, output=2+2=4
    • 输入r, FST 从4 -> 5, output=4+0
    • 输入u,FST 从5 -> 7, output=4+0
    • 输入s, FST 到达终止节点,output=4+0=4

    那么 Term Dictionary 生成的 FST 对应 input 和 output 是什么呢?可能会误认为 FST 的 input 是 Dictionary 中所有的 Term,这样通过 FST 就可以找到具体一个 Term 对应的 Posting 数据。

    实际上 FST 是通过 Dictionary 的每个 NodeBlock 的前缀构成,所以通过 FST 只可以直接找到这个 NodeBlock 在 .tim 文件上具体的 File Pointer, 然后还需要在 NodeBlock 中遍历 Entry 匹配后缀进行查找。

    因此它在 Lucene 中充当以下功能:

    1. 快速试错,即是在 FST 上找不到可以直接跳出不需要遍历整个 Dictionary,类似于 BloomFilter。
    2. 快速定位 Block 的位置,通过 FST 是可以直接计算出 Block 的在文件中位置。
    3. FST 也是一个 Automation(自动状态机)。这是正则表达式的一种实现方式,所以 FST 能提供正则表达式的能力。通过 FST 能够极大的提高近似查询的性能,包括通配符查询、SpanQuery、PrefixQuery 等。

    3.3 倒排查询逻辑

    在介绍了索引表和记录表的结构后,就可以得到 Lucene 倒排索引的查询步骤:

    • 通过 Term Index 数据(.tip文件)中的 StartFP 获取指定字段的 FST
    • 通过 FST 找到指定 Term 在 Term Dictionary(.tim 文件)可能存在的 Block
    • 将对应 Block 加载内存,遍历 Block 中的 Entry,通过后缀(Suffix)判断是否存在指定 Term
    • 存在则通过 Entry 的 TermStat 数据中各个文件的 FP 获取 Posting 数据
    • 如果需要获取 Term 对应的所有 DocId 则直接遍历 TermFreqs,如果获取指定 DocId 数据则通过 SkipData快速跳转
      在这里插入图片描述

    4 Lucene 数值类型处理

    上述 Terms Dictionary 与 Posting List 的实现都是处理字符串类型的 Term,而对于数值类型,如果采用上述方式实现会存在以下问题:

    • 数值潜在的 Term 可能会非常多,比如是浮点数,导致查询效率低
    • 无法处理多维数据,比如经纬度

    所以 Lucene 为了支持高效的数值类或者多维度查询,引入了 BKDTree。

    4.1 KDTree

    BKDTree 是基于 KDTree,KDTree 实现起来很像是一个二叉查找树。主要的区别是,KDTree 在不同的层使用的是不同的维度值。

    下面是一个2维树的样例 ,其第一层以 x 为切分维度,将 x>30的节点传递给右子树,x<30的传递给左子树,第二层再按 y 维度切分,不断迭代到所有数据都被建立到 KD Tree 的节点上为止。

    在这里插入图片描述

    4.2 BKDTree

    BKD 树是 KD 树和 B+ 树的组合,拥有以下特性:

    • 内部 node 必须是一个完全二叉树
    • 叶子节点存储点数据,降低层高度,减少磁盘 IO

    在这里插入图片描述

    5 总结

    本文先介绍了倒排索引的概念和结构,然后对 Lucene 倒排索引的 Terms Dictionary 和 Posting List 的整体结构以及倒排索引的查询逻辑,最后介绍了 Lucene 对数值类型所做的处理。

    倒排索引有效的解决了搜索中的很多问题,而 Lucene 对倒排索引的实现包含了很多巧妙的结构和设计,对数据存储压缩以及查询很有借鉴意义,值得深入学习。

    参考资料

    Lucene 源码分析:https://www.amazingkoala.com.cn/Lucene/
    Lucene BKD 树:https://www.shenyanchao.cn/blog/2018/12/04/lucene-bkd/
    Lucene 查询原理及解析 :https://www.infoq.cn/article/ejEG02VRoeGVaLw4j_LL
    Lucene 倒排索引探秘:https://www.6aiq.com/article/1564413040138 Lucene
    词典 FST 深入剖析:https://www.shenyanchao.cn/blog/2018/12/04/lucene-fst/

    展开全文
  • Lucene倒排索引原理

    2014-07-07 10:52:19
    Lucene倒排索引原理 转自:http://dev.csdn.net/author/kingjIang/28cf4f5f62ca4bb696c43d5c438e79f7.html Lucene是一个高性能的java全文检索工具包,它使用的是倒排文件索引结构。该结构及相应的生成算法如下:...

    Lucene倒排索引原理

    转自:http://dev.csdn.net/author/kingjIang/28cf4f5f62ca4bb696c43d5c438e79f7.html

    Lucene是一个高性能的java全文检索工具包,它使用的是倒排文件索引结构。该结构及相应的生成算法如下:
      
      0)设有两篇文章1和2
      文章1的内容为:Tom lives in Guangzhou,I live in Guangzhou too.
      文章2的内容为:He once lived in Shanghai.
      
      1)由于lucene是基于关键词索引和查询的,首先我们要取得这两篇文章的关键词,通常我们需要如下处理措施
      a.我们现在有的是文章内容,即一个字符串,我们先要找出字符串中的所有单词,即分词。英文单词由于用空格分隔,比较好处理。中文单词间是连在一起的需要特殊的分词处理。
      b.文章中的”in”, “once” “too”等词没有什么实际意义,中文中的“的”“是”等字通常也无具体含义,这些不代表概念的词可以过滤掉
      c.用户通常希望查“He”时能把含“he”,“HE”的文章也找出来,所以所有单词需要统一大小写。
      d.用户通常希望查“live”时能把含“lives”,“lived”的文章也找出来,所以需要把“lives”,“lived”还原成“live”
      e.文章中的标点符号通常不表示某种概念,也可以过滤掉
      在lucene中以上措施由Analyzer类完成
      
      经过上面处理后
       文章1的所有关键词为:[tom] [live] [guangzhou] [i] [live] [guangzhou]
       文章2的所有关键词为:[he] [live] [shanghai]
      
      2) 有了关键词后,我们就可以建立倒排索引了。上面的对应关系是:“文章号”对“文章中所有关键词”。倒排索引把这个关系倒过来,变成:“关键词”对“拥有该关键词的所有文章号”。文章1,2经过倒排后变成
      关键词 文章号
      guangzhou 1
      he 2
      i 1
      live 1,2
      shanghai 2
      tom 1
      
      通常仅知道关键词在哪些文章中出现还不够,我们还需要知道关键词在文章中出现次数和出现的位置,通常有两种位置:a)字符位置,即记录该词是文章中第几个字符(优点是关键词亮显时定位快);b)关键词位置,即记录该词是文章中第几个关键词(优点是节约索引空间、词组(phase)查询快),lucene 中记录的就是这种位置。
      
      加上“出现频率”和“出现位置”信息后,我们的索引结构变为:
      关键词 文章号[出现频率] 出现位置
      guangzhou 1[2] 3,6
      he 2[1] 1
      i 1[1] 4
      live 1[2],2[1] 2,5,2
      shanghai 2[1] 3
      tom 1[1] 1
      
      以live 这行为例我们说明一下该结构:live在文章1中出现了2次,文章2中出现了一次,它的出现位置为“2,5,2”这表示什么呢?我们需要结合文章号和出现频率来分析,文章1中出现了2次,那么“2,5”就表示live在文章1中出现的两个位置,文章2中出现了一次,剩下的“2”就表示live是文章2中第 2个关键字。
      
      以上就是lucene索引结构中最核心的部分。我们注意到关键字是按字符顺序排列的(lucene没有使用B树结构),因此lucene可以用二元搜索算法快速定位关键词。
      
      实现时 lucene将上面三列分别作为词典文件(Term Dictionary)、频率文件(frequencies)、位置文件 (positions)保存。其中词典文件不仅保存有每个关键词,还保留了指向频率文件和位置文件的指针,通过指针可以找到该关键字的频率信息和位置信息。
      
       Lucene中使用了field的概念,用于表达信息所在位置(如标题中,文章中,url中),在建索引中,该field信息也记录在词典文件中,每个关键词都有一个field信息(因为每个关键字一定属于一个或多个field)。
      
      为了减小索引文件的大小,Lucene对索引还使用了压缩技术。首先,对词典文件中的关键词进行了压缩,关键词压缩为<前缀长度,后缀>,例如:当前词为“阿拉伯语”,上一个词为“阿拉伯”,那么“阿拉伯语”压缩为<3,语>。其次大量用到的是对数字的压缩,数字只保存与上一个值的差值(这样可以减小数字的长度,进而减少保存该数字需要的字节数)。例如当前文章号是16389(不压缩要用3个字节保存),上一文章号是16382,压缩后保存7(只用一个字节)。
      
       下面我们可以通过对该索引的查询来解释一下为什么要建立索引。
      假设要查询单词 “live”,lucene先对词典二元查找、找到该词,通过指向频率文件的指针读出所有文章号,然后返回结果。词典通常非常小,因而,整个过程的时间是毫秒级的。
      而用普通的顺序匹配算法,不建索引,而是对所有文章的内容进行字符串匹配,这个过程将会相当缓慢,当文章数目很大时,时间往往是无法忍受的。

    转自:http://www.chedong.com/tech/lucene.html

    Lucene是一个基于Java的全文索引工具包。

    1. 基于Java的全文索引引擎Lucene简介:关于作者和Lucene的历史
    2. 全文检索的实现:Luene全文索引和数据库索引的比较
    3. 中文切分词机制简介:基于词库和自动切分词算法的比较
    4. 具体的安装和使用简介:系统结构介绍和演示
    5. Hacking Lucene:简化的查询分析器,删除的实现,定制的排序,应用接口的扩展
    6. 从Lucene我们还可以学到什么
    另外,如果是在选择全文引擎,现在也许是试试Sphinx的时候了:相比Lucene速度更快,有中文分词的支持,而且内置了对简单的分布式检索的支持;

    基于Java的全文索引/检索引擎——Lucene

    Lucene不是一个完整的全文索引应用,而是是一个用Java写的全文索引引擎工具包,它可以方便的嵌入到各种应用中实现针对应用的全文索引/检索功能。

    Lucene的作者:Lucene的贡献者Doug Cutting是一位资深全文索引/检索专家,曾经是V-Twin搜索引擎(Apple的Copland操作系统的成就之一)的主要开发者,后在Excite担任高级系统架构设计师,目前从事于一些INTERNET底层架构的研究。他贡献出的Lucene的目标是为各种中小型应用程序加入全文检索功能。

    Lucene的发展历程:早先发布在作者自己的www.lucene.com,后来发布在SourceForge,2001年年底成为APACHE基金会jakarta的一个子项目:http://jakarta.apache.org/lucene/

    已经有很多Java项目都使用了Lucene作为其后台的全文索引引擎,比较著名的有:

    • Jive:WEB论坛系统;
    • Eyebrows:邮件列表HTML归档/浏览/查询系统,本文的主要参考文档“TheLucene search engine: Powerful, flexible, and free”作者就是EyeBrows系统的主要开发者之一,而EyeBrows已经成为目前APACHE项目的主要邮件列表归档系统。
    • Cocoon:基于XML的web发布框架,全文检索部分使用了Lucene
    • Eclipse:基于Java的开放开发平台,帮助部分的全文索引使用了Lucene

    对于中文用户来说,最关心的问题是其是否支持中文的全文检索。但通过后面对于Lucene的结构的介绍,你会了解到由于Lucene良好架构设计,对中文的支持只需对其语言词法分析接口进行扩展就能实现对中文检索的支持。

    全文检索的实现机制

    Lucene的API接口设计的比较通用,输入输出结构都很像数据库的表==>记录==>字段,所以很多传统的应用的文件、数据库等都可以比较方便的映射到Lucene的存储结构/接口中。总体上看:可以先把Lucene当成一个支持全文索引的数据库系统

    比较一下Lucene和数据库:

    Lucene 数据库
    索引数据源:doc(field1,field2...) doc(field1,field2...)
                      \  indexer /
                     _____________
                    | Lucene Index|
                    --------------
                     / searcher \
     结果输出:Hits(doc(field1,field2) doc(field1...))
     索引数据源:record(field1,field2...) record(field1..)
                  \  SQL: insert/
                   _____________
                  | DB  Index   |
                   -------------
                  / SQL: select \
    结果输出:results(record(field1,field2..) record(field1...))
    Document:一个需要进行索引的“单元”
    一个Document由多个字段组成
    Record:记录,包含多个字段
    Field:字段 Field:字段
    Hits:查询结果集,由匹配的Document组成 RecordSet:查询结果集,由多个Record组成

    全文检索 ≠ like "%keyword%"

    通常比较厚的书籍后面常常附关键词索引表(比如:北京:12, 34页, 上海:3,77页……),它能够帮助读者比较快地找到相关内容的页码。而数据库索引能够大大提高查询的速度原理也是一样,想像一下通过书后面的索引查找的速度要比一页一页地翻内容高多少倍……而索引之所以效率高,另外一个原因是它是排好序的。对于检索系统来说核心是一个排序问题

    由于数据库索引不是为全文索引设计的,因此,使用like "%keyword%"时,数据库索引是不起作用的,在使用like查询时,搜索过程又变成类似于一页页翻书的遍历过程了,所以对于含有模糊查询的数据库服务来说,LIKE对性能的危害是极大的。如果是需要对多个关键词进行模糊匹配:like"%keyword1%" and like "%keyword2%" ...其效率也就可想而知了。

    所以建立一个高效检索系统的关键是建立一个类似于科技索引一样的反向索引机制,将数据源(比如多篇文章)排序顺序存储的同时,有另外一个排好序的关键词列表,用于存储关键词==>文章映射关系,利用这样的映射关系索引:[关键词==>出现关键词的文章编号,出现次数(甚至包括位置:起始偏移量,结束偏移量),出现频率],检索过程就是把模糊查询变成多个可以利用索引的精确查询的逻辑组合的过程。从而大大提高了多关键词查询的效率,所以,全文检索问题归结到最后是一个排序问题。

    由此可以看出模糊查询相对数据库的精确查询是一个非常不确定的问题,这也是大部分数据库对全文检索支持有限的原因。Lucene最核心的特征是通过特殊的索引结构实现了传统数据库不擅长的全文索引机制,并提供了扩展接口,以方便针对不同应用的定制。

    可以通过一下表格对比一下数据库的模糊查询:

      Lucene全文索引引擎 数据库
    索引 将数据源中的数据都通过全文索引一一建立反向索引 对于LIKE查询来说,数据传统的索引是根本用不上的。数据需要逐个便利记录进行GREP式的模糊匹配,比有索引的搜索速度要有多个数量级的下降。
    匹配效果 通过词元(term)进行匹配,通过语言分析接口的实现,可以实现对中文等非英语的支持。 使用:like "%net%" 会把netherlands也匹配出来,
    多个关键词的模糊匹配:使用like "%com%net%":就不能匹配词序颠倒的xxx.net..xxx.com
    匹配度 有匹配度算法,将匹配程度(相似度)比较高的结果排在前面。 没有匹配程度的控制:比如有记录中net出现5词和出现1次的,结果是一样的。
    结果输出 通过特别的算法,将最匹配度最高的头100条结果输出,结果集是缓冲式的小批量读取的。 返回所有的结果集,在匹配条目非常多的时候(比如上万条)需要大量的内存存放这些临时结果集。
    可定制性 通过不同的语言分析接口实现,可以方便的定制出符合应用需要的索引规则(包括对中文的支持) 没有接口或接口复杂,无法定制
    结论 高负载的模糊查询应用,需要负责的模糊查询的规则,索引的资料量比较大 使用率低,模糊匹配规则简单或者需要模糊查询的资料量少

    全文检索和数据库应用最大的不同在于:让最相关的头100条结果满足98%以上用户的需求

    Lucene的创新之处:

    大部分的搜索(数据库)引擎都是用B树结构来维护索引,索引的更新会导致大量的IO操作,Lucene在实现中,对此稍微有所改进:不是维护一个索引文件,而是在扩展索引的时候不断创建新的索引文件,然后定期的把这些新的小索引文件合并到原先的大索引中(针对不同的更新策略,批次的大小可以调整),这样在不影响检索的效率的前提下,提高了索引的效率。

    Lucene和其他一些全文检索系统/应用的比较:

      Lucene 其他开源全文检索系统
    增量索引和批量索引 可以进行增量的索引(Append),可以对于大量数据进行批量索引,并且接口设计用于优化批量索引和小批量的增量索引。 很多系统只支持批量的索引,有时数据源有一点增加也需要重建索引。
    数据源 Lucene没有定义具体的数据源,而是一个文档的结构,因此可以非常灵活的适应各种应用(只要前端有合适的转换器把数据源转换成相应结构), 很多系统只针对网页,缺乏其他格式文档的灵活性。
    索引内容抓取 Lucene的文档是由多个字段组成的,甚至可以控制那些字段需要进行索引,那些字段不需要索引,近一步索引的字段也分为需要分词和不需要分词的类型:
       需要进行分词的索引,比如:标题,文章内容字段
       不需要进行分词的索引,比如:作者/日期字段
    缺乏通用性,往往将文档整个索引了
    语言分析 通过语言分析器的不同扩展实现:
    可以过滤掉不需要的词:an the of 等,
    西文语法分析:将jumps jumped jumper都归结成jump进行索引/检索
    非英文支持:对亚洲语言,阿拉伯语言的索引支持
    缺乏通用接口实现
    查询分析 通过查询分析接口的实现,可以定制自己的查询语法规则:
    比如: 多个关键词之间的 + - and or关系等
     
    并发访问 能够支持多用户的使用  

    关于亚洲语言的的切分词问题(Word Segment)

    对于中文来说,全文索引首先还要解决一个语言分析的问题,对于英文来说,语句中单词之间是天然通过空格分开的,但亚洲语言的中日韩文语句中的字是一个字挨一个,所有,首先要把语句中按“词”进行索引的话,这个词如何切分出来就是一个很大的问题。

    首先,肯定不能用单个字符作(si-gram)为索引单元,否则查“上海”时,不能让含有“海上”也匹配。

    但一句话:“北京天安门”,计算机如何按照中文的语言习惯进行切分呢?
    “北京 天安门” 还是“北 京 天安门”?让计算机能够按照语言习惯进行切分,往往需要机器有一个比较丰富的词库才能够比较准确的识别出语句中的单词。

    另外一个解决的办法是采用自动切分算法:将单词按照2元语法(bigram)方式切分出来,比如:
    "北京天安门" ==> "北京 京天 天安 安门"。

    这样,在查询的时候,无论是查询"北京" 还是查询"天安门",将查询词组按同样的规则进行切分:"北京","天安安门",多个关键词之间按与"and"的关系组合,同样能够正确地映射到相应的索引中。这种方式对于其他亚洲语言:韩文,日文都是通用的。

    基于自动切分的最大优点是没有词表维护成本,实现简单,缺点是索引效率低,但对于中小型应用来说,基于2元语法的切分还是够用的。基于2元切分后的索引一般大小和源文件差不多,而对于英文,索引文件一般只有原文件的30%-40%不同,

      自动切分 词表切分
    实现 实现非常简单 实现复杂
    查询 增加了查询分析的复杂程度, 适于实现比较复杂的查询语法规则
    存储效率 索引冗余大,索引几乎和原文一样大 索引效率高,为原文大小的30%左右
    维护成本 无词表维护成本 词表维护成本非常高:中日韩等语言需要分别维护。
    还需要包括词频统计等内容
    适用领域 嵌入式系统:运行环境资源有限
    分布式系统:无词表同步问题
    多语言环境:无词表维护成本
    对查询和存储效率要求高的专业搜索引擎

    目前比较大的搜索引擎的语言分析算法一般是基于以上2个机制的结合。关于中文的语言分析算法,大家可以在Google查关键词"wordsegment search"能找到更多相关的资料。

    安装和使用

    下载:http://jakarta.apache.org/lucene/

    注意:Lucene中的一些比较复杂的词法分析是用JavaCC生成的(JavaCC:JavaCompilerCompiler,纯Java的词法分析生成器),所以如果从源代码编译或需要修改其中的QueryParser、定制自己的词法分析器,还需要从https://javacc.dev.java.net/下载javacc。

    lucene的组成结构:对于外部应用来说索引模块(index)和检索模块(search)是主要的外部应用入口

    org.apache.Lucene.search/ 搜索入口
    org.apache.Lucene.index/ 索引入口
    org.apache.Lucene.analysis/ 语言分析器
    org.apache.Lucene.queryParser/ 查询分析器
    org.apache.Lucene.document/ 存储结构
    org.apache.Lucene.store/  底层IO/存储结构
    org.apache.Lucene.util/ 一些公用的数据结构

    简单的例子演示一下Lucene的使用方法:

    索引过程:从命令行读取文件名(多个),将文件分路径(path字段)和内容(body字段)2个字段进行存储,并对内容进行全文索引:索引的单位是Document对象,每个Document对象包含多个字段Field对象,针对不同的字段属性和数据输出的需求,对字段还可以选择不同的索引/存储字段规则,列表如下:
    方法 切词 索引 存储 用途
    Field.Text(String name, String value) Yes Yes Yes 切分词索引并存储,比如:标题,内容字段
    Field.Text(String name, Reader value) Yes Yes No 切分词索引不存储,比如:META信息,
    不用于返回显示,但需要进行检索内容
    Field.Keyword(String name, String value) No Yes Yes 不切分索引并存储,比如:日期字段
    Field.UnIndexed(String name, String value) No No Yes 不索引,只存储,比如:文件路径
    Field.UnStored(String name, String value) Yes Yes No 只全文索引,不存储
    public class IndexFiles { 
      //使用方法:: IndexFiles [索引输出目录] [索引的文件列表] ... 
      public static void main(String[] args) throws Exception {
        String indexPath = args[0];
        IndexWriter writer;
        //用指定的语言分析器构造一个新的写索引器(第3个参数表示是否为追加索引)
        writer = new IndexWriter(indexPath, new SimpleAnalyzer(), false);
    
        for (int i=1; i<args.length; i++) {
          System.out.println("Indexing file " + args[i]);
          InputStream is = new FileInputStream(args[i]);
    
          //构造包含2个字段Field的Document对象
          //一个是路径path字段,不索引,只存储
          //一个是内容body字段,进行全文索引,并存储
          Document doc = new Document();
          doc.add(Field.UnIndexed("path", args[i]));
          doc.add(Field.Text("body", (Reader) new InputStreamReader(is)));
          //将文档写入索引
          writer.addDocument(doc);
          is.close();
        };
        //关闭写索引器
        writer.close();
      }
    }
     

    索引过程中可以看到:

    • 语言分析器提供了抽象的接口,因此语言分析(Analyser)是可以定制的,虽然lucene缺省提供了2个比较通用的分析器SimpleAnalyser和StandardAnalyser,这2个分析器缺省都不支持中文,所以要加入对中文语言的切分规则,需要修改这2个分析器。
    • Lucene并没有规定数据源的格式,而只提供了一个通用的结构(Document对象)来接受索引的输入,因此输入的数据源可以是:数据库,WORD文档,PDF文档,HTML文档……只要能够设计相应的解析转换器将数据源构造成成Docuement对象即可进行索引。
    • 对于大批量的数据索引,还可以通过调整IndexerWrite的文件合并频率属性(mergeFactor)来提高批量索引的效率。

    检索过程和结果显示:

    搜索结果返回的是Hits对象,可以通过它再访问Document==>Field中的内容。

    假设根据body字段进行全文检索,可以将查询结果的path字段和相应查询的匹配度(score)打印出来,

    public class Search { 
      public static void main(String[] args) throws Exception {
        String indexPath = args[0], queryString = args[1];
        //指向索引目录的搜索器
        Searcher searcher = new IndexSearcher(indexPath);
        //查询解析器:使用和索引同样的语言分析器
        Query query = QueryParser.parse(queryString, "body", 
                                  new SimpleAnalyzer());
        //搜索结果使用Hits存储
        Hits hits = searcher.search(query);
        //通过hits可以访问到相应字段的数据和查询的匹配度
        for (int i=0; i<hits.length(); i++) {
          System.out.println(hits.doc(i).get("path") + "; Score: " + 
                             hits.score(i));
        };
      }
    }
    在整个检索过程中,语言分析器,查询分析器,甚至搜索器(Searcher)都是提供了抽象的接口,可以根据需要进行定制。

    Hacking Lucene

    简化的查询分析器

    个人感觉lucene成为JAKARTA项目后,画在了太多的时间用于调试日趋复杂QueryParser,而其中大部分是大多数用户并不很熟悉的,目前LUCENE支持的语法:

    Query ::= ( Clause )*
    Clause ::= ["+", "-"] [<TERM> ":"] ( <TERM> | "(" Query ")")

    中间的逻辑包括:and or + - &&||等符号,而且还有"短语查询"和针对西文的前缀/模糊查询等,个人感觉对于一般应用来说,这些功能有一些华而不实,其实能够实现目前类似于Google的查询语句分析功能其实对于大多数用户来说已经够了。所以,Lucene早期版本的QueryParser仍是比较好的选择。

    添加修改删除指定记录(Document)

    Lucene提供了索引的扩展机制,因此索引的动态扩展应该是没有问题的,而指定记录的修改也似乎只能通过记录的删除,然后重新加入实现。如何删除指定的记录呢?删除的方法也很简单,只是需要在索引时根据数据源中的记录ID专门另建索引,然后利用IndexReader.delete(Termterm)方法通过这个记录ID删除相应的Document。

    根据某个字段值的排序功能

    lucene缺省是按照自己的相关度算法(score)进行结果排序的,但能够根据其他字段进行结果排序是一个在LUCENE的开发邮件列表中经常提到的问题,很多原先基于数据库应用都需要除了基于匹配度(score)以外的排序功能。而从全文检索的原理我们可以了解到,任何不基于索引的搜索过程效率都会导致效率非常的低,如果基于其他字段的排序需要在搜索过程中访问存储字段,速度回大大降低,因此非常是不可取的。

    但这里也有一个折中的解决方法:在搜索过程中能够影响排序结果的只有索引中已经存储的docID和score这2个参数,所以,基于score以外的排序,其实可以通过将数据源预先排好序,然后根据docID进行排序来实现。这样就避免了在LUCENE搜索结果外对结果再次进行排序和在搜索过程中访问不在索引中的某个字段值。

    这里需要修改的是IndexSearcher中的HitCollector过程:

    ...
     scorer.score(new HitCollector() {
    	private float minScore = 0.0f;
    	public final void collect(int doc, float score) {
    	  if (score > 0.0f &&			  // ignore zeroed buckets
    	      (bits==null || bits.get(doc))) {	  // skip docs not in bits
    	    totalHits[0]++;
    	    if (score >= minScore) {
                  /* 原先:Lucene将docID和相应的匹配度score例入结果命中列表中:
    	       * hq.put(new ScoreDoc(doc, score));	  // update hit queue
                   * 如果用doc 或 1/doc 代替 score,就实现了根据docID顺排或逆排
                   * 假设数据源索引时已经按照某个字段排好了序,而结果根据docID排序也就实现了
                   * 针对某个字段的排序,甚至可以实现更复杂的score和docID的拟合。
                   */
                  hq.put(new ScoreDoc(doc, (float) 1/doc )); 
    	      if (hq.size() > nDocs) {		  // if hit queue overfull
    		hq.pop();			  // remove lowest in hit queue
    		minScore = ((ScoreDoc)hq.top()).score; // reset minScore
    	      }
    	    }
    	  }
    	}
          }, reader.maxDoc());

    更通用的输入输出接口

    虽然lucene没有定义一个确定的输入文档格式,但越来越多的人想到使用一个标准的中间格式作为Lucene的数据导入接口,然后其他数据,比如PDF只需要通过解析器转换成标准的中间格式就可以进行数据索引了。这个中间格式主要以XML为主,类似实现已经不下4,5个:

    数据源: WORD       PDF     HTML    DB       other
             \          |       |      |         /
                           XML中间格式
                                |
                         Lucene INDEX

    目前还没有针对MSWord文档的解析器,因为Word文档和基于ASCII的RTF文档不同,需要使用COM对象机制解析。这个是我在Google上查的相关资料:http://www.intrinsyc.com/products/enterprise_applications.asp
    另外一个办法就是把Word文档转换成text:http://www.winfield.demon.nl/index.html


    索引过程优化

    索引一般分2种情况,一种是小批量的索引扩展,一种是大批量的索引重建。在索引过程中,并不是每次新的DOC加入进去索引都重新进行一次索引文件的写入操作(文件I/O是一件非常消耗资源的事情)。

    Lucene先在内存中进行索引操作,并根据一定的批量进行文件的写入。这个批次的间隔越大,文件的写入次数越少,但占用内存会很多。反之占用内存少,但文件IO操作频繁,索引速度会很慢。在IndexWriter中有一个MERGE_FACTOR参数可以帮助你在构造索引器后根据应用环境的情况充分利用内存减少文件的操作。根据我的使用经验:缺省Indexer是每20条记录索引后写入一次,每将MERGE_FACTOR增加50倍,索引速度可以提高1倍左右。

    搜索过程优化

    lucene支持内存索引:这样的搜索比基于文件的I/O有数量级的速度提升。
    http://www.onjava.com/lpt/a/3273
    而尽可能减少IndexSearcher的创建和对搜索结果的前台的缓存也是必要的。

     

    Lucene面向全文检索的优化在于首次索引检索后,并不把所有的记录(Document)具体内容读取出来,而起只将所有结果中匹配度最高的头100条结果(TopDocs)的ID放到结果集缓存中并返回,这里可以比较一下数据库检索:如果是一个10,000条的数据库检索结果集,数据库是一定要把所有记录内容都取得以后再开始返回给应用结果集的。所以即使检索匹配总数很多,Lucene的结果集占用的内存空间也不会很多。对于一般的模糊检索应用是用不到这么多的结果的,头100条已经可以满足90%以上的检索需求。

    如果首批缓存结果数用完后还要读取更后面的结果时Searcher会再次检索并生成一个上次的搜索缓存数大1倍的缓存,并再重新向后抓取。所以如果构造一个Searcher去查1-120条结果,Searcher其实是进行了2次搜索过程:头100条取完后,缓存结果用完,Searcher重新检索再构造一个200条的结果缓存,依此类推,400条缓存,800条缓存。由于每次Searcher对象消失后,这些缓存也访问那不到了,你有可能想将结果记录缓存下来,缓存数尽量保证在100以下以充分利用首次的结果缓存,不让Lucene浪费多次检索,而且可以分级进行结果缓存。

    Lucene的另外一个特点是在收集结果的过程中将匹配度低的结果自动过滤掉了。这也是和数据库应用需要将搜索的结果全部返回不同之处。

    我的一些尝试

    • 支持中文的Tokenizer:这里有2个版本,一个是通过JavaCC生成的,对CJK部分按一个字符一个TOKEN索引,另外一个是从SimpleTokenizer改写的,对英文支持数字和字母TOKEN,对中文按迭代索引。
    • 基于XML数据源的索引器:XMLIndexer,因此所有数据源只要能够按照DTD转换成指定的XML,就可以用XMLIndxer进行索引了。
    • 根据某个字段排序:按记录索引顺序排序结果的搜索器:IndexOrderSearcher,因此如果需要让搜索结果根据某个字段排序,可以让数据源先按某个字段排好序(比如:PriceField),这样索引后,然后在利用这个按记录的ID顺序检索的搜索器,结果就是相当于是那个字段排序的结果了。

    从Lucene学到更多

    Luene的确是一个面对对象设计的典范

    • 所有的问题都通过一个额外抽象层来方便以后的扩展和重用:你可以通过重新实现来达到自己的目的,而对其他模块而不需要;
    • 简单的应用入口Searcher, Indexer,并调用底层一系列组件协同的完成搜索任务;
    • 所有的对象的任务都非常专一:比如搜索过程:QueryParser分析将查询语句转换成一系列的精确查询的组合(Query),通过底层的索引读取结构IndexReader进行索引的读取,并用相应的打分器给搜索结果进行打分/排序等。所有的功能模块原子化程度非常高,因此可以通过重新实现而不需要修改其他模块。 
    • 除了灵活的应用接口设计,Lucene还提供了一些适合大多数应用的语言分析器实现(SimpleAnalyser,StandardAnalyser),这也是新用户能够很快上手的重要原因之一。

    这些优点都是非常值得在以后的开发中学习借鉴的。作为一个通用工具包,Lunece的确给予了需要将全文检索功能嵌入到应用中的开发者很多的便利。

    此外,通过对Lucene的学习和使用,我也更深刻地理解了为什么很多数据库优化设计中要求,比如:

    • 尽可能对字段进行索引来提高查询速度,但过多的索引会对数据库表的更新操作变慢,而对结果过多的排序条件,实际上往往也是性能的杀手之一。
    • 很多商业数据库对大批量的数据插入操作会提供一些优化参数,这个作用和索引器的merge_factor的作用是类似的,
    • 20%/80%原则:查的结果多并不等于质量好,尤其对于返回结果集很大,如何优化这头几十条结果的质量往往才是最重要的。
    • 尽可能让应用从数据库中获得比较小的结果集,因为即使对于大型数据库,对结果集的随机访问也是一个非常消耗资源的操作。

    参考资料:

    Apache: Lucene Project
    http://jakarta.apache.org/lucene/
    Lucene开发/用户邮件列表归档
    Lucene-dev@jakarta.apache.org
    Lucene-user@jakarta.apache.org

    The Lucene search engine: Powerful, flexible, and free
    http://www.javaworld.com/javaworld/jw-09-2000/jw-0915-Lucene_p.html

    Lucene Tutorial
    http://www.darksleep.com/puff/lucene/lucene.html

    Notes on distributed searching with Lucene
    http://home.clara.net/markharwood/lucene/

    中文语言的切分词
    http://www.google.com/search?sourceid=navclient&hl=zh-CN&q=chinese+word+segment

    搜索引擎工具介绍
    http://searchtools.com/

    Lucene作者Cutting的几篇论文和专利
    http://lucene.sourceforge.net/publications.html 

    Lucene的.NET实现:dotLucene
    http://sourceforge.net/projects/dotlucene/

    Lucene作者Cutting的另外一个项目:基于Java的搜索引擎Nutch
    http://www.nutch.org/   http://sourceforge.net/projects/nutch/

    关于基于词表和N-Gram的切分词比较
    http://china.nikkeibp.co.jp/cgi-bin/china/news/int/int200302100112.html

    2005-01-08 Cutting在Pisa大学做的关于Lucene的讲座:非常详细的Lucene架构解说

    特别感谢:
    前网易CTO许良杰(Jack Xu)给我的指导:是您将我带入了搜索引擎这个行业。

    展开全文
  • Lucene倒排索引原理.doc

    2011-09-13 01:58:31
    Lucene倒排索引原理,Lucene倒排索引原理,Lucene倒排索引原理
  • lucene倒排索引原理

    2012-06-15 17:31:14
    Lucene是一个高性能的java全文检索工具包,它使用的是倒排文件索引结构。该结构及相应的生成算法如下: 0)设有两篇文章1和2 文章1的内容为:Tom lives in Guangzhou,I live in Guangzhou too. 文章2的内容...
    Lucene是一个高性能的java全文检索工具包,它使用的是倒排文件索引结构。该结构及相应的生成算法如下: 

    0)设有两篇文章1和2
    文章1的内容为:Tom lives in Guangzhou,I live in Guangzhou too.
    文章2的内容为:He once lived in Shanghai.

    1)由于lucene是基于关键词索引和查询的,首先我们要取得这两篇文章的关键词,通常我们需要如下处理措施
    a.我们现在有的是文章内容,即一个字符串,我们先要找出字符串中的所有单词,即分词。英文单词由于用空格分隔,比较好处理。中文单词间是连在一起的需要特殊的分词处理。
    b.文章中的”in”, “once” “too”等词没有什么实际意义,中文中的“的”“是”等字通常也无具体含义,这些不代表概念的词可以过滤掉
    c.用户通常希望查“He”时能把含“he”,“HE”的文章也找出来,所以所有单词需要统一大小写。
    d.用户通常希望查“live”时能把含“lives”,“lived”的文章也找出来,所以需要把“lives”,“lived”还原成“live”
    e.文章中的标点符号通常不表示某种概念,也可以过滤掉
    在lucene中以上措施由Analyzer类完成

    经过上面处理后
    文章1的所有关键词为:[tom] [live] [guangzhou] [i] [live] [guangzhou]
    文章2的所有关键词为:[he] [live] [shanghai]

    2) 有了关键词后,我们就可以建立倒排索引了。上面的对应关系是:“文章号”对“文章中所有关键词”。倒排索引把这个关系倒过来,变成:“关键词”对“拥有该关键词的所有文章号”。文章1,2经过倒排后变成
    关键词 文章号
    guangzhou 1
    he 2
    i 1
    live 1,2
    shanghai 2
    tom 1

    通常仅知道关键词在哪些文章中出现还不够,我们还需要知道关键词在文章中出现次数和出现的位置,通常有两种位置:a)字符位置,即记录该词是文章中第几个字符(优点是关键词亮显时定位快);b)关键词位置,即记录该词是文章中第几个关键词(优点是节约索引空间、词组(phase)查询快),lucene中记录的就是这种位置。

    加上“出现频率”和“出现位置”信息后,我们的索引结构变为:
    关键词 文章号[出现频率] 出现位置
    guangzhou 1[2] 3,6
    he 2[1] 1
    i 1[1] 4
    live 1[2],2[1] 2,5,2
    shanghai 2[1] 3
    tom 1[1] 1

    以live 这行为例我们说明一下该结构:live在文章1中出现了2次,文章2中出现了一次,它的出现位置为“2,5,2”这表示什么呢?我们需要结合文章号和出现频率来分析,文章1中出现了2次,那么“2,5”就表示live在文章1中出现的两个位置,文章2中出现了一次,剩下的“2”就表示live是文章2中第 2个关键字。

    以上就是lucene索引结构中最核心的部分。我们注意到关键字是按字符顺序排列的(lucene没有使用B树结构),因此lucene可以用二元搜索算法快速定位关键词。

    实现时 lucene将上面三列分别作为词典文件(Term Dictionary)、频率文件(frequencies)、位置文件 (positions)保存。其中词典文件不仅保存有每个关键词,还保留了指向频率文件和位置文件的指针,通过指针可以找到该关键字的频率信息和位置信息。

    Lucene中使用了field的概念,用于表达信息所在位置(如标题中,文章中,url中),在建索引中,该field信息也记录在词典文件中,每个关键词都有一个field信息(因为每个关键字一定属于一个或多个field)。

    为了减小索引文件的大小,Lucene对索引还使用了压缩技术。首先,对词典文件中的关键词进行了压缩,关键词压缩为<前缀长度,后缀>,例如:当前词为“阿拉伯语”,上一个词为“阿拉伯”,那么“阿拉伯语”压缩为<3,语>。其次大量用到的是对数字的压缩,数字只保存与上一个值的差值(这样可以减小数字的长度,进而减少保存该数字需要的字节数)。例如当前文章号是16389(不压缩要用3个字节保存),上一文章号是16382,压缩后保存7(只用一个字节)。

    下面我们可以通过对该索引的查询来解释一下为什么要建立索引。
    假设要查询单词 “live”,lucene先对词典二元查找、找到该词,通过指向频率文件的指针读出所有文章号,然后返回结果。词典通常非常小,因而,整个过程的时间是毫秒级的。
    而用普通的顺序匹配算法,不建索引,而是对所有文章的内容进行字符串匹配,这个过程将会相当缓慢,当文章数目很大时,时间往往是无法忍受的。
    展开全文

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 534
精华内容 213
关键字:

lucene倒排索引原理