Lucene倒排索引

Lucene倒排索引

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

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

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

假设有两篇文章1和文章2&＃xff1a;

文章1的内容为&＃xff1a;Tom lives in Guangzhou,I live in Guangzhou too.
文章2的内容为&＃xff1a;He once lived in Shanghai.

1. 取得关键词

由于Lucene是基于关键词索引和查询的&＃xff0c;首先要取得这两篇文章的关键词&＃xff0c;通常需要如下处理措施&＃xff1a;

• 我们现在有的是文章内容&＃xff0c;即一个字符串&＃xff0c;我们先要找出字符串中的所有单词&＃xff0c;即分词。英文单词由于用空格分隔&＃xff0c;比较好处理。中文单词间由于是连在一起的&＃xff0c;所以需要特殊的分词处理。
• 文章中的"in" “once” “too” 等词没有什么实际意义&＃xff0c;中文中的"的" “是” 等字通常也无具体含义&＃xff0c;这些不代表概念的词是可以过滤掉的。
• 用户通常希望查 “He” 时能把含 “he” 和 “HE” 的文章也找出来&＃xff0c;所以所有单词需要同一大小写。
• 用户通常希望查 “live” 时能把含 “lives” 和 “lived” 的文章也找出来&＃xff0c;所以需要把 “lives” &＃xff0c;“lived” 还原成 “live”。
• 文章中的标点符号通常不表示某种概念&＃xff0c;也可以过滤掉。

在Lucene中以上措施由Analyzer类完成。经过上面处理后&＃xff0c;得到如下结果&＃xff1a;

文章1的所有关键词为&＃xff1a;[tom] [live] [guangzhou] [i] [live] [guangzhou]

文章2的所有关键词为&＃xff1a;[he] [live] [shanghai]

2. 建立倒排索引&＃xff1a;

有了关键词后&＃xff0c;就可以建立倒排索引。上面的对应关系是&＃xff1a;“文章号” 对 “文章中所有关键词” 。

倒排索引把这个关系倒过来&＃xff0c;变成&＃xff1a;“关键词” 对 “拥有关键词的所有文章号”。

倒排索引关键词文章号对应关系示例&＃xff1a;

通常仅知道关键词在哪些文章中出现还不够&＃xff0c;还需要知道关键词在文章中出现的次数和位置&＃xff0c;通常有两种位置&＃xff1a;

• 字符位置&＃xff1a;记录该词是文章中第几个字符&＃xff08;优点是显示并定位关键词快&＃xff09;
• 关键词位置&＃xff1a;记录该词是文章中第几个关键词&＃xff08;优点是节约索引空间、词组查询快&＃xff09;&＃xff0c;Lucene中记录的就是这种位置

加上『出现频率』和『出现位置』信息后&＃xff0c;索引结构如下&＃xff1a;

以live这行为例&＃xff1a;live在文章1中出现了2次&＃xff0c;文章2中出现了1次&＃xff0c;它出现的位置为"2, 5, 2" 。

关键字是按字符顺序排列的&＃xff08;Lucene没有使用B树结构&＃xff09;&＃xff0c;因此Lucene可以用二元搜索算法快速定位关键词。

3. 实现

实现时&＃xff0c;Lucene将上面三列分别作为词典文件&＃xff08;Term Dictionary&＃xff09;、频率文件&＃xff08;frequencies&＃xff09;、位置文件&＃xff08;positions&＃xff09;保存。

词典文件保存了每个关键词&＃xff0c;还保留了指向频率文件和位置文件的指针&＃xff0c;通过指针可以找到该关键词的频率信息和位置信息。

Lucene中使用了field的概念&＃xff0c;用于表达信息所在的位置&＃xff08;如标题中、文章中&＃xff0c;URL中&＃xff09;&＃xff0c;在建索引中&＃xff0c;该field信息也记录在词典文件中&＃xff0c;每个关键词都有一个field信息&＃xff0c;因为每个关键字一定术语一个或多个field。

4. 压缩算法
为了减小索引文件的大小&＃xff0c;Lucene对索引还使用了压缩技术。

首先&＃xff0c;对词典文件中的关键词进行了压缩&＃xff0c;关键词压缩为 <前缀长度&＃xff0c;后缀>&＃xff0c;例如&＃xff1a;当前词为"阿里伯语"&＃xff0c;上一个词为"阿拉伯"&＃xff0c;那么"阿拉伯语"压缩为<3, 语>。

其次大量用到的是对数字的压缩&＃xff0c;数字只保存与上一个值的差值&＃xff08;这样可以减少数字的长度&＃xff0c;进而减少保存该数字需要的字节数&＃xff09;。例如&＃xff1a;当前文章号是16389&＃xff08;不压缩需要用3个字节保存&＃xff09;&＃xff0c;上一文章号是16382&＃xff0c;压缩后保存7&＃xff08;只用一个字节&＃xff09;。

5. 应用场景

假设要查询单词"live"&＃xff0c;Lucene先对词典二元查找、找到该词&＃xff0c;通过指向频率文件的指针读出所有文章号&＃xff0c;然后返回结果。词典通常非常小&＃xff0c;因而&＃xff0c;整个过程的时间是毫秒级的。

而用普通的顺序匹配算法&＃xff0c;不建索引&＃xff0c;而是对所有文章的内容进行字符串匹配&＃xff0c;这个过程会相当缓慢&＃xff0c;当文章数目很大时&＃xff0c;时间往往是无法忍受的。