第九章表与信息检索-Read.pptx

第九章 表与信息检索 1 、各种表查找 2 、散 列 矩形表的存储 存储方式 ： 行主存储(row-major-ordering) 列主存储(column-major-ordering) 矩形表的寻址 矩形表的查找： 寻址公式(Index function)与访问表(Access table ( i ， j )在矩形表中的位置是： n ×i + j 各种矩形表的变形 主对角型、三角型 三角型表的寻址 下(上)三角型表的寻址公式与访问表 (i ， j)的寻址公式是 1+2+…+i + j = ½i(1+i)+j `锯齿状的表(jagged table) 锯齿型表的查找 例 :基于8行10列的表 倒排表 为什么要用倒排表 除了主关键字外 ， 在实际应用中需要对其它属性(次关键字)进行搜 索 。利用次关键字建立索引表 ， 称之为次索引表 ， 以提高搜索效 率。 次索引表的组织方式： 在次索引表中列出该属性所有的值 ， 对每一个取值建立有序表 ， 即 把所有具有相同属性的对象按其存放地址递增顺序或者按主关键 字递增的顺序排列。 为了掌握每种取值的对象的数量，增设对应链表的长度。因此，次索引表的每一 索引项由次关键字、链表长度和链表三部分组成。 所谓倒排表就是次关键字建立的次索引的组合。 在次索引中按主关键字递增排列的优点是： 一旦对象的存储地址发 生修改 ， 只要修改主索引 ， 次索引可以一概不变。 学号 姓名 性别 专业 成绩1 · · · 08 男 · · · 03 男 · · · 83 女 24 男 47 女 95 男 56 女 · · · 倒排表映象图 主索引表 数据表(区) 次关键字 长度 女 3 男 4 次索引表 08 24 47 56 83 95 03 关键字 指针 24 95 47 56 83 08 03 100 400 600 300 700 500 200 地址 倒排表的例 例 稀疏矩阵(Sparse matrix) 稀疏矩阵的三元组存储 0 0 1 0 0 0 0 0 0 0 2 5 0 0 0 0 0 7 0 8 进一步可表示成 0 2 1 2 0 2 2 1 5 3 2 7 3 4 8 三元组序列 十字链表表示稀疏矩阵 十字链表的构成 每一行或列中的非零元素分别组成一条循环链表 ， 若某行（列） 全为零元素 ， 该行（列） 所对应的链表是只含有头结点的空链表。 各行的链表的头结点另行构成一条循环链表 ， 各列的链表亦然。 整个链表由一个“头结点 ”引入。 每一个非零元素的结点 ， 按其所在的行与列 ， 同时处于相应的行循环链表与列 循环链表中。 结点的构造 col right row value head down 2 5 T 0 T 十字链表的例 T 4 3 2 4 F 7 3 1 1 5 0 2 4 F 2 2 F 2 1 5 F T 0 F 3 8 T 0 2 例 1 函数的定义 下标函数(index function) 抽象类型 散列表(hash table) 例 拉链法 拉链表