倒排索引


1. 介绍

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

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

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

2.Lucence 倒排索引原理

  • Lucence 是一个开源的高性能的 Java 全文检索引擎工具包, 他是一个全文检索引擎的架构,并不是一个完整的全文检索引擎,

  • Lucence 提供了完整的查询引擎和索引引擎,部分文本分析引擎。 目的是为软件开发人员提供一个简单易用的工具包, 以方便在目标系统中实现全文检索的功能, 或者以此为基础建立起完整的全文检索引擎。

Lucence 使用的是倒排索引结构。 该结构以及相应的生成算法如下,假设有两篇文章 1 和 2 :

文章1的内容为:Tom lives in Guangzhou,I live in Guangzhou too.

文章2的内容为:He once lived in Shanghai.

2.1 去的关键词

由于 Lucence 是基于关键词索引和查询的, 首先我们要去的这两篇文章的关键词集

通常我们需要如下处理措施:

a. 我们现在有的是文章内容, 即一个字符串, 我们先要找出字符串中的所有单词, 即分词。 英文单词由于用空格分隔, 比较好处理。 中文档次中间是连在一起的需要特殊的分词处理。

b. 文章中的 in、once、too 等词没有什么实际意义, 中文中的 “的” 、“是” 等字通常也无具体含义, 这些不代表概念的词可以过滤掉

c. 用户通常希望查询 “He” 时能把包含 “he” “HE” 的文章也找出来, 所以单词需要统一大小写。

d. 用户通常希望查询 “live” 时能把 含 “lives”、“lived” 的文章也找出来, 所以需要把 “lives”、“lived” 还原成 “live”

e. 文章中的标点符号通常不表示某种概念, 也可以过滤掉

在Lucence中以上措施由 Analyzer 类完成。 经过生面处理后,

文章1的所有关键词为:[tom] [live] [guangzhou] [i] [live] [guangzhou]    

文章2的所有关键词为:[he] [live] [shanghai]

2.2 建立倒排索引

有了关键词后, 我们就可以建立倒排索引了。 上面的对应关系是: “文章号” 对 “文章中出现的词”, 倒排索引把这个关系倒过来, 变换成 关键词 –> 拥有该关键词的所有文章号

文章 1、2 经过倒排后变成

关键词 文章号
guangzhou 1
he 2
i 1
live 1,2
shanghai 2
tom 1

通常仅知道关键词在哪些文章中出现还不够, 我们还需要知道关键词在文章中出现的次数和出现的位置, 通常有两种位置:

a. 字符位置, 即记录该词是文章中第几个字符(优点是关键字高亮时定位快)

b. 关键词位置, 即记录改词是文章中第几个关键词(节约索引空间、词组(phase) 查询快), Lucence中记录就是这种位置。

加上 “出现词频” 和 “出现位置” 信息后, 我们的索引结构变为:

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

以 live 这张为例, 我们说明一下结构:

live 在文章1 中出现了两次, 文章2 中出现了一次, 他的出现位置为 2,5,2 这表示什么呢? 我们需要结合文章号和出现频率来分析, 文章1 中出现了两次, 那么2,5 就标识live在文章1 中出现的两个位置, 文章2 中出现了一次, 剩下的2 就标识 live 在文章2 中的第2个关键词。

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

3. 实现

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

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

4.压缩算法

为了减小索引文件的大小, Lucence对索引还使用了压缩技术。

首先, 对词典文件中的关键词进行压缩, 关键词压缩为<前缀长度, 后缀>, 例如当前词为 “阿拉伯语”, 上一个词为阿拉伯, 那么阿拉伯语 压缩为<3,语>

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

5. 应用原因

下面我们可以通过对该缩印的查询来解释一下为什么要建立索引。

假设要查询单词 live Lucence 先对词典二元查找, 找到改词, 通过指向频率文件的指针读出所有文章号, 然后返回结果。 词典通常非常小, 因而, 整个过程是毫秒级的。

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


文章作者: hnbian
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 hnbian !
评论
 上一篇
Spark SQL 3.Hive On Spark Spark SQL 3.Hive On Spark
1. Spark on hive 与 Hive on Spark 的区别 Spark on hive Spark通过Spark-SQL使用hive 语句操作hive,底层运行的还是 spark rdd 就是通过sparksql,加载hi
2018-05-29
下一篇 
Spark SQL 2.自定义函数 Spark SQL 2.自定义函数
1. SparkSQL 中自定义函数类型在 Spark SQL 中,用户自定义函数(User-Defined Function,简称 UDF)是一种特殊的函数,允许用户定义自己的逻辑来处理数据。这些函数可以直接在 Spark SQL 查询中
2018-05-25
  目录