第九章 表与信息检索.ppt

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