【优秀毕业论文】 基于web的xml中文检索模型的研究与实现.pdf

分类 一 号 单 位代码 学 一 号 叠 了 声菜 六 了 硕士学 位论文 论文题 目基于的中文检索模型的研究与实现 作者 专 姓名 业 公爱国 计算机软件与理论 指导教 师姓名 专业技术职务 石冰教授 年月 日 山东大学硕士学位论文 目录 摘要 绪论 研 究 背景 国内外研究发 展情况 的提出 信息检 索的研究情况 信息检 索与文本 信息检 索 二 本文 研究 内容及 组织 结 构 本章 小 结 相关研 究 数据模型 模型 模型 检索 模型 的 查询 模型分 析 基于简 单关键字的查询方 式 基于结 构匹配与关键 字 相结合的查询 模型 查询模型的选 择 本章 小结 信息检 索 中的索引技术 侧 索引结构 基于路 径 的索引 基于倒排表的索引 基于序列的索引 二 巧 基于联接的索引 侧压检 索模型 的选 择 二 本 章小 结 一 一 一 第页 山东大学硕士学位论文 一种基于关键字查询的检 索模型 引言 二 数学模型 系统架 构 二 索引模型 节 点 的编码 文档 一 关 键字 一 节点 倒 排 表 二 关键字 一 文档 倒 排表 二 索引检 索算法 相 关 度计算 算法 索引 的更新 实验 本章 小 结 卜 二 系统设 计 与 实 现 系统的体 系 结 构 系统 的功 能 结构 的解析处理 一 解析器 的选 择 卜 中文切 词处理 卜 二 索引 的存储及更 新 节点的编码 索引存储设计 索引更新设计 系统 核心算法 二 曰 索引检 索算法 节 点合并算法 今 可 氏 响 二 二 娜 相关度计算算法 二 实验结果 亡 了亡 曰户 第页 山东大学硕士学位论文 实验环境和实验数据 评价 标准 实验 结果及分 析 本 章小结 结束语 参考 文献 致 谢 攻 读学位期 间已经发 表 的 学术论 文 第页 山东大学硕士学位论文 摘要 枷是网络上数据表示 和交换的主要标准 提 高检索效率和准确度是信息 检 索面临的主要问题 信息检索系统与传统的信息检 索 系统不 同 主要体现在 三 个方面 首先检 索的对象不同 检索的对象 是元素 而不是传统信 息检 索的文档其 次 检 索的索引不仅需 要 建立内容索引 还 需要建立 结构信息索 引最 后 由 于检索的对象不同 所 以检索的结果相关度计算算法 也比较复 杂 不 仅需 要按照传 统的信息检索理 论考虑关键 字之 间的距离 还 需要考虑 文档树的结构 为满足 结构复杂 大规模的信息检索的需要 本文 深入研 究了信息 检索的已有理论及 原型系统 主要研究了信 息检索系 统的索引结构和索 引检索 算法 以及检索 结果 的相 关度计算 方法三个方 面 的内容 提出并实现了一 种基于关键字查询的中文检索模型 本文包括个 方面的内容第一 分析 了已有的数据 索引结构 中存在的 问题 提出 了一种高效的基于倒排表的 文 档 一关 键字 一节 点 两级索 引结构 该 结构在不 显著增加索引 的空间占用 的情况 下 包含了更加 丰富的文档的结构和内容 信 息 缩 小了索引检索时文档搜索的范 围 提高了检索的效 率第二 在提出的基于倒排表 的 文档 一关 键字 一节 点 两 级索引 结构的基 础上 提 出了一种 高效的索引检索算法 该算法 与索引结构相结 合 通 过 优化 索引结构的搜 索顺 序 有效 的提高了基于关键 字的信息检 索的 检索效率第三 本文提出 了一种基于 一 的查询 结果相 关度计算算法 该算 法 基于已有的信息检索理论中结果相关度计算算法 既考 虑了数据中关键 字 出现的位置 又考虑了翔文档的树型结构对 查询结果相关度的影响 从而提高 了检索的效 率第四 设计并实现了一个中文信息检索系统的核心功 能原 型 系统一 系统是一个 中文枷信息检 索系统 集成了本文提出的 文档 一关键字一节点 两级索 引结构 基于此索 引结构的索引查询算法和结果 相 关度计算算法 实验证明此 系统可以比较准确 高 效 的完成数据的检索 关键词翔信息检索系统关键字查询倒排表索引相 关度算法 第页 山东大学硕士学位论文 卿 如 雌 一 加明翎 倒礼 劝对 翎 入 劝 一一 一 入卫二 切 劝 翎 劝 加 而 一 袖 侧 勿 朗 劝 留 翎 理 即场 侧 州 叮 心 明址 一 一 一 一 一 一一一 第页 山东大学硕士学位论文 绪 论 研 究背景 随着互联网的兴 起 网络上的信 息大量涌现 这 些信息从结 构 化程度的角 度可以划 分为三 类第一种是完全结构化的数据 如关系型数据和面向对象的数 据第二种是 无结构的文本数据 如 纯 文本文件等还有一种新兴的数据结构 就是半结构化 数据 这种 数据 的最大特点 是拥有不规 则 可变的数据结构 最 典型 的 半结 构 化数据 就是 它己经 成为 工 以及 电子 商 务中进行数据表示 和数据交 换的标准 由于其所具有的自描 述性 灵活的数据结构以及丰富的数 据表 示 能 力 等特点 现 在己经被 广 泛 应用到 工 智 能信 息 检索 电子商务中的数据表 示和数据交换 数据集成 数 字图书 馆等领域 数据 指数级 的增长 要求 实现对数据 更有 效的数据 管理能力和更快 更 准确的 查询 因此 近些年来有 许 多的研究者以及企业都开始研究面向数据 的信息管理 系统 以满足上述需求 大量 信息 的 出现对 信 息检索提出较高 的要求 特别是针对互联网 上的信 息 的检 索 传统 的结 构 化 数 据和无 结 构的文本数据 我 们都己经拥有比较成熟的 检 索理 论 和检索工 具 结构化的数据可 以采 用 关 系 型 数 据库或对象型数据库进 行管理 而无 结构的文本我们则采用可以信息检索 的 方 式进 行 访问 但是传统 的 文本数据检 索的理论 和方 法并不适用于 数据 的检 索 如何 提高检 索 效率和准确度是信 息检 索面临的 主要问题 国内外研究发展情况 的提出 年月万 维网协会设 计提出 了的概念 它 是 的一个 子集 是 针 对和的局 限性而创立 的 既具 有的 强大功 能和 第页 山东大学硕士学位论文 可扩 展 性 同时又具有的简单性 保留了的功能 删除了 中所 有非核心的 未被 使用的和含义模糊的 部 分 其复 杂程度降为的 不仅 适用于站 点 在电子商 务 数据 库 知识管理 数据交流和 共享 自然 语言转 换 等方面都 有广泛的 应用 年以后 在计算 机科学 外的领 域也得到了应 用 例如 等语言 作 为一种元标记语言 可以用来定义 其 他的标记语言 并且这种标记 语言的元素标记 是由用 户自己定义的 的另外一个重要特 点它将文档内容 和显示样 式分隔 开来 文档中的标记是 用来 描述数据元素 的含义 而 不 是 描述其如 何显 示 因此是一种自描 述 的数据 数据的优点在于 适 用于上的数据交换 由 于上存在的数 据既有 结 构 化数据 也有无 结构文本 还有如音 频和 视频那样的流数据 数 据的出现 使得我 们可以实现各 种 格式数据之间 的交换 因为其具有 数据自描述性 能实现更有 意义 更准确 的搜索 数据 的 自描 述能力 使 得 搜索能够 依靠标记 和 文档内元素之 间的依 存关系 实现更加准确的 定位 真正从根本上解 决了当前信息搜索的 问题 它能实现 异构 系统 间的 通信 传 统的结 构化数据库难以适 应多 系统间 异 构数据的融合 而数据由 于其 自描 述性能 很好地适应 这种数据集成 的需 要 这 为未来电子商务的发展 创造了 良好 的软件条 件 规信息检索 的研究情况 根据文 档 存 储的数据 的 不同 文档可以分 为两类 数据文档 在此类文档主要 用于存储 数据数值 其标记和结 构主 要用来表示数据 的意义 文 本 文档 此类文档 中 以文本信息为主 其 标记和结构主要 用来 表 示文本 信 息的逻辑结构 根 据文档的分 类 信息检索可以分 为数据检 索和信息检索两 第页 山东大学硕士学位论文 类 两 者 的区别主要 是检 索的模 式不 同 在数据检 索 中 用 户事先知 道数据 的存储 结构 而在信 息检索中 用户不知 道数据的存 储 结构 而只是 按照自己的构想来组织查询 式 信 息的组织模式不同 在数 据 检索中 所有的数据组织在一定的己知的模 式下 而信 息 检 索的数据的模式是未知 的 或 者互 不相同的 到目前 为止 通 过研究 者的努 力 目前已经取得一 些 成果 比如 幻 和 枷文本 检 索 系统 大 多数的信息检 索的技 术是 来 源于数据库 领域 其所 用 的技 术也 是由信 息检 索 技术 演变而来 对于规信 息检 索 仅仅依靠简 单的遍历是 不可行 的 为了提 高检 索的性 能 必须建 立 高 效的信 息 索引结构和索引检 索算法 同时 为了提高检索 结果的 准确度 结果的匹配度计算也自然被引入到信息检索中来 因此 文档 索引技术 和索引检 索技术 以及 结 果 的匹配度计算是信息检 索研究的主要三 个 方面 其 中 索引技术和索引检 索技术是信息 检索的核心内容 研 究者 们提出了多种 方法对文 档建立索引 如铭 一 兀 田刃 等 索引检 索 算法 与索引 的 结构是紧密联 系在一起的 根 据不同 的索引逻辑结 构 研究者 们提出了多种不同的检 索 算法 如 基于 一 的 基于吧的凡 信息检索 与文本信息检索 以文档为中心 的数据主要 是用来表示人类自然语言描述的数据 如电 子邮件 商务文档和 用 户手册 这种文档具有更复 杂的结构 一般不是机器自 动产生 的 目前 上 的大部分数据 都可以表示成这种文档 而 且近 年来 数 字 图 书 馆 项目中也 出现了大量这样的用于表示书 籍 资料信息 的数 据一 以文档为中心的文档的特点 是半 结 构 化 或 非 结构化的数据较 多的 混和 内容文档 顺序比较重要 对以文档为中心的数据 我 们 通常采 用 类 似于信 第页 山东大学硕士学位论文 巴巴巴巴巴巴竺竺巴巴巴巴巴巴巴巴 息检 索的 方 法 进行 管理 虽然 在 管理以文档为中心的数 据时 我 们可以借鉴信息检索技术 中的 许 多 方 法 但 其与 传 统 的信 息检 索 仍存在 很多不同之处 信 息检 索查询返回的结果是数据 中 的某个 元 素 而不是文本检 索中的文档 在信息检 索 中 结果的排 序方 法上传 统的信 息检 索 技 术 有 很大 不 同 首先 对象不同 传统的信 息检 索 中排序对象是 文档 而在信 息检 索 中则为数据 中的元 素其 次 查 询 结果与 查询条件之间 的相关度计算也有 很 大的不同 在传统信 息检 索 中 相 关度的 计算主 要依据 是 查询 关键字在查询 结果中的位置 和出现 频率 而在信息检 索中 由于查询返 回的结果带有 结 构信息 因此在计算这种复 杂元素 与查询条件之 间的相关度时 还 必 须考虑结 构信息对相关度计算的影 响 由以 上分析可以看出 信 息检 索 较文本 检索更加的复 杂 不能简 单的 将传 统 的文本 检 索的 方法 和模型 用于信 息检索 本文研究内容及组织结构 本文 主要 包含以 下四个方 面的内容 第一 提出 了一种基于倒排 表的 文档 一 关 键 字 一 节点 两级索引结 构 该 索引优化 了对数 据的 结构和内容数据 的索引 通过减 少索引检 索时文档 搜 索的 范围和索 引 的读取次数 提高了检 索 的效率 第二 提出了一种基于此结构的索引检 索 算法 该算法通 过优化 索引结构 的搜索顺序 提高了基于关 键 字的数据 检索的检 索效率 第三 提出了一种基于 一 的 查询 结果 相关度计 算算法 该算法综合考 虑了文档中关键字的 出现频率和文档的树型结构对 查询结果相 关度的 影响 从而提高了检 索结 果 的准确 度 第四 设 计并 实现了 一个中文信 息检 索 系统核心功 能的原型系统一 系统是一个中文信息检 索系统 第页 山东大学硕士学位论文 巴巴巴竺竺巴巴二巴巴巴巴巴巴巴巴 集成了本文提出 的 文档 一关 键字 一节 点 两 级索引结构 基于此索引 结构 的索引 查 询算法 和相关度计算算法 论 文的 组织 结构 如下 第一章 绪论 从总体上 论述 了课题的来源及意义 技术背景和课题 的主 要工作 第二章 检索技术 中的索引技术研 究 论述了数据模型 和信 息检 索系统 中的居 于核心 的索引模型 第三章 信息检索 系 统的 查询模型研 究论述了当前的信 息检索 模型 的分类 第四章 一种 基于关 键 字的检 索 模型 第五章 系统设计与 实现 第六 章 结 束 语 本章小结 本 章主要 介绍了基于的信 息检 索的研 究 背景 课题来源 和意 义节简要介绍了该 领 域当前国内外 的研究发 展情况 简述了信息检 索技 术与传统 文本 信 息检 索技 术的区别 及信息检索 技 术的难点最后 节提出 了本论文 的研 究 内容和 组织 结构 第页 山东大学硕士学位论文 相关研究 在进行本文 的研究之前 我 们需要对信息检 索 系统 的数 学模型 和 查询 模型 进行研究 这是因为信息检 索 系统 中使用的查询模型 决 定了信息 检索系统中各项处 理的实现 方 式 包 括数 据的索引结构 查询处 理 查询 结果相 关度计算等 等 数据模型 数据模型 随着应用的 需 求和人类对于信 息 管理研究的不断深 入而逐 渐发 展 提出了关系 模型 阁 在此基础上建立的关系数 据库 称为当前的 主 流 数据库 系统 随之又出现了面向对象的数据模型 它具有面向对 象 技术 的封 装 性和结构性的特点 因此 基于对象模型的对象型数据库系 统 也应 运而 生 传统 的数据库管理系统使用 的 是 基于结 构 化的数 据 模型 其特征 就 是数 据 库预 先 都有一个固 定的模式 数据遵 守严 格的类型定义 模式 的作用在于检验 数 据和查询优 化 而数据的模式却是不固 定的 国 际上从年代中叶开始 研究数据的模型 并且取得了很 多成 果 模型 数据是由半 结构化数据 发展而来的 半结构化数据 的 内容与模式 都包 含 在 数据中 因此 被 称 为 是 自描述 的 有些半结构化数据没有 单 独的模式 而 有些只对数据做不 严格的 约束 年 斯坦福大学等人 提出 了模型 仁 用于描述半 结构 化 数 据 模型中 半结构 化 数 据可 以用一个有向的标记图来表示 一个对 象由一个 四元组 表示 其 每 个 域的意义如下 变长字 符串 描述对 象的意 义 对象值 的类型 包括两种一种为 原 子 型 如 等另 外一种 为 复 杂类型 包含零 第页 山东大学硕士学位论文 甲尸只甲赚尸 份尸 个 或多个子对象 每个子对象用一条 带标记的边与其相 连 对 象 类 型 为原 子 型 的称为 原子对象 而对象类型 为复杂型的称 为复杂对 象 对象的值 用于唯一标识每 个对象 在中 每个对象 允许有多个父 对象 因此 在 有 向图中允许环的存 在 模型 可严 格定义如 下 半 结构 化数据可用 二 的带有根 节 点 的有向图表示 其中尸 表 示有限节 点集 表示带标记的边 的集合 为标记集 为根节 点 由沿一定顺序的可以访问所有的 节点 模型 文 件由嵌套的 带标记 的元素组成 每一个元 素 又可 以拥有零 个 或 多个属 性值 对 以及零 个或多个子元 素 每个子 元 素 本身也是元素 或 不带 标记 的文本 由 于被定义 为一种标记语 言而 不是数据模型 因此是一种 有序的数据 文件 良构 一 的 文件不对其 中的标记 属性名以及嵌套 模式做 任何 限制 如 果 它符 合一定的文 档类型定义 则 被成 为是合法 的文档 为了在软件 中使用数据 组织 为枷数据定 义 了文档对象模型 用于将 数据映射到一定 的数据 结构中 具有半 结构 化 数 据的许多特征 如自描 述 性 结构的易 变 性 并且 模型中的标记 对 象 原子值 分别对应与中的标记 元素 但与模型 之 间也有 很大 的区别 主 要体现 在以下几个方面 模型不是一个 有序的数 据 模型 对 象的各 个子对 象之 间 没有固定 的顺 序 而则 是有序的数 据 其次 中没有属性的概念 只有子对 象 是一种树型结构的数据 但 它采用特 殊类型的属性和 来实 现 元 素 到元素之间 的链接 从 而 也可演 变成 一种图 型结构 第页 山东大学硕士学位论文 检索模型的查询模型 分析 基于简单关键 字的查询方式 在这 种查询模型中 用户提交的查询是由想 要 查找的关 键 字 构成 这种查 询形式 非 常类似于当前的网络搜索引擎 如 雅 虎 用户输 入 任 意的词 语 短语或一句话甚至一段 文章 作 为查询 例 如 对于图中的数据 用 户 的查 询可以是 查 询 语言 或 信 息 检 索技 术 对于这种 查询其查 询 结果的确 定有两种连续法和非连续法 连 续法 要求结果中包含所有查询 中的关键 字 而非连 续法中则仅 要求查 询结果中包 含 至少一个查询 中的关 键 字 我 们 以连续法 为例 说明确定查 询结果的方法 用户的 查询可 以用包含个 关键字的序列 表 示 若采用 二 叭 任 表示 几 数据中所有直接或 间接包含所有 查 询 关 键 字的节 点 其中表示一个 节 点 表示数 据 中的所 有节点的集合 表示第 个查询关键字 则查 询的结 果为除去中己经 包含全部关键 字的 子节 点后仍 然 包含所有查询 关键 字的 节 点 之所 以除去那些己经包含 全部查 询关键字的子 节点是因为他们也可 以作为一个独立 的 查 询结 果 因为查 询 中并没有规定哪些 层次的节 点才可 以作为结 果节 点 因此任 意层次的满足 查询 条 件的任 意标记 的 节点都可 以作为查询结果而且这 些子节点 相 对于他们 的祖先 节 点来说 是更 具 体的节点 具 有更 强 的区别性 在基于关键字的 查询 结果中力图返回 那 些 最具体的 节 点 第页 山东大学硕士学位论文 吵叮 卜 刀叨信息检索 八 哪 叮 阶 儿 声 数据库技术 比 数据库查询 跳以 对长文本字段采用信息检索技术进行查询二 以 即 叮 阶 叮 数据库技术发展 以 出现了一些新 的数据类型 如 刀功 灯 以 儿 甜 加 数据管理 八 抽 叮 阅通简介 红沈 即 对富含文本 的刀祖数据需采用信息检索 的方法来查询 已对 户 泊 儿 招 八 卿 图富 含文本 信息的文 本 下面举例说明 在图中 的文档 中 若用户的 查询为 富含文本的 数据 则在为的 中的 节点是一个正确的查询结果 而 且是一个最具体 的结果 节 点 因为 它直接包含了所 有查询 关键 字 而 的 节点 的祖先节点 则不会被这回作为 查询结果 虽然它包含了所有查询关 键 字 但是这些关 键 字 都处 于节 点中 而节 点已经被返回作 为 查 询结果了 此外 以上处理保证了在 查询结果集中不会 出现 相互嵌套的结 果 即 不会 出现一个查询结 果包含另外一个查询 结果 的现 象 确 保了查 询结果之 第页 山东大学硕士学位论文 间 的相互独 立 例 如 若查询为 数据库查询 则为的中 的 的子节点 应 该被返回作为一个查 询 结 果 因为其包含了所有查询 关键 字 但其祖先节 点为也 是一个正确的 查 询结果 因为除了后代节 点包含所有关 键字之外 在节点的其 他 地方也包含了所 有的 查询关 键 字 因此也应该 作 为查询结 果返回 但需要 将其中 的节点除 去 基于关键 字的查询模型的优点 是便于用户使用 因为其 查询 界面简单 仅 要 求 用户像传 统的信 息检 索 系统中那样输入自己需 要 的查询 关键字 而对 内结构信息的 处 理则由系统 自动完成 而 且 对于 工 上的信 息而言 由 于其 大多是模式互不相同的 所 以 基于关键 字的检 索 方法特 别适 用于信 息检 索 但其 缺点是基于简单 关 键 字 的 查询模型 的查询结果 由于缺少必要的限制 而经常变 得难以理解 因为这种查询模型 允 许 查 询结果可以是数据中 的任 意层次 任 意标记的 节点 因而当用户浏览这些查询结果时 难以判断 该结果 节 点在源数据所处 的上下文环境 因 而也就是难以理解 该 节 点所包 含 的信 息的意义 例如 当用 户查询为 简 介 时 对图中 的数据会返 回为的 中的的子 节点作为结果 节 点 但 对于用户 来 说 这种 结果节点 太 具 体了 他不 知道这个究竟 是一个元素 还是 一个元 素的信 息 可 以采用两种方法 解决 这个问题一是在返回查询结果 时同时 给 出结果节 点在数 据 中的上下文信息 如 对于节 点 则 相应地给出其父节 点乃至 其 他祖先节点信息 这样用户在浏览查询结果时 就可以根据其对应的上下 文 信 息准确 理 解 该节 点的具体 意义第二种解决办法是由用户 指定 一 些节点 只 有这些节 点才可以作为查询 结果返回的节点 称为 指定结 果 节 点 如果得 到 的 查询结果 是这些 节 点 的后代节 点 则返回包含这 些结 果 节点的指定结 果 节点 若得 到的 查询 结果 不 属于这些 指 定结果节 点的 后代节 点 或 超 过 这 些节点的范 围 则抛弃这部分 结果节 点不返回给用户 例 如在 图中的源数据 用 户可以选择元素 元素作为指定结果 节 点 此时 用户提 交的查 询 的查询 结果中只包 含 这些指 定结果节点元素 第页 山东大学硕士学位论文 基于结构匹配与关键字相 结合的查询模型 在 这 种查 询模型 中 用 户提 交的 查询主 要 由两部分 信 息组成 一部分 是结 构匹配 条件 另一 部分 是查询关 键 字 例如对图中的源数 据用户可以 提 交这样的 查 询 查找所 有 书 中讲述有 关枷数据模型 的章节 用可以 表示为 翔数据 模型 在 这 种查询 中 结构匹配条 件用于指定查 询结果 需满足 的结构条件 而查询 关键 字则指定查询 结果的信 息 中需包含的一 些关键字 该类查询 与查询非常 相 似 不同的地 方在于其 中增加了一 些查询 关 键字匹配 条件 因此这 种查询也可 以类 似于查询表 示 为 一棵查询树 其查询 结果 对 应于源数据树 中的一棵子树 在结果 子树 中所有路径 及标记信息都与查 询树严格匹配 而 且对于查询树 中包含 查 询 关键 字的节 点在 结果子 树中的相应 节 点也应满足这些查 询 关键字匹配 条 件 值 得注意 的是 在这种基于结构匹配和关键 字相结合的查询模型中 只有 那 些 用户指 定 的目标节点在上例中为元 素才 能作为查询结果被返回 其 他的 节点 则一概不予考 虑 而且在这些 目标节点 中即使包 含某些 后代节点也 满 足 查 询 中的关键字匹配条件 也不会作为 查询结果被返回 这一点 与基于简 单关键字的查询模型完 全不 同 基于结构匹配和关键 字相结合 的查询模型的第一个 优 点是用 户可以准确地 找 到自己所需 要 的信 息 即 用户可 以定位于既满 足一定 结构匹配条件又满足 一 定的关键 字匹 配条 件的信息第二个 优点 是用 户可以方 便 清楚地理解 查询 结果 所具 有 的含义 因为这 些结果 都必须是用 户 在查询 中指 定的目标节 点 而不会 出现基于简单关键字的 查 询模型中存 在的查询结果 混杂 意 义含糊不清的问题 但这种查询模型也有一个局 限性 就 是用户在查询数据 之前 则 须 事 先 知道 其所 具有的准确的模式 信息 查 询模型 的选 择 通过综 合以上两种信息检 索模型的查询模型 本文提出的信息检 索模型采 用 基于关键字 的查询模型 原因如下 第页 山东大学硕士学位论文 基于关键 字的查询模型 的接 口简单 用户不需要知道 数据 的逻 辑 结 构 本文提出的信 息检 索 是基于基于数据 的 而上的文 本数 据的模式多种 多样 各 不相同 即 本文 是 建 立在用户不知道 数据 的逻辑 结构的基础上的 而基于结构和关键字 结 合 的查询模型是基于用户事先了解数 据 逻 辑结构的基础上的 所 以 采用此 查询模型是最适合本文 研 究设想 的查询 模型 对于基于关 键 字 的查询模型存在的 查询结果比较模糊 可 以采用不 同 的 结果 表 示 方 法予 以解决 比如采用返回上 下文 的 方法 用户可以通过结果节点 链接浏览该节 点 的上下 文信息 本章小结 本章 研究了 当前信 息 检 索模型 的数学模型和 查询模型 综 合 分析了两种信 息检索 系统的查询模型各 自的特点 和优 缺点 最后节结 合本文 研究分析得出的信 息检索模型的特点 阐述了本 系统选择 基于关键 字的 查询模型的 原因 第页 山东大学硕 士学位论文 信息检索中的 索引技 术 信息检 索不是 根 据 用户的 查询式简单 的遍历文档集 如果这 样的话检索 效 率很 低 为了提高检 索 效 率 信息检索也必须和传统 的 文本 信息检索一样建立索引结 构 并基于索引结构 提出高效的索引检索算法 所以 索引技 术是信息检索 技 术的核心 关系 到信息检 索的检 索 效 率和 准 确度 索引结构 基于路径 的索引 第一类是基于路 径的索引 比如和 通 过路 径 表达式进 行 查询一直 是文档索引和 查询研究领域 内主要的研 究 焦点 之一 试图提 取文档的某 种 结 构抽象 并通过这种结构加速 查询过程 使 用结构指 导 查询处理 这 也 是名称的由来 如图 通 过数据源 可 能得 到或两种 路径索引处 理简单路 径查询有 非常 高的效 率 但它不能很好 的支持 分 支查 询和带 有通配 符的查 询 可以采 取一些改 进 的策略来解 决这 个问题 但那样 往 往使 索引 结构过大 以致于 不能 高效的执行 查询 产 月 碑 们洲阳枉 滚封 乍 戈到妇 洲 人 了 洽 六 点甲 净 人甲 人 甲 卜 南丫 八 甲 也也 也也 也 图数 据 源 及 其 对 应 的 两种 第页 山东大学硕士学位论文 基于倒排 表 的索引 倒排 表索引 是传统 的信息检 索的文档 索引技术 在信息检 索中 倒排 表也 是一项很重要的索引技术 但是 需要根 据的特点进 行改进 不 是以文 档位 索引 的对象 而是节点 等系统的索 引结 构 都 是基于倒排表 的索引 结构 一个 倒排表 索引 是一个倒排 表的集合 其 中每一个倒 排表 都与一个特定的 关键 字关联 特定关键字的倒排表 是 所有包含该关键字 的 节点的统一资源 标志 符 如果关键字在文档中出现的位置 也 需 要索引 那么倒 排表中每一项也包 含一个位置偏 移量 关键 字的位置信息用 来进行模糊 查询 查询 结果 的相关 度计算 倒排 表中的一项 最小是一个 两元 组 其 中 是一个 倒排表的结构如 图所 示 关键字 节点 爪 已力 二 已 即叭 图倒 排 表 示 意 图 构 建倒排 表 的流 程比较简单给定文档 集 解析器首先逐 个扫描 每一 篇文档 用来统计 所有的元数据 如标签然 后 根 据关 键字 生成一组 关键 字 位置元组 并将他们送 到索引器 索引 器将 他们插入 到 倒排列表 中 此 过程循环之 行直到所 有 的文档 都 索引完 毕 基于倒排表 结 构的索引 的优点是索引 的生成算法比较简单 只需 要便 利一次文档集同 时其检索算法也很 容 易实现支 持结果 的相关度计算 但是缺点也很明显 倒排 表 的 体积一般比较大 为数据集的 一 所 以其生成和检索需要占用较 大的资源 第页 山东大学硕士学位论文 基于序列 的索引 和在最 近两年内出现 这种索引 方法把文档和查 询表达式 都 转 化成某 种 序列 然后通 过子序 列匹配 寻找数 据库中匹配的模式 图是 一个简单的文档 使用的索 引方法 我们把 文档进行 序 列化 编 码 编码结果 如图 其中 每 个括号里逗 号前面的字 符是文 档 节点 的名 字 后面 的字 符串是由根节点到 该 节 点 的路 径 所有的括号以逗号前 面的字 符为 关键字 按照先 序遍历文档 树型结构的次序排列 飞 盆 双 阮 口 二口 工 口 上刁亡翻艺 刀 翻甚周口 鱿吕 刀亡益口七七 习 图一个简单的 州压文档 力二 望遨 少迅且 柳 材 恤 朽 夕 材 汪巧才 尸泞 卿 飞 尸 了 仙 司 石 习 共 尸习乏 晰 燕 图文档的序列 化编码 和查 询匹配 这种 索引模 式 对分支查 询和带有通配符的 查询具有天 生 的优势 是现 在 索引方法最令人激动的一个研究方 向 但是 我们发 现这种 索引方法含 有 以下一些缺点通 过把 整 个文档 转化成序列的方式 来建立索引结构 索引 的大小往往不能得到 很好 的控制 同 时 非连续的 子串匹配意味着匹配 点分散 在 整 个 索引结构中 这不可 避 免的需要大 量的磁盘 并且 不幸的是 由 第页 山东大学硕士学位论文 巴巴竺巴三巴竺巴巴巴巴竺巴巴 于匹配点是分散的 通 过 增 大 磁 盘 单页大 小的方式几乎不能改 善查 询性 能 约 该类方法利 用了文档 中相似模 式反复出现的特 性 但 我 们认 为 相反地 文档的这个特 点迫使该 类算法搜 索 索引的 大 部分区域 来寻找匹配 搜索的 中间结果集可能比较大 即使最后结 果集比较小 目前流 行的做法是在或树的路 径 或节点上建立索引 路 径索引 能够高效的进行简单 查 询 但是 含有 分 支 结构的 查询通常要被 分解成多个子 查询 每个 查询对 应树上的一条路径 然后 通过耗 时的联 结操 作把 子查询 的 结 果组合 成最后的结果 因 为 同样 的原因 这类方 法不能高效 的 处 理 或 这类 涉及多条 路径 的 查询 为了避免耗 时 的联结操作 一些索引方法在 频 繁出现的多 路 径查询上建立 特殊 索引 这种方法 潜在的缺点有必须 了解查询 模式不是普适的方 法 因为并不 是所有的分支查 询都能得到优 化索引可能因 此变的很 大 而 且难 以维护 高效 的检索半 结 构化的数 据 必须同 时在文档 的 结 构和内容上建 立索引 然而 很多算法仅仅在结构上建立 索 引 或 者分 别 在结构和内容上建 立索引 基于联接的索引 另外一种是 基于联接操 作的索引 方法 使用 这种方 法 时 一个复杂 的路 径表 达 式被分解成多个 被称 为 原子表 达 式 的基本 路 径表 达 式 通过访问索 引结构 可以直 接得到原子表达式的查 询结 果 所有 其 他 形 式的 查询表达式都 包 括 联接操作 和就是属 于 这种索 引 方法 工 通过几个算法来处 理正则路 径表 达 式查询 分别 为 一 用来 搜索由一个元素到另外一个元素 的路径 叭用来扫描 有序的元 素 和 属 性 以查找元素一属性对 一 用来 在重复的 路径或元素上查找 一 这种索引方 法能够处理带 有 通配符的 查 询 但是 联接操作的运 算复 杂 度 较 高 使查询的处理 效率不高 算法 过多的依赖联接 操 作 更 使 这 种 情况恶化 第页 山东大学硕士学位论文 检索模型 的选择 通 过 综合以上 四种信息检 索 模型 的 查询模型的优缺点 本文提出的 信息检 索系统 采用基于倒排 表结构的索引模型 原因如下 本文提出的信息检 索系统是基于关 键 字 的查询模型 在 检索时不需 要考 虑检索文档的结构以及 节 点之 间 的关系 而是要求 在索引过程中 索引 的结构信息 通 过 节 点的编码可以在基于倒排 表的索引上实现 这一要求 基于倒排 表 的索引结构的生成算法实现只需要遍历一次文档集 生 成索引 的效 率比较 高 另外三种索引需 要 根 据文档的结 构建 立索引 基于倒 排表的索引检 索 效 率比较 高 只需要 遍历 一次包含 关键字的倒 排 索引 即可 基于序列 和联接的索引模型 的查询需 要进 行联结操 作 降低了检 索 效率 基于路径的索 引模型不需要进 行 联接操作 但是仅支持结 构 化 的查询 对于非结构 化 的查询却只能采用模糊查找的 方法 效 率比较 低 为了提高检 索准 确 度 本文提出 的信息检 索系统需 要对结果进行 相 关度计算 基于倒排表的索引结构支持 结果 的排序 输出 而另 外 三种 模型都 需要在 查 询 结果时进 行 大量 的模式匹配计算 基于倒 排 表的索引结构 占用空间大 的缺点 可 以通 过 优化 数据 结 构等方 法 减少 存储空间 的占用 并通 过磁盘 页面簇 集优 化 方 法减 少 磁 盘的次数 提 高检 索 性 能 本章小结 本 章 研 究分析了数据 索 引技术的相 关 理论 和 最新进展 以及 当前 检索模型 的优 点和存在的一 些缺陷 下 一章 我 们将 对检 索模型中的查询 模型作 深 入研 究与 分析 一 一 一 一 一 第页 山东大学硕士学位论文 一种基于关键字查询的 检索模型 引言 数据作 为一种 数据 表现 和交换的格 式 正 在赢得巨大 的成功 特别 是在 上被 广泛接受 和 采用 随着的 不断普 及 数据 的管理和 查询问 题 也越 来越 引起人 们 的重视 当前 基于文本 数据的关 键字检 索已经有了相 当成熟的模型和系统 比如和百度等 搜 索引擎 但是 将基于文本 数据的关 键 字检索 的 模型直接应用于检索还存 在很多问题 这是由 于仅仅是 一种表示语 言 不能够表达语义 数据模型则通 过 自定 义标签弥补了的这种局 限 用于表示半结构化 的数 据 使用 查 询 语言 例 如 是文档 检 索的一种方法 但是这种 检 索方法需要 用户 学习查询语言 并且了解文档的结 构 模 式 另一种方 法 是 基于关键 字查询的方法 其 特点是查询方 法简单 用户不需要学 习复杂的查询语言 不需 要事 先了解 检 索 信 息的组织结 构 基于关 键字查询的 人 检索方法 面临以下几个问题 检 索返回的结果 应该定位到包含关键 字的节点 即元素 传统检 索 仅 仅是 定位文档 检索应该支 持结果排 序 但 是文档检 索 中的查询 结果的 相关度计算 相对复 杂 文 档本身是一棵 树的结构 所以在检索 中 结果的相关 度计算不仅 应该考虑距离的 因素 还 应 该考虑 到关键字 在文档树 中的位 置 针 对上述问题 研究者提出 的解决方法有和 使用 基于编码 的倒排 表 对元 素 内容建立索引并提出算法 用于计算元素 与查 询关键字之间 的 相 关度 该算法 是 对算法的改进 支持 面向节 点的检索和结果 排序 但 是其 索引 结构比较 简单 检 索效率仍可以通过优 化 索引结构加以改 进 另外 其相关度算法仅适 用于含有联 接的文档 第页 山东大学硕士学位论文 根据 关 键 字在文档 中 的位置对关键字进 行标识 使用树结构 作为文档 索引 的结 构 但是当 侧压 文档较大时其 树 结 构的索 引文件 会占 用比较 大的空间 所 以运行时 需要大量的内存空间 检 索效 率比较低 要实 现高效 的 查 询 必须 建 立 一 定的索引来 支 持查询的实现 目前提出的 索引方法从实现思想上可以分为两大类 第一类为结构归纳法 如 铭 下 一 等第二类 为节点定位法 如 刃又 等 结构归 纳 法的主 要思想 是对整个 源数 据的结构进行 归 纳 总结出所 有出现过的标记路径 以及 这 些标记路径可到达的 节 点 执行 查询 时 首 先将用户 的查询 转 换为结 构归 纳中的标记路径集 进而确定其所到 达的所有节点目标节 点集 然后检验 这 些节 点 是 否满足 用户查询中的其 他 条 件 对源数 据的 结构归纳可 以用 图结 构表示 也可以采用其 他的方式如等 节 点 定 位法 的 出发思想 是 为源数据中的每个节 点赋予 一些定 位 值 并根据 这些定 位 值确定 节点之 间的关 系 如父子 祖先一后代关 系 左邻居 右邻居 节点一 属性等 执行查询 时 将用户的查 询 分 若 干 步 完成 路 径 表达式 中的每一个标 记或 通配符 对应于一步 每一步 中 从当前节 点集开始 通过 包含 连 接 使用每个节 点被赋予 的定位 值 确定 该步所 对 应的结果节 点 集 该结果节点集又作为下一步 中的 当前 节点集 如 此循环直至完成整个查询 为了提高检索效率和检 索 准确度 本 文 提 出了一种新 的 入二检 索模型 该模型使用 基于倒 排 表的 文档 一 关键字 一 节点 的两 级索引结构 一一 吻 和 基于该索引的检 索 算法 支持面向节 点的索引检索 而且该 算法 是线性的 从而提高了检 索的效 率本文还 提出一个 基于 一 的相关 度 计算 方法 支持了返 回结果 的排序 数 学模型 文 档可以用树来表示 称为树 一棵 州 树可 以定义 为 第页 山东大学硕士学位论文 竺生已匕二竺二二二二二二二二二 其 中 其中 为节点元 素的集合为数 据 集合 因为文档 中的数据 分 为 属性和元素包 含 的 内容 而属性都 可以表示 为子元 素 所以本 文 中我们 约定 所 有 的数据为元素数据 代表元素之间 的 关联 边 的集 合 定义 任 是的子 元 素 或 者数 据 表示 了文档的结构 劝护 卜 力司工 助 介卜 扭 加招 加卿姗 枷 助玲 卿 厄诚加玲 厄诚加巧 吵 枷 护 娜 户 地司 如几犯 声 触 白 沁护 址 址而场卿二 罗 瓜 目 访护舒在如匆晓李沁护 访护 允抽 户 卜 刀 灿抬抬 抬叮叮叮 菌函心 址 曰 允娜户 灿 沙 图文档实 例图文 档树 设查 询关键字集 合 二 二 其 中 为一个 查询关键字 设谓词 表示关键 字直接或 间接包含于节 点 对一个关键 字的 查询结果集合 一 八 设 是包含所有 关键字的节点 任八任 那么 对 于 关键字集合 二 其 查询 结 果可以表示 己 八 忆 八 表示至少包含一个查询 关键字的元 素的集合 其 中不包含子 元素中包 含关键字的元 素 这是因为 如 果其子 元 素中包含了关 键 字 那么 其子元素 一 一 一 一 一 一一 一 一 一 第页 山东大学硕士学位论文 就应 作为 查 询结果 如 图所示文档 如 果查询关键字 为 结 果 应 该是 行 行 第行 索 索引建立 立 查询结果 卜一 用户查询 图系统 架构 系统架构 我们提出 的基于关键 字的检 索 模型 的系统架 构 如 图所示 索引 建立 模块 用于将 州比文档建立 文档 一 关键字 一 节点 的两 级索 引结构 索 引检 索 模 块 接收用 户 的 查询 检索索引文档 并将检 索结果排 序 后返回给 用 户 索引模型 节点的编码 节 点编码 是唯一表示 节 点 的方法 常用 的节 点编码有基于 起始 位置 的编 码 基于节 点在文档树种 的遍历顺 序的编码 本模型使用前 缀 编码 方法表示文档 中 的节点 这种 编码 方法使用 父节点 的编码作为子节 点 的编 码的前 缀 图 当判断节 点关系时 只需判断是否成立 其 中是 兄弟节点的序 号 使用编码 我们 可以很 容 易确定节点之间 的关 系 当对多个 关 键 字 进行 查询 时 包含关键字的节 点可能位于文档 第页 山东大学硕士学位论文 树的不同层次上 编码能表示 节 点在文档 树中的位置 这 样易于进行多 个节点的合并处理编码支持 文档的 更新操 作 缺 点 是 解析编码 解析算法的 时 间效 率比较 低 睡 一 巨亘 一性巫二堕座到 图文档 一 关 键 字 一 节 点倒排 表 文档 一关 键 字 一节点倒 排表 文档 一 关 键字 一 节点 倒排 表 一一 一 一 一 的 结构如图 所示文档 一 关键字 一 节 点倒排表的结构是一个三 元 组毛 表 示文档的唯一编号表 示关 键字 是包含关键 字的节 点 的信 息的一个三元组 表示 该节 点在文档 中的前缀 编码 表示关键 字 在节 点中的位置 表示关键字对于该节点 的相 关 度 文档 一 关 键 字 一 节点倒排表是一个两级 的倒排索引结构 第一 级索引是文档 关键字 索引 此 索 引包含了每一文档包含的所有的关键 字 其关 键字列 表按照关键字的检索 次数倒 序排 列第二级索引 是关 键 字 一 节 点索引 包 含了每 一个关键 字在 该 州压 文档中所在的节 点 的编 号 位置及 关键 字相对于该 节点 的相 关 度 其 中节 点信 息按照节 点的编号的字 典顺序排列 这 就保证了可能合 并的节点是由低到 高顺 序 排列的 使用文档 一 关键字 一 节点倒排 表 减少了索引 文件的次数 只需 要 检 索一个文档的索引 每一个文档 索引仅需 要一次 进行一遍检 索 易于合 并 操 作 提 高了检 索效率 检索一个 关键 字 就可以根 据 关键 字 一 文档 索引检 索出一篇文档 中包含查询关键字的所有 节 点 然 后可 以进 行 针 对 此 文档的合并处理 在实际实现 中 可以分布式 检 索不同 文档的索引 一 一 一一 一 一 一一一 第页 山东大学硕士学位论文 图 关 键 字 一 文档倒 排 表 关键字 一文 档倒 排 表 关键 字 一 文档倒 排表 一一 的结 构 如 图 是 一个二元组 表示关 键字表示包 含 该 关 键 字的文档的信息 的结 构是一个两元组笼 是该文档的唯一编号 是 关 键 字相对于文档的相关 度评 分 我们设其计算公式为 夏 表示文档 表 示节点 关键字对于文档的评分 我们是取关键字对 于该 文档 中的节 点的评 分的最大值 关键 字 一 文档 倒排表 缩小了检 索的 范 围 检索包含关键 字的文档的 文档 关 键 字 一 节点 索引就可以找 到 该文档中所有包含 关键 字的节 点 索引检索算法 我 们提出的索引检索算法 是基于我们提出的索引结构的 如 图 算法 首 先通过检索关键 字 一 文档索引 一 行 确 定 需要检索的文档然后检 索文档 一 关 键 字 一 节 点索引找 到包含关键字的节 点 一 行 找出文档 中包含关键 字的 节点 并对节点 按照编 码字 典排序最 后 根 据公式和公式合 并和计算节 点相对于查询的相 关度 一 行 节点合 并处理中 算法使用栈记 录访问过 的节 点的编码 与 当前访问 节点的编码 的最大公共前 缀行 然后弹出所 有不属于公共 前缀的项 一 行如 果弹出项 包 含了所有的关 键 字 则把它 添加到 结果表 中否则 就按照 第页 山东大学硕士学位论文 公 式和公式将 他们加 入 到 其父节点中 即栈中的下 一项 算法 的检 索以文档为中心 检 索范 围是所有包含关 键 字的文档 而 且对每 一篇文档仅需要扫 描一次 就 能确定该 文档中所 有 包含关键 字的 节 点 所以该算 法 的时间复 杂度是 即按照关 键 字 的数目线性增长 的 但 是由于使用了 文档 一 关键 字表 并且显然 需要合并的节 点都 是包含于同一文档 内的 因 此 该算 法在实际实现 时可以分 布式并行处 理 文给出 了算法合 并部 分 的 时空复 杂度 证 明 设查 询 第一个处 理 的关键字是 根 据 关 键 字 一 文档倒排表 找到包含 侧比 的第一个文档 编号为 对于 文档 在文档 关键字 一 节 点倒 排索引 表中查 找 包含 和 昭 的 节 点 得 到 表 如图所 示然后 对表 进 行合并处 理 对的每一个 节 点 依次处 理 一 第一个处