【11.3】索引--倒排索引

• 基于属性的倒排

• 要求检索结构中某个或若干个属性满足一定条件的结点(不是按关键码的值检索)

• 按照属性建立索引

• 对正文文件的倒排

• 以文中的词(word)为索引项建立的索引

教师数据库主表

一、基于属性的倒排

• 对某属性按属性值建立索引表，称倒排表
• “属性 – 指针”对 (attr, ptrList)
• (属性值，具有该属性值的各记录指针)
• 指针可以是关键码，或该记录的主文件地址
• 颠覆主文件的顺序，因而称为倒排索引
• 属性往往是离散型的
• 对于连续型的索引，往往用B树
• 倒排文件:带有倒排索引的文件

教师数据库倒排表：

优缺点

• 优点:

• 能够对于基于属性的检索进行较高效率的处理

• 缺点:

• 花费了保存倒排表的存储代价

• 降低了更新运算的效率

二、 对正文文件的倒排

• 正文索引 (Text Indexing )处理的就是“建立一个数据结构以提供对文本内容的 快速检索”

• 方法

• 词索引 ( word index )

• 全文索引 ( full-text index )

2.1 词索引

• 基本思想:

• 把正文看作由符号和词所组成的集合，从正文中抽 取出关键词，然后用这些关键词组成一些适合快速 检索的数据结构。

• 适用于多种文本类型，特别是那些可以很容易 就解析成一组词的集合的文本

• 适用于英文

• 中文等东方文字要经过“切词”处理

2.2 全文索引

• 基本思想:

• 把正文看作一个长的字符串

• 在数据结构中记录的是子字符串的开始位置

• 查询就可以针对正文中的任何子字符串

• 可以对每一个字符建立索引，从而使查询 词不再限于关键词

• 需要更大的空间

2.3 倒排文件使用最广泛的是词索引

• 词索引使用 最广泛
• 一个已经排过序的关键词的列表
• 其中每个关键词指向一个倒排 (posting list)。指向该关键词出现文档集合；在文档中的位置

2.4 倒排索引建立示例

正文文件:由6个文档组成，每个文档都是长字符串

2.5 建立正文倒排文件

1. 对文档集中的所有文件都进行分割处理， 把正文分成多条记录文档

• 切分正文记录取决于程序的需要。定长的块、段落、章节，甚至一组文档

2. 给每条记录赋一组关键词

• 以人工或者自动的方式从记录中抽取关键词
• 停用词( Stopword )
• 抽词干( Stemming )
• 切词(Segmentation)

中文切词 Chinese Segmentation：

我知道你不知道我知道你不知道我知道你不知道

• 我知道，你不知道。我知道，你不知道我知道，你不知道
• 我知道你，不知道我。知道你不知道我，知道你不知道
• 我，知道你不知道我知道。你，不知道我知道你不知道

3. 建立正文倒排表、倒排文件

• 得到各个关键词的集合
• 对于每一个关键词得到其倒排表
• 然后把所有的倒排表存入文件

2.6 对关键词的检索

• 第一步，在倒排文件中检索关键词
• 第二步，如果找到了关键词，那么获取文件中的对应的倒排表，并获取倒排表中的记录
• 通常使用另一个索引结构(字典)进一步对关 键词表进行 有效索引
• Trie
• 散列

2.7 倒排文件优劣

• 高效检索，用于文本数据库系统
• 支持的检索类型有限
• 检索词有限(只能用索引文件中的关键词)
• 倒排文件中的索引效率可能不高
• 需要的空间代价往往很高

三、思考

• 怎样有效地组织属性倒排索引表?
• 一个关键词如果在同一个文本中多次出现，它在倒排文件中的索引项是否能进行合并?

参考资料

北京大学 《数据结构与算法》 张铭、赵海燕、宋国杰、黄骏、邹磊、陈斌、王腾