Lucene倒排索引原理是什么

本篇内容主要讲解“Lucene倒排索引原理是什么”，感兴趣的朋友不妨来看看。本文介绍的方法操作简单快捷，实用性强。下面就让小编来带大家学习“Lucene倒排索引原理是什么”吧!

创新互联-专业网站定制、快速模板网站建设、高性价比梁溪网站开发、企业建站全套包干低至880元,成熟完善的模板库,直接使用。一站式梁溪网站制作公司更省心,省钱,快速模板网站建设找我们，业务覆盖梁溪地区。费用合理售后完善，10多年实体公司更值得信赖。

一、搜索引擎介绍

1.1 搜索引擎是什么

这里引用百度百科的介绍：

搜索引擎（Search Engine）是指根据一定的策略、运用特定的计算机程序从互联网上搜集信息，在对信息进行组织和处理后，为用户提供检索服务，将用户检索相关的信息展示给用户的系统。

1.2 搜索引擎分类

搜索引擎包括全文索引、目录索引、元搜索引擎、垂直搜索引擎、集合式搜索引擎、门户搜索引擎与免费链接列表等。

本文主要介绍全文索引，即百度使用的搜索引擎分类。

全文索引

首先是数据库中数据的搜集，搜索引擎的自动信息搜集功能分两种：

一种是定期搜索，即每隔一段时间（比如Google一般是28天），搜索引擎主动派出“蜘蛛”程序，对一定IP地址范围内的互联网网站进行检索，一旦发现新的网站，它会自动提取网站的信息和网址加入自己的数据库。
另一种是提交网站搜索，即网站拥有者主动向搜索引擎提交网址，它在一定时间内（2天到数月不等）定向向你的网站派出“蜘蛛”程序，扫描你的网站并将有关信息存入数据库，以备用户查询。

当用户以关键词查找信息时，搜索引擎会在数据库中进行搜寻，如果找到与用户要求内容相符的网站，便采用特殊的算法——通常根据网页中关键词的匹配程度、出现的位置、频次、链接质量——计算出各网页的相关度及排名等级，然后根据关联度高低，按顺序将这些网页链接返回给用户。这种引擎的特点是搜全率比较高。

1.3 搜索引擎能解决什么问题

高效查询数据（运用多种算法查询数据，查询速率是毫秒级别，无论是千万条数据还是上亿的数据）
比较容易，将普通的数据库切换成搜索引擎比较容易。
大数据量、时效性、高并发等等。

1.4 搜索引擎的应用场景

数据库达到百万数据级别的时候
要求检索时效性、性能要求高，Ms级响应

1.5 Solr

接下来看在平常的互联网中搜索引擎的应用Solr。那么什么是Solr呢？它和es相比有什么优点和不足呢？

我们先来简单地介绍一下solr：

Solr是一个基于Lucene的全文搜索服务器。同时对其进行了扩展，提供了比Lucene更为丰富的面向使用的查询语言，同时实现了可配置、可扩展并对查询性能进行了优化，并且提供了一个完善的功能管理界面。它支持Xml/Http协议，支持JSONAPI接口。

它具有如下特点：

可扩展性：Solr可以把建立索引和查询处理的运算分布到一个集群内的多台服务器上。
快速部署：Solr是开源软件，安装和配置都很方便，可以根据安装包内的Sample配置直接上手，可分为单机和集群模式。
海量数据：Solr是针对亿级以上的海量数据处理而设计的，可以很好地处理海量数据检索。
优化的搜索功能：Solr搜索速度够快，对于复杂的搜索查询Solr可以做到毫秒级的处理，通常，几十毫秒就能处理完一次复杂查询。

二、分词介绍

接下来，我们将了解分词是如何实现的。那么，我们为什么要去分词呢，这和搜索引擎有什么关系呢？我们在搜索框里输入的几个词或者一段话是如何拆成多个关键字的呢？

大家听说过哪些分词器吗？比如lucene自带的中文分词器smartcn，还有最常用的IK分词器等等，今天我们主要讲一下IK分词器。

2.1 IK分词器

IK分词器首先会维护几个词典来记录一些常用的词，如主词表：main2012.dic、量词表quantifier.dic、停用词stopword.dic。

Dictionary为字典管理类中，分别加载了这个词典到内存结构中。具体的字典代码，位于org.wltea.analyzer.dic.DictSegment。这个类实现了一个分词器的一个核心数据结构，即Tire Tree。

Tire Tree（字典树）是一种结构相当简单的树型结构，用于构建词典，通过前缀字符逐一比较对方式，快速查找词，所以有时也称为前缀树。具体的例子如下。

举例

比如：我是北京海淀区中关村的中国人民。

我们设置的词典是：北京、海淀区、中关村、中国、中国人民，那么根据词典组成的字典树如图所示：

Lucene倒排索引原理是什么

然后我们根据这个字典树来对这段话进行词语切分。IK分词器中，基本可以分为两种模式：一种是smart模式、一种是非smart模式，可以在代码中初始化的时候去配置。

我们其实不用解释这两种模式的字面含义，直接打印两种模式的结果就可以看出来：

原句：我是北京海淀区中关村的中国人民
smart模式：北京、海淀区、中关村、中国人民
非smart模式：北京、海淀区、中关村、中国、中国人民

显而易见，非smart模式是将能够分出来的词全部输出；smart模式是根据内在的方法输出一个合理的分词结果，这就涉及到了歧义判断。

举例

举个更有代表性的例子：张三说的确实在理。

根据正向匹配可能的词元链：

L1:{张三，张,三}
L2:{说}
L3:{的确,的,确实,确,实在,实,在理,在,理}

首来看一下最基本的一些元素结构类：

public class Lexeme implements Comparable{  
    ……  
   
    //词元的起始位移  
    private int offset;  
    //词元的相对起始位置  
    private int begin;  
    //词元的长度  
    private int length;  
    //词元文本  
    private String lexemeText;  
    //词元类型  
    private int lexemeType;  
     ……  
}

这里的Lexeme（词元），可以理解为是一个词语或单词。其中的begin，是指其在输入文本中的位置。注意，它是实现Comparable的，起始位置靠前的优先，长度较长的优先，这可以用来决定一个词在一条分词结果的词元链中的位置，可以用于得到上面例子中分词结果中的各个词的顺序。　　

/* 
* 词元在排序集合中的比较算法
* @see java.lang.Comparable#compareTo(java.lang.Object) 
*/  
public int compareTo(Lexeme other) {  
//起始位置优先  
    if(this.begin < other.getBegin()){  
        return -1;  
    }else if(this.begin == other.getBegin()){  
     //词元长度优先  
     if(this.length > other.getLength()){  
         return -1;  
     }else if(this.length == other.getLength()){  
         return 0;  
     }else {//this.length < other.getLength()  
         return 1;  
     }  
        
    }else{//this.begin > other.getBegin()  
     return 1;  
    }  
}

smart模式歧义消除算法：

词元位置权重比较(词元长度积),含义是选取长的词元位置在后的集合
L31:{的,确实,在理}1*1+2*2+3*2=11
L32:{的确,实,在理} 1*2+2*1+3*2=10
L33:{的确,实在,理} 1*2+2*2+3*1=9
最后的分词结果:张三,说,的,确实,在理

三、倒排索引算法

3.1 介绍

我们可以把倒排索引算法想象成查字典时的目录一样，我们知道需要查的字的目录后，就会很快地查找到。如果用专业的语言解释的话就是：

倒排索引源于实际应用中需要根据属性的值来查找记录。这种索引表中的每一项都包括一个属性值和具有该属性值的各记录的地址。由于不是由记录来确定属性值，而是由属性值来确定记录的位置，因而称为倒排索引(inverted index)。带有倒排索引的文件我们称为倒排索引文件，简称倒排文件(inverted file)。

倒排文件（倒排索引），索引对象是文档或者文档集合中的单词等，用来存储这些单词在一个文档或者一组文档中的存储位置，是对文档或者文档集合的一种最常用的索引机制。

搜索引擎的关键步骤就是建立倒排索引，倒排索引一般表示为一个关键词，然后是它的频度（出现的次数），位置（出现在哪一篇文章或网页中，及有关的日期，作者等信息），它相当于为互联网上几千亿页网页做了一个索引，好比一本书的目录、标签一般。读者想看哪一个主题相关的章节，直接根据目录即可找到相关的页面。不必再从书的第一页到最后一页，一页一页地查找。

3.2 Lucene倒排索引原理

Lucerne是一个开放源代码的高性能的基于java的全文检索引擎工具包，不是一个完整的全文检索引擎，而是一个全文检索引擎的架构，提供了完整的查询引擎和索引引擎，部分文本分析引擎。目的是为软件开发人员提供一个简单易用的工具包，以方便在目标系统中实现全文检索的功能，或者以此为基础建立起完整的全文检索引擎。

假设有两篇文章1和2：

文章1的内容为： Jack lives in BeiJing,I live in BeiJing too. 　　文章2的内容为： He lived in Taiyuan.

1）取得关键词　

首先我们要用我们之前讲的方式分词，然后由于英文的原因，我们需要将in、on、of这些没用实际意义的词过滤掉，然后将第三人称单数加s或者过去式加ed这些词还原回去，如lived变回live，lives变回live，然后把不需要的标点符号也去掉。经过上面的处理之后，剩下的关键字为：

文章1的所有关键词为：[Jack] [live] [BeiJing] [i] [live] [BeiJing] 　　

文章2的所有关键词为：[he] [live] [Taiyuan]

2）建立倒排索引

关键词            文章号[出现频率]              出现位置 　　
BeiJing             1[2]                      3，6 　　
he                  2[1]                      1 　　
i                   1[1]                      4 　　
live                1[2]                      2，5, 
                    2[1]                      2 　　
Taiyuan             2[1]                      3 　　
tom                 1[1]                      1

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