【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
个人公众号,比较懒,很少更新,可以在上面提问题,如果回复不及时,可发邮件给我: tiehan@sina.cn