（计算机科学与技术专业论文）面向内容安全的数据索引技术.pdf

国防科学技术大学研究生院硕十学位论文 摘要 网络内容审计是属于信息安全的个有机组成部分，是一种非常重要的安全 机制，已成为计算机网络安全领域中应重点研究的问题。网络内容审计旨在通过 收集网络流量，在后台处理机上进行分析处理，从而识别网络上常见的一些通信 协议，还原其通信内容，根据用户定制的规则对通信内容进行存储、监控和分析。 数据索引是实现网络内容审计的一种重要机制，能为内容审计提供针对通信内容 的监控、分析等功能，实现网络传播信息的可控性和网络传送信息的可知性。 本论文基于内容审计系统分段模型，研究通信内容的数据索引技术，包括索 引结构、索引性能模型以及多存储节点的负载均衡等。论文主要包括下列内容： ( 1 ) 深入分析网络内容审计系统的关键技术，研究以数据库作为通信内容的 存储平台、对通信内容建立索引的可行性。 ( 2 ) 提出一种基于共享前缀的两级索引结构，通过对汉字、英文、数字索引 词进行前缀编码，把具有相同前两字节的索引词映射到一级索引的同一位置；二 级索引使用共享前缀树的结构组织索引词后续字节的索引，既能通过二分查找快 速定位索引文件存储块的位置，又能通过共享前缀的方式减少对相同字的存储， 有效地减少索引文件占用的存储空间。 ( 3 ) 研究共享前缀索引结构的性能模型，详细地分析了该结构并行查找时的 时间性能和空间性能。设计了一个基于z i p f 定律的多存储节点负载均衡算法c c a 。 ( 4 ) 综合考虑查全率、查准率、吞吐量、方便性等因素，设计了基于多线程 的检索接口，既便于高效快速的内容检索，又可以实现内容匹配自动报警功能。 ( 5 ) 实现了一个基于共享前缀索引结构的索引子系统s p i n d e x 。测试结果 表明该索引子系统具有较高的时空性能，可以较好地应用于在线的内容审计系统。 主题词：内容审计，共享前缀，两级索引，性能模型 第i 页 国防科学技术大学研究生院硕叶：学位论文 a b s t r a c t n e t w o r kc o n t e n ta u d i t i n gi sa ni m p o r t a n tp a r to ft h en e t w o r ks e c u r i t y ，a n di th a s b e c o m eam a j o rt o p i ci nn e t w o r ks e c u r i t y n e t w o r kc o n t e n ta u d i t i n gf i r s t l yi d e n t i f i e s m o s tc o m m o np r o t o c o l si nn e t w o r kb yc o l l e c t i n ga n dp r o c e s s i n gn e t w o r kt r a f f i c si n b a c k g r o u n dp r o c e s s e r ，a n dt h e nr e c o v e r st h ec o m m u n i c a t i o nc o n t e n t so f t h e s et r a f f i c s ， a n ds t o r a g e ，d e t e c ta n da n a l y st h ec o m m u n i c a t i o nc o n t e n t sa c c o r d i n gt ot h ec u s t o m i z e d r u g u l a t i o n d a t ai n d e xi sa ni m p o r t a n t t e c n o l o g yo fn e t w o r kc o n t e n ta u d i t i n g i to f f e r s t h ef u n c t i o no fd e t e c t i n ga n da n a l y s i n gt h ec o m m u n i c a t i o nc o n t e n t s ，a n di m p l e m e n t st h e c o n t r o l l a b l ea n dk n o w a b i l i t yo fi n f o r m a t i o nt r a n s m i t t e dv i an e t t h i st h e s i ss t u d i e st h ed a t ai n d e xt e c h n o l o g yi nc o n t e n ts e c u r i t yb a s e do n s e g m e n t i o nm o d e lo fc o n t e n ta u d i t i n gs y s t e m ，w h i c hi n c l u d e si n d e xs t r u c t u r e ，i n d e x p e r f o r m a n c e m o d e la n dw o r k l o a d b a l a n c ef o rm u l t i n o d e s t o r a g e t h e m a i n c o n t r i b u t i o n so ft h et h e s i sa r ea sf o l l o w s ： ( 1 ) d e e p l ya n a l y s et h ek e yt e c h n o l o g yo fc o n t e n ta u d i t i n gs y s t e m r e s e a r c ht h e f e a s i b i l i t yo fu s i n gd a t a b a s e a st h es t o r a g ep l a t f o r ma n dc r e a t i n gi n d e xf o r t h e c o m m u n i c a t i o nc o n t e n t s ( 2 ) a nt w o - l e v e li n d e xc o n s t r u c t i o nb a s e do ns h a r e p r e f i xh a sb e e np r o p o s e d ，i t u s e ss i m p l yp r e f i xc o d i n gm e t h o dt om a pw o r d sb e g i n n i n gw i t ht h es a m et w ob y t e st o t h es a m ep o s i t i o no ft h ef i r s tl e v e li n d e x ，a n du s e ss h a r e p r e f i xt r e e ( s p t r e e ) a st h e s e c o n dl e v e li n d e xt of i n dt h es t o r a g ep o s i t i o no fi n d e xf i l er a p i d l y ，i ta l s or e d u c e st h e s t o r a g es p a c eo fi n d e x f i l e s ( 3 ) s t u d yt h ep e r f o r m a n c em o d e lo fs h a r e - p r e f i xi n d e xc o n s t r u c t u r ea n da n a l y s et h e t i m ep e r f o r m a n c ea n ds p a c ep e r f o r m a n c eu n d e rp a r a l l e ls e a r c hm o d e l d e s i g nt h e c c a ( c r o s sc i r c l ea l g o r i t h m ) f o rm u l t i n o d es t o r a g eb a s e do nz i p fl a w ( 4 ) c o n s i d e r i n gt h er e c a l lr a t i o ，p r e c i s i o nr a t i o ，t h r o u g h p u ta n dc o n v e n i e n c eo f i n d e xc o n s t r u c t i o n ，a n dd e s i g nas e a r c hi n t e r f a c eb a s e d0 nm u l t i t h r e a d ，w h i c hi sa p tt o s e a r c hr a p i d l ya n di n p l e m e n tt h ea u t o a l a r mo fc o n t e n tm a t c h i n g ( 5 ) i m p l e m e n ta ni n d e xs y s t e mc a l l e d s p i n d e xb a s e do ns h a r e p r e f i xi n d e x c o n s t r u c t i o n e x p e r i m e n t a lr e s u l t ss h o wt h a t ，t h i si n d e xs y s t e mh a su p p e rs p a c e - t i m e p e r f o r m a n c e ，c a nc o m m e n d a b l yu s ei no n - l i n ec o n t e n ta u d i n gs y s t e m 。 k e y w o r d s ：c o n t e n ta u d i t i n g 。s h a r e p r e f i x 。t w c e - i e v e li n d e x 。p e r f o r m a n c e m o d e i 第i i 页 国防科学技术大学研究生院硕十学位论文 表目录 表3 1 基于字的索引词表示例一1 4 表3 2 共享前缀树查找算法1 7 表3 3 计算存储节点号算法一2 6 表4 1 结果合并排序算法一3 5 表5 1 记录资源情况表一3 8 表5 2 测试结果表一3 8 表5 3 与g o o g l ed e s k t o p 的检索结果比较4 0 表5 4m s n 通信内容检索测试4 l 表5 5m a i l 指定邮箱自动报警测试4 2 第1 页 国防科学技术人学研究生院硕士学位论文 图 目录 图2 1内容安全审计模型图6 图2 2 位图索引模型示意图8 图2 3p a t 树及p a t 数组模型图一9 图2 4 从正向索引到倒排索引1 1 图3 1h a s h 索引示例图1 5 图3 2 集合a 对应的共享前缀树1 7 图3 3 共享前缀树查找流程图一1 9 图3 4 单支树示例图一1 9 图3 5 改进后的共享前缀树1 9 图3 6 索引词编码映射图一2 0 图3 7 一级索引单元结构图一2 0 图3 8 集合a 形成的二级索引结构图2 l 图3 9 索引总体结构图一2 2 图3 1 0 交叉循环算法( c c a ) 示例2 7 图4 1索引子系统框架图2 9 图4 2 索引更新模块图2 9 图4 3多路归并索引图一3 0 图4 4 索引管理模块设计图一3 0 图4 5 索引子系统检索流程图一3 1 图4 6 并行检索接口图3 l 图4 7 软件定时流程图一3 2 图4 8 索引更新策略图一3 3 图4 9 带缓存的检索结构图一3 6 图5 1索引子系统离线测试环境一3 8 图5 2 索引词数目增长趋势图3 9 图5 3 索引词总数统计图3 9 图5 4 负载均衡度图一4 0 图5 5 审计系统测试环境一4 l 第1 v 页 独创性声明 本人声明所呈交的学位论文是我本人在导师指导下进行的研究工作及取得 的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含 其他人已经发表和撰写过的研究成果，也不包含为获得国防科学技术大学或其它 教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任 何贡献均已在论文中作了明确的说明并表示谢意。 学位论文题目： 亘囱凼空塞全鲍数量室l 挂苤 学位论文作者签名： 嗌f 选 日期： 朋罗年2 月矽日 学位论文版权使用授权书 本人完全了解国防科学技术大学有关保留、使用学位论文的规定。本人授权 国防科学技术大学可以保留并向国家有关部门或机构送交论文的复印件和电子 文档，允许论文被查阅和借阅；可以将学位论文的全部或部分内容编入有关数据 库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文 ( 保密学位论文在解密后适用本授权书) 学位论文题目： 重囱凼窒塞全煎熬量盎曼i 筮苤 学位论文作者签名：喧这日期：砌7 年p 月冲日 作者指导教师签名：垫鱼些 日期：m 鼍年，上月砷蝈 国防科学技术大学研究生院硕士学俯论文 第一章绪论 近些年来，我国的互联网络得到了迅猛发展，各种网络业务不断普及，新的 网络应用不断涌现，互联网在人们工作和生活中扮演着越来越重要的角色。截至 2 0 0 8 年6 月底，中国网民数量达到2 5 3 亿，网民规模跃居世界第一位i lj 。电子邮 件、即时通信、电子商务、远程办公、网络音频、网络游戏等得到了长足发展和 迅速普及。互联网已经渗透到人们工作和生活的方方面面，对提高人们的工作效 率、方便相互交流沟通以及丰富休闲娱乐方式具有越来越重要的作用。 随着各种基于互联网络的应用的迅速发展，安全问题也日益突出，网络安全 已经成为影响国家、社会和国民经济的重要因素。由于电子邮件、即时通信以及 w e b 技术的发展，利用这些技术从事违反企事业单位信息安全的情况越来越普遍， 一些非法分子大量利用电子邮件、q q 等向境外发送涉及企业秘密的信息。某些恶 意攻击者利用园区网存在的安全风险、安全漏洞，破坏学校的教学系统和教学资 源。更令人担心的是：我国大陆地区被植入木马的主机i p 数量越来越多，木马除 窃取个人隐私信息和重要数据外，还越来越多地被用来窃取国家秘密和企业秘密， 给国家和企业带来无法估量的损失。 网络带给人们自由开放的同时，也带来不可忽视的安全风险。为应对互联网 络中日益严重的安全问题，保障互联网络正常有效的运行，促进互联网络在国民 经济和日常生活中发挥更加重要的作用，各种网络安全设备和信息安全技术成为 当前研究的热点。 1 1 研究背景 伴随着基于互联网的各种业务的不断普及和互联网在生产、生活中作用的增 强，信息安全问题日益突出。准确把握互联网流量中各种业务的种类以及严格控 制各种业务的通信内容，一方面有助于防止国家和企事业单位内部信息外泄，更 好地保护国家和企事业单位的利益不受到侵害；另一方面，有利于运营商检测各 种网络业务的安全运行，解决与各种网络应用密切相关的安全问题。 网络内容审计技术是一种应用于网络高速链路并联安全分析的技术，主要通 过收集网络流量，对网络流量进行分类重组，从而识别网络上一些常见的通信协 议，并根据应用协议还原其通信内容，如常见的h t r p 、q q 、m s n 、w e b m a i l 、 p o p 3 、s m t p 等协议。目的在于监控和分析通信内容，并提供给管理员自动报警 利检索功能。 网络通信技术的大步发展，使得为桌面工作台提供的网络带宽越来越高，各 第1 页 国防科学技术大学研究生院硕十学位论文 种网络业务应用越米越普遍。网络安全审计技术需要解决在高带宽的网络环境下 网络协议数据的还原，通信内容的监控和分析等问题。数据索引技术是一种高效 分析文本内容的技术，针对还原的通信内容可以采用数据索引的方式来达到对通 信内容进行监控和分析的目的。但网络内容审计的索引和检索与通用搜索引擎有 很大的区别。首先，网络内容审计的索引数据来源于各种应用协议还原后的通信 内容，通用搜索引擎是通过“蜘蛛”程序周期性的从网站中获得网页内容，前者 在索引时必须快速处理高速的数据流，后者则可以周期性地处理更新的网页；其 次，网络内容审计的索引数据一般具有较短的有效周期，而通用搜索引擎的索引 数据的有效期依赖于原始网页数据的存在；最后，内容审计系统的检索面向特定 人员，一般是安全管理员。 由于以上这些特点，如何在面向大量的还原数据时为内容审计系统设计新的 索引和检索机制，是能否全面把握网络内容安全的一大挑战。 1 2 课题意义 内容安全审计系统通过对网络信息的内容进行实时的处理和分析，记录各种 通信信息，这些信息可以让系统管理人员和有关人员事后进行审计和分析，以便 及时发现系统存在的问题并采取相应的安全管理措施，同时还能对系统本身可能 存在的安全漏洞或缺陷进行预测。应用于人规模企业网络环境的网络内容审计系 统可以保护企业内部数据安全，应用于校园园区口的网络内容审计系统可以发现 校园网的潜在漏洞、提高网络系统整体安全。 数据索引技术提供了一种能在文本记录中检索特定索引词的方法，其应用在 内容审计系统中，为企业网管理员对通信内容的监控和分析提供技术支撑，是网 络内容审计的关键技术。 研究内窖审计技术的意义主要有下面三个方面： ( 1 ) 对网络链路中通信内容的实时监测和过滤。保证网络用户在网络上发送 的信息、传送的文件中不涉及企业秘密，保障企事业单位的信息安全。 ( 2 ) 对网络链路通信内容中出现的特殊信息进行即时报警。在己知某些网络 蠕虫的扫描策略和传播模型的基础上，通过对特定通信内容的监测发现非法信息 的传播，并能够快速锁定通信双方当前的网络地址，提供给企业管理员告警提示。 ( 3 ) 建立对网络链路通信内容的事后查询和采证机制。管理员可对存储的海 量信息进行检索和采证，在需要时可还原会话场面。 研究数据索引技术的意义主要在于数据索引技术能为内容安全审计提供事后 查询和采证机制；在进行特定信息的即时报警时，数据索引技术是实现即时报警 的必要技术手段；同时，数据索引技术为安全管理员管理大量的协议通信数据提 第2 页 国防科学技术人学研究生院硕十学位论文 供丫便捷的服务。 内容审计技术和数据索引技术在网络管理和网络安全领域具有上述重要作 用，但网络带宽的日益增长对这些技术提出了更高的要求。为有效管理和控制互 联网通信，需要对这些技术做迸一步的研究。 1 3 主要工作 本文对当前流行的网络内容审计系统模型进行了研究，分析了分段索引模型 和流水索引模型的优缺点，针对应用于网络内容审计系统的数据索引技术，重点 研究了索引结构、索引更新机制和检索机制。 本文所做的主要工作集中在下面几个方面： ( 1 ) 确定采用在线方式的倒排索引机制。数据索引最核心的技术是索引结构 的设计和实现。本文分析和比较了多种数据索引模型，确定了在倒排索引的基础 上，采取更具实时性、更高效的多级索引的技术路线。 ( 2 ) 提出了针对汉字、英文和数字索引词的统一前缀编码映射方案。采用统 一的前缀编码映射方案，每个索引词均能快速地映射到索引词表中，统一的编码 方案简化了索引词表的组织形式。 ( 3 ) 提出一种基于共享前缀的两级索引结构。利用前缀编码方案把具有相同 前缀的索引词映射到一级索引表的同一表项中；二级索引使用共享前缀树的结构 组织索引词后续字节的索引，既能通过二分查找快速定位索引文件存储块的位置， 又能通过共享前缀的方式减少对相同字的存储，有效地减少索引文件占用的存储 空间。试验结果表明，该索引结构下索引文件大小与源文档大小的压缩比达到0 5 9 ， 与顺序索引和h a s h 索引相比，具有较高的时卒效率。 ( 4 ) 设计了基于共享前缀的高性能索引子系统s p i n d e x 。研究了该倒排索 引结构的性能模型，详细分析了该结构并行检索时的时空性能。针对该索引结构 的多节点存储，实现了一个基于z i p f 定律的负载均衡算法c c a 。 ( 5 ) 设计了一个基于多线程的并行检索接口。详细介绍了检索结果的合并和 排序算法、索引缓存机制等。 1 4 本文结构 本文分成六章，各章内容如下所述： 第一章介绍了本课题的研究背景，论述了内容审计技术和数据索引技术在当 前网络安全领域的意义，并说明了本文进行的主要工作。 第二章介绍了内容审计技术和数据索引技术的研究现状，并对当前具有广泛 第3 页 国防科学技术大学研究生院硕十学位论文 应州的倒排索引技术的研究现状做了详细分析。 第三章针对倒排索引的索引词表的组织问题，提出了共享前缀的思想；基于 汉字、英文和数字索引词的前缀编码方案，设计了一种基于共享前缀的两级索引 结构；研究了该索引结构多存储节点负载均衡算法c c a 。 第四章设计了一个基于共享前缀的高性能索引子系统s p i n d e x 和基于多线 程的并行检索接口，详细分析了s p i n d e x 系统各子模块的实现方案，介绍了实现 s p i n d e x 系统的关键技术。 第五章分别对高性能索引子系统和内容审计系统进行了测试，包括测试 s p 附d e x 系统的时空性能和检索效果等。 第入章对本课题的工作进行了总结和展望。 第4 页 国防科学技术大学研究生院硕十学付论文 第二章相关研究 内容审计技术是网络安全领域的一项重要技术，是网络安全监控、网络侦察 和网络举证等工作的关键环节。由于网络带宽的日益增长和各种网络应用的日益 普遍，需要研究更好的内容审计技术来满足高带宽的链路监控需求。本章介绍了 网络内容审计技术的发展状况，讨论了数据索引技术的研究现状。 一个网络要保护起来分3 个阶段：事前、事中和事后1 2 】。事前就是发现网络已 经潜在的安全问题或者是潜在的弱点、隐患并弥补，常用的工具是网络扫描系统； 事中是对正在运行的系统进行防护，防止黑客攻击，目前普遍使用的是防火墙和 入侵检测技术；而事后的查询、取证和分析，就必须用到内容审计系统。网络内 容审计系统能够帮助我们对网络通信内容进行监控和分析，可通过寻找入侵和违 规行为，记录网络上发生的一切，为用户提供取证手段。 本章第一节对网络内容审计技术的系统模型做了较深入的探讨。第二节比较 了几种常用的数据索引模型，重点介绍了索引创建技术、更新技术和缓存技术的 研究现状。 2 1 内容审计技术研究现状 内容审计记录用户使用计算机网络资源访问的所有资源和所有访问过程。完 整地记录审计追踪数据是事后调查取证的基础。通过对一些重要的事件进行记录， 从而在系统发现错误或受到攻击时能定位错误和找到攻击成功的原因。审计记录 应具有防止攻击删除和修改的措施。在c c 准则【3 】中，对信息系统安全审计的功能 有一个完整的定义：信息系统安全审计主要指对与安全有关的活动的相关信息进 行识别、记录、存储和分析；审计记录的结果用于检查网络上发生了哪些与安全 有关的活动，谁( 哪个用户) 对这个活动负责。主要功能包括：安全审计自动响 应、安全审计数据生成、安全审计分析、安全审计浏览、安全审计事件选择、安 全审计事件存储等。 根据内容审计系统的功能需求，研究人员对内容审计技术进行了广泛研究。 2 1 1 内容审计系统模型 内容审计的处理过程包括数据采集、报文重组、应用协议还原、通信内容索 引和数据检索等。通信内容的存储方法包括存储为文件和存储为数据库记录，存 储为文件有利于应用会话的现场再现，存储为数据库记录有利于对通信内容的处 理。根据内容审计的处理流程，内容审计系统可以划分为两种模型：流水模型和 第5 页 国防科学技术人学研究生院硕士学位论文 分段模型。如果要保证通信内容索引的及时性，采朋i 司一处理机执行应用协议还 原和通信内容索引，则称为流水模型。如果将通信内容的索引过程延迟到通信内 容存储后再进行，并且以多处理机的方式进行处理，则称为分段模型，分段模型 具有低耦合性，也容易调节协议识别、通信内容索引以及检索的性能平衡。 流水模型的一个缺点是通信内容索引阶段容易成为瓶颈，从而导致前面协议 还原阶段阻塞，这将严重影响系统的处理能力。一般在高速网路链路上，如2 5 g p o s 、1 0 gp o s 等，通常需要采用硬件进行分流和协议识别才能达到对通信内容的 实时j f 控的目的，采用硬件的分流机制和多协议还原处理卡能保证高速链路上协 议处理的实时性和高吞吐率。 在园区出口和非高速的链路上可以采用软件平台，基于分段模型进行内容安 全审计。采用专用的处理机完成协议还原和通信内容存储，而另外的处理机完成 数据索引工作并提供检索服务。 基于分段模型的网络内容审计系统如图2 1 所示。 芝二二：j 图2 1 内容安全审计模型图 文献1 4 j 针对使用流水模型的内容审计系统，首先分析了真实网络t r a c e 中网络 流量特性，提出了针对较大流的分流算法h a m f ，试验表明该算法分流均衡性好， 流破坏率低，丢包率低，符合安全处理需求。 文献1 5 j 通过网络处理器和改进的捕获驱动进行高效数据报文捕获，通过设置虚 拟磁盘、优化文件系统进行海量数据存储，并着眼于内容审计，采用多线程、简 化协议等方法进行协议分析，解决了在千兆级网络巾存在的一系列性能问题。 n e t i1 0 互联网信息安全审计管理系统，通过旁路侦听的方式对进出网吧网络 数据进行实时采集、分析、记录，可以过滤各类不良信息，支持多种条件审计， 为我国公共场所上网安全，打击各类网上犯罪活动提供良好的帮助。 第6 页 国防科学技术大学研究生院硕十学位论文 2 2 数据索引技术相关研究 本节详细讨论数据索引技术的相关研究，承接2 1 节的内容，本节主要关注的 是在协议还原和识别后通信内容的分析问题。对通信内容建立索引，与传统的基 于字符串匹配的方法分析通信内容相比，更容易实现监控和分析的目的，也更适 合于特定信息的报警、信息查询等工作。本节介绍了通用的数据索引模型，详细 分析了索引创建技术、索引更新技术和缓存技术。 2 2 1 数据索引模型 数据索引的思想最初起源于图书的目录查询服务，数据索引模型丰要解决为 关键词与出现该关键词的文档之间建立映射关系的问题。目前，常用的数据索引 模型丰要有：倒排文件模型 6 1 ( i n v e r t e df i l e ) 、签名文件模型f 7 】( s i g n a t u r ef i l e ) 、 位图模型( b i t m a p ) t s l 、p a t 树和p a t 数组模型1 9 1 。对于给定的文档，前三种索引模 型都要求从文档中划分出索引词( 具有独立语义的关键词) ，即将文档看做索引 词集合；而p a t 树和p a t 数组将文档看成一组半无限串的叠加。 国内对全文索引的研究也很深入，尤其是针对中文文档索引的研究。e 2 相 邻矩阵模型【lo j 和互关联后继树模型( i s t r e e ) 1 1 1 都是针对中文索引提出的全文检 索模型。这两种模型都能够利用索引生成原文，因而可以完全抛弃原文，节约存 储空间。下面将一一讲述主流的数据索引模型。 2 2 1 1 倒排文件模型( i n v e r t e df i l e ) 倒排文件模型【6 1 要求在对文档进行索引词划分的基础上，对索引词集合和文档 进行倒排，即从文档对索引词集的正向索引形成索引词对文档集的倒排索引。 在倒排文件索引模型中，索引数据包括两部分：索引词表和索引信息，索引 词表包含索引词和指向该索引词的文档出现信息的指针；索引信息是指索引词在 文档中的出现信息，一般包括文档编号、索引词在该文档中的出现次数以及出现 的位置序列。对于带有格式特征的文档，如w o r d 文档、h t m l 文档等，索引文 件信息通常还包括是否在标题中出现、索引词在文档中是否加粗等。 当前普遍采用基于倒排文件的数据索引技术，著名的搜索引擎g o o g l e 的创始 人在1 9 9 8 年提出g o o g l e 原型系统【l2 】时，就介绍了g o o g l e 采用了倒排索引的技术。 当前广泛使用的开源搜索架构l u c e n e 也是采用倒排文件索引模型。l u c e n e 1 3 1 是一 个基于j a v a 语言的全文检索工具包，其使j j 倒排文件的索引结构，在进行文档索 引时，首先把文档划分成多个索引词，形成文档对索引词的正排索引集合，然后 建立倒排索引。 倒排文件索引的个主要难点是索引词表的组织，目前常见的词表组织方法 第7 页 国防科学技术大学研究生院硕十学位论文 包括顺序组织和h a s h 组织。顺序组织是最简单的索引浏组织方法，这种力。法一 般采用数组，将文档中出现的索引词一一添加到索引词表中，但在这种索引表中 查找索引词是低效和耗时的。h a s h 组织针对顺序组织的词表进行了优化，通过 使用h a s h 函数，将索引词映射到索引词表的某个位置，对于具有相同h a s h 值的 索引词，其索引信息将链接在索引词表的同一表项中，这种方法的缺点是难以找 到合适的h a s h 函数，使得索引词的h a s h 值较均匀地分布。传统的基于h a s h 算法 组织的索引词表存在大量碰撞的索引词。 倒排文件的优点有：实现相对简单，很容易支持同义词查询；倒排文件的缺 点有：存储开销较大，动态索引时开销大。 2 212 签名文件模型( s i g n a t u r ef i l e ) 签名文件p j 有时也称散列函数法，在本方法中，每个文档都通过h a s h 函数及 重叠编码( s u p e r i m p o s e dc o d i n g ) 产生一个称为签名( s i g n a t u r e ) 的位串。具体做 法是：为每个文档建立一个关联签名( 例如：w 位的向量) ，文档中的索引词做 为散列函数的参数产生几个散列值，与这些值相应的签名的位被置为1 ，当把文档 中每个索引词的散列值叠加时，就得到了合并后的文档签名的全集。文档的签名 结果顺序存入一个单独的文件( 签名文件) 中，签名文件比原文件小得多，因此 可以提供更快速的检索。当要检索一个索引词是否在给定文档中出现时，要将该 索引词作为散列函数的参数计算出相应的散列值，如果某些文档的描述符中所有 的对应位均被置位，则此索引词可能出现在该文档中。由于散列函数很容易产生 冲突，因此，要确认查询项是否真正出现，必须扫描文本。 存在误匹配是签名文件的一个主要缺点，可以通过加大文档签名宽度w 来降 低误匹配率，当然这是以增加索引空间为代价的，并且在查询过程中，误匹配检 查是必不可少的，这在一定程度上增加了查询的开销。 2 2 1 3 位图模型( b i t m a p ) 位图 8 1 是一种非常简单的索引结构，每个索引项都表示为一个位矢量 ( b i t v e c t o r ) ，每位记录一个文档的索引信息，如果索引词出现在某个文档中，该 位置l ，否则置0 。位图使用起来非常简单而且查询速度很快，尤其适合布尔检索。 档号 索引谪 l2345 6 78 中国 1 o001 0 l0 人民 0ll0l 00 1 图2 2 位图索引模型示意图 但是，位图窒间墅堡赞别人，甚罕足原文档的几十倍。尽管已经发现了一些 第8 页 国防科学技术大学研究生院硕十学位论文 高效的位图压缩方法，但雎缩后的空问开销仍然远大于倒排索引和签名文件，所 以位图是三种索引模犁中应用最少的一种。 上述三种索引模型从实质上讲，是同一基本观念的变体。倒排表表行可视为 存储单行位图的一个特殊稀疏矩阵，签名文件可被认为是对位图的每一行进行压 缩存储，每行表示多个索引词；反之，位图等同于这样的倒排表，其中的索引项 的位置是通过在连续单词之间间隔地用一元编码来表示的。位图也相当于签名文 件的简化形式，其中应用了单个散列函数并且签名宽度足够宽，以至于不会出现 歧义。 2 214p a t 树和p a t 数组 p a t 树是一种特殊的p a t r i c i a 树，它是由g o n n e t 和m a n b e r1 9 】提出。它将每 一个文档看成一组半无限串的叠加，并且将这种半无限串的排序结果被表示成树 的形式。p a t 树的最大优点是使用了树型结构加快检索速度和能还原出原文档。它 的最大缺点是空间开销大，而且创建过程中需要较大的空间开销，创建效率也很 低，而且，无论是p a t 树的创建过程还是检索过程，都严重依赖源文档，而倒排索 引在检索过程中是不需要访问源文档。p a t 数组模型是改进的p a t 树模型，它将p a t 树的叶结点串行化表达，就得到了p a t 数组【9 】。p a t 树和p a t 数组在创建和合并的过 程中均需要大量移动数据，因此两者的动态性能都不理想。图2 3 描述了一个p a t 树模型和p a t 数组模型。 pat树pat数组 a b c ，彳c a b c y c a b a b c a b c b a b c b c c 图2 3p a t 树及p a t 数组模型图 p a t 树不需要对源文档进行划分，而是把文档中的每个字符到文档尾字符都形 成一个字符串，如文档“a b a b c 包含五个字符，可以表达为五个字符串：a b a b c ， b a b c ，a b c ，b c 和c ( 一般称这种字符串为文档的半无限串) 。用每个半无限 串首字符的位置标记该半无限串，对这些半无限串按词典序排列，排列结果： a b a b c ，a b c ，b a b c ，b c 和c ，然后对这五个半无限串，以划分出前缀的形式 构造节点，形成树型结构，即得到该文档的p a t 树。而对于这五个排序后的半无限 串，按顺序使用其标号形成数组，则成为p a t 数组。 第9 页 国防科学技术大学研究生院硕士学彼论文 对于p a t 树的查找，是从p a t 树的根节点开始，按照节点代表的串以前缀匹配 的形式在树中进行查找。如在图2 3 的p a t 树中查询串“a b c ，首先沿根结点按 串的前缀( a b ) 找到第一个孩子节点( 节点a b ) ，而后再从该节点开始，用串 剩余部分的前缀( c ) 找到第二个节点( c ) ，串剩余长度为o ，串匹配节点。 p a t 数组是由p a t 树的叶结点串行化得到的，反映了文档中所有半无限串的词典排 序结果，查询可以直接在数组中进行。 2 2 2 索引创建技术的研究现状 中文文档索引创建的基本原理大致与英文文档索引相似，但由于中文汉字组 词及书写的特殊性，中文索引系统的实现较之英文索引检索系统更为复杂。 索引的核心技术是将待索引文档中所有的索引词的出现信息记录到索引文件 中。在英文检索系统中，由于英文文档中英文单词的出现有空格作为分隔符，英 文单词就可以作为一个索引词且提取这些索引词的过程也容易实现，但在中文系 统中，索引词可以是单个汉字字符，也可以是一个汉字词组，甚至是习语。因此， 就会形成两种基本的索引结构，即基于宁的索引和基于词的索引。 无论是中文检索系统还是英文检索系统，索引的创建流程一般包括两个阶段， 第一个阶段是索引词的提取，第二个阶段是把从源文档到索引词集的正向索引转 变为从索引词到源文档集的反向索引，也即倒排索引。 第一阶段：提取索引词 要建立索引，首先需要对源文档进行自动分词，提取组成源文档的索引词， 这些索引词包括汉字单字或词组、英文单词、连续数字等，然后对分词结果进行 筛选，去除停止词( 一般将文档中的介词，代词等虚词称为停止词。如中文中的 “的”、“地”、“得”、“我们”等，英文中的“a m ”、“i s ”、“a r c 、“i t ”、 “t h e r e 等) ，合并相同的索引词。这样就得到了源文档中出现的索引词的词表 以及各索引词的出现位置信息。 对于英文索引系统和基于字的中文索引系统，文档的自动分词都比较简单。 英文文档根据英文单词问的空格逐个提取，而中文文档则可以根据汉字的编码来 提取单个字。如果是基于词的中文检索系统，则还需要对提取出的单个字进行组 词，常用的技术常常包括二分法和词库组词。 二分法把文档中的句子以相邻两字的组合为单位进行分隔，如：“信息安全 工程导论”，分词处理后为“信息息安安全全i i 程程导导论。此方法简单 易行，而且基于该技术的中文检索系统比基于字的中文检索系统效率高。著名的 开源搜索引擎l u c e n e 中就给出了二分法的类，因此，使用l u e e n e 提供的类就可以 实现一些简单的中文检索系统。 第1 0 页 国防科学技术人学研究生院硕十学位论文 侧库组训如果使用专门的词厍匹配进行组词，准确性就可以大人提高。如： “信息安全工程导论”，组词后为“信息安全工程导论”，能够基本准确地匹配 常见词组。中科院计算机所的i c t c l a s l3 。7 j 就是使用词库组词实现的系统，该系统 训练出的词库就能够很好地识别出绝大部分的中文词组。 第二阶段：建立倒排索引 对于第一阶段从文档中提取出的索引词，本阶段就需要建立从索引词到文档 集的倒排索引。借助文献1 1 4 j 的研究，可以用图2 4 来描述本阶段。 1 ) 正向索引2 ) 倒排索引 图2 4 从正向索引到倒排索引 该过程实际上是对每个文档d o c ，求函数f ( d o c i ) = e l e m e n t o ，e l e m e n h ， e l e m e n t j ) 的逆函数( 其中i 为文档编号，i 为索引词编号) ，然后再合并相同 的索引词的过程。为了加快该过程的速度，该过程全部需要在内存中完成。在数 据量比较小时，有足够的内存保证该创建过程可以一次完成，当数据规模较大而 且文档数量以较快速度增长时，必须采用分组索引，甚至是多处理节点并行完成， 然后再合并索引。 文献 b j 对通用索引创建流程进行了更加详细的描述： ( 1 ) 对文档进行自动分词，合并相同索引词的索引信息。 ( 2 ) 按一定规则排序索引词，形成索引词表，也称为索引表。对于新加入的 索引词，就在索引表中添加一项并给该表项分配一个同定大小的基本空间。对于 出现频率较低的索引词来说太大的基本空间将造成浪费，所以需要分配合适大小 的基本空间。 ( 3 ) 如果这个索引词已经存在于索引表中，则只需将索引信息添加到该词的 基本空间即可。 ( 4 ) 写入每个索引词的索引信息到临时文件。如果此时分配给该索引词的空 间用完，则在临时文件末尾给其分配新的溢出空间，出现次数越多的索引词分配 的溢出空间也越大。索引信息写入后，将上一索引区的向前指针更新为新分配空 第1 l 页 国防科学技术大学研究生院硕士学位论文 问在临时文档中的偏移量。 ( 5 ) 对于文档中的每个索引词，重复步骤( 2 ) ( 4 ) ；对于每篇文档重复 步骤( 1 ) ( 5 ) 。 ( 6 ) 所有文档处理完后，对于每个索引词，我们将分散在临时文档中的索引 信息合并在一起。 文献【1 6 】研究基于文档划分的倒排索引创建方法，这种方法适合l 于用来处理内 容动态变化的文档。通过对文档进行划分，当文档中某个子划分块发生变化时， 只需要更新该划分块的索引信息即可，而不是重新对整个文档进行索引。文献【1 7 - 1 9 1 对索引的分布式实现及其负载均衡问题进行了研究，大规模搜索引擎一般需要多 索引节点并行工作才能提供良好的索引服务，而索引的负载均衡是分布式索引实 现的一个主要问题。文献【2 0 - 2 2 1 分别对在线索引和跨媒体数据检索提出了新的索引 策略，这些文献在基于在线索引的基础上，提供了针对图片、文字和音乐的不同 媒体领域的综合检索服务。 2 2 3 索引更新技术的研究现状 在很多应用中，如某些实时新闻网站、w e b 信息挖掘系统等，新文档以很快 的速度增长，而且要求新加入的文档能够即刻提供检索。这时，离线索引的方式 就不能满足要求，采用存线索引的方式，即检索系统在创建索引的同时提供检索 服务。动态环境下倒排索引的构建大大增加了索引和检索的复杂性。如何降低在 线索引的代价以及动态调节索引和检索性能是在线索引的关键问题。 与离线索引技术相比，在线索引构建具有更高的要求，支持增量更新，能够 以较小的代价处理快速增加的文档；在构建索引的同时可以提供检索服务，新文 档即刻可供检索。 迄今为止有4 类索引更新方法【2 列： 第一种方法足索引重建，在添加新文档时对整个文档集和新文档一起重新建 立索引，丢弃旧索引。