（计算机应用技术专业论文）计算机证据搜索与分析技术研究.pdf

摘要 计算机证据搜索与分析技术研究 摘要 计算机取证系统包括证据搜索和证据分析两部分。证据搜索主要是完 成对已有证据的信息定位、搜集。证据分析主要是对证据搜索部分得到的 搜索结果进行全方位的整理、分析、研究从而确定证据倾向性。本论文题 目是计算机证据的搜索和分析研究，本文深入研究了计算机取证系统的证 据搜索和证据分析两方面内容并取得了以下成果： ( 1 ) 分析了计算机取证系统的证据搜索和证据分析两部分的研究现 状、相关算法和实现方法，为计算机取证系统的证据搜索和分析提供了理 论基础。 ( 2 ) 确定了证据分析部分的存储介质关键字搜索系统软件的核心功 能，基于m f c 对话框平台设计了系统软件框架结构，多线程技术实现 了在存储介质中搜索多内码关键字的系统软件，解决了系统软件的关键技 术问题。为计算机取证系统的证据搜索提供了工具支持。 ( 3 ) 引入了意群的概念，训练了证据倾向性词库，从平滑处理、设 定阀值角度改进了朴素贝叶斯算法，提出了基于意群的计算机证据倾向性 分析技术，为计算机取证系统中的证据分析提供了实际可用的方法。 ( 4 ) 实验结果表明：本文设计的存储介质关键字搜索系统和基于意 群的计算机证据倾向性分析方法具备合理的框架结构，有良好的应用效 果，可以满足用户的实际需求。 北京化t 大学硕十学位论文 本文的研究成果对进一步研究计算机证据的搜索和分析、完善取证系 统具有一定的指导意义。 关键词：计算机取证，关键字搜索，证据倾向性，贝叶斯 i i a b s t r a c t r e s e a r c h o ns e a r c ha n da n a l y s i s0 fc o m p u t e r e v i d e n c e a b s t r a c t c o m p u t e rf o r e n s i c ss y s t e mi n c l u d e st w os e c t i o n s ：e v i d e n c es e a r c ha n d e v i d e n c ea n a l y s i s m a i nf u n c t i o no ft h ee v i d e n c es e a r c hi sc o l l e c t i o na n d p o s i t i o ne v i d e n c e m a i nf u n c t i o n o ft h ee v i d e n c e a n a l y s i s i s f i n i s h i n g ， a n a l y z i n ga n dr e s e a r c h i n gt h er e s u l t so fe v i d e n c es e a r c h ，s oa st od e t e r m i n e c o m p u t e re v i d e n c et e n d e n c t h e t i t l eo ft h i st h e s i si s r e s e a r c ho ns e a r c ha n d a n a l y s i so fc o m p u t e re v i d e n c e h e r ed e e p l yr e s e a r c h e d t h ec o n t e n t so f e v i d e n c es e a r c ha n de v i d e n c ea n a l y s i s t h ep r i n c i p a lr e s u l t sa r ea sf o l l o w s ： f i r s t l y , r e s e a r c hs t a t u s ，a l g o r i t h m ，i m p l e m e n t a t i o nm e t h o do fe v i d e n c e s e a r c ha n de v i d e n c ea n a l y s i sa r ea n a l y z e d ，w h i c hc a np r o v i d et h e o r e t i c a lb a s i s f o rc o m p u t e rf o r e n s i c ss y s t e m s e c o n d l y , t h ec o r ef u n c t i o no fk e y w o r d ss e a r c h i n s t o r a g em e d i ai s d e t e r m i n e d s y s t e ms o f t w a r ef r a m e w o r ki sd e s i g n e db a s e do nm f cd i a l o g p l a t f o r m t h ef u n c t i o nt h a ts e a r c h e st h em u l t i i n n e 卜c o d ef o r mo fk e y w o r d si n s t o r a g em e d i ai si m p l e m e n t e db yu t i l i z i n gm u l t i t h r e a dt e c h n o l o g y t h ek e y t e c h n i q u e so fs y s t e ms o f t w a r ea r es o l v e d t h es y s t e ms o f t w a r ep r o v i d e sa b e t t e rt o o ls u p p o r tf o rc o m p u t e rf o r e n s i c s t h i r d l y , h e r e u s e st h ec o n c e p to fs e n s eg r o u pa n dn a i v eb a y e s i a n i i i 北京化t 大学硕 ：学位论文 a l g o r i t h mt os t u d ys e n s eg r o u p b a s e dc o m p u t e re v i d e n c et e n d e n c ya f e a s i b l e m e t h o di sp r o v i d e df o re v i d e n c ea n a l y s i so fc o m p u t e rf o r e n s i c ss y s t e m f i n a l l y , t h er e s u l t ss h o wt h a t ：t h es y s t e ms o f t w a r et h a ts e a r c h e sk e y w o r d s i ns t o r a g em e d i aa n dt h em e t h o do fs e n s eg r o u p b a s e dc o m p u t e re v i d e n c e t e n d e n c yh a v er e a s o n a b l ef r a m es t r u c t u r e ，g o o da p p l i c a t i o ne f f e c ta n dc a n m e e tu s e r sn e e d s t h er e s e a r c hr e s u l t so ft h i st h e s i sf o rf u r t h e rs t u d ys e a r c ha n da n a l y s i so f c o m p u t e re v i d e n c e ，p e r f e c tc o m p u t e r f o r e n s i c s s y s t e m h a v e g u i d i n g s i g n i f i c a n c e k e yw o r d s ：c o m p u t e rf o r e n s i c s ，k e y w o r ds e a r c h ，c o m p u t e re v i d e n c e ， b a y e s i v 北京化工大学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立 进行研究工作所取得的成果。除文中已经注明引用的内容外，本论文不含 任何其他个人或集体已经发表或撰写过的作品成果。对本文的研究做出重 要贡献的个人和集体，均已在文中以明确方式标明。本人完全意识到本声 明的法律结果由本人承担。 作者签名：醴 日期：型翌：丝 关于论文使用授权的说明 学位论文作者完全了解北京化工大学有关保留和使用学位论文的规 定，即：研究生在校攻读学位期间论文工作的知识产权单位属北京化工大 学。学校有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允 许学位论文被查阅和借阅；学校可以公布学位论文的全部或部分内容，可 以允许采用影印、缩印或其它复制手段保存、汇编学位论文。 保密论文注释：本学位论文属于保密范围，在上年解密后适用本授 权书。非保密论文注释：本学位论文不属于保密范围，适用本授权书。 作者签名： 导师签名： 日期：塑丝型 日期：趁z 望：立丝 第一章绪论 1 1 研究目的和意义 第一章绪论 随着全球计算机相关技术的快速发展，计算机的应用也越来越广泛，随之而来的 计算机犯罪也趋于复杂、多样化。非法入侵计算机系统、肆意修改计算机存储内容、 利用计算机进行犯罪活动等现象率见不鲜。计算机安全成为了各个国家和组织密切关 注的问题【l4 1 。计算机证据在计算机屏幕上的表现形式是多样化的，综合了文本、图形、 图像、动画、音频及视频等多种媒体信息【5 】。因此，如何获取计算机犯罪的证据，怎 样在仅有的证据中分析出蛛丝马迹从而调查破获计算机犯罪案件，以及最大限度地减 少受害人的损失等等一系列问题接踵而至【6 】。为了解决这些问题，计算机取证技术应 运而生。由于目前的计算机取证工具都是集中在存储介质的分析上，而其他工作全部 依赖于取证专家进行人工分析【7 1 ，因此取证人员是否能够短时间、全面缜密地对计算 机证据进行分析是计算机取证技术研究的核心。 计算机取证系统分为证据搜索和证据分析两部分。因此本文从证据搜索和证据分 析两个方面对计算机取证系统进行了论述。 1 证据搜索 本文开发了存储介质关键字搜索系统。存储介质关键字搜索系统属于计算机取证 范吲8 。9 】。存储介质关键字搜索系统可以对可疑存储介质进行全方位取证。随着计算机 硬件技术的飞速发展，存储介质的容量也越来越大，因此，怎样通过搜索存储介质内 容快速定位可疑扇区中可疑字词，查找存储介质中有利的证据成为了本文亟待解决的 关键问题。 2 证据分析 本文提出了基于意群的计算机证据倾向性分析方法，以文档为例，对计算机证据 进行了倾向性分析。本方法对计算机取证系统的证据分析部分具有一定的参考价值。 1 2 国内外研究现状 本小节主要对证据搜索部分的研究现状进行了探讨。 1 2 1 搜索工具研究现状 目前，随着计算机硬件技术的飞速发展，大容量存储介质无论是在生活还是在工 作中，它的使用率都逐渐攀升，越来越多的用户使用大容量存储介质来存储更多的数 北京化t 大学硕十学位论文 据。虽然大容量存储介质有存储量大的优点，但是不容易管理、查找速度慢等缺陷也 越来越显著，这些问题不但困扰着普通的用户，同时也对专业取证机构的取证过程造 成了一定的困扰，因此存储介质搜索工具也就随之诞生了，本节主要以硬盘搜索工具 为介绍对象。 目前国内外的硬盘搜索工具种类繁多，以下具体介绍： 1 国内外搜索工具研究现状 ( 1 ) 国内搜索工具 国内搜索工具有百度硬盘搜索和e n a d d 快易搜等搜索工具，下面只对前两种做具 体介绍： 百度硬盘搜索工具 百度硬盘搜索工具是可以检索中英文双语的硬盘搜索软件。百度硬盘搜索工具可 以对硬盘上的文档、图片、邮件等信息进行快速定位，同时，利用硬盘中文件的相关 信息自动生成索引，实现硬盘的管理功能。 百度硬盘搜索工具工作原理是利用了索引的方法。百度硬盘搜索工具首先建立硬 盘上文件的信息索引，一旦收到用户的搜索请求，就会在已有的索引中查找。 百度硬盘搜索工具优点是无论用户在线与否，都可以查找网页浏览历史，同时可 以收缩显示m p 3 、图片的子目录页面，而且在用户没有搜索到相关信息的情况下，对 用户所搜索内容做了优化，为用户提供了有效的建议。缺点是对百度硬盘搜索工具所 在的安装目录有一定的空间要求。 e n a d d 快易搜 e n a d d 是一款硬盘搜索工具，它的功能是查看硬盘上文件资料。e n a d d 支持多关 键字搜索，同时可以对搜索结果分页显示、图片式预览。 e n a d d 工作原理是采用了按分类、按时间、按目录的方式来搜索文件，同时自定 义了索引更新频率，而且不断优化内部数据结构，使搜索相应时间平均处在毫秒级。 e n a d d 优点是搜索速度快，支持千万级的文件搜索，同时支持多关键字的搜索。 缺点是在用户的使用便捷性方面还有待于改进。 ( 2 ) 国外搜索工具 国外搜索工具有很多种，其中包括l o c a t e 、g o o g l ed e s k t o ps e a r c h 、a s kj e e v e s 等 等，下面对国外搜索工具及其优、缺点简要介绍： ( j ) l o c a t e l o c a t e 是一款可以从存储介质中查找目标文件的国外软件。 l o c a t e _ t _ 作原理是使用数据库技术把任意指定的硬盘目录和其他媒体介质上的文 件( 包括文件的名称、大小、修改时间等信息) 的相关信息保存起来，搜索时直接搜 索数据库记录。最后，l o c a t e 能够将记录文件存放位置、大小、同期等搜索结果以文 本文件的方式输出。 2 ， 第一章绪论 l o c a t e 优点就是能够从已有数据库中进行检索，快速定位存储介质中的文件位置， 从而大大提高了查找文件的速度。缺点就是随着存储介质的更新，l o c a t e 要不断同步 更新数据库。 g o o g l ed e s k t o ps e a r c h g o o g l ed e s k t o ps e a r c h 多数情况下是在浏览器中运行的，它可以搜索到微软的 o f f i c e 、音乐、图片等普通类型文件，同时可以搜索到a o l 即时聊天记录， g o o g l e d e s k t o ps e a r c h 工作原理是针对每个文件建立索引，当用户输入文件名后就从索引 内提取相关的路径。 g o o g l ed e s k t o ps e a r c h 优点是软件可以随意放置在桌面上，不会影响用户其他的 工作，同时快速定位待搜索内容。缺点是虽然此工具能够根据一张图片的元数据或是 m p 3 文件找到其相应的位置，但是不能发现相关类似的文件。同时，不能搜索r t f 格式文件、压缩文件、x m l 和其他一些流行文件格式，只有下插件才可以弥补漏洞。 a s kj e e v e s a s kj e e v e s 采用了问答的方式进行检索。 a s kj e e v e s 的工作原理是a s kj e e v e s 利用了一个由数千个问题模版和数百万个答 案组成的知识库，问题模版用于匹配用户提问，用户选择了特定的模版以后就会得到 相应的答案【1 们。 a s kj e e v e s 优点是搜索速度快，采用了问答式搜索方式具有创造性。a s kj e e v e s 缺点是返回结果并不很精确。 c o p e r n i cd e s k t o ps e a r c h c o p e r n i cd e s k t o ps e a r c h ( 简称c d s ) 是由老牌集成搜索公司c o p e m i c 开发的搜索 工具，该软件能够搜索到例如计算机硬盘驱动器上的文件、电子邮件和存储在任何位 置上的电子邮件附件等音乐、图片、视频文件。同时，该软件是目前唯一能够搜索 f i r e f o x 历史纪录和收藏夹的软件。 c o p e m i cd e s k t o ps e a r c h 工作原理是利用了“智能代理”的方法，即带有智能搜索 技术，以分布引导方式简单快捷地建立搜索任务，使用逻辑运算符对下载搜索结果进 行精选，同时，可以多种文件类型导出或通过电子邮件邮寄搜索报告【“】。 c o p e r n i cd e s k t o ps e a r c h 优点是可以不受限制地设置、添加特定的文件类型对搜索 结果进行重新搜索，同时在存储介质上文件有所改动时，该软件也可以实现实时更新， 而且c o p e r n i cd e s k t o ps e a r c h 的检索范围也很广泛，智能性、灵活性都很高。缺点是 不能把搜索结果即时列出、没有j e e v e s 的分类显示功能和g o o g l e 的网页缩略图功能 等缺点。 w i n d o w s 搜索工具 w i n d o w s 搜索工具是微软推出的类似于m s nd e s k t o ps e a r c h 的搜索工具。 w i n d o w s 搜索工具工作原理是当接收到用户的搜索请求时，对硬盘中文件逐个进 3 北京化t 大学硕十学位论文 行查找，用户每发出一次搜索请求就要对硬盘重新扫描一次。 w i n d o w s 搜索工具优点是搜索范围大、搜索功能强大。缺点是由于每次搜索请求 都要对硬盘重新扫描，因此不仅占用资源较大，同时在效率上也受到了严重的影响。 2 现有产品的不足 现有产品存在搜索文件种类不够全面，搜索准确率不是很高和产品所占用的资源 比较大等问题，存在很大的改进空间。 1 2 2 搜索算法研究现状 目前，搜索算法有很多种，回溯法、启发式搜索算法、增量搜索算法等等。下面 就对一些典型的搜索算法研究现状进行具体的介绍。 1 回溯法 回溯算法是所有搜索算法中最为基本的一种算法，同时，也是求解多约束条件问 题的最佳解时采用的首选方法【l 2 1 。 回溯法一般用于解决排课系统、求解四皇后、学生宿舍分配【1 3 】等问题上，在实际 中有着很广泛的应用。 2 启发式搜索算法 启发式搜索算法是状态空问搜索算法中的一种。状态空间搜索算法是将问题求解 过程表现为从初始状态到目标状态寻找这个路径的过程【1 4 1 。状态空间搜索算法分为： 广度优先搜索算法、深度优先搜索算法和启发式搜索算法。由于广度优先搜索算法和 深度优先搜索算法是穷举所有的路径分支，当空间较大时，穷举的工作量十分大，明 显降低了搜索效率，因此这两种算法存在一定的局限性。而状态空间搜索算法中的另 一种启发式搜索由于对状态空间中搜索位置进行了评估，优化了搜索算法，因此被广 泛地应用起来。 从国内外的研究情况来看，到目前为止，现代启发式算法分为以下几种： 图1 2 现代启发式算法 f i g 1 - 2m e t a - h e u r i s t i ca l g o r i t h m s 其中，模拟退火算法s a 主要用于组合优化问题，此算法克服了其他方法容易陷 4 第一章绪论 入局部解的缺点，而且目前s a 主要发展方向是与其他算法结合构成新的混合算法来 避免局部解【1 5 】。蚁群算法a c a 在调度、旅行商、指派问题上都得到了很好的应用【1 6 】。 3 增量搜索算法 增量搜索算法的原理是本次搜索时会利用之前的一些相关搜索信息来提高本次的 搜索效率。通常用来解决动态环境下的重规划问题，在人工智能领域，一些实时系统 经常会根据外界的环境变换来修正自身，这样会产生一系列变化较小的问题，这时利 用增量搜索将非常有效【i 7 j 。 目前，国内外主要的增量搜索算法有u a 木算法【1 8 】，以l p a 木算法为基础发展而来 的d * l i t e 算法【1 9 】和d d * l i t e 算法【2 0 1 。 在不断改进增量搜索算法的同时，一种结合启发式搜索和增量搜索的算法也应运 而生。当多目标问题搜索图的状态改变时，利用基于增量的启发式搜索算法，可以使 用部分之前搜索保留的信息来求解新问题的最优解，一定程度上提高了问题求解的效 率1 2 。因此，增量搜索算法与启发式搜索算法结合式算法的应用也越来越广泛。 1 3 论文主要工作及创新点 1 作者在课题研究中的主要工作如下： ( 1 ) 收集课题研究的相关资料 对证据搜索中的搜索工具和搜索算法在国内外的发展现状、发展趋势进行资料搜 集，做出了综述报告：对证据分析中的研究方法进行了总结。最后综合证据搜索和证 据分析两方面资料制定论文研究计划。 ( 2 ) 研究搜索对象 对证据搜索中的系统搜索对象硬盘进行全方位、详细的了解。 ( 3 ) 研究核心算法 深入研究了中文分词算法、模式匹配算法，提出了存储介质关键字搜索策略，同 时完成了存储介质关键字搜索系统的编码工作。 ( 4 ) 基于意群文本倾向性分析研究 深入研究基于意群文本倾向性分析算法，利用贝叶斯算法进行倾向性分析。同时， 提出了改进措施，完成了基于意群计算机证据倾向性分析研究工作。 ( 5 ) 对系统进行全面的测试，分析实验结果，总结研究经验。针对系统存在的缺陷， 制定进一步的工作计划。 2 论文的主要创新点包括如下几点内容： ( 1 ) 从计算机取证系统的证据搜索和证据分析两方面进行了研究。 ( 2 ) 以扇区为单位对存储介质关键字进行搜索，具体搜索定位在每个扇区上，方便 5 北京化t 大学硕f ：学位论文 了工作人员进行取证。 ( 3 ) 在对存储介质关键字进行搜索时，对已经删除的关键字仍然可以定位，提高了 搜索的全面性。 ( 4 ) 采用配罱文件的方式记录搜索过程，提高了搜索效率。 ( 5 ) 提出意群的概念，同时改进了朴素贝叶斯算法，提高了证据倾向性分析、判断 的准确性。 1 4 论文内容及组织结构 本论文共分为六章，论文写作的组织结构说明如下： 第一章为绪论。本章包括了研究目的和意义、国内外研究现状、论文主要工作及 创新点、论文结构。 第二章为存储介质关键字搜索技术的研究，即计算机取证系统的证据搜索部分。 本章包括了搜索对象、搜索目标分词算法和模式匹配算法的原理及其本文对两种算法 的研究分析情况。本章为后续章节的证据搜索软件设计和实现奠定了理论基础。 第三章为基于意群的计算机证据倾向性分析研究，即计算机取证系统的证据分析 部分。本章包括了意群方法、用于证据倾向性分析的朴素贝叶斯改进算法和算法处理 要素的分析。文章为证据分析提供了实际可用的分析方法。 第四章为系统软件原型，即计算机取证系统的证据搜索部分的软件实现。本章详 细介绍了系统软件的功能、设计框架、系统软件的实现过程、系统软件实现的关键技 术和系统软件的开发环境。 第五章为实验结果与分析，分析了存储介质关键字搜索和基于意群的计算机证据 倾向性研究的实验结果，并得出实验结论。 第六章为结论与展望，总结了论文的主要成果，提出了存在的不足和今后的研究 方向。 6 第二章存储介质关键字搜索技术的研究 第二章存储介质关键字搜索技术的研究 存储介质关键字搜索技术是计算机取证的重要组成部分。计算机取证系统首先搜 索证据，然后在搜索结果上对证据进行整理、分析。因此，计算机取证系统包括了证 据搜索和证据分析两部分，如图2 1 所示。 t f - q 证据搜索 算 机 取 证 系 - q 证据分析 统 图2 - 1 计算机取证系统 f i g 2 1c o m p u t e rf o r e n s i c ss y s t e m 本文在第二章和第三章分别介绍了证据搜索和证据分析的相关技术。 本章对存储介质关键字搜索技术的研究分别从搜索对象( 硬盘) 、搜索目标分词 算法( 关键字分词) 和模式匹配算法三个方面进行研究、分析，只有对这三个方面有 了深刻、透彻的了解，才能够完成存储介质关键字搜索系统的丌发。 下面，本章将对搜索对象、搜索目标分词算法和模式匹配算法三个方面逐一进行 阐述。 2 1 搜索对象研究 2 1 1 搜索对象 存储介质关键字搜索系统的搜索对象是存储介质，而存储介质主要是指硬盘、u 盘、光盘等。本文重点介绍硬盘的相关技术。 随着1 9 7 3 年，i b m 生产的第一个磁盘存储系统( i b m3 0 5r a m a c ) 的诞生，硬 盘技术有了正确的结构基础，即“温彻斯特 技术【2 2 1 ，从此硬盘逐渐发展起来。如今， 硬盘无论是在产品技术还是在容量上都到达了前所未有的巅峰时刻。 因为硬盘是计算机中重要的数据存储部件，保存着使用者所有的数据信息，所以 很容易成为犯罪分子破坏的对象。如何最低限度地减少对硬盘中存储信息的破坏、如 何在硬盘中发现犯罪的蛛丝马迹等等都成为了计算机取证人员面临的挑战。而要解决 这些问题，首先就要对硬盘的物理结构和逻辑结构有详细、深入地了解，这样才能确 保取证人员得到更加全面的数据分析结果。 7 北京化工人学硕一l ：学位论义 2 1 2 搜索对象分析 本节将从硬盘的内部结构、硬盘容量计算公式、硬盘分区表和w i n d o w s 文件系统 四个方面对搜索对象硬盘进行详细研究、分析。 1 硬盘内部结构【2 3 】 硬盘本质决定了硬盘的内部结构是不变的。硬盘的内部结构可以分为四个组成部 分，如图2 2 所示。 图2 - 2 硬盘内部结构 f i g 2 2i n t e r n a ls t r u c t u r eo f h a r dd i s k 2 硬盘容量计算公式 硬盘是由一个个盘面组合而成的。在硬盘中存储数据的基本单位是扇区。在计算 硬盘容量时，必须要了解盘面号、磁头号、磁道、柱面、扇区的代表意义，具体如下 所示： ( 1 ) 盘面号 盘面是硬盘的组成单元。盘片分为上下两面，而每一盘面都使用面号来标记，面 号是根据自上而下的原则从0 开始编号的。 ( 2 ) 磁头号 每个盘面都有用于读写数据的独立的磁头，对磁头进行编号也是遵循自上而下的 原则从0 开始顺序进行，其实盘面号即是磁头号。 ( 3 ) 磁道 磁道代表着盘面上的同心圆，即硬盘每个盘面以转轴为中心被划分成直径不等的 多个同心圆，这些同心圆就被称为磁道。 ( 4 ) 柱面 在垂直方向上，直径相同的磁道构成柱面，柱面数= 磁道数，柱面编号是根据自外 而内的原则从0 开始编号。 ( 5 ) 扇区 扇区是硬盘存储数据的基本单位。扇区是以圆心为中心点，按照逆时针的方向将 8 第二章存储介质关键，搜索技术的研究 每个磁道划分为夹角相等的弧，每个扇区大小为5 1 2 字节。 扇区 f ， 垂霾疆 ji r 黼- i ( 1 瑟口 l j 覆口 图2 - 3 扇区分类 f i g 2 - 3s e c t o rc l a s s i f i c a t i o n 扇区可以分为物理扇区和逻辑扇区，其中，物理扇区是扇区在磁盘上的绝对位置， 而逻辑扇区则是在硬盘上所有扇区按照顺序统一编号以后所得到的、在磁盘上的相对 位置【2 4 1 。 硬盘容量的计算公式如式( 2 1 ) 所示： 容量= 盘面数柱面数扇区数5 1 2 。式( 2 1 ) 3 硬盘分区表 通常情况下，硬盘被分成多个分区，分区的一般形式为【2 5 】： ( 1 ) 主分区 ( 2 ) 扩展分区 ( 3 ) 非d o s 分区：单独划分硬盘中一块区域供其他如l i n u x 等o s ( 操作系统) 使 用，对于w i n d o w so s 来讲，此分区仅仅是一块被划分出去的存储空间，只有非d o s 分区内的o s 才可以管理、使用。 主分区中有一个特殊但十分重要的扇区m b r ( 主引导) 扇区，它处于硬盘的0 磁 道0 柱面l 扇区，主分区表中只能分四个分区，无法满足实际的用户需求，因此设计 了e b r ( e x t e n d e dm b r ) ，扩展分区信息以链表形式存放【2 6 】，如下图所示。 图2 - 4 主分区表、扩展分区和逻辑盘的关系图 f i g 2 - 4r e l a t i o n s h i po f p r i m a r yp a r t i t i o nt a b l e ，e x t e n d e dp a r t i t i o nt a b l ea n dl o g i c a ld i s k 9 北京化工人学硕上学位论文 图2 4 主扩展分区、扩展分区和逻辑盘的结构在数据结构中称为链表结构。链表 结构可以不需要占用成块的存储空间，使得硬盘碎片得到有效地利用，同时添加、删 除都较顺序表方便。 4 w i n d o w s 文件系统 ( 1 ) w i n d o w s 文件系统分类 w i n d o w s 文件系统主要有两种： o f a t a f a t l 2 ( 不支持大于2 g b 分区) b f a t l 6 ( 不支持大于2 g b 分区) c f a t 3 2 ( 支持大小为4 g b 的文件) ( z ) n t f s ( 支持大小为6 4 g b 的文件) ( 2 ) 数据存储结构 文件系统的不同决定了数据存储结构的不同，具体数据存储结构如下： ( d f a t 文件系统硬盘数据组成【2 7 】 a b o o t 引导区 b f a t 文件分配表 c d i r 文件目录区 d d a l 队数据区 其中，系统区包括引导区和文件分配表区。引导区用来保存逻辑盘的一些基本信 息和重要参数，引导区位于第0 个扇区，大小为一个扇区。f a t 文件分配表是一个链 表结构，保存了分区中每簇的使用情况，位于引导区和若干保留扇区之后。d i r 即根 目录区( d i r e c t o r y ) ，d i r 位于第二f a t 表之后( f a t l 2 和f a t l 6 文件系统中) ，大小 为3 2 个扇区。d a t a 数据区用来存放文件内容，利用f a t 和d i r 区的信息，文件系 统可以准确定位文件内容在数据区中的位置。 n t f s 文件系统硬盘数据组成 a 分区引导扇区 b m f t 主文件表区 c s y s t e mf i l e 系统文件区 d f i l e a r e a 文件数据区 其中，n t f s 分区引导扇区用来保存逻辑盘的一些基本信息和重要参数，系统启 动时可以引导操作系统定位磁盘上的文件。m f t 主文件表用来确定文件在磁盘上的位 置，在系统空间分配、读写磁盘时都将访问到m f t 主文件表。s y s t e mf i l e 系统文件区 是用来存储m f t 表中前1 6 条记录的。f i l e a r e a 文件数据区是运行时用来存储文件内 容属性的数据区域。 1 0 第二章存储介质关键字搜索技术的研究 2 2 搜索目标分词算法研究 对于语言来说，英语通过空格或者是符号就可以大致地得到单词之间的界限，即 可以通过判断空格或者符号所在的位置来对语料进行分词，但是对中文而言却比较复 杂，中文词语可以采用不同的方式组合形成不同的语义【2 8 1 。中文分词是搜索技术的前 提条件，同时也是搜索技术的瓶颈，采用怎样的中文分词技术将直接影响关键字搜索 的效率。因此，在对存储介质关键字进行搜索时，分词技术是一个关键性的问题。 2 2 1 算法阐述 自从1 9 8 3 年第一个分词系统c d w s 的出现【2 9 】，分词技术越来越被人们所重视。 经过研究人员近3 0 年的努力工作，分词技术已经取得了一定的进展。 目前，分词算法主要包括几类【3 0 1 ，如图2 5 所示： 图2 5 自然语言分词算法 f i g 2 - 5a l g o r i t h mo fw o r ds e g m e n t a t i o n 图2 5 对目前的研究算法进行了分类总结，下面就几种典型的算法进行简单阐述。 1 最大匹配法( m a x i m u mm a t c h i n gm e t h o d ，m m 法) 该算法是最早出现的分词算法，该算法利用了机械式匹配算法原理，通过建 立词库并按照一定的顺序( 正向或逆向扫描) 对字符串进行扫描分词【3 。 虽然最大匹配算法应用比较广泛，但是由于最大匹配算法在使用时必须要先设定 北京化t 大学顾 ：学位论义 一个匹配词长的初始值，因此限制了算法的灵活性，降低了分词效率，此算法还有待 于改进。 2 基于统计语言模型( t h es t a t i s t i c a ll a n g u a g em o d e l ，s l m ) 的自动分词算法 s l m 方法利用了机器学习手段从语料库中获取分词所需要的某些实用知识，从而 为分词提供了一定的信息补充【3 2 】。由于词是稳定的组合，在上下文中词语和词语之间 相邻出现的概率能够反映出词的可信度，因此，对语料中相邻共现的汉字的组合频率 统计，得出的就是一些实用的信息 3 3 - 3 4 】。 3 标记法 目前，标记法有很多种，也是目前比较主流的分词方法之一。 标记法主要是将分词知识的学习转换成字串的标注过程，由于每个字在构造一个 特定的词语时都占据一个词位，因此把分词过程看成是学习词位信息的机器学习过程 3 5 1 o 在本文中主要就采用了l m r 标记法来对语料进行分词。 2 2 2 算法框架 中文分词是对包含有中、英文、数字的语料输入分词系统，对语料分词并分类输 出，具体流程如下刚3 6 l 所示： i 中、英文、数字语料 上 分词处理系统 j上上 中英 数 文文 字 单单 集 词词 集集 图2 - 6 分词原理图 f i g 2 - 6d i a g r a mo fw o r ds e g m e n tp r i n c i p l e 1 语料输入 输入待分类的语料段落，其中语料段中包括中文、英文、数字等。 2 分词处理 分词系统采用了合适的算法，对输入语料进行分词处理 3 分类输出 最后，经过了分词处理系统后，语料段里的中、英文、数字等按照分类输出到相 应的集合中去，完成了语料分词。 1 2 第二章存储介质关键搜索技术的研究 2 2 3l m r 分词算法 在存储介质关键字搜索系统中主要是采用了l m r 标记法，具体原理阐述如下。 l m r 标记法分为两部分：信息熵标记法和基于转换的训练学习。 1 l m r 标记规则 ( 1 ) l m l m 用来标记一个汉字词汇最左边的字。 ( 2 ) m m m m 用来标记一个汉字词汇中间的字。 ( 3 ) m r m r 用来标记一个汉字词汇最右边的字。 ( 4 ) l r l r 用来标记一个单独的字。 例如，对于“全北京市 利用l m r 标记方法可以得到结果“全l r 北l m 京l m m 市m r ”。 2 l m r 标记算法 本文使用了两次最大信息熵( m a x i m u me n t r o p y ) 标记法，分别对输入的语料从 左向右、从右向左扫描标汜，最后采用变换算法( t r a n s f o r m a t i o nb a s e da l g o r i t h m ) 对 结果进行合并。 ( 1 ) 最大信息熵标记法 本文采用的是最大熵马尔科夫模型( m a x i m u me n t r o p ym a r k o vm o d e l ，m e m m ) 。 最大熵马尔科夫模型是最大熵模型的序列化形式【3 7 瑚】。 模型被定义为h t ，其中，日是上下文观测值或是历史值，丁为可能的标记集合。 条件概率p ( h ，t ) 可以表示成式( 2 - 2 ) 所示 p ( h ，f ) ：掣兀k 口 j = l 其中，万是归一化因子， 厂，厂z ，) 是特征值，f ( h ，t ) o ，1 ) 。每个特征值都 有一个相关参数口，参数口，代表着此特征万的权重。 训练过程中，输入一个字符序列 c - ，c 2 ，a ) 和相应的l m r 标记 t l , f ：，厶) ，训练 的结果将得到参数值伽，口- ，0 1 2 ，口。) ，p 代表训练中数据的最大的可能性，如公式( 2 3 ) 所示： ( p ) ：e ( h 曲) ：n 掣血彩枷) i = 1i = l j = l 采用h e m m 方法最大的成功之处就是依赖于合适的特征值的选择【3 9 1 ，给定( ，0 ， 1 3 北京化工大学硕士学位论文 特征值必须能够分析语段从而得到t 的推测值。 ( 2 ) 改进m e m m 方法 在m e m m 方法中只能对输入语段从一个方向开始扫描，对于m e m m 来说这是一 个弱点，即标注偏置问题( l a b e lb i a sp r o b l e m ，l b p ) 。l b p 是指离开一个给定状态 的转移只是彼此竞争，不会同模型中其它转移竞争，按概率术语，转移值是在给定当 前状态和观察序列条件下的条件概掣删。 解决l b p 的方法就是采用了两次m e m m ，第一次从左向右扫描输入字符串，第 二次从右向左扫描字符串，这样就解决了标注偏置的问题。 2 3 模式匹配算法研究 本文在搜索时主要采用了字符串模式匹配的方法。字符串的模式匹配实现了子串 在目标串中的定位操作。目前，字符串模式匹配算法有很多种。本文经过对各算法比 较，并根据实际需要选定了适合的算法并对其进行了改进。 2 3 1 算法阐述 模式匹配比较经典的算法有b f 、b m 和k m p 算法。下面对其原理及其优缺点逐 一进行介绍、比较，借此得到本文采用的算法。 1 b f 算法 b f 算法又称蛮力匹配算法，是一种效率很低的算澍4 。 b f 算法原理是在给定主串t = 丁t ，t 2 ，以) 和模式串p = 尸t ，尸z ，r ) 后，先将死 和p l 进行比较，如果不同，就将死和p l 进行比较，直到丁的某个字符正和毋相同， 再将正和尸i 之后字符串进行比较，如果仍然相同，则继续比较，如果r 的某个字符 与尸的字符不同，则r 返回到本趟开始字符的下一个字符继续比较，重复上述过程， 如果尸中字符全部比较完，则匹配成功，否则匹配失败【4 z j 。 b f 算法是典型的模式匹配算法中的一种，它是朴素的模式匹配算法，b f 算法同 其他算法相比简洁、直观。但是b f 算法在模式匹配的过程中产生了多余的回溯，直 接影响了模式匹配的效率。所以，b f 算法的应用并不是很广泛。 2 b m 模式匹配算法 b m 算法是1 9 7 7 年b o y e r 和m o o r e 提出来的一个算法【矧。 b m 算法的基本原理是从后向前进行匹配，直到找到匹配失败的位置或是发现成 功的匹配，并根据匹配的情况查找良好后缀跳跃表和不良字符跳跃表来使窗口位置向 后跳跃【州。也就是对模式串p 进行了预先处理，计算出两个偏移函数b a d c h a r ( 针对 某个字符) 和g o o d s u f f i c ( 针对某个子串) ，然后主串丁和模式串p 对齐，从右向左 1 4 第二章存储介质关键7 搜索技术的研究 匹配，当主串r 与模式串尸匹配失败时，利用b a d c h a r 和g o o d s u 伍x 函数计算偏移量， 最后采用其中最大的偏移量，依次重复进行【4 5 1 。 b m 算法是目前模式匹配中应用比较广泛的一种算法。但是，b m 算法并没有对 已经匹配的后缀和导致失配( 匹配失败) 的当前字符之间的关系进行分析m 】，这样大 大降低了算法的效率。同时，实际应用中，b a d c h a r 函数使用次数要比g o o d s u f f i x 函 数使用的次数多，依此可以看出b a d c h a r 函数在模式匹配时对于移动指针而言是起着 主导地位的，单独使用b a d c h a r 函数也是可以的【4 7 】。所以，b m 算法还有待于简化。 3 k m p 算法 算法是d e k n u t h 、j h m o r r i s 和v r p r a t t 同时发现的【4 8 4 9 1 ，简称k m p 算法。采 用该算法可以在复杂度是o ( m + n ) 的时间内完成对关键字的搜索。 k m p 算法原理是维护一个既是窗口中已读入字符串s 的后缀也是模式串尸的前缀 的最长字符串【5 0 】。在每次读入一个字符串时就要对这个最长的字符串进行实时更新， 在窗口中某个字符匹配失败以后，k m p 算法就会利用产生滑动窗口依次移动多个字 符的方式来避免字符的重复读入【5 。 与其他几种模式匹配算法项比较，k m p 算法在主串s 和模式串尸出现大量的“部 分匹配的情况下，匹配效率比较高，因此，本文利用k m p 算法、同时对k m p 算法 进行了改进从而实现模式匹配，以下对k m p 算法进行详细介绍。 2 3 2k h p 改进算法 1 k m p 改进算法的原理 定义：假设在字符串s = s i ，s ：，岛) 中查找字符串p = p l ，p 2 ，只) 。f 和指示主 串s 和模式串p 中当i j 正在比较的字符位置。 k m p 改进算法原理如下所示： ( 1 ) 在利用k m p 算法进行搜索的过程中，每当一趟匹配过程中出现字符不相匹配 时，不需要回溯f 指针，而是利用己经得到的“部分匹配”的结果将模式向右“滑动”尽可 能远的一段距离后，继续进行比较【5 2 】。 ( 2 ) 当s 与p i 字符匹配失败即“失配”时，匹配从串p 中第k 个字符与串s 中第f 个字符开始继续进行比较，推理过程如下： 假设在岛与尸i 字符匹配失败情况下，与串尸中第k ( 的) 个字符比较，不存在 肛 后满足关系式( 2 4 ) 。 尸l p 2 r i = 一k + l & 一k + 2 & 一i 式(