搜索技术入门到精通

Thursday, April 05, 2007

第四章 4.2 倒排索引基本原理 Principle of Inverted Index

Trie是效率最高的索引形式,下图表示由文本到的前缀树的创建过程。

插入操作的时间复杂度O(l),其中l = max(length of word)

查询的操作的时间复杂度O(l)

删除操作的复杂度为O(n),其中n = length of dictionary


Trie有消耗了大量内存且难以分块的缺点,同时伴随着I/O和瓶颈,一般来说用分块的倒排索引来解决内存不足问题,最后对分块的索引块做一次归并。倒排索引一般分成两个文件来存储,其中一个称为位置文件,纪录了词出现的文档和位置信息;另外一个是词典文件,纪录索引文本出现过的词,按照字符的顺序来存储。其中每个词有个指针,表示对应了第一个文件中的那个纪录。这样的结构保证了检索的时候词典能被保存在内存中,进一步的意义在于,检索词出现在哪些文档中以及位置能被迅速地找到。用一个例子来说明,有个这样的句子该怎么索引?
Tom lives in Guangzhou, I live in Guangzhou too.
分析过后剩下为
tom live guangzhou I live guangzhou
从词的角度出发一共有五个词,可以得出这样的一张词表

name

position

frequency

tom

1

1

live

5,22

2

guangzhou

10,27

2

i

20

1

文本的内容经过分析之后抽取出的内容见上表,即索引文件的内容,可以加对表的内容压缩存储优化,通常只对位置字段做差分压缩,最后将内容按照存储格式存储起来。

归并两个索引需要归并排序词典文件和合并位置文件:如果词典中的词不相同,连接相应的位置文件内容;如果词相同,连接相应位置条目的内容。一次归并操作的时间复杂度为O(n1 + n2),其中n1n2分别为索引词典的长度。索引器的效率一般在4Mb/min1Gb/min之间,其中20%-30%的时间在做归并操作。对于归并操作没有很好的理论精确地得出最优的归并方式,本人采用词典长度接近的优先归并的方式,类似哈夫曼编码规则的顺序来归并,并取得了约10%的性能升。

No comments: