北京大学：《数据结构与算法》课程教学资源（实验班讲义）第十章 索引技术

1031基于属性的倒 0I97.0204 ■对某属性按属性值建立索引表,称倒排 0375,0552 (attr, ptrList) 020A4 记录指骨可以是类健码,或该记录的主文件地址 颠摄主文件的顺序,因而称为倒排索引 ■属性往往是高散型的 0375.0552 对于连续型的索引,往往用B树 倒排文件:带有倒排索引的文件 张陪写 新。■印乡究 北京太 孔稳写 权新有轴命剑究 检索实例 玩具部中年齡在50岁以上或者工资在 ■优点:能够对于基于属性的检索 GE≥50oR ≥500 进行较高效率的处理 分型找 缺点: 对后两个丰 花费了保存倒排表的存储代价 降低了更新运算的效率 张铭帖编写 孔写 1032对正文文件的倒排 词索引 正文索引〔 Text Indexing处理 ■基本思想: 的就是“建立一个数据结构以提 把正文看作由符号和词所组成的集合,从正 后 供对文本内容的快速检索”。 些适合快速检索的数据结构。 方法 适用于多种文本类型,特别是那些可以 很容易就解析成一组词的集合的文本 词索引( word index) 适用于英文 全文索引fu- text index) ■中文等东方文字要经过“切词”处理 北京大息学 张铭 政■印究 张帖写

6 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 31 10.3.1 基于属性的倒排 „ 对某属性按属性值建立索引表，称倒排 表 „ (attr, ptrList) „ （属性值，具有该属性值的各记录指针） „ 记录指针可以是关键码，或该记录的主文件地址 „ 颠覆主文件的顺序，因而称为倒排索引 „ 属性往往是离散型的 „ 对于连续型的索引，往往用B树 „ 倒排文件：带有倒排索引的文件 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 32 0375, 0552 0197 0204, 0673 0100, 0193 0172, 0201, 0221 2500 3000 3500 4000 5000 SAL list EMP# 0197, 0375, 0552 0100 0193, 0204 0673 0172 0221 0201 26 32 39 40 43 47 55 AGE list EMP# 0100, 0221, 0552 0172, 0201 0193, 0197, 0204 0375, 0673 玩具部 食品部 服装部 电器部 DEPT list EMP# 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 33 检索实例 列出玩具部中年龄在50岁以上或者工资在 5000元以上的职工记录 (DEPT=“Toy”AND(AGE≥50 OR SAL≥5000))。 分别找出满足条件DEPT=“Toy”， AGE≥50，和SAL≥5000的指针集合，然后 对后两个指针集合求并，并且将结果集合与第 一个指针集合求交，最后的结果集合中包含的 指针所指的各记录即为所求。 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 34 „ 优点：能够对于基于属性的检索 进行较高效率的处理 „ 缺点： „ 花费了保存倒排表的存储代价 „ 降低了更新运算的效率 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 35 10.3.2 对正文文件的倒排 „ 正文索引(Text Indexing)处理 的就是“建立一个数据结构以提 供对文本内容的快速检索”。 „ 方法 „ 词索引(word index) „ 全文索引(full-text index) 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 36 词索引 „ 基本思想： „ 把正文看作由符号和词所组成的集合，从正 文中抽取出关键词，然后用这些关键词组成 一些适合快速检索的数据结构。 „ 适用于多种文本类型，特别是那些可以 很容易就解析成一组词的集合的文本 „ 适用于英文 „ 中文等东方文字要经过“切词”处理

全文索引 基本思想 词索引使用最广泛 把正文看作一个长的字符串 在数据结构中记录的是子字符率的开始位量 一个已经排过序的关键词的列表 查询就可以针对正文中的任何子字符串 其中每个关键词指向一个倒排表 (每限子柔 z符建立索引,从而使查 (posting list) ■需要更大的空间 指向该关键词出现文档集合 在文档中的位置 张陪写 新。■印乡究 北京太 孔稳写 权新有轴命剑究 阿淘城 倒排索引 pm4e饰e 位 建立正文倒排文件 5细断网 a{68 6每 (L3)(44) 1.对文档集中的所有文件都进 行分割处理,把正文分成多条记 6ke(42) 录文档 切分正文记录取决于程序的需要 e(12)(15(22) 定长的块、段落、章节,甚至一组 文档 张铭帖编写 叔所有,轨圆即 孔写 丽中科院计算所汉语词法分新系统 2.给每条记录赋一组关键词 操作选项 一输出格式 ■以人工或者自动的方式从记录中 语切分一级注二根根注‘北大杯准C米速8 抽取关键词 停用词( Stopword) ”,车整上作 空 a抽词干( Stemming ■切词( segmentation) 北京大息学 张铭 权质有,印究

7 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 37 全文索引 „ 基本思想： „ 把正文看作一个长的字符串 „ 在数据结构中记录的是子字符串的开始位置 „ 查询就可以针对正文中的任何子字符串 „ 可以对每一个字符建立索引，从而使查 询词不再限于关键词 „ 需要更大的空间 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 38 词索引使用最广泛 „ 一个已经排过序的关键词的列表 „ 其中每个关键词指向一个倒排表 （posting list） „ 指向该关键词出现文档集合 „ 在文档中的位置 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 39 倒排索引 1 2 3 4 5 6 7 8 9 10 11 12 13 编号 词语 （文档编号，位置） cold days hot in like nine old pease porridge it pot some the (1,1) (1,2) (1,3) (1,4) (1,5) (1,6) (3,2) (2,2) (2,3) (2,4) (2,5) (3,1) (4,6) (3,3) (4,1) (4,2) (4,3) (4,4) (4,5) (4,7) (4,8) (5,1) (5,2) (5,3) (5,4) (5,5) (5,6) (6,1) (6,2) (6,3) 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 40 建立正文倒排文件 „ 1. 对文档集中的所有文件都进 行分割处理，把正文分成多条记 录文档 „ 切分正文记录取决于程序的需要 „ 定长的块、段落、章节，甚至一组 文档 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 41 „ 2. 给每条记录赋一组关键词 „ 以人工或者自动的方式从记录中 抽取关键词 „ 停用词(Stopword) „ 抽词干(Stemming) „ 切词（segmentation） 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 42