【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 倒排文件优劣

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

三、思考

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

参考资料

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

这里是一个广告位,,感兴趣的都可以发邮件聊聊:tiehan@sina.cn
个人公众号,比较懒,很少更新,可以在上面提问题,如果回复不及时,可发邮件给我: tiehan@sina.cn