（计算机软件与理论专业论文）备份系统中流式全文索引嵌入模型的研究与设计.pdf

中山火学硕二l 学位论文备份系统中流式伞文索引嵌入模型的研究 j 设计 备份系统中流式全文索引嵌入模型的研究与设计 专业名称 计算机软件与理论 硕士生 曾芳 指导教师 倪德明副教授 摘要 随着本地存储设备容量的增大 文件数量的增多 数据备份系统中的归档 集规模也日益庞大 现有的数据备份系统 无论是开源还是商用 归档管理中都 缺乏对归档文件按内容搜索的功能 用户在归档集中寻找相关内容的信息时 需 要手动在成千上万个归档文件中查阅 严重地降低了信息查找的效率 本文首次提出将全文搜索与数据备份系统相结合的思路 即在备份文件的 同时对文件建立全文索引 最终实现对归档集进行按内容搜索的功能 备份系统 对文件的处理是一次扫描的 为了提高性能 我们希望备份和建索引的过程是在 一次扫描过程中同步完成的 然而 备份系统中文件是以数据流的形式输入的 备份处理是对数据流中连续的固定大小的数据段分次进行 这意味着一个文件可 能要被分成多段处理 现有的开源全文搜索引擎 处理文件时都是以完整文件为 处理单位 不支持对文件数据流的多段处理 在数据备份系统中 我们需要的是 一个能够支持文件流式全文索引的子模块 本文介绍了全文搜索引擎原理及中文分词等关键技术 通过分析各种类型 的文件格式以及研究开源搜索引擎框架l u c e i l e 的内部结构 建立了一个流式全 文索引的嵌入模型 然后用半形式化的语言 对数据流及流式嵌入模型的特点进 行了分析与描述 在该理论模型的指导下 结合现有技术实现了一个应用原型 该原型支持对文件数据流的分段文本提取和全文索引 并能够作为子模块嵌入到 数据备份系统中 使备份与全文索引过程同步 有效地把全文搜索同数据备份系 统结合起来 最终实现了对备份生成的归档集进行按内容搜索的功能 本文同时 也为有相似需求的领域提供了设计级复用的基础 关键词 数据备份 流式 文本提取 全文索引 中山人学硕上学位论文备份系统中流式全文索引嵌入模型的研究j j 设计 r e s e a r c ha n dd e s i g no fe m b e d d e dm o d e lo f s t r e a m i n gf u l l t e x ti n d e x i n gi nb a c k u ps y s t e m m a j o r c o m p u t e rs o 胁a r ea 1 1 dt h e o r y n a m e f a n gz e l l g s u p e i s o r a s s o c i a t ep r o d e m i n gn i a b s t r a c t a sas t e a d yp r o 伊e s si sm a d ei nw e b s e a r c m n gt e c l l l l 0 1 0 9 y w ec a l lf l n dm em o s t w a l l t e di n f o m a t i o n 锄o n gm a s so fi n e l e v a n to n e si nm ei n t 锄e tm o r eq u i c k ly a tt h e s 锄et i m e t l l em l m b e ro fd o c u m 饥t si si n c r e a s i n gf 瓠t s i n c et h es t o r a g ed e v i c e sa r e 黟o w i n gl a r g c r s oh o wt o 丘n ds o m es p e c i 6 cf i l e sq u i c k l ya m o n gl o t so fl o c a lf i l e s b c c o m e sv e r yc m c i a l n o w a d a y se v e r yd a t ab a c k u ps y s t e i l l n om a t t e ro p e l l s o u r c eo r c o m m e r c i a l o f f e r sn oa b i l i t yo fs e a r c h i n gm ec o n t e n t so fa r c h i v e s w h e nu s e r sw a n t t of i n ds o m er e l e v a n tc o n t e n t t 1 1 e ys h o u l dc h e c ke a c hf i l ei nc d r o m so rd i r e c t o r i e s o n e b yo n e t k sr e d u c e s t h ee 伍c i e n c yo fi n f o n i l a t i o nr e t r i e v a ld r a s t i c a l l y t h i s 枷c l ea n a l y s e st h ed e f i c i e l l c i e so fc u 盯饥td a t ab a c l i j ps y s t e i i l si na r c h i v e s m a l l a g e i l l e n t a n da p p l yt h et e c h n o l o g yo f 如l l t e x ts e 鲫 n gi n t od a t ab a c k u ps y s t e m s t be na b l eu s e r ss e a r c m n ga r c 1 1 i v e s w ee s t a b l i s ha 如1 1 一t e x ti n d e xd a ta b a s e 仔o mm e c o n t e l l to f 绯 h i v e s w h 锄d o i n gs o m eb a c k u p w ed e f i n i t e l ys h o u l ds c a nf i l e so n c e t bi m p r o v et h ep e r f o m l a n c eo fi n d e x i n g w ec r e a t et l l ei n d e xd a t a b a s ea tm es 锄e t i m e t h a tm e a n sb a c k u pa i l di n d e x i n gt a k ep l a c es i m u l t a n e o u s l y s i n c em ed a t ao f f i l e si st m s 触 e di nm ef o mo fd a t as t r e 锄 f i l e sw i l lb ec u ti m os e v 删p a r t s 7 i t l e r e a r em a n ye 瓶c i e n to p e l l s o u r c e 如1 1 t e x ts e a r c he i l 百n e s h o w e v e rw h e l lt h e ya r e c r e a t i n gi n d e x e s e a c hf i l es h o u l db e 仃a n s f e ri naw h 0 1 er a m e rt h a ni np a r t s a sa r e s u l t m ee x i s t i n go p e l l s o u r c ed e s k t o ps e a r c he n 百n ec a nn o tb eu s e da sas u b m o d u l ei nb a c l u ps y s t 锄d i r e c t l y w bn e e da ni n d e x i n gm o d u l e w h i c ha l l o w st h e d a t ao ff i l e sa r et r a n s f e r r e di nt h ef i o mo fd a t as t r e 锄 n l em a i np u 叩o s eo f 衄sa n i c l ei st os o l v em ep r o b l 锄m e n t i o n e da b o v e f i r s t w e 百v eab r i e fi n 臼o d u c t i o no fs o m ek e yt e c h n o l o 百e s s u c ha s n l ep r i n c i p l eo f 向1 1 一t e x ts e a r c he n 舀n ea 1 1 dc 1 1 i n e s ew o r d s e g m e n t a t i o ne t c a r e rad e n s er e s e a r c ho f i i 中山大学硕上学位论文 备份系统中流式全文索引嵌入模型的研究与设计 s e v e r a lc o m m o nf o 衄a t so ff i l e s a n dt h e 觚n e w o r ko fl u c e n e v h i c hi saf a m o u s o p e n s o u r c es e a r c he n 舀n e w ec r e a t ea l l 锄b e d d e dm o d e lo fs t r e 锄i n g 如l l t e x t i n d e x i n g t h e nw ei n 仃d d u c ea n da n a l y s e ss o m ek e yf e a t u r e so fd a t as t r e 锄a n dt h e m o d e li ns e m i f o m a l l a n g u a g e u n d e rt h eg u i d eo fm i sm o d e l w eg e ta p r o t o t y p e w h i c hc a ns p l i tf i l e si n t od a t as t r e a n l sa n dd os t r e a m i n gi n d e x i n g a n dt h e nw e i m p l e m e n tt h ep r o t o t y p ea sas u bm o d u l ei nad a t ab a c k u ps y s t e i l l w h i c hh a sa p l u g i na r c h i t e c t u r e b a c k u pa 1 1 di n d e x i n gt a k ep l a c es i m u l t a j l e o u s ly a n dw ef i n a l l y o 位rt h eu t i l i t yo fs e a r c h i n ga r c h i v e sb yc o n t e n t t h ea 1 1 a l y s e sa 1 1 dd e s i 印c a nb e r e u s e di ns o m es i m j a ra r e a s k e y w o r d s d a t ab a c k u p s t e 锄i n g i i l f 0 舯a t i o ne x 仃a c t i o n 如1 1 t e x ti n d e x i i i 原创性声明 本人郑重声明 所呈交的学位论文 是本人在导师的指导下 独立进行研究 工作所取得的成果 除文中已经注明引用的内容外 本论文不包含任何其他个人 或集体已经发表或撰写过的作品成果 对本文的研究作出重要贡献的个人和集 体 均已在文中以明确方式标明 本人完全意识到本声明的法律结果由本人承担 学位论文作者签名 肾菪 日期 洳簿厂月扣日 使用授权声明 本人完全了解中山大学有关保留 使用学位论文的规定 即 学校有权保留学位 论文并向国家主管部门或其指定机构送交论文的电子版和纸质版 有权将学位论 文用于非赢利目的的少量复制并允许论文进入学校图书馆 院系资料室被查阅 有权将学位论文的内容编入有关数据库进行检索 可以采用复印 缩印或其他方 法保存学位论文 学位论文作者签名 咻 日期 细8 年歹月肜日 导师签名 够蝴 日期 z 艿年应月 p 日 中山大学硕士学位论文备份系统中流式伞文索引嵌入模型的研究与设计 第1 章绪论 1 1 本文的研究背景 本节作为本文研究结果的应用项目背景概述 简要地介绍数据备份的概念 流式数据处理等内容 并针对现有备份系统存在的不足 提出改进思路 1 1 1 数据备份概念 信息技术的迅猛发展 使得人们对计算机信息系统的依赖性越来越强 随 之数据增长越来越快 价值愈来愈宝贵 管理好计算机中的各种数据资源对人们 的工作乃至生活至关重要 因此近年来 数据备份与恢复技术的发展和利用逐渐 得到人们的重视 数据备份顾名思义 是指为防止人为操作失误或系统故障等导致数据丢失 损坏 对文件 文件系统或其他需要使用的资源进行的备用复制 通常是将这些 资源复制到磁带机或者可移动存储设备上 数据备份是容灾的基础 有了数据备 份 就可以在系统遭受破坏或其他特定情况下 对数据重新加以利用 1 1 另外 我们也可以把数据备份作为历史数据归档的一种方式 将历史数据按照计划进行 备份 不仅可以防止数据意外丢失 也可以为我们对历史数据进行查询 统计以 及分析等工作提供保障 在文献 2 中 对数据备份的流程给出了详细和准确的定义 备份 拷贝 转换 传输 存储 管理 即 备份就是对各种需要备份的原始数据使用对应的 方式进行拷贝 然后根据需要对拷贝数据进行一系列的数据转化 包括压缩 加 密等 转换后的数据通过某种方式传输到介质 并且以适当的存储结构存储在 选定的介质中 数据备份系统中 数据是流式处理的 因为备份数据是以数据流的形式输 入的 数据流具有下列特点 3 1 数据源源不断地到达 数据量庞大 中山大学硕上学位论文备份系统中流式全文索引嵌入模型的研究与设计 2 数据是有序的 不断增加 分段读取的 3 数据 经处理 除非特意保存 否则不能被再次取出处理 或者再次提 取代价较高 数据流的特点决定了不可能控制它流出的顺序 也不可能在内存中存储所 有的数据 1 1 2 流式数据处理 上一节中提到了数据流式处理 流式处理是一种处理数据的方式 当前 流 式处理主要应用于大规模的多媒体数据文件 为了节省传输带宽 提高数据的处 理效率 图形图像 声音等在网络的传输过程中 大多采用流式处理方式 微软 w i n d o w s 自带的m e d i ap l a y e r 就是一种流式处理多媒体数据的工具 可用于流式 地实时播放音频 视频和多媒体文件 通过这种流式处理方式 媒体数据可以边 下载边播放 而且不占用客户端的存储空间 处理和播放完随即被清除 在传输 过程中 数据流具有严格的前后时序关系 研究领域内 流式处理也主要应用于对多媒体数据的应用 文献 4 介绍了 一种二维图像空间转换的流式处理算法 这种算法可以把具有高分辨率的二维图 像 经过一系列过滤之后 转换为低分辨率的二维图像 并且输出的低分辨率图 像失真度很低 在对网络多媒体数据的处理中 文献 5 给出了一种多层次的内 存预取结构 在存储器芯片的内外两个层次上实现对多媒体数据的预取 以节省 网络带宽 文献 6 中提出 在流式处理时 可以根据多媒体文件的内容对数据 进行预记录 从而保证数据传输和播放的连续性 流式处理具有传输速率高 数据同步 稳定性高等特性 是实现网络音频 视频传输的最佳方式 如今 流式处理技术被广泛运用于与多媒体相关的多种领 域 当然 流式处理的思想还可以应用于更加广泛的领域 除了用于处理多媒体 数据类型外 还可以用于处理其他类型的数据 比如上节提到的备份数据 1 1 3 对于现有备份系统的改进思路 目前 存在很多成熟的数据备份系统 研究领域 以研究存储管理和备份 中山大学硕士学位论文备份系统中流式全文索引嵌入模型的研究与设计 策略者居多 如 a m 锄d a p s t o r e v 髓t i 等 商业领域 备份软件市场主要被 v e r i t a s c a l e g a t o 三大公司所占领 另外i b m h p c o m p a r e 等传统硬 件厂商也推出了自己的备份软件 然而 所有的这些数据备份系统 对归档集的管理都比较薄弱 它们不支 持对归档集按照内容来进行搜索 使得归档资源查找效率十分低下 用户在归档 集中寻找包含特定内容的文件时 需要手动在庞大的归档资源中一一查阅 操作 非常不便 随着归档介质容量的不断增大 归档集资源也日益膨胀 站在高效利 用资源的角度 迫切需要实用的理论和方法来处理如此海量的信息 当前的搜索引擎研究正好适应了这一需要 值得在数据备份系统中学习和 借鉴 搜索引擎的功能是针对用户提出的查询关键词 快速准确地提示用户所需 信息的位置 结合搜索引擎技术 本文对数据备份系统的归档管理提出一种改进 思路 即 在备份文件时对文件按内容建立全文索引 并把建立的全文索引数据 库追加到归档集中 当用户对归档集有内容查询的需求时 只需定位该归档集的 全文索引数据库 输入关键字进行搜索即可 通过提供这种帮助 用户可以很方 便地查找到所需的归档文件 数据备份系统对文件的备份处理是一次扫描的 为了达到高效的性能 我 们希望在备份的这一次数据扫描过程中 能够同时建立全文索引数据库 即备份 和建索引的过程是同步进行的 然而 存在的问题是 备份处理的数据是以数据 流的形式输入的 换句话也就是说 备份时对文件数据是流式处理的 数据流具 有数据量大 数据到达的顺序独立 数据一经处理 除非特意保存 否则不能被 再次取出处理等特点 基于这些特点 若想使索引建立的过程同步于备份的数据 处理 则要求数据备份系统建立全文索引时对文件数据也是流式处理的 1 2 本文的主要工作及意义 目前 存在很多高效的开源搜索引擎 能够支持快速的本地文件搜索 但 它们建索引的过程是以文件为单位的 只能每次处理一个完整的文件 而不支持 对文件数据流分多段处理 因此 现有的开源桌面搜索引擎都不能直接作为一个 子模块 应用于数据备份系统中 本文根据备份系统面临的实际问题和用户的具体需求 对文件数据流分段 3 中山人学硕i 学位论文备份系统中流式全文索引嵌入模型的研究与设计 解析和全文索引进行研究和分析 提出备份系统中的流式全文索引嵌入模型 在 该理论模型的指导下 设计出一个基于开源搜索引擎框架c l u c e n e l u c e n e 的 c 版 的应用原型 并定义好了原型与外部的标准接口 嵌入到数据备份系统 中 实现了备份与索引过程同步 有效地把全文搜索同备份还原系统结合起来 具体内容包括 1 提出现有数据备份系统在归档管理上存在的不足 并对备份系统中数 据流的性质进行分析 探索出将全文搜索与数据备份系统相结合的思路 2 建立了一个流式全文索引嵌入模型 该模型的外部接口遵循数据备份 系统中文件数据流分段处理的插件原则 3 研究各种数据类型文件的存储格式 分析从其文件的数据流中分段解 析文本数据的可能性 并设计一个抽象的流式解析类 对于满足流式解析条件的 各种类型文件 只要继承该抽象类实现相应的解析器即可 4 实现了h t m l m l p d f d o c 等文件类型的流式解析器 能够分 段提取对应文件数据流中的文本内容 并在其外封装了一个文件类型识别器 在 处理文件数据流时能够自动识别数据流的不同类别而调用不同的解析器 5 研究丌源搜索引擎框架l u c e n e 的内部结构 为c l u c e n e l u c e n e 的 c 版本 定制中文分析器 采用对中文进行同时按字词建索引的综合方法 提 高其对中文的支持度 增加查询结果的准确率 本文实现的应用原型能够作为一个插件无缝地嵌入到数据备份系统中 对 数据透明处理并建立全文索引数据库 通过对索引数据库进行指定关键字搜索定 位 可以返回归档集中的查询结果 本文有效地解决了数据备份系统中归档资源查找效率低下的问题 同时 提出的流式全文索引嵌入模型也为有相似需求的领域提供了设计级复用的基础 1 3 本文的组织结构 全文共分六章 第一章对数据备份相关内容进行概述 并阐述本文写作背 景和写作内容 第二章首先分类介绍了搜索引擎 说明搜索引擎实现的基本原理 然后介绍了与搜索引擎相关的中文分词和信息提取等关键技术 第三章对数据备 份系统中数据流的特性进行研究和分析 采用半形式化的语言对数据流进行描 4 中山大学顾十学位论文 备份系统中流式全文索引嵌入模型的研究与设计 述 在此基础上建立了一个流式全文索引嵌入模型 并给出了模型的基本定义与 性质 第四章是模型的设计与实现 先设计了一个抽象的文件数据流解析类 然 后分析各种类型文件的存储结构以及对其文件流进行分段提取文本数据的可能 性 并对于满足条件的各种类型文件 继承该抽象类实现相应的流式解析器 接 着对l u c e n e 全文搜索引擎框架进行了剖析 为c l u c e n e l u c e n e 的c 版本 添加了中文分词 第五章简要叙述了原型作为一个模块在备份系统中的应用 介 绍了系统的功能和特点 并对系统的结构和搜索工作流程进行了说明 第六章是 总结与展望 在总结现有研究工作的基础上 指出不足 展望更进一步的研究 中山大学硕十学位论文备份系统中流式全文索引嵌入模型的研究与设计 第2 章全文搜索引擎理论及关键技术 2 1搜索引擎简介 人们习惯上认为搜索引擎是网站或网页信息查询的工具 其实这只是一种狭 隘的认识 广义地说 搜索引擎是指能够响应用户提交的搜索请求 并返回相应 查询结果的信息技术和系统 这里所说的信息可以是任意的信息 即包括网站信 息 也包括本地资源中的信息 如文件系统中的文件等 下面就按搜索作用域 的不同 来分别介绍w e b 搜索引擎和桌面搜索引擎 2 1 1w e b 搜索引擎 谈及 w 曲搜索引擎 大家一定不陌生 近年来 涌现出的 g o o 百e 百 度 等搜索引擎已经潜移默化地改变了人们的生活 成为人们在生活和工作中遇 到问题时最常用的求助方式 w 曲搜索引擎 是伴随着w w w 网络出现的搜索 网上信息资源的新工具 它通过c r a w l e r s p i d e r w b n n r o b o t 等计算机软件 程序自动遍历w e b 空间 对一定i p 地址范围内的互联网站进行检索 一旦发现 新的网站 它会自动提取网站的信息和网址加入自己的数据库 为保证采集的资 料是最新的 它还会回访已抓取过的网页 w 曲搜索引擎具有检索面广 信息量 大 信息更新速度快 特定主题的检索专指性强等特点 按照工作方式的不同 可以把w 曲搜索引擎分为如下三种基本类别 全文 搜索引擎 目录搜索引擎和元搜索引擎 7 我们平常说的搜索引擎一般都是指的全文搜索引擎 全文搜索引擎是名副 其实的搜索引擎 国外具代表性的有g o o g l e i n k t o m i t e o m a w i s e n u t 等 国 内著名的有百度 b a i d u 网易有道等 它们都是在w 曲上提取各个网站的信 息 主要是文字信息 然后建立自己的网页数据库 搜索时按照用户给定的查询 条件在网页数据库中匹配相关的记录 然后把记录按照权值由高到低进行排序后 呈现给用户 因此他们是真正的搜索引擎 6 中山大学硕 上学位论文备份系统中流式全文索引嵌入模型的研究 j 设计 目录搜索引擎只是由人工把收集到的网站信息的链接按照目录分类 然后 罗列出来 严格意义上来说算不上是真正的搜索引擎 这有点类似于字典 用户 仅靠分类目录就可找到需要的信息 由于w e b 信息的海量性和人工处理能力 经济代价的限制 目录搜索引擎信息的即时性和全面性难以保证 这类搜索引擎 中最有代表性的是雅虎 国内的新浪 搜狐搜索也都属于这一类 元搜索引擎一般不用自己收集信息 也没有独立的索引数据库 它们的搜 索结果是通过调用 控制和优化其它多个独立搜索引擎得到的 然后再以统一的 格式在同一界面集中显示 国外著名的元搜索引擎有h l f o s p a c e d o g p i l e 等 中 文元搜索引擎中具代表性的有搜星搜索引擎 2 1 2 桌面搜索引擎 如今 计算机已经应用到了社会生活的很多方面 如文档编辑 视频音频 编辑 软件设计 网页编辑等 这样 在本地磁盘上就遗留了大量的文本文档 音视频文件 源代码文件等 微软 g 0 0 西e 等公司察觉到本地数据这个庞大资 源的潜在市场后 纷纷推出了自己的桌面搜索引擎 桌面搜索引擎也是一种全文 搜索引擎 它的规模虽然没有w 曲搜索所涉及的规模庞大 但是资源种类丰富 涉及的技术面广 与一般基于浏览器地址栏的搜索方式不同 桌面搜索是建立在 本地文件系统上层的搜索系统 不需要通过浏览器来进行搜索 桌面搜索将散落 在各层目录中的文档的有关信息提取出来 建立成索引存放到一个文档数据库 它的任务是帮助用户建立本地计算机资源的一个全局视图 让用户需要什么信息 资源都可以快速地找到 国内的中搜发布了全球第一款搜索桌面软件 网络猪 常用的主流桌面搜索引擎有g o o 酉e a s kj e e v e sd e s k t o p h o t b o td e s k t o p 等 2 2 全文搜索引擎的基本原理 w 曲全文搜索引擎和桌面搜索引擎实现的原理类似 都包括两方面的核心 技术 一个是如何建立和维护全文搜索的索引数据库 另一个是如何提供快速有 效的检索机制 两者实现的区别是 在建立索引数据库时 文档搜集方式和类型 有所不同 w 曲全文搜索引擎的文档搜集即页面抓取工作 由一个或多个分布式 7 中山火学硕j 学位论文备份系统中流式全文索引嵌入模型的研究与设计 的网络爬虫完成 网络爬虫依据一定的网络协议在互联网中抓取 整理网页 并 把网页送入网页数据库 显然 w 曲全文搜索引擎处理的文档即为网页 而桌面 搜索引擎的文档搜集对象为本地资源 本地资源不仅包括网页 还包括多种格式 的文档资源 如o f f i c e 文档 p d f 文档 标记格式文档x i l 等 因为不对 w 曲数据进行处理 所以桌面搜索引擎不需要网络爬虫来搜集文档 但是由于资 源文档种类多样 其文档解析处理要比w 曲全文搜索引擎复杂 下面以桌面搜 索引擎为例子 介绍全文搜索引擎的基本原理 全文搜索引擎的实现原理 可以用图2 1 所示的四个步骤归纳隅 文本数据提取 上 i 建立索引数据库 上 l 在索引数据库中搜索 j r i 对搜索结果进行处理 图2 1 全文搜索引擎的买现步骤图 1 文本数据提取 这个步骤也称为索引预处理 它是指由文件解析器对各种类型的文件进行 解析 提取其中的文本内容 因为除了纯文本文件 其它类型的文件都包含文本 内容外的一些格式控制信息等 有的文件类型甚至对文本内容进行了压缩和加 密 所以 在建立索引数据库之前 必须先把要索引的文本内容从各种文件中提 取出来 2 建立索引数据库 建立索引数据库是整个全文搜索引擎中最关键的部分 包括分析和写索引 两个步骤 分析数据时 先将预处理后得到的文本内容划分成一个个词 然后再 从中去掉一些使用很频繁却没有实际意义的词 分析处理完后 就可以将分析结 果写入到索引文件中 并按一定的数据结构进行存储 目前 有很多种索引的建 立方式 采用哪种方式取决于搜索引擎的规模 不过现在大多数搜索引擎都是采 中山火学硕士学位论文 备份系统中流式伞文索引嵌入模型的研究与设计 用倒排索引的数据结构进行存储 倒排索引在下一节中介绍 3 在索引数据库中搜索 建立好索引数据库后 就可以开始对其进行搜索 用户输入查询条件后 先对查询条件进行解析 得到查询关键词的组合 然后由搜索程序从全文索引数 据库中搜索 找出符合该关键词组合的所有相关文件 4 对搜索结果进行处理和排序 搜索到用户需要的信息后 还需要综合相关信息和关键词出现的次数形成 相关度数值 然后进行排序 相关度越高 排名越靠前 最后将搜索结果的文件 路径和文件内容摘要等内容组织起来返回给用户 这样 就在一定程度上保证了 总是将最相关的文件最先呈现给用户 图2 2 是一个典型的全文搜索引擎系统架构图 虚线以下是搜索引擎的核心 部分 虚线以上是其对外的接口 图2 2 全文搜索引擎系统架构图 9 中山大学硕上学位论文备份系统中流式全文索引嵌入模型的研究与设计 2 3倒排索引 倒排索引是全文搜索引擎中使用最广泛的文件索引方式 所谓 倒排 是 指依据内容关键词来列举包含该关键词的文件 倒排索引是相对于传统的正排索 引而言的 正排索引是以文档的 号为关键词 每个文档具有唯一的仍号 表中记录 项记录文档中的每个词以及每个词的位置信息 查找时扫描表中每个文档的记录 项 直到找出所有包含查询关键词的文档 正排索引结构如图2 3 所示 这种组 织方法简单且易于维护 但是在查询的时候需对所有的文档进行扫描以确保没有 遗漏 这样扫描时间就会很长 查询效率低下 所以通常都采用另一种词表组织 方式 倒排索引 其结构如图2 4 所示 文档1 广 文档2 关键词l 工 关键词l 囱 关键词1 关键词l 文档1 文档1 关键词2 关键词2 图2 3 正排索引结构 文档2 文档2 关键词3r 一 关键词3r 图2 4 倒排索引结构 倒排索引 是一种符合人们思维习惯的数据结构 它描述一个文档集合 d d c s 元素和一个词项集合 陋r m 元素对应关系 9 1 记 d d 田 盔 畋 以 刀脚 乞 乙 1 0 中山大学硕士学位论文备份系统中流式全文索引嵌入模型的研究 与设计 其中 d 0 a 中的项代表所有文档的d 号 髓嬲中的项代表每篇文档内容中 出现过的字词 从理论上说 倒排索引是一种面向单词的索引机制 它以死嬲 中的项t 为词 关键字 进行索引 词对应的记录表项用来记录所有出现这个词 的文档d 以及词在对应文档中出现的位置 这有点类似于一些书后面的索引 列举出了一些单词 你可以通过索引查找这些内容在书中出现的位置 倒排索引的关键字数量不会随着文本内容的增长而线性增长 因为无论多大 数量的文本数据库 总能够规范出一个词 关键字 表 倒排索引的建立和维护 相对正排索引都较为复杂 但是在搜索的时候由于可以一次得到查询关键词所对 应的所有文档 所以效率远远高于正排索引 2 4中文分词 中文分词是中文全文搜索引擎中不可或缺的一部分 分词 顾名思义 就 是将一段文本拆分成多个词 而中文分词 就是将连续的汉字序列按照一定的规 范重新组合成词序列的过程 回顾前面介绍的全文搜索引擎实现原理 建立全文索引数据库时有一个分 析的步骤 分析包括将预处理后得到的文本内容分词 再去掉一些没有实际意义 的词 在分析过程中 中文面临与英文处理不同的问题 英语单词之间用空格分 隔 遇到一个空格就可以认为是一个词的结束和一个新词的开始 所以英文分词 很简单 而在中文文本中 语句是连续书写的 词与词之间不存在空格符 也可 以说 从形式上看 汉语中没有 词 这个单位 因此 要从中文句子中区分出 词 就必须要用到中文分词技术 2 4 1中文分词对中文搜索引擎的影响 之前已经介绍了 目前的搜索引擎 大多是基于一种称为倒排索引的结构 以什么作为索引的关键词 直接影响到整个搜索引擎的查全率 查准率和速度 我们先看看不使用中文分词的情况 如果不使用中文分词 可以采用单字索引方式以及2 元组合索引方式 下 中山大学硕士学位论文 备份系统中流式伞文索 j l 嵌入模型的研究j j 设计 面先来看单字索引方式 例如 大学 先索引 大 字 然后再索引 学 字 同样 对于一篇文 章 先把所有的汉字都单独索引一次 并记录他们的位置 搜索过程中 也是先 找 大 字的所有文档 再找 学 字的所有文档 然后做 交叉与 运算 即 包含这两个字 而且位置连续的文档才会作为符合要求的结果 这种索引方式操 作起来很简单 但是查询起来效率却会很低下 因为在每次查询过程中 进行 交 叉与 操作的计算量会很大 我们再来看2 元组合索引方式 比方说 对于 研究生 这个词 先索引 研究 再索引 究生 同样 对于一篇文章 把所有相邻的2 个汉字都作为 一个关键词索引起来 并记录他们的位置 搜索过程类似于单字索引 先找包含 研究 的所有文档 再找包含 究生 的所有文档 然后做 交叉与 运算 即包含这两个单元 而且位置连续的文档才会作为符合要求的结果 这种方式看 起来比较笨拙 但以两个字作为索引单元 大大减少了查询时 交叉与 的运算 量 相对单字索引方式搜索效率有所提高 以上谈及的两种方式 都可以不进行中文分词就实现搜索引擎的索引和搜 索 但它们的准确度不是很高 词是中文语言中最小的语意单位 以词为单位作 为搜索引擎的索引关键词 可以大大提高搜索引擎结果的准确性 同时也可以减 小搜索过程中的计算量 2 4 2中文分词的研究现状 由于中文分词技术对于搜索引擎意义非常重要 在本文的主要工作中 也 包括为开源搜索引擎框架c l u c e n e 添加中文分词 所以在这里仅粗略介绍一下分 词的研究现状 后面章节将会就与本文相关的分词方法和本文所实现的方法进行 详细阐述 近年来我国已经开发了多种现代书面汉语自动分词软件 切分算法也在不 断增加 l o j 归根结底 众多分词方法都是以最主要的三种分词方法为基础 且目 前国内公开报道过的分词系统采用的分词方法也是以这三种为主要类型 它们分 别是 基于字符串匹配的分词方法 基于理解的分词方法和基于人工智能的分词 方法 l l 中山人学颀一 学位论文 备份系统中流式全文索引嵌入模型的研究与设计 1 基于字符串匹配的分词方法 这种分词方法按照一定的策略把待分词字 串切分成子串 若该子串与词典中的词条相匹配 则表示该子串为词语 常用的 匹配策略有 正向最大匹配法 逆向最大匹配法 最少切分 还可以将上述方法 相互组合或者利用各种其它的语言信息来进一步提高切分的准确率 2 基于理解的分词方法 基于理解的分词方法的分词系统通常由三部分组 成 分词子系统 句法语义子系统 总控部分 在总控部分的协调下 分词子系 统可以获得有关词 旬等的句法及语义信息 从而对分词歧义进行判断 即它模 拟了人对句子的理解过程 3 基于人工智能的分词方法 人工智能是对信息进行智能化处理的一种模 式 基于人工智能的分词法包括专家系统分词法 神经网络分词法和神经网络专 家系统分词法等 按中文分词技术的要求 比较理想的自动分词系统应该综合词法 句法和语 义信息 但目前这种方法还不大可能实现 1 2 因为计算机对词法 语义自动分析 的技术还不成熟 所以基于字符串匹配的分词方法仍旧是目前广泛使用的分词方 法 我们也称这种方法为机械分词法 目前在中文分词的解决方案中 走在国内业界最前沿的是中国科学院计算机 技术研究所研制出的i c t c l a s 该系统的分词正确率高达9 7 6 甚至一些商业 项目都使用它来分词 2 5信息抽取 信息抽取是指把非结构化数据转换成结构化的 无二义的数据的过程 l3 1 这些结构化的数据或者直接被用户使用 或者被储存起来为后来的分析做准备 国内的信息抽取技术起步较晚 但由于借鉴了国外的研究成果和经验总结 目前 也取得了很大的进展 很多研究机构都实现了自己的信息抽取系统 比如中国科 学院的基于g a t e 的中文信息抽取系统 1 4 中国人民大学的基于预定义模式的 包装器 l5 中国科学技术大学的基于x m l 的网页信息抽取等 1 6 用于搜索领域的信息抽取技术 实际上就是全文搜索引擎的一个文档预处 理过程 搜索引擎建立文件索引 处理的对象是有意义的文本数据 如果要索引 的是非文本文件 就需要在索引前先从各类非文本文件中提取出文本信息 如对 中山大学硕士学位论文备份系统中流式全文索引嵌入模型的研究与设计 w o i m 文档 p d f 文件 标记格式文档h t m l x m l 等等进行分析 有针对性 地提取出各类型文档中的文本内容 目前研究从从各类文档中提取内容的丌源项目有很多 表2 1 为索引不同类 型的文件所用的不同的a p i 工具 17 1 表2 1 索引文件类型与a p i 工具列表 文件类型所使用的a p i 工具下载地址 h t m lp a r s e r h t t p h t m l p a r s e r s o u r c e f o r g e n e t h t m l 文件 m u l t i v a l e n t h t t p m u l t i v a l e n t s o u r c e f o r g e n e t j t i d yh t t p j tid y s o u r c e f o r g e n e t j d o mh t t p w w w j d o m o r g m l 文件p i c c o l oh t t p p i c c o l o s o u r c e f o r g e n e t x e r c e s h t t p x m l a p a c h e o r g x e r c e s j p d f b o xh tt p w w w p d f b o x o r g x p d fh t t p w w w f o o l a b s c o m x p d f j p e d a th t t p w w w j p e d a t o r g p d f 文件 p d ft e x ts t r e a mh tt p w w w j p e d a l o r g m u l t i v a l e n t h t t p m u l t i v a l e n t s o u r c e f o r g e n e t e t y m o np jh t t p m 硎 e t y m o n c o m a n ti w o r d h t t p w w w w i n f i e l d d e m o n n l c a t d o c h t t p f t p w a g n e r p p r u v i t u s s o f t w a r e w 0 r d 文件 c a t d o c w v w a r e h tt p w v w a r e s o u r c e f o r g e n e t o p e n o f f ic es d k h tt p w w w o 古e n o f f ic e o r g j a k a r t ap o ih t t p j a k a r t a a p a c h e o r g p o i 以上这些 都是在文件解析中最受欢迎 且简单易用的工具 大都用j a v a 语言编写 它们不能够对一个文件的数据流分段进行文本提取 只能够以完整的 文件数据为处理单位 2 6本章小结 搜索引擎本身是个复杂并且庞大的系统 一个搜索引擎的实现要涉及多种技 术 本章先简单介绍了搜索引擎及其分类 然后剖析了全文搜索引擎的基本实现 原理 并阐述了与中文搜索引擎密切相关的三个重要技术 倒排索引 中文分 1 4 中山人学硕j 学位论文备份系统中流式全文索引嵌入模型的研究与设计 词和信息抽取 本章是全文的背景知识介绍部分 对后文模型的研究与实现工作 做了铺垫 在以后的章节里 如没有特别说明 所指的索引均为中文全文索引 中山人学硕 学位论文备份系统中流式全文索引嵌入模型的研究与设计 第3 章流式全文索引嵌入模型的研究与分析 3 1数据流处理模型 数据流处理模型是一种新的数据处理模型 在这种模型中 数据不再是以 固定的关系形式存在 而是以大量连续的 没有边界的 跟随时间变化的数据流 形式存在的 1 8 目前国外有很多关于数据流的原型系统 例如s t a j l f 0 r d 大学的s t r e a m 项 目研究群 伯克利大学的t e l e 伊叩h c q 系统 1 9 和布朗大学的a u r o r a 原型系统 2 0 s t r e a m 原型系统是一个数据流管理系统 它可以按照用户的查询需求针对数据 流进行实时的连续查询 t e l e 伊印h c q 系统是一个通用的数据流管理系统 在开 放式关系数据库管理系统p o s t 乒e s q l 基础上开发 在a u r o r a 系统中 用支持七种 操作和连接操作的有向弧表示对流数据的查询操作执行语言 如今 很多的应用中都用到了数据流 比如电话通信 网络检测 股市交易 等等 虽然数据流中数据的基本单位还是关系模型中的元组 但是由于数据流数 据量大且流速快 不能把流数据简单的放到传统的数据库管理系统 d b m s 中处 理 并且数据流的查询是连续的 当新数据到达时所有当前活动的查询都被执行 而传统的d b m s 并不是为快速连续的存放单独的数据单元而设计的 并不支持 连续查询 传统的d b m s 的主要目标是通过稳定的查询设计 得到精确答案 显然 数据流系统中的查询和传统的关系数据库的查询有着不同的处理方式 数 据流中查询处理的两个重要性质 近似性和自适应性 是对流数据进行快速查 询和其他处理 如数据分析和数据采集 的关键要素 近似性是指查询结果不是精 确值 只是一个近似值 自适应性是指查询计划不是固定不变的 而是随着数据 流的变化而变化的 2 基于以上特性 数据流的查询处理只能对数据进行一次扫描 且数据流中 的数据一旦流过就不能够再次访问 因此必须使用一种有效的方法来近似描述已 经流过的数据 1 6 中山人学硕上学位论文得份系统中流j l 伞文索引嵌入模型的研究 j 设计 3 2流式全文索引嵌入模型 从上面的描述可知 本文研究的流式全文索引嵌入模型 虽然同样也是对大 量连续的 快速的数据流进行的处理 但是和目前在科技文献上出现的 数据流 有很大不同 3 2 1备份系统中的数据流 本文研究的数据流 是数据备份系统中的数据流 指的是有边界的 亦即 本文中处理的数据流 不管数据量有多大 都是有始有终的 我们对这种特定数 据流进行抽象 可以表述为 备份系统中的数据流是指连续高速产生的 有始有 终的大量数据元素所组成的序列 流式全文索引嵌入模型的输入数据流 被视为无结构的数据流 模型处理 时 数据流按照一定的序列 依次进入内存的处理区域 数据流处理方法 需要 满足以下要求 冽 1 在对数据流的分析过程中 每个数据元素至多只能被检查一次 2 尽管在数据流中新数据元素的产生是大量的 但在分析过程中 对内 存的使用或消耗应该是有限的 3 2 2数据流的性质 记数据流为d 依次