Suffix Tree
19
11
40
33
信息检索实验室
difference between suffix array and inverted list


suffix array: the occurrences of each word are sorted lexicographically by the text following the word inverted list: the occurrences of each word are sorted by text position
信息检索实验室
Trie树

优点

查找效率高，与词表长度无关

Trie树的查找效率只与关键词长度有关 目前我们分词词表最长的词为13个字


事实上索引词表中词过长会降低检索召回率

“大不列颠及北爱尔兰联合王国”

索引的插入，合并速度快

用户如果只输入“北爱尔兰”则无法返回该结果



缺点

注意，直接遍历Trie树需要搜索大量的无效节点 可以把数据存在一个数组中，Trie只保存指针 这样合并时，只需要对数组进行遍历即可
信息检索实验室
倒排文件



Lucene的词汇表 即采用这种方式 假设现在词表中 有16，000个词 indexInterval=16 则在词表中需要 查找次数为16＋ log(1000) = 26次
信息检索实验室
倒排文件

词汇表的查找树

把词汇表中的关键词以树的形式组织 二叉树，B树，Trie 等 考虑到平衡性，性能低于二分查找
Hash( y[0..5] ) = 17819 Hash( y[1..6] ) = 17533 Hash( y[2..7] ) = 17579
信息检索实验室
签名文件

文档的签名

把文档中的关键词散列成F位的位串Signature 顺序访问原文档的关键词，把散列所得的位串依次存 入文件

重叠编码(superimposed coding)
所需空间较大


实现较复杂
如果是完全m叉树，节点数指数级增长 好在Trie不是，但所需空间仍然很大 不可达上限： 词数 ×字符序列长度 ×字符集大小 ×指针长度 例如：20000 × 6 × 256 ×4 ＝120M
信息检索实验室
差值压缩（Delta Compression）

置入文件
‘l’ 60 ‘d’ 50 ‘m’ ‘a’ ‘n’28 19 ‘t’ ‘e’ ‘x’ ‘t’ ‘w’ 11 ‘o’ ‘r ‘d’ ‘s’ ‘l’ 60 ‘d’ 50 ‘m’ 3 1 ‘t’ ‘n’28 5 ‘w’ 6
40 33
space overhead: 120%~240% over the text size

对于插入的文档需要反复地调用排序和查找算法 索引合并时还需要堆排序等方法合并多个有序的词汇表

排序的时间复杂度为N*log N （分配排序例外）


检索的效率一般

如果合并最主要的时间开销在于IO操作的话，这点还是次要的
二分查找logN的复杂度已经具有较好的效率 能不能变成和词汇数量无关的常数复杂度
6 9 11 17 19 24 28 33 40 46 50 55 60
1
This is a text. A text has many words. Words are made from letters. Vocabulary letters Supra-Index Suffix Array Inverted list

Karp-Rabin匹配例子
AA C T C T
G C AA C T C T C A G C AA C T C T C A G C AA C T C T C A
关键词 x[0..5 ]：
文本y[0..9 ]： 文本y[0..9 ]： 文本y[0..9 ]：
Hash( x[0..5] ) = 17579
签名文件是倒排文档和全文扫描之间的折中

总之

信息检索实验室
倒排文件

倒排索引思想

每个文档都可以用一系列关键词来表示 如果按关键词建立到文档的索引便可以根据关键词快 速地检索到相关文档 词汇表（Vocabulary）


倒排文件组成

根据Heap’s定律，通常比较小O (n), : 0.4~0.6 通常我们称存放词汇表的文件为索引文件（index file）
实现简单 速度极快 关键在于找到一个好的散列函数


优点


缺点

随着现在散列空间的增大，问题相对简单

当冲突过多时效率会下降
信息检索实验室
倒排文件

词汇表的顺序排列


优点

把词汇按照字典顺序排列 词汇的查找采用二分查找 实现简单 词汇表体积小（通常只有几兆） 索引构建的效率一般



缺点

二叉查找树


B树

是多路查找树，效率高于二叉树，实现更麻烦
查找时间只跟词的长度有关 而于词表中词的个数无关 词表较大时才能体现出速度优势


Trie 树

Log (词表长度) > E(词长) E表示期望
信息检索实验室
Trie树

什么是trie树

trie树是一种用于快速检索的多叉树结构 trie树把要查找的关键词看作一个字符序列。
签名文件
Block 1 Block2 Block3 Block4 This is a text. A text has many words. Words are made from letters. 文本
000101
签名文件
110101 100100
101101
h(text) h(many) h(words) h(made) h(letters)

置入文件必须包含如下信息

当前词出现的文档号ID，以及在文档中的位置Pos

差值压缩

记录当前ID和前一ID的差值 记录当前Pos和前一Pos的差值 这样做能有效减少表示ID，Pos所需的字长

例如：关键词A在文档13，124，346中出现 如果不压缩，由于346>256,需要要两个字节 而346－124＝222<256，只需一个字节
信息检索实验室
Occurrences Text 4… 4… Inverted index 2… 1, 2 … 3…
倒排文件

倒排文件的性能

时间代价主要取决于词汇表的组织方式

词表文件通常较小且比较固定 对于未登录词和数词可以按字建索引

空间代价主要取决于对置入文件的压缩能力

置入文件的压缩能减少IO操作，也能提高部分时间性能

根据这一序列构造用于检索的树结构。

在trie树上进行检索类似于查阅英语词典。

例如，电子英文词典，为了方便用户快速 检索英语单词，可以建立一棵trie树。
信息检索实验室
词典单词： a、b、c、 aa、ab、 ac、ba、 ca、 aba、abc、 baa、bab、 bac、cab、 abba、 baba、 caba、 abaca、 caaba


后缀树（Suffix tree）

子串查找 最长重复子串 最长公共子串 回文子串

后缀数组（Suffix array）

按后缀树的先根遍历顺序，存储后缀
信息检索实验室
1
6 9 11
17 19
24 28
33
40
46 50
55
60
This is a text. A text has many words. Words are made from letters. Text Suffix Trie


我们不需要为每个关键词都保存一个Signature 多个关键词共用一个Signature可以减少文件的长度 由于重叠编码和哈希冲突的原因，关键词和Signature不 是一一对应的关系 Signature匹配并不能保证关键词一定出现，还需要检查

错误匹配（False drop）


信息检索实验室
索引和查找
胡晓光 信息检索实验室
信息检索实验室
提纲


顺序查找 索引查找

签名文件 倒排文件 PAT树（Patricia tree）

关于压缩
信息检索实验室
说明

索引和查找的关系

索引和查找其实是密不可分的 建索引时必须不断的执行查找操作

查找和查询的区别

查找（search）

如何在索引中定位关键词信息 Query处理：如何根据用户输入确定关键词 检索模型：如何利用查找返回的信息计算相似度等

查询（query）


文本压缩和索引压缩的区别

注意文本压缩不能有效地减少索引文件的大小
信息检索实验室
顺序查找

精确匹配算法


Brute Force Knuth-Morris-Pratt Boyer-Moore Shift-Or Suffix Automaton Dynamic Programming Non-deterministic Finite Automaton Bit-Parallelism