倒排索引

基本概念

正常索引: 通过唯一id, 查找对应的数据记录, 比如MySql索引
倒排索引: 通过数据内容, 查找包含此内容的id集合

id	title	detail
1	lucene study	base of lucene
2	java study	java is the best language

我们对title字段建立倒排索引可以得到

term	ids	offset
lucene	[1]	0
java	[2]	5
study	[1, 2]	11

term: 内容在分词后的基本单元. ids: 包含此term的记录id列表. offset: ids存储在索引文件的offset位置

FST

如何找到term呢? lucence使用了FST(Direct Construction of Minimal Acyclic Subsequential Transducers)算法. 本质上是构建一个最小化的无环有限自动机, 并在此基础上加上转换功能

确定(Deterministic): 对给定的任何input, 最多只有一条路径可以到达
无环(Acyclic): 对给定的任何input, 不会重复访问已经过的状态
接受(Acceptor): 给定的input, 当且仅当 input的最后一个字符指向的状态为终结状态时, 表示接受
转换(Transducer):在自动机每接受input的一个字符的时候, 可以产生一个值, 当到达接受状态时, 这个值就是output

lucene中的实现

在lucene中, term就是input, offset就是output, 构建FST有几个要求

term是按照字典表排好序的
term元素数量不可变

简单示例

先看个示例最终生成的FST结构

# input/output
ca/1
cat/5
dog/10
dot/15

每条边标识可接受的字符, 边本身有值, 没有值的表示值为0
- c/1: 接受字符c, 此边的值为1
- a: 等价于a/0
每个圈代表一个状态, 一般情况下没有值, 在特殊情况也会有值
加粗的表边标识到达的状态为终结状态
output为从开始状态到终结状态所经过的边的值总和. 特殊情况下加上最终状态的值.

特殊情况示例

ca/5
cat/1
caz/2

构建的过程

很难简短的说清楚构建的细节, 制作了一个页面, 可以自己设计input/output, 并观察FST的变化, 来帮助理解
http://xiaozhukk.com/web/index.html#/fst(可能加载有点慢)

FST的功能

在了解了FST的结构之后, 可以看到查询指定的term只跟term本身长度有关, 可以认为时间复杂度为O(1)

基本的搜索场景: 搜索java
在FST中查找term的offset, 再根据offset找到包含此term的数据记录id列表. 然后通过id获取原始记录就类似于数据库了.

SkipList

假设我要检索同时包含java和lucene的记录呢. 或者只要包含java或lucene的记录呢. 方法是分别在FST中找出java和lucene的id列表, 然后做交集或并集.

lucene选择使用SkipList来索引id列表, SkipList是已排序的结构, 在多个已排序的列表做交集或并集, 时间复杂度为O(n), 利用上SkipList中的跳跃指针, 能更加优化平均时间复杂度.

评分

到目前为止, 我们可以快速的检索出相关的记录. 我们希望与查询相关程度高的评分更高, 排在前面.

TF-IDF权重计算

TF(term frequencey): term在一个文档中出现的次数, TF越大表示这个文档与term关联越高
DF(document frequency): 包含term的文档总数目, DF越大表示这个term的区分度越小, 一个查询能被分成多个term, 意味着包含DF高的term的文档关联性反而要小
IDF(inverse document frequency): = log(文档总数/DF), 经过计算DF越小, IDF值越高, 文档权重越高,

我们定义一个term在一个文档(document)中TF-IDF的值为