全文检索技术研究与应用论文 (2).doc_第1页
全文检索技术研究与应用论文 (2).doc_第2页
全文检索技术研究与应用论文 (2).doc_第3页
全文检索技术研究与应用论文 (2).doc_第4页
全文检索技术研究与应用论文 (2).doc_第5页
已阅读5页,还剩26页未读, 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

摘 要 全文检索是现代信息检索技术的一个非常重要的分支 它是处理非 结构化数据的强大工具 也是搜索引擎的核心技术之一 本文对中文全 文检索的有关技术进行了较为深入的研究 在基于字表的全文索引方面 本文提出了一种改进的倒排索引结构 同传统索引结构相比 更便于索 引的构建 维护 更新 本文的重点放在了全文检索技术的应用上 对 如何利用新技术 改善检索系统的结构 提高检索系统的性能和效率 加快检速度 不断适应网络信息发展等方面做了重点研究 全文检索是一种 IO 密集型的应用 以往的全文检索系统的开发多在 关系数据库的基础上进行 本文针对全文数据库的特点 深入讨论此法 弊端与不足 并提出了在文件系统上构建的解决方案 由于目前全文检 索系统的开发平台并不多见 本文介绍了一种全文检索引擎工具包一 Lucene 它功能强大 小巧精悍 便于嵌入各种应用 近年在世界各地 被广泛使用 诸如 IBM 等公司都使用其核心代码 作为一个开源软件 它为我们学习搜索引擎的核心技术提供了绝佳的机会 对其剖析研究 进行二次开发 是一件很有意义的事情 在应用方面 本文主要工作是本校学位论文全文数据库的设计与实 现 关键字关键字 全文检索 倒排文件 Lucene 全文数据库 自动分词 THE RESEARCH AND IMPLEMENTATION OF FULL TEXT RETRIEVALSYSTEM ABSTRACT Full text retrieval is an important information retrieval technology It is a powerful tool fordealing with nonstructural data and is one of the key technologies of the search engine This paper deeply research on Chinese full text retrieval technology In the filed of full text index based on word inverted table a improved word based Chinese inverted index structure is proposed which has a better performance than traditional approaches and convenient for constructing maintaining and updating index According to its characteristic we design its corresponding optimized search method Analysis shows that better dynamic performance and high indexing speed is possible using this structure This paper pays more attention in application of full text retrieval technologies How to use new technique optimize the structure of retrieval system improve performance and efficiency quicken search speed and adapt the development of current web is also discussed in this paper Full text retrieval is an I O intensive application Its previous developments are carried on the basis of relation database This paper deeply discusses the abuse and deficiency of this mode according to its characteristic Because the development platform of full text retrieval is absent currently Lucene a full text search engine toolkit is introduced into the paper It has powerful performance and its body is cabinet capable and vigorous this convenient for it embedded applications At present Lucene is employed world abroad so that many professional companies such as IBM also use its core code As an open source code soft Lucene offer a superexcellent chance to study search engine key technology It is worthful to take a parse research and carry second development to it In the application aspect this paper work mostly in the design and implement of the degree dissertation full text database in university KEY WORDS Full text Inverted File Lucene Full text Database Divided Syncopation 0 目 录 一 全文检索技术简介 1 1 1 论文研究背景 1 1 2 什么是全文检索 1 1 3 全文检索与关系数据库 2 1 4 全文检索需要解决的问题 3 二 建立索引库 4 2 1 索引文件分类 4 2 1 1 顺排档结构 4 2 1 2 倒排档结构 4 2 2 倒排索引压缩 6 2 2 1 倒排索引压缩初步实现 6 2 2 2 动态文本集的倒排索引压缩方案 7 2 2 3 Lucene 压缩技术 8 2 3 索引增量更新 9 2 3 1 利用 B 树实现倒排索引的更新 9 2 3 2 Dual Structure 索引结构 10 2 3 3 Lucene 索引过程优化 11 三 中文分词研究 12 3 1 什么是中文分词 12 3 2 为什么需要中文分词 12 3 3 中文分词技术 14 3 3 1 基于字符串匹配的分词方法 14 3 3 2 基于理解的分词方法 17 3 3 3 基于统计的分词方法 18 3 4 分词中的难题 18 3 4 1 歧义识别 19 3 4 2 新词识别 19 四 索引数据库的搜索 21 4 1 词库查找方法 21 1 4 2 LUCENE搜索算法 21 4 3 搜索过程优化 23 参考文献 25 致 谢 26 0 一 全文检索技术简介 1 1 论文研究背景 信息时代产生了大量数字信息 而这些信息大致可分为两类 结构 化数据和非结构化数据 结构化数据指的是诸如企业财务帐目和生产数 据 学生的分数数据等等 非结构化数据的则是一些文本数据 图象声 音等多媒体数据等等 据统计 非结构化数据占有整个信息量的 80 以 上 对于结构化数据 用 RDBMS 关系数据库管理系统 技术来管理是 目前最好的一种方式 但是由于 RDBMS 自身底层结构的缘故使得它管理 大量非结构化数据显得有些先天不足 特别是查询这些海量非结构化数 据的速度较慢 而通过全文检索技术就能高效地管理这些非结构化数据 国内外对全文检索的研究方兴未艾 己有一些较成熟的商用产品相 继问世 中文全文检索与英文检索相比 由于自然语言体系不同 索引 机制也不完全相同 英文以词为单位建索引 与字母无关 而中文以字 为最小单位 再者 英文的分词以空格和标点为分界符 而汉字的分词 往往依赖于词库 因而中文全文检索与英文实现相比困难些 不得不承 认目前国内的研究水平与国际上还有较大差距 坐等国外成果 然后加 以移植改造的老路是行不通的 因此在国内进行全文检索的研究非常必 要 1 2 什么是全文检索 全文检索是指计算机索引程序通过扫描文章中的每一个词 对每一 1 个词建立一个索引 指明该词在文章中出现的次数和位置 当用户查询 时 检索程序就根据事先建立的索引进行查找 并将查找的结果反馈给 用户的检索方式 这个过程类似于通过字典中的检索字表查字的过程 全文检索是指以文本为检索对象 允许用户以自然语言根据资料内 容而不仅是外在特征来实现信息检索的手段 全面 准确和快速是衡量 全文检索系统的关键指标 全文检索不仅可以实现对数据资料的外部特 征的检索 诸如标题 作者 摘要 附录等 而且还能直接根据数据资 料的内容进行检索 实现了支持多角度 多侧面地综台利用信息资源 总之 全文检索技术是现代信息检索的一项重要技术 1 3 全文检索与关系数据库 全文检索提出基于文件系统的全文数据库 使用文件系统存储文档 建立全文库时 文本的添加 删除 更新可以通过全文数据库管理系统 来实现 因此可以说是实现了一个微型的专门为全文检索设计的数据库 系统 所谓微型的 是因为它只实现数据的增 删 改 查找 获取 而不涉及复杂的事务处理等 使用文件系统构建全文数据库的根据如下 1 无论关系数据库还是全文数据库最终数据都是以文件的形式存 在的 数据库实现的基础是文件 对数据库的任何操作最终要转换为对 文件的操作 当前占主流的关系数据库是文件系统的发展 文件系统中 每个文件存储同质实体的数据 各文件是孤立的 没有体现实体之间的 联系 关系数据库中 数据的物理组织必须体现实体之间的联系 支持 数据库的逻辑结构 因此数据库要存储四方面的数据 数据描述 即数据 2 外模式 模式 内模式 数据本身 数据之间的联系和存取路径 这四 个方面的数据都要采用一定的文件组织方式组织存储起来 1 而全文数据库可以说是介于文件系统和关系数据库之间的体系结构 它一般包含的实体少 实体间的关联也少 结构相对简单 对事务性和 并发性要求不高 所以一般情况下 基本的检索过程应采用文件系统来 实现 这样使得查询直接 快速 有效提高执行速度 2 全文数据库不需要事务支持 考虑到全文数据库系统的操作主要是读数据 写操作主要是插入新 数据 删除和修改几乎没有 插入数据往往是间隔一段日期 待积累了 一定的新文献数后才进行 而且即使有数据插入 也不需要锁住读操作 因为用户只是查询文献 暂时看不到新加入的文章 以往的数据照样可 以使用 所以 数据库根本不需要事务支持 而对事务的管理恰恰是很 费时间的 这样在效率上就能得到很大提高 实际上 当前各大搜索引擎 其后台存储的主流设计都是基于自设 计的文件系统 1 4 全文检索需要解决的问题 一套完整的全文检索一般包括 1 对不同文本的统一处理 2 索引的建立 考虑索引压缩率 是否支持动态索引更新等问题 3 对汉语词语进行正确的切分 4 检索问题 考虑检索效率 查全率 查准率等问题 3 5 排序问题 本文就围绕以上 5 个问题进行分析与研究 二 建立索引库 2 1 索引文件分类 2 1 12 1 1 顺排档结构 顺排档结构 顺排档文档是以 DocID 为主序的 每一文档下存放各自出现的词的 ID 及各词所出现的次数和具体位置信息 各数据项的存储长度固定 2 4 2 1 22 1 2 倒排档结构 倒排档结构 1 一级索引 一级索引文件属于记录式文件 每一记录大小固定 共有三个数据项构成 WordID 文档数 第一个文档开始位置 其中 WordID 是词典中词条的 ID 文档数是指这个词总共在多少个文档中出现 文档开始位置是一个文件指针指向二级索引中出现当前词的文档集中的 第一个文档存储位置 这个指针是一个长整形值相当于指明了是二级索 引文件中的第几条记录 因为各记录长度也是固定大小 通过这个指向 可以直接定位到二级索引文件读取位置 然后读取 nDocs 个记录即可 因为它们是存放在连续的地址空间上 2 二级索引 二级索引也是一种记录式文件 每一记录有三个数 据项组成 DocID 出现次数 第一个 Hit 位置 其中 DocID 是文档的 ID 出现次数指的是当前文档中某一个词出现的次数 第一个 Hit 位置 5 也是一个指针 指向 Hits 文件中的某一位置 通过这个指针就可以直接 定位到 Hits 位置中的读取位置 这样连续读取 nHits 个记录就可以将所 有当前词在当前文档中的出现的位置信息都读入 这些文件将属于同一 WordID 下的所有文档记录按其词在整个文档的权值从大到小排列 3 Hits 位置信息文件 这些文件每一记录只有一个数据项 即 Hit 位置信息 只记录了各词在文档中出现的位置 将同一词在同一文 档中的出现位置按出现的先后排列 这样在读取文档并提取摘要时只需 对字符串从头到尾扫描一边即可 不需要来回扫描 2 2 倒排索引压缩 2 2 12 2 1 倒排索引压缩初步实现倒排索引压缩初步实现 一个倒排索引通常由字典表文件 dictionary file 和记录文件 postings file 两部分组成 字典文件记录了文本集中出现的每个单 词及其倒排列表在记录文件中的位置和大小等信息 一个单词对应的倒 排列表可以表示为 n d1 f1 di fi dn fn n 表示单词在 n 个文档中出现 di 为文档 ID fi 为单词在文档 di 中出现的词频 是单词出现在某个文档中的位置列表 事实上 一个倒排列表可拆分为三部分 1 一个文档 ID 序列 1 i n 2 n 个位置序列 3 一个词频序列 其中 第 1 和第 2 两个序列都是 6 递增的整数序列 鉴于这种递增的特性 可以用间隔 di 1 di 和 pik 1 pik 来代替序列中的值 那么上边三个整数序列就转化为如下形式 1 一个文档 ID 间隔序列 2 n 个位置间隔序列 3 一个词频序列 转化成间隔后 没有损失任何信 息 因为初始倒排列表总是可以通过计算间隔的和还原 此外 还给序 列的取值带来了两个影响 样本空间缩小 概率分布不均衡性扩大 因 此预示着存在基于概率分布的高效压缩方法 目前己经提出了一些模型 描述整数值的概率分布 适用于对以上任一序列的压缩 这些模型可以 分成两类 1 全局模型 所有序列使用相同的压缩参数 2 局部模型 对于不同序列 其压缩参数是不同的 这个参数通常 是单词的出现频率 局部模型的压缩效率一般高于全局模型 且在解码 速度方面也很有优势 但实现更复杂 2 2 22 2 2 动态文本集的倒排索引压缩方案动态文本集的倒排索引压缩方案 我们考虑文本集动态性时 将文本内部的动态调整用两次文本层次 的调整代替 即对一个文本作文字改动视为删除旧文本和增加新文本 因此一般只考虑文本层次的索引动态同步调整 上文 3 1 节提到一个倒 排列表可拆分成三部分序列 事实上这三部分的动态特性并不相同 根 据这一特点 我们可以采用混合编码的方案 对三部分序列实施不同的 压缩方法 力求在满足动态性的前提下 尽可能地实现高压缩率 7 位置序列记录的是某单词在一个文本内部的位置 由于只考虑文本层次的增加 删除 所以该序列内部的值不会发生任何 的改动 它是静态的 可以采用压缩率较高的任何压缩方法 与文档 ID 序列和词频序列相比 位置序列占用的索引空间往往多于二者 故而位 置序列的压缩对整个倒排索引的压缩率起决定性作用 到目前为止 压 缩率最高的首推二进制内插编码 虽然它的压缩与解压比较耗时 但与 由压缩减少的 I O 时间相比 可以忽略 因此我们可以对位置序列采用 二进制内插编码 与位置序列不同 文档 ID 序列和词频序列 会随文档的增加 删除而增删序列的元素 所以必须 采用支持动态性的压缩方法 二进制内插编码虽然有较高的压缩率 但 它不支持序列的动态更新 所以不能采用 能够支持动态序列的压缩方 法主要有 可变字节编码 编码 和 编码 三者中压缩率最高的 是 编码 所以对两个序列都采用 编码 需要指出的是 由于文档 ID 序列是递增序列 所 以多将其先转化成间隔序列后再进行压缩 这就给后续的增加元素操作带来了困难 例如 文档 ID 序列 它对应的间隔序列为 对该序 列进行压缩 如果今后增加一个文档 19 则需要知道文档 ID 序列最后 一个文档 ID 的值 17 才能求两者的间隔值 2 19 17 而由间隔序列得出 17 必须从头到尾解压整个序列 然后求总和才能得到 这就需要额外的 I O 时间和解压时间 尤其是对于较长的序列来说更是一笔可观的开销 为避免这一问题 我们可以把文档 ID 当前的最大值存放到单词表里该倒 8 排列表对应单词信息中 词频序列不是递增序列 不用转化为间隔形式 因此不存在类似文档 ID 序列的问题 从文档 ID 间隔序列中删除一个元素则比较简单 只需修改其后的一 个元素值为两者的和即可 如上例中的文档 ID 序列 如果删除文档 9 则间隔序列修改为 第三个 3 1 2 2 2 32 2 3 LuceneLucene 压缩技术压缩技术 为了减小索引文件的大小 Lucene 对索引也使用了压缩技术 首先 对词典文件中的关键词进行了压缩 关键词压缩为 例如 当前词为 阿拉伯语 上一个词为 阿拉伯 那么 阿拉伯语 压缩为 其次大量用到的是对数字的压缩 数字只保存与上一个 值的差值 这样可以减小数字的长度 进而减少保存该数字需要的字节 数 例如当前文章号是 16389 不压缩要用 3 个字节保存 上一文章 号是 16382 压缩后保存 7 只用一个字节 注意是 上一个词 由 于词典是按顺序排列的词典是按顺序排列的 这种压缩方法的效果会非常显著 2 3 索引增量更新 2 3 12 3 1 利用利用 B B 树实现倒排索引的更新树实现倒排索引的更新 文献 3 提出在倒排索引的字典表上建一个 B 树索引 以支持字典表 的扩充 B 树的索引项就是单词 一个单词对应的倒排列表放在一个 B 树块中 如果一个块装不下 则在堆文件 heap file 中分配一片连续 的空间 再从 B 树叶子节点链一条指针到堆文件中 此后 若倒排列表 还要膨胀 超出了已有空间 则重新在堆文件 heap file 中分配一片 9 空间 把原倒排列表迁移到新空间中 再将新增倒排列表合并到后面 然后将旧空间标记为空闲 对这个堆文件的管理可以采用动态存储空间 分配的算法 如伙伴系统 使用堆文件来处理溢出 会增加查询时的 I O 的时间 由于使用伙 伴系统管理堆文件可能导致频繁地申请和释放空间以及频繁地迁移索引 数据 在字典表上建一个 B 树 显然需要额外的硬盘空间存放 B 树索引块 而且每次查找倒排列表都需要从 B 树的树根遍历到叶子节点 因此增加 了查找的时间 2 3 22 3 2 Dual StructureDual Structure 索引结构索引结构 文献 3 提出了一种 Dual Structure 索引结构 它动态地区分长 短倒排列表 并对长 短列表采用两种不同的存储结构及配套的检索 更新策略 其一是针对短倒排列表的 某词通过静态散列函数映射到桶里 一 个桶可以装多个倒排列表 桶数是固定的 且每个桶都只有一个存储块 每个词的倒排列表初始都是短倒排列表 当某个桶溢出时 将桶中最长 的倒排列表晋升为长倒排列表 在字典表中做上标记后 将它迁移到长 倒排列表使用的存储结构中 这样就动态地实现了长 短倒排列表的区 分 另一种是将长倒排列表放在变长的连续块中 且末尾预留一部分空 闲空间 这些块不让其他词的倒排列表共享 对于给定的词 可以通过 查单词表来判定它是否对应一长倒排列表 该方法有以下不足 10 1 它只考虑了文档的插入操作 而忽略了删除操作 2 采用静态散列函数 不管文档的多少 桶的大小及桶数都不能改 变 且不同桶之间不能共享存储块 这样 当文档量很少时 桶空间大 量闲置 造成空间的浪费 而当文档量很大时 即使是非高频词的倒排 列表也会变得较大 桶数远远满足不了它们的需要 所以 需要一种动 态散列表的支持 使得桶的数量可变 3 动态地区分长 短倒排列表的策略虽然简单 但也不尽合理 只 要发生桶溢出便把最长的倒排列表转移到长倒排列表的存储区 会误把 相当数量的短倒排列表排挤到长倒排列表中 4 对长倒排列表的管理采用的是绕开操作系统直接管理硬盘的方式 这样做不适合多任务操作系统 因为当还有其他程序要读写磁盘时 很 难保证不发生错误 2 3 32 3 3 LuceneLucene 索引过程优化索引过程优化 大部分的搜索 数据库 引擎都是用 B 树结构来维护索引 索引的 更新会导致大量的 IO 操作 Lucene 在实现中 索引一般分 2 种情况 一种是小批量的索引扩展 一种是大批量的索引重建 在索引过程中 并不是每次新的 DOC 加入进去索引都重新进行一次索引文件的写入操作 文件 I O 是一件非常消耗资源的事情 Lucene 先在内存中进行索引 操作 并根据一定的批量进行文件的写入 这个批次的间隔越大 文件 的写入次数越少 但占用内存会很多 反之占用内存少 但文件 IO 操作 频繁 索引速度会很慢 在 IndexWriter 中有一个 MERGE FACTOR 参数可 以帮助你在构造索引器后根据应用环境的情况充分利用内存减少文件的 11 操作 根据我的使用经验 缺省 Indexer 是每 20 条记录索引后写入一次 每将 MERGE FACTOR 增加 50 倍 索引速度可以提高 1 倍左右 三 中文分词研究 目前在中文搜索引擎领域 国内的搜索引擎已经和国外的搜索引擎 效果上相差不远 之所以能形成这样的局面 有一个重要的原因就在于 中文和英文两种语言自身的书写方式不同 这其中对于计算机涉及的技 术就是中文分词 3 1 什么是中文分词 众所周知 英文是以词为单位的 词和词之间是靠空格隔开 而中 文是以字为单位 句子中所有的字连起来才能描述一个意思 例如 英 文句子 I am a student 用中文则为 我是一个学生 计算机可以 很简单通过空格知道 student 是一个单词 但是不能很容易明白 学 生 两个字合起来才表示一个词 把中文的汉字序列切分成有意义的 词 就是中文分词 有些人也称为切词 我是一个学生 分词的结果是 我 是 一个 学生 3 2 为什么需要中文分词 目前的搜索引擎 大多是基于一种称为倒排索引的结构 4 以什么 做为索引的 Key 值 直接影响到整个搜索引擎的准确度 召回率 速度 12 我们先看看不使用中文分词的情况 如果不使用中文分词 可以采用单个汉字索引方式 例如 雅虎 先索引 雅 字 然后再索引 虎 字 同样 对于一篇文章 先把所有的 汉字都单独索引一次 并记录他们的位置 搜索过程中 也是先找 雅 字的所有文档 再找 虎 字的所有文档 然后做交叉 与 运算 即包含 这两个字 而且位置连续的文档才会做为符合要求的结果 这种方式是 最基本的索引方式 现在有些小引擎中还在使用 但这里存在一个很有 挑战性的问题 总共的常用汉字是 3000 多个 我们每次查询过程中 进 行 与 操作的计算量会相当大 对于大数据量搜索引擎来说 超过 10 亿 的文档 每天上亿次查询 这样的索引结构 无疑是对硬件和算法的极 大挑战 考虑到速度问题 如果不使用分词 还有另外一种选择 n 元组合 索引方式 2 元 3 元等 拿 2 元来说 中国人 先索引 中国 再索引 国人 同样 对于一篇文章 以 2 为单位 把所有相邻的汉字都索引起 来 并记录他们的位置 搜索过程中 也是先找包含 中国 的所有文档 再找 国人 的所有文档 然后做交叉 与 运算 即包含这两个单元 而 且位置连续的文档才会做为符合要求的结果 这样以两个字做为索引单 元 可以大大减少在搜索过程中的计算量 以上两种方式 都可以不需要分词 也能实现搜索引擎的索引和搜 索 但是这里存在一个不可忽视的问题 准确度 一个很常见的例子 和服 如果按照上面两种方式 都会查到包含 主板 和服 务器 的文档 北大 也会得到 东 北大学 对于大数据量的搜索引擎来说 每个搜索 次都会有成千上万个结果 用户已经很挑选他真正想要的文章 如果这 13 里还要增加许多错误 估计用户体验会极差 这时候 我们需要中文分 词 词 是中文语言中最小的语意单位 以词为单位做为搜索引擎的索 引的 Key 值 会大大提高搜索引擎结果的准确性 同时保证了搜索过程 中计算量小 其实还有一个优点 以词为单位的索引 索引库会比上两 种方式小很多 很明显 如果以 中国人做为一个词 那么搜索的时候 不需要任何 与 运算 索引的时候记录也会减少 3 3 中文分词技术 中文分词技术属于自然语言处理技术范畴 对于一句话 人可以通 过自己的知识来明白哪些是词 哪些不是词 但如何让计算机也能理解 其处理过程就是分词算法 现有的分词算法可分为三大类 基于字符串匹配基于字符串匹配的分词方法 基于基于 理解理解的分词方法和基于统计基于统计的分词方法 5 3 3 13 3 1 基于字符串匹配的分词方法 基于字符串匹配的分词方法 这种方法又叫做机械分词方法 它是按照一定的策略将待分析的汉 字串与一个 充分大的 机器词典中的词条进行配 若在词典中找到某 个字符串 则匹配成功 识别出一个词 按照扫描方向的不同 串匹配 分词方法可以分为正向匹配和逆向匹配 按照不同长度优先匹配的情况 可以分为最大 最长 匹配和最小 最短 匹配 按照是否与词性标注 过程相结合 又可以分为单纯分词方法和分词与标注相结合的一体化方 法 常用的几种机械分词方法如下 最小匹配算法 14 在所有的分词算法中 最早研究的是最小匹配算法 Minimum Matching 该算法从待比较字符串左边开始比较 先取前两个字符组成 的字段与词典中的词进行比较 如果词典中有该词 则分出此词 继续 从第三个字符开始取两个字符组成的字段进行比较 如果没有匹配到 则取前 3 个字符串组成的字段进行比较 依次类推 直到取的字符串的 长度等于预先设定的阈值 如果还没有匹配成功 则从待处理字串的第 二个字符开始比较 如此循环 例如 如果还没有匹配成功 取出左边两个字组成的字段与词典 进行比较 分出 如果 再从 还 开始 取 还没 字典中没有此词 继续取 还没有 依次取到字段 还没有匹配 假设阈值为 5 然后从 没 开始 取 没有 如此循环直到字符串末尾为止 这种方法的优点是 速度快 但是准确率却不是很高 比如待处理字符串为 中华人民共和国 此匹配算法分出的结果为 中华 人民 共和国 因此该方法基本上 已经不被采用 最大匹配算法 基于字符串的最大匹配 这种方法现在仍比较常用 最大匹配 Maximum Matching 分为正向和逆向两种最大匹配 正向匹配的基本思 想是 假设词典中最大词条所含的汉字个数为 n 个 取待处理字符串的 前 n 个字作为匹配字段 查找分词词典 若词典中含有该词 则匹配成 功 分出该词 然后从被比较字符串的 n 1 处开始再取 n 个字组成的字 段重新在词典中匹配 如果没有匹配成功 则将这 n 个字组成的字段的 最后一位剔除 用剩下的 n 一 1 个字组成的字段在词典中进行匹配 如 此进行下去 直到切分成功为止 15 例如 待处理字符串为 汉字多为表意文字 取字符串 汉语多为 表 假设比较的步长为 5 本文步长 step 都取 5 与词典进行比较 没有 与之对应的词 去除 表 字 用字段 汉语多为 进行匹配 直至匹配到 汉语 为至 再取字符串 多为表意 循环到切分出 文字 一词 目前 正向最大匹配方法作为一种基本的方法已被肯定下来 但是由于错误比 较大 一般不单独使用 如字符串 处理机器发生的故障 在正向最大 匹配方法中会出现歧义切分 该字符串被分为 处理机 发生 故障 但是使用逆向匹配就能得到有效的切分 逆向最大匹配 RMM Reverse Directional Maximum Matching Method 的分词原理和过程与正向最大匹配相似 区别在于前者从文章或 者句子 字串 的末尾开始切分 若不成功则减去最前面的一个字 比如 对于字符串 处理机器发生的故障 第一步 从字串的右边取长度以步 长为单位的字段 发生的故障 在词典中进行匹配 匹配不成功 再取字 段 生的故障 进行匹配 依次匹配 直到分出 故障 一词 最终使用 RMM 方法切分的结果为 故障 发生 机器 处理 该方法要求配备逆 序词典 一般来说根据汉语词汇构成的特点 从理论上说明了逆向匹配的精 确度高于正向匹配 汉语语句的特点一般中心语偏后 有研究数据 单纯 使用正向最大匹配的错误率为 1 169 单纯使用逆向最大匹配的错误率 为 1 245 实际应用中可以从下面几方面改进 同时采取几种分词算法 来提高正确率 改进扫描方式 称为特征扫描或标志切分 优先在待分析 字符串中识别和切分出一些带有明显特征的词 以这些词作为断点 可将 原字符串分为较小的串再来进机械分词 从而减少匹配的错误率等 16 逐字匹配算法 逐字匹配算法 基于 TRIE 索引树的逐字匹配算法 是建立在树型词 典机制上 匹配的过程是从索引树的根结点依次同步匹配待查词中的每 个字 可以看成是对树某一分枝的遍历 因此 采用该算法的分词速度 较快 但树的构造和维护比较复杂 一种改进的算法是和最大匹配算法 相结合 吸取最大匹配算法词典结构简单 TRIE 索引树算法查询速度 快的优点 因此词典结构和最大匹配词典构造机制相似 区别在于词典 正文前增加了多级索引 匹配过程类似 TRIE 索引树进行逐字匹配 在性 能上和 TRIE 索引树相近 还可以将上述各种方法相互组合 例如 可以将正向最大匹配方法 和逆向最大匹配方法结合起来构成双向匹配法 由于汉语单字成词的特 点 正向最小匹配和逆向最小匹配一般很少使用 一般说来 逆向匹配 的切分精度略高于正向匹配 遇到的歧义现象也较少 统计结果表明 单纯使用正向最大匹配的错误率为 1 169 单纯使用逆向最大匹配的错 误率为 1 245 但这种精度还远远不能满足实际的需要 实际使用的分 词系统 都是把机械分词作为一种初分手段 还需通过利用各种其它的 语言信息来进一步提高切分的准确率 一种方法是改进扫描方式 称为特征扫描或标志切分 优先在待分 析字符串中识别和切分出一些带有明显特征的词 以这些词作为断点 可将原字符串分为较小的串再来进机械分词 从而减少匹配的错误率 另一种方法是将分词和词类标注结合起来 利用丰富的词类信息对分词 决策提供帮助 并且在标注过程中又反过来对分词结果进行检验 调整 从而极大地提高切分的准确率 17 3 3 23 3 2 基于理解的分词方法基于理解的分词方法 这种分词方法是通过让计算机模拟人对句子的理解 达到识别词的 效果 其基本思想就是在分词的同时进行句法 语义分析 利用句法信 息和语义信息来处理歧义现象 它通常包括三个部分 分词子系统 句 法语义子系统 总控部分 在总控部分的协调下 分词子系统可以获得 有关词 句子等的句法和语义信息来对分词歧义进行判断 即它模拟了 人对句子的理解过程 这种分词方法需要使用大量的语言知识和信息 由于汉语语言知识的笼统 复杂性 难以将各种语言信息组织成机器可 直接读取的形式 因此目前基于理解的分词系统还处在试验阶段 3 3 33 3 3 基于统计的分词方法基于统计的分词方法 从形式上看 词是稳定的字的组合 因此在上下文中 相邻的字同 时出现的次数越多 就越有可能构成一个词 因此字与字相邻共现的频 率或概率能够较好的反映成词的可信度 可以对语料中相邻共现的各个 字的组合的频度进行统计 计算它们的互现信息 定义两个字的互现信 息 计算两个汉字 X Y 的相邻共现概率 互现信息体现了汉字之间结合 关系的紧密程度 当紧密程度高于某一个阈值时 便可认为此字组可能 构成了一个词 这种方法只需对语料中的字组频度进行统计 不需要切 分词典 因而又叫做无词典分词法或统计取词方法 但这种方法也有一 定的局限性 会经常抽出一些共现频度高 但并不是词的常用字组 例 如 这一 之一 有的 我的 许多的 等 并且对常用词的 识别精度差 时空开销大 实际应用的统计分词系统都要使用一部基本 的分词词典 常用词词典 进行串匹配分词 同时使用统计方法识别一 18 些新的词 即将串频统计和串匹配结合起来 既发挥匹配分词切分速度 快 效率高的特点 又利用了无词典分词结合上下文识别生词 自动消 除歧义的优点 到底哪种分词算法的准确度更高 目前并无定论 对于任何一个成 熟的分词系统来说 不可能单独依靠某一种算法来实现 都需要综合不 同的算法 据了解 海量科技的分词算法就采用 复方分词法 所谓复 方 相当于用中药中的复方概念 即用不同的药才综合起来去医治疾病 同样 对于中文词的识别 需要多种算法来处理不同的问题 3 4 分词中的难题 有了成熟的分词算法 是否就能容易的解决中文分词的问题呢 事 实远非如此 中文是一种十分复杂的语言 让计算机理解中文语言更是 困难 在中文分词过程中 有两大难题一直没有完全突破 3 4 13 4 1 歧义识别歧义识别 歧义是指同样的一句话 可能有两种或者更多的切分方法 例如 表面的 因为 表面 和 面的 都是词 那么这个短语就可以分成 表面 的 和 表面的 这种称为交叉歧义 像这种交叉歧义十分常 见 前面举的 和服 的例子 其实就是因为交叉歧义引起的错误 化 妆和服装 可以分成 化妆 和服装 或者 化妆 和服 装 由于没有 人的知识去理解 计算机很难知道到底哪个方案正确 6 交叉歧义相对组合歧义来说是还算比较容易处理 组合歧义就必需 根据整个句子来判断了 例如 在句子 这个门把手坏了 中 把手 是个词 但在句子 请把手拿开 中 把手 就不是一个词 在句子 19 将军任命了一名中将 中 中将 是个词 但在句子 产量三年中将 增长两倍 中 中将 就不再是词 这些词计算机又如何去识别 如果交叉歧义和组合歧义计算机都能解决的话 在歧义中还有一个 难题 是真歧义 真歧义意思是给出一句话 由人去判断也不知道哪个 应该是词 哪个应该不是词 例如 乒乓球拍卖完了 可以切分成 乒乓 球拍 卖 完 了 也可切分成 乒乓球 拍卖 完了 如果没有 上下文其他的句子 恐怕谁也不知道 拍卖 在这里算不算一个词 3 4 23 4 2 新词识别新词识别 新词 专业术语称为未登录词 也就是那些在字典中都没有收录过 但又确实能称为词的那些词 最典型的是人名 人可以很容易理解句子 王军虎去广州了 中 王军虎 是个词 因为是一个人的名字 但 要是让计算机去识别就困难了 如果把 王军虎 做为一个词收录到字 典中去 全世界有那么多名字 而且每时每刻都有新增的人名 收录这 些人名本身就是一项巨大的工程 即使这项工作可以完成 还是会存在 问题 例如 在句子 王军虎头虎脑的 中 王军虎 还能不能算词 新词中除了人名以外 还有机构名 地名 产品名 商标名 简称 省略语等都是很难处理的问题 而且这些又正好是人们经常使用的词 因此对于搜索引擎来说 分词系统中的新词识别十分重要 目前新词识 别准确率已经成为评价一个分词系统好坏的重要标志之一 20 四 索引数据库的搜索 4 1 词库查找方法 词库的查找过程其实是一个典型的字典问题 dictionary problem 可以使用三类方法 1 一类是基于单词比较 comparison based 的方法 如 顺序查找 折半查找 二叉排序树 平衡二叉树等 其查找的效率 依赖于查找过程中比较的次数 且这类方法一般都有一个前提就是单词 必须事先排好序 2 第二类是基于表示法 representation based 的方 法 如 串树 trie 其查找不是建立在单词的比较上 而是利用组成 单词的字母字符序列或数字序列的逐个比较 尤其适合于英文单词和数 值的查找 3 第三类则是无需经过任何比较 一次存取便能得到所查单 词位置的散列法 通过对单词 K 作某种算术运算 f K 计算的结果就是 K 及其相关数据的存储位置 45 若对于不同的单词得到同一散列值 便产生了冲突 冲突会降低查询效率 因此应尽量避免 4 2 lucene 搜索算法 21 1 把 tii 文件调入内存 7 2 在内存中用二分查找找到相应的 Block 3 把 tis 文件中相应的 Block 调入内存 4 在 Block 中顺序找到相应的 Term 5 Term 在索引里是有序排列的 6 采用二分查找机制来定位索引里的 Term 7 在 Index 包 TermInfosReader 类中的实现代码 private final int getIndexOffset Term term throws IOException int lo 0 binary search indexTerms int hi indexTerms length 1 while hi lo int mid lo hi 1 int delta pareTo indexTerms mid if delta 0 lo mid 1 else return mid return hi 22 4 3 搜索过程优化 lucene 支持内存索引 这样的搜索比基于文件的 I O 有数量级的 速度提升 8 而尽可能减少 IndexSearcher 的创建和对搜索结果的前台的缓存也 23 是必要的 Lucene 面向全文检索的优化在于首次索引检索后 并不把所有的 记录 Document 具体内容读取出来 而起只将所有结果中匹配

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论