（管理科学与工程专业论文）单汉字全文检索技术研究.pdf

河北工业大学硕士学位论文 单汉字全文检索技术研究 摘要 随着计算机技术的快速发展，信息的种类和数量以惊人的速度增长，其中又以文字信息 量最大。如何对这些大量的文本信息进行存储和快速检索，一直是信息技术中研究的热点问 题，全文检索系统正是满足人们的这些要求应运而生的。全文检索的一个重要应用就是办公 自动化领域，在我国随着办公自动化进程的加速，对全文检索特别是中文全文检索的需求激 增。全文检索技术已是办公自动化系统的一个重要组成部分。 本文研究内容： 1 在对现有全文检索理论和检索系统的分析基础上，对基于单汉字的全文检索技术及 其标引方法进行了优化研究，提出了一种基于u n i c o d e 字符串的倒排文件存储结构 及其检索方法。 2 将单汉字全文检索技术与w e b 技术相融合，较为全面深入地探讨了建立一个应用于 局域网的单汉字全文检索系统所涉及的主要技术，基本上完整地展现了构建w e b 信 息检索系统的方法。 关键词：全文检索，单汉字，倒排索引，搜索引擎 呈竖王金苎丝茎茎查塑窒 r e s e a r c ho nf u l l - t e x tr e t r i e v a lt e c h n o l o g yf o r t h es i n g l e c h i n e s ew o r dc h a r a c t e r a b s t r a c t w i t ht h ed e v e l o p m e n to f c o m p u t e rt e c h n o l o g i e s ，t h et y p ea n da l t l o u n o f i n f b r m m i o na r e s i g n i f i c a n t l yi n c r e a s i n g a m o n g d i f f e r e n tk i n d so f i n f o r m m i o n ，t h ew o r d si n f o r m a t i o ne x p a n d s m u c hm o r et h a no t h e r s i th a sb e e nav e r yh o ti s s u et h a th o wt os t o r ea n dr e t r i e v et h ev a s tw o r d s i n f o r r n a t i o n c h i n e s ef u l l t e x tr e t r i e v a lt e c h n o l o g yi sj u s tb r o u g h tu pf o rt h en e e do f t h ew o r d s i n f o r m a t i o nr e t r i e v a l o f f i c ea u t o m a t i o ni sa ni m p o r t a n ta p p l i c a t i o no fc h i n e s ef u l l t e x tr e t r i e v a l t e c h n o l o g y i no u rc o u n t r yw i t ht h eq u i c kd e v e l o p m e n to fo f f i c ea u t o m a t i o n ，f u l l t e x tr e t r i e v a l t e c h n o l o g ye s p e c i a l l yc h i n e s ef u l l t e x tr e t r i e v a lt e c h n o l o g yi sn e e d e di n c r e a s i n g l y s oc h i n e s e f u t 一t e x tr e t r i e v a lt e c h n o l o g yh a sb e e na ni m p o r t a n tp a r t & o f f i c ea u t o m a t i o n t h ec o n t e n t so fr e s e a r c h e si nt h j st h e s i s ： 1 i nt h i sp a p e r , b a s e do na n a l y z i n gt h et h e o r i e so f f u l l t e x tr e t r i e v a la n dt h ee x i s t i n gr e t r i e v a ls y s t e m s ， t h ea u t h o rt u r n sar e s e a r c ht o w a r d st h em e t h o do fb u i l d i n gu pt h ef u l l - t e x tr e t r i e v a ls y s t e mb a - s e do n t h es i n g l ec h i n e s ec h a r a c t e r sa n dm a k e sar e l e v a n to p i 姐i z a t i o nw h a t sm 。r e ，ak i n do fs t r u c t u r eo f i n v e r t e di n d e xf i l e sa b o u tt h es t r i n go fu n i c o d ea n dar e t r i e v a lm e t h o da r ep u tf o r w a r d 2 w i t ht h ec o m b i n a t i o no fw e bt e c h n o l o g i e sa n df u l l t e x tr e t r i e v a lt e c h n o l o g y ，t h et h e s i s s t u d i e st h ec o r et e c h n o l o g ya b o u th o wt ob u i l daw e br e t r i e v a ls y s t e m a st h ec o n t r i b u t i o n ， t h em e t h o do fb u i l d i n gt h ew e bi n f o r m a t i o nr e t r i e v a ls y s t e mi sp r e s e n t e d ， k e yw o r d s ：f u l l - t e x tr e t r i e v a l ，c h i n e s ew o r dc h a r a c t e r ，i n v e r t e di n d e x ，s e a r c he n g i n e s 河北工业大学硕士学位论文 第一章绪论 1 - 1 选题背景及意义 近年来，随着科技的发展和经济的腾飞，图书馆、新闻出版、企业等单位电子数据激增，可供人们 选择的信息和联机文本数据库的数量急剧增加，传统的手工检索方式越来越不符台发展的需要。因此需 要采用更好的技术来充分利用这些信息。另外随着人们对计算机使用的普及，传统的书目检索系统只能 检索出二次信息，获得原文的线索需再通过手工查阅原文献的检索方式已越来越不能满足人们的检索需 要了，因为即使通过查检书目而获得大量满足要求的文献，多数文献由于其原文本身难以获取而束手无 策，忍痛放弃。全文检索系统正是为了让检索者能够“步到位”而产生的，而且由于其包含信息的原 始性，信息检索的彻底性，所用检索语言的自然性等特点迅速发展，已成为情报检索技术的热点。 全文检索的一个重要应用就是办公自动化系统。在我国近些年随着图书馆、报社、电台、电视台、 信息中心、大中型企业、政府等单位各种电子文件、档案、公函等信息的剧增，如何从这些海量文本中 快速找到所需要的信息，已是办公自动化过程中所面临的一个重大难题。因此在我国随着办公自动化进 挥的加速，对全文检索特别是中文全文检索的需求激增，全文检索技术已是办公自动化系统的一个重要 组成部分。 中文全文检索技术在原理上同西文全文检索是一致的，但汉字本身的特点使中文系统的实现比西文 系统更为复杂，且中国的全文检索技术起步较晚，因此同国外的全文检索技术还有一定的差距。基于汉 语自身的特点，我国研究者吸收西文全文检索的成熟技术，结合已有的汉语处理技术，对中文全文检索 进行了积极的研究。目前全文数据库及其检索系统的迅速增长，已是当前计算机化的情报存贮与检索的 前沿课题。 1 - 2 本文研究内容 本文将全文检索技术与w e b 技术相融合，较为全面深入地探讨了建立一个应用于局域网的单汉字中 文全文检索系统所涉及的主要技术和必要环节，提出了一种基于u n i c o d e 字符串倒排索引的存储结构。 既为全文检索的实现拓展了新的思路，也基本上完整地展现了构建w e b 信息检索系统的方法。 本文研究内容： 1 对目前的全文检索技术分析，找出不足和需改进之处。针对其不足，对基于单汉字的全文检索 理论进行了优化研究，提出了改进方法。 2 对目前的网络爬行者技术分析，提出了一个具体文本标记权值的存储方法及其网络爬行的算法。 并给出了理论和算法的具体实现。 单汉字全文检素技术研究 1 - 3 本文结构 全文整体结构如下： 第一章选题背景、意义，论文研究内容和论文结构。 第一章对目前全文检索技术的特点、优势、发展历史及业界情况及其研究前沿进行丁概述研究。 第= 章对全文检索的绑织索引技术、检索模型和基于中文的分词和单汉字检索技术进行了研究，并 将分词和单汉字检索技术进行了比较。 第四章在对现有的静态全文索引和动态全文索引基础上，对单汉字全文检索提出了种改进的文档 倒排索引结构，有效的提高建立索引及其数据的读取速度。并且给出了这种方怯的数据存储结构、标引 算法年检索算法。 第五章分析了网页文档的特点，结台标记加权的方法和网络爬虫技术构造了一个适用于局域网内的 搜索引擎。并给出了标记加权及阿络爬虫的实现方法。 第六章给出了该全文检索系统的部分实现方法。 第七章提出了目前中文全文榆索技术的不足及有待改进之处。 第七章提出了目前中文全文榆索技术的不足及有待改进之处。 2 河北工业大学硕士学位论文 第二章全文检索概述 2 - 1 全文检索技术的基本概念 全文检索( f u l l t e x tr e t r i e v a l ) 作为信息检索的最新技术，代表着信息检索技术的方向。但由于其 历史不长，所以尚无一个公认统一的定义。许多文献资料对全文检索的定义为“全文检索是指以全文 文本信息作为检索对象，建立全文数据库，除了具有布尔逻辑检索功能外，还具有文本检索功能，并允 许h j 户以自然语言检索，直接获得原文中的有关章节和段句”。 与传统的检索相比，全文检索有许多特点：口 1 直接性。提供存取全文文本的空间，能直接检查原始文献或解决问题所需要的文献资料，不必进 行一二次检索。全文检索得到的是全文文本，而不是文献的摘要或替代品。 2 详尽性。文献的正文部分或附属部分都可以检索和显示。 3 方便灵活性。文本中任何字符或字符串都可以作为检索的入口点，用户可直接查询文本中的任何 成分或特定单元。 4 广泛适用性。能处理结构化和非结构化的各类文本数据。能够采集各种来源文本，这些来源可能 是跨越广泛地理分布的，也可以是不同介质、不同格式产生的文本，整理转换成标准形式，实现全文检 索； 5 后处理能力。具有对检索出的文本进行处理的能力，并且以用户乐于接受的形式提供检索并加工处 理文本使检索系统功能得到了延伸。 6 用户友好性。易学易用，界面友好，检索方法接近自然语言。 7 易于自动化。分词、标引易在计算机上实现。 2 - 2 全文检索的发展过程 计算机信息检索经过了3 0 多年的研究和实践，在理论和应用上，都取得大的发展，出现了众多新 型的检索系统。发展过程归纳入下：i z l 第一阶段：1 9 7 1 年以前，国外研制和建立了不少信息检索系统，并取得一定的进展，但工作方式是 传统的批处理检索方式。如1 9 5 4 年美国海军兵器中心图书馆在旧m 7 0 1 型计算机上成功建立了世界上第 一个计算机文献检索系统，可是，这一阶段的数据的存取与数据的通信能力比较差。 第二阶段：1 9 7 1 年以后，产生并发展了联机情报检索系统，如美国国家医药图书馆建立的在线计算 机图书馆中心o c l c 和s d c 公司建立的s y s t e md e v e l o p m e n tc o m p a n y 都是在线数据库查询系统。这一阶 段的特点是联机数据库集中管理，具有完备数据库联机检索功能，但其数据库通信能力也较差。 第三阶段：目前以i n t e r n e t 的出现为标志，系统大多采用分布式的网络化管理。当前情报资源的主 单汉字全文检索技术研究 要特点是：数字形式表达、多媒体和多载体、内容覆盖全社会领域、分布无序、难于规范化和结构化、 内容特征抽取复杂、用户界面要求较高等。这些特点导致了信息处理从传统模式的转变，如体系结构从 终端土机方式到客户服务器结构方式；网络环境从局域网到广域网；信息结构从结构化到非结构化；系 统功能从单纯信息检索到综合信息管理和服务等。 我国计算机全文检索起步于8 0 年代初期，并在计算机编制主题词表、汉语自动分词和标引、数据库 建造、情报检索和相关软件的研伟4 、联机检索、机器翻译、图书馆业务管理、全文检索理论等主耍领域 取得了很大进步。在微机工作平台上，目前已建立了十儿种中英文检索软件，其中比较著名的有易宝北 信的t r s 、北大方正的m i r s 、中国百科术语数据库和海文q u i c k 等。这些全文检索系统软件在建库、 检索方法、检索速度、检索准确性等方面各有千秋，多适用于单机用户使用，有的也采用了客户服务器 方式。 由于汉语语言的独特性，十几年来，我国的计算机信息检索基本上仍以传统的顺序检索或顺序检索 与倒排文档相结合的检索方法为主，局限于以传统人工赋词标引方法为主的目录或摘要二次文献，以及 以词检索为主的全文系统。这与国外的信息检索系统有一定的差距。 2 - 3 全文检索前沿 ( 1 ) 超文本检索 超文本检索技术是以超文本网络为基础的信息检索技术。在超文本检索系统中正文信息是以节点而 不是以字符串为信息的基本单元，节点间以链连接。在检索时，节点间的各种链接关系可以动态的选择 激发通过链从一个节点跳到另一个节点，实现联想式检索。 ( 2 ) 概念信息检索” 概念信息检索，又称基于知识的信息检索，是通过对文献中的原文信息进行语义上的自然语言处理， 析取各种概念信息，由此形成一个知识库。然后根据对用户提问的理解，检索知识库中相关信息，以提 供直接的回答。 ( 3 ) 智能检索口1 简单地根据用户的输入而搜索文献的检索方式在很多情况下不能很好地满足用户的需求：一种常见 的情况是，用户头脑里清楚自己所要搜寻的是什么信息，但却很难找到或不能确定用哪一个词来描述。 因此，就有可能使搜索变得困难，智能化检索就可以解决这一问题。智能检索的目标是自动根据用户的 提示( 如最初的检索项) 而搜索出相关的文档。智能检索还可以进一步采用人工智能技术、自然语言处理 技术等，有广阔的发展空间，它的使用将使全文检索的查询效率进一步提高。 除此之外，文本采掘技术、多媒体检索和视频信息查询等新技术也在研究之中。 4 2 - 4 全文检索系统的衡量指标 对每一个检索系统都需要特定的指标来衡量该检索系统的优嶷程度。通常我们依据用户的检索结果 河北工业大学硕士学位论文 来评测。用户针对最终得到的文献记录，确定出相关文献有多少篇，不相关文献有多少篇，分析相关文 献对用户课题起到何种帮助或效果，最后用一定的衡量指标来衡量本次检索效率。检索效率的衡量指标 有很多，目前认为晟重要又最常用的有两个：查全率( r e c a l lr a t i o ) 和查准率( p r i c is i o nr a z i o ) 。 查准率：垫垫曼塑塑叁壅堂堕塑。1 0 0 ( 2 1 ) 被检出的文献的总篇数 查全率：墼熊当塑塑茎茎! ! 塑型 。i o o ( 2 2 ) 数据库中的相关文献篇数 在实际检索中，当放宽检索以提高查全率时，往往使查准率下降；反之，当缩小检索范围以提高查 准率时，往往又使查全率减小，两者往往是一种互逆关系。除了查全率和查准率两个常用指标外，还有 误捡率、漏检率、离散率、拒绝率等，有如下关系： 查全率+ 漏检率= l 查准翠+ 误检率= l 除查全率和查准率两个指标外，还有以下指标： 响应时间：又叫检索速度，是指从提交检索课题到查出资料结果所需的时间。对于动辄上l g b 的海量 全文数据来讲，检索速度至关重要。如果检索系统速度太慢，系统实用性就会大打折扣。最基本的检索 速度是“千万汉字，秒级响应”。 收录范围：指所查找的范围。只有收录范国全面，才能保证真正的查全。 用户负担：指用户在检索过程中付出精力的总和。 输出形式：系统所检索出的资料的形式，可能是资料号、记录、文摘或全文等。输出的信息越多且 便于浏览，用户越容易做出相关性判断。输出形式影响用户对查准率的容忍限度。 检索指标举例说明： 例l ：查询关键字“华人”，不能把“中华人民”查出来。否则是误查，出现分词错误。 例2 ：查询关键字“电脑”，也应把“微机”、“计算机”等查出来。否则是漏查。全文检索系统应 具备联想能力。 例3 ：查询关于华北地区的情况，应把北京的情况包括在内，因为北京属于华北地区。查询关于交通 工具的情况，应把诸如b 机、火车、汽车、自行车等的情况包括在内。这要求全文检索系统有推理能力。 例4 ：蠢询关键字“下岗”，由于这个词是新词，目前的词典中不易找到。但检索系统应及时做出反 应，不能出现明显的速度瓶颈。 例5 ：在流行配置的微机上运行中文全文检索系统。如果在一般规模的数据中查询任意的关键字，当 等待的时间是以“l o 秒”作为时闻单位时，系统并不实用。 5 单汉字全文检索技术研究 第三章全文检索关键技术 全文检索主要是由两方面的核心技术相结合而实现的。一个是建立和维护全文检索索引库，另一个 是提供快速有效的检索机制。一个全文检索系统的实现过程一般由前处理、检索操作和后处理三个阶段 构成，田而在设计时，要针对实际应用需求，确定索引库的数据结构和存储方式，以及如何从原始文档 中抽取出全部有用信息并将这些信息记录到索引库中。在索引库的基础上，系统要提供快速有效的检 索机制阻及友好的结果反馈机制，从而实现在尽可能短的时间内查找到符合用户需求的全部源文档。 3 - 1 全文数据库组织与索引技术 建立一个全文检索系统，首先要将源文档转换为能够进行文本查找的全文数据库，包括全文的分割 处理以及检索标识的提取，这称为全文本的前处理工作。前处理实现对各种文档格式的支持与转换以及 信息过滤，对信息的标引、分类，生成可供检索的索引库，即进行全文数据库的组织与索引，这是整个 系统的基础。其中涉及以下几个关键技术。 3 - 1 1 分词技术 词语切分技术一直是汉字信息处理研究中的关键问题，并且也成为一大瓶颈问题。对于任何一种类 型的情报检索系统来说，用户提交的检索提问往往是所需文献的关键词，要使系统能够快速准确的在数 据库中定位到包含该关键词的文献，则必须将原文献内容转换成特定的简明标识，即对文献进行标引。 标引是建立索引和检索的基础。全文数据库的标引与书目数据库的标引不同之处在于全文文本的篇幅巨 大，其中关键词、人名、地名、年代等知识项数不胜数，要把其中所有具有检索意义的词全部抽取出来， 采用手工标引是不现实的。而自动标引必然会涉及到词语的自动切分问题。 汉语是以汉字为单位的，缺少严格意义的形态变化的表意文字，没有明显的形态界限作为分词标 志，不同的分词形式还可能代表着不同含义，于是分词问题就成了计算机处理汉语的首要难题。 3 - i 2 组织索引技术 对于容量巨大的全文文档库，为了实现快速响应，一般需要预先对其建立索引，检索过程则是基于 这些索引进行的。 全文检索系统建立索引的过程分为两步：1 ) 依次对每个已经入库的文献进行扫描，获得文献中所有 具检索意义的词及其位置信息。2 ) 把每个词的位置汇总到一起，记录到索引文件中。”5 根据在索引文件 所记录信息的不同组织方式，国外将全文数据库的索引机制区分为两大方法，即对标签文件( s i g n a t u r e f i le s ) 建立的全文索引和对倒排文件( i n v e r t e df i l e s ) 建立的索引。标签文件技术是将每个文档都划 分成一定数量单词的段，然后按照一定的算法( 如哈希函数) 将每一段转换成一个位串( ab i ts _ r i n g ) 6 河北工业大学硕士学位论文 形式的标签( s i g n a t u r e ) ，用以唯一标识文献，所有标签的集合组成一个标签文件，索引文件则由这个 标签文件和一个指向相应的数据文件( d a t af il e ) 物理地址的指针数组组成。其索引结构如图3 1 所示。 标签 数组指针 图3 1 标签文件索引结构 数据文件 f i g 3 1 i n d e xs t r u c t u r eo f t h es i g n a t u r ef i l e s 检索时首先以同样的算法将检索式转换成相应的位串，将其与标签文件中的各标签进行位运算，结 果为“l ”则被认为命中，然后根据相应的数组指针获得原文献。这种方法对原文的压缩比率高、查询速 度- 陕，但位运算可能导致误匹配，而且只能判断某个单词在文献中是否出现，而无法获取其出现的位置、 次数等，且对于容量过大的数据库来说难以确定高效的处理算法。”因此，在全文索引库的建立过程中， 更为普遍采用的还是撼排索引技术。 倒排索引是以全文中所有可检索项( 包括字段信息、任意字词) 建立一个或多个索引。索引文件和 倒排文件在物理上是分开的，逻辑上也可组合成为倒排索引文件。在索引中，每条记录包含索引词以及 与该词有关的逻辑记录号或指针。倒排文档中还可加入文献中各个词的位置信息，包括逻辑记录号、段 号、行号等。检索时，由索引文件指向倒排文件倒排文件指向主文件。倒排索引的形式多样，其基本 结构如图3 2 所示。 倒排索引文件 地址对照文件 l 逻辑记 在主文件中的地址 l 录号 物理记录号相对位置 r t 1 主文件 l 竺竺兰l 兰兰兰苎! | 兰兰兰兰! l 二= 囤3 。2 倒排文件索引结构 f i g 3 2i n d e xs t r u c t u r eo f t h ei n d e xf i l e s 7 单汉字全文检索技术研究 全文数据库的索引文件与一般数据库的索引文件不同后者是按整个字段建立索引，而全文索引则 大多只是就文本型字段( t e x t ) 和短语型字段( p h r a s e ) 而言，前者适于由若干段落组成的文本，后者 适于题名、人名、机构等较短的文本。因而全文索引主要体现在倒排文件中。 3 2 全文检索模型 信息检索系统的核心是查找，它需要在大量复杂信息中，筛选出符合用户需要的信息。检索模型就 是用来描述这一查找过程的。根据查找相关信息方式的不同，可将检索分为布尔模型、向量空间模型、 概率模型、模糊逻辑模型等。 3 2 - l 布尔逻辑模型 布尔逻辑模型f 9 1 是最简单的检索模型，也是其它检索模型的基础。标准布尔逻辑模型为二元逻辑， 即一系列对应于文件特征的二元变量。这些变量包括从文件中提取的文本检索词，有时也包括一些更为 复杂的特征，如数据、短语、私人签名和手工加入的描述子。在布尔模型中有确切的文件特征表达集合， 用户可以根据检索项在文档中的布尔逻辑关系递交查询。匹配函数由布尔逻辑的基本法则确定，所检索 出的文档或者与查询相关，或者与查询无关。查询结果一般不进行相关性排序。 3 - 2 2 模糊递辑模型 为了处理精度和复杂性之间的矛盾，引入了模糊逻辑模型【9 1 ，它以逻辑真值为 o ，1 的模糊逻辑为 基础的，以隶属函数概念来描述现象差异的中间过渡。在查询结果处理过程中引入模糊逻辑运算。将所 检索的文件信息和用户的查询要求进行模糊逻辑比较，按照相关性的优先次序排出查询结果，在布尔检 索中借助模糊逻辑模型能够克服布尔逻辑查询结果的无序性。 3 - 2 3 向量空间模型 向量空间模型i i 是近年来使用较多且效果较好的一种信息检索模型。向量空间模型是由s a t t o n 及其 学生们提出的，并在著名的s m a r t 系统中实现。 向量空间模型将文档看作由相互独立的词条组( t l ，t 2 ，l n ) 构成，对于每一词条t i ，都根据其在 文档中的重要程度赋以一定的权值w i ，这样文档就映射成为以各个词条组成的n 维空间中的一个点。对 于所有文档和用户查询部可映射到此文本向量空间。用户查询和被检索文档两者的相似程度可用向量之 间的夹角来度量。这种表示模型考虑到了文档的内容特征，而且文档之间的相似程度的度量比较简单， 现在有一些w e b 上的检索系统采用了这种检索模型，并取得了较好的效果。 3 - 3 4 概率模型 8 彳e 信息检索中存在不确定性问题，对查询本身来说，它不能唯地表示信息需求，对于结果来说 河北工业大学硕士学位论文 不能判定查询结果的正确与否。对于布尔检索也是如此，因为查询的提交本身就是一种不确定方式。为 了解决在布尔检索模型中的不确定性问题引入了概率检索模型。该模型基于概率排队理论：当文件按 相关概率递减原则排列时可以获得最大的检索性能。 3 - 3 1 中英文全文检索的区别 3 - 3 中文全文检索技术 英文全文索引与全文检索在许多检索系统中已应用多年，而中文全文检索的研究历史则相对较短。 二：者既有相似之处、也有不同。在计算机内部，无论汉字、西文和数字都以字节形式存储。中、英文全 文检索实际上都是将一个计算机存储的文本记录与用户信息需求做相似程度的比较，并把足够相似的文 本记录返回的过程。 中文全文索引和英文全文索引之间主要区别是如何确定索引单元。这神差别是由于汉语本身造成 的：1 l 、汉语词与词之间不象西文那样有空格，有明显的切分标记。在汉语中一个字符既可以作为一个词 使用，又可以和相邻的一个或几个字构成词，丽词的含义并不是组成它的各个单字之间的简单迭加。 2 、汉语迄今为止仍未有一部公认的、确切完备的并适于电脑处理的语法。西文现在有罗列例旬的传 统语法，层次加形式化分析描述语言结构的结构主义语法和数学演绎方法的转换生成语法，而汉语语法 却无标准性。 3 、中文检词方法的多样性及句法的“意重合”特点使分词十分困难。 4 、书面材料丢失了语音材料中所蕴含的部分有用信息，声调等的变化可提供大量的切分信息。 5 、汉语中的新词不断增加。 从以上分析来看，中文全文检索比英文全文检索困难得多，它涉及到词语切分问题。目前中文全文 检索技术根据倒排文件包含索引词形式的不同，可将全文检索分为基于单汉字的全文检索和基于分词的 垒史检索。 3 - 3 ，2 基于分词的全文检索研究 3 - 3 2 1 词的切分方法 从理论上讲，情报检索是以概念为基本单元，词是概念的基本组成部分，中文同西文一样，词也应 是基本的最小检索单位。 基于分词的中文全文检索系统就是以词为索引项的全文检索技术。这种全文检索系统除具有检索模 块以外，还要有自动分词系统和词典，从而实现按词建库和按词检索。以词为检索项的技术重点是词的 切分问题，分词方法主要有基于词表的分词方法。以词为索引项的技术重点是词的切分问题。 尽管计算机自动分词存在着许多困难，但由于自动分词是许多应用工作的第一步，促进了研究的持 续4 ；断，提出了不少方法，它们各有优缺点。目前分词方法很多，归纳起来不外乎两类：第一类是在生 9 单汉字全文检索技术研究 成关键词时，将语法、句法、语义结合起来，试图模仿人类的阅读过程。但有时语法、句法、语义连开 发人员都不是很清楚，故一般情况下不采用。第二类由字典匹配法和基于频度方法组成，这些方法比起 上一种来较具体、实用。 目前国内已经公开报导的分词系统所采用的分词方法基本上分为以下几类： ( 1 ) 典型的自动分词方法1 1 “ 正向晟大匹配法( 删法) 和逆向摄大匹配法( r 埘法) 正向最大匹配法是最早提出的自动分词方法，它的基本思想是先取一句的前六个字查字典，若不是 一个词，则删除六个字的最后一个宇再查，这样一直查下去，直到找到一个词为止。对句子剩余部分重 复此工作，直到把所有的词都分出为止。逆向晟大匹配法和法一样，不同的是它是从句子的最后六个字 开始的，每次匹配不成功时去掉汉字串中前面的一个字。 两法思路清晰，易于计算机实现，但由于试图用相对稳定的词表来代替灵活多变，充满活力的词汇， 把词表作为判词的唯一标准，因而具有很大的主观性和局限性。另外，删法和r m m 法实际上否认了“词中 含词”这一语言现象( 即组合递归性) ，因此出错率高，拒分现象严重。 ( 2 ) 高频优先法1 此法是基于词频的统计，字与字之间的构成结合律和歧义切分等现象的分词提出来的。根据现代 汉语频率词典，对于报刊和政论性文章，不同音节词的概率为：双音节词7 4 ；三音节词3 7 ，单音节 词172 、五以上字节词0 4 。汉语是一字一音节，因而也可以说，两字组词的概率比其它所有方式的概 率加起来还多。分词时首先考虑两字词，然后考虑单字词，。这种方法提高了分词效率，但歧义问题 也无能为力，出错率并不减低。 3 - 3 2 2 分词检索技术的优点 i 、检索速度较按字检索的快。在理想情况下，检索词语经分词后的检索单元数量一般要少于以字为 检索项的检索系统，当检索词语较长时，检索效率的提高比较明显。 = 、查准率较高。系统可以利用语言学知识借助词典和分词规则避免歧义词，如检索“华人”这个词， 按字检索会将“中华人民共和国”也检出，而分词系统可以借助分词规则和词典避免这一情况。 ：i 、可以借用英文全文检索系统中已有的理论及方法，英文全文检索中有许多成熟有效的方法可以直 接借鉴。 4 、可以完成概念层次、主题的提取和检索。 3 - 3 2 3 分词检索技术的缺点 l 、构造一个可以跟上时代发展的词典是分词系统的一个难题。由于现代语言的发展和外来语的引进， 符合新时代特色的词典的构造不是一件简单的事，成为分词检索系统开发的制约因素。添加新词语，建 立众多词语的新概念模式、删除过时词语的维护工作量极大。从成本角度看，词典的更新维护加大了用 户的使用成本，不利于系统的推广。 2 、中文构词方法的复杂性使得人们难以构造一个完全准确、合理的分词规则，因此查全率一直是分 词算法难以解决的问题，影响了基于分词的全文检索系统的可靠性。迄今为止始终没有一种有效的分词 规则可以彻底解决查全、查准率的问题。 3 、在分词过程中大量的人名、地名和许多专有名词、新的语言词语、外来词无法在词典中记录，而 1 0 河北工业大学硕士学位论文 分词规则也无法识别这些词，只能借助按字索引的方式解决。在实务中有相当多的检索信息是这类名词 因此从实际看，降低了分词检索的效率，使得分词检索系统的检索效率优势大打折扣。 3 - 3 3 基于单字的全文检索研究 3 - 3 3 1 单汉字检索的优化研究 近年来人们把汉字文本的检索放在单字一级的基点上，以绕开词的切分问题。所谓单汉字检索系统， 就是对每个单字的出现位置进行倒排索引，并依据单字的位置信息进行检索的检索方法。其索引库的主 要部分是每个字的位置信息，建立字索引时，需要扫描整个源文档，对出现的每一个有效字符，计算其 在交档中出现的位置，并将该位置的值加入到对应的字索引库中。【l m 咀单个汉字为单位建立索引的单汉字索引技术绕过了自动分词的处理障碍，为全文检索系统的实现 提供了一条新思路。我国学术界对单汉字索引和检索技术的优化研究进行了许多有益的探索，提出了不 同的改进方法并对每一种的具体实现提出了不同的实现算法。 ( 1 j 停用字表1 停用词表即把汉语中频频出现的助词、连词、语气词等都收入到停用词表中。如“的”、“了”、 “啊”、“吧”，这些词一般不具有检索意义，把这些词都归入停用词表，就可以节约空间，压缩索引 的篱幅，加快检索的速度。但是严格地说，建立停用词表也会产生一些问题，因为汉字的丰富语义，有 些字看上去没有检索意义，在有的时候又会有检索意义、如“的”字通常没有实际意义，但“美的”却 是一种家电品牌，把“的”字收入停用词表，则检索“美的”时就查不到相关资料。 ( 2 ) 建立后控词表”“ 控制词表辅助检索策略是一种人工优化方法，后控词表则是控制词表功能的机器自动实现形式。后 控词表中收录同义词和相关词，其目的是为了减轻检索者的智力负担，提高系统的查全率和查准率。在 检索过程中，用户只需输入表达某一概念的一个检索词，系统就会自动从后控词表中搜索出相关词，或 根据要求提出上位词、下位词作为检索词，以保证检索结果的完全和准确。在王森开发的s c t r $ 系统中， 后控词表收有同义词和上位词，其记录格式如表3 1 所示： 表3 1 记录格式 t a b l e3 1f o r m a to f t h ef e e o r d 主题词同义词上位词 3 ) 生成检索结果文档【1 6 i 将已检索过的所有检索词连同与它们有关的记录号( 即检索的中间结果) 组成检索结果倒排档。以后 检索时，对倒排档中存有的检索词可以直接采用倒排检索的方法而不必进行单字组配或位置运算，其功 能在于：加快系统响应速度；以检索结果文档中存储的检索词为基础建立的后控关键词典，具有很强的 针对性，且可避免一个庞大却利用率低下韵后控词典所造成的资源浪费。 1 4 ) 预捡索 将常用词组或机内主题词表中所有的词作为检索字串，查找单汉字索引，进行组配运算蛆生成词组 1 1 单汉字全文检索技术研究 倒排档或主题词倒排档。预检索的目的在于尽可能地将费时的单字逻辑组配运算提前于用户完成， 以减少用户检索时的等待时间。但是预检索在提高检索速度的同时，却增加了维护的负担，尤其是当主 题词袭很大时，用每个词对所插入的记录进行预检索以更新倒排档是一项费时的工作，而且用户最终 可能只用到少量的词，盲目的预检索势必造成倒排档的日益庞大却利用率不商。 3 - 3 3 2 按字检索技术的优点 t 1 ) 建立索引方法镝捷。接字索； 技术采用按单个汉字建立位置索引的方法。按照g b 2 3 1 2 的规定共 有6 i 6 ， 个汉字。这样索引集合就非常小，最大不会超过6 7 6 3 。在这一点上与其它索引项技术相比优点非 常明显。 ( 2 ) 节约了标引时间。汉字是中文构成的最小单位，具有不可分割性。汉字与汉字之间存在着自然 分割，无需任何特殊技术便能提取到“标引字”。因此使用单汉字标引技术，既省去了手工标引所需的 大量时间和精力，也省去了自动分词过程所带来的许多麻烦。 ( o ) 具有查全率高的优点。单汉字的标引技术是将文档的全部字符建立索引，因此具有1 0 0 的查全 率，不会漏查，明显优于按词检索。 ( 一i ) 检索词语的组合可以十分灵活，适应性强。按字检索可以适应于任何专业，对于任何专业性强 或专指度高的概念，只要向系统输入代表该概念的汉字，就可获得一定的检索结果。 ( j ) 便于用户的系统维护。随着时代的发展进步，新词语，新概念层出不穷，分词系统的词典面临着 繁杂的词典维护工作，按字检索则无需建设词典，系统维护十分方便，使用成本低廉。 ( o ) 用户操作简便。用户无需学习标引知识，输入检索词语就可以完成检索过程，操作十分简便。 3 - 3 3 3 按字检索技术的缺点 t 1 ) 相对于按词检索，按字检索速度铰陧，检索效率较低。中文词语一般由2 4 个单字组成，按字检 索需要检索出这些单字后做逻辑乘运算，检索单元数量要多于按词检索，因此按字检索比按词检索的速 度慢。 【2 ) 查准率较低，有时会出现歧义现象，检出的无用信息比按词检索的多，需要通过对检索词语进 行后控处理才能提高查准率。 由于查准率较低，用户需要自己构造一个比较复杂的逻辑公式完成查准要求，加莺了检索青的智 力负担。 ( ) 在没有实际含义的虚字、分辨力极低的汉字上牺牲了空间。 3 - 3 4 中文全文检索算法的比较结论 在实践中，在某些涉及法律政策条款检索、专利、商标注册检索以及检索结果已知具有唯一性的苛 亥检索条件下，基于分词的中文全文检索方法就不能保证查全检索要求，可能会造成漏查并造成用户无 法接受的后果。因此，在实务中的查全率是衡量中文全文检索技术水平的一个非常重要的指标。全文检 索系统分词理论研究历经二十余年仍无根本解决查全率的办法，而按字检索算法就完全可以保证1 0 0 9 6 查 全率。 在查准率方面，按字检索词语的歧义现象的确存在，但其检索出的歧义结果一般不会是主流结果。 因此，按字检索的查准率是可以令人接受的。同时。按词检索的查准率仅仅是比按字检索方法略好，并 1 2 河北工业大学硕士学位论文 不能达到1 0 0 的要求，也就是说按词检索的查准率也只是达到在人们可以接受范围之内比按字检索稍好 的程度。 i n t e r n e _ 的发展使信息量快速膨胀，中文的高速检索问题必须加以很好的解决。按字检索的检索效 率低于按词检索，因此，从实践上看，中文全文检索理论的一项熏要_ t 作就是如何提出一套在检索速度 方面可能仍然低于按词检索，但是较以住有较大增加，使得检索速度从实践上看是可接受的、基于单字 的全文检索数据结构和算法模型。 1 3 单汉字全文检索技术研究 第四章单汉字全文检索的优化研究 全文检索技术包含两方面的核心问题：一个是如何建立和维护索引库；另一个是如何提供快速有效 的检索机制。因而在设计时，要针对实际应用需求，确定索引库的数据结构和存储方式。 4 - 1 1 静态索引技术 4 - 1 现有的索引技术 所谓静态索引，就是假设被索引的原文基本不变化，或者更新的周期很长一旦被索引的原文更新， 所有的索引文件都要重新做一遍，也有人称之为索引重装技术。 静态索引技术早在2 0 世纪7 0 年代初就在d i a l o g 系统中实现了。在静态索引技术中，整个数据库由4 个 文档组成b ，如下页图4 1 所示。 主文档( m a s t e rf i l e ) ，存储与打印格式相似的文件正文，包括文件标识( 格式、长度) 以及每一段的 格式长度、段代码和段内容。数据库中的全部文档按顺序文档方式存放。 主索引( m a s t e ri n d e x ) ，每条记录由指针、文献号、删除标志、文献密级和格式化数据组成。其中， 指引指向主文档，格式化数据来自主文档中相应的格式化字段。 倒排文档( i n v e r t e df ii e ) ，与一般的倒排文档相似，但对于每个词在文件中出现的情况提供更详 细的信息。每个记录由控制串及若干个出现值构成。控制串项的内容有某词的文献数量、总词频及出现 位置数据。这些位置信息使得系统在倒排检索阶段就能支持各种位置检索，检索过程中不必查询主文档 便能满足检索者的各种检索运算要求。 倒排索引( i n v e r t e di n d e x ) ，是系统利用“停用词表”进行自动抽词后生成的文档。每个记录由j 项内容组成，即倒排文档指针、总文献量、总词频、同义词指针和词本身。 静态索引技术有它的优点，就是把索引分小。如果把i x 和i f 放在一起，索引显得很大，内存中放不 下索引数据，把i x 和i f 分开后，工x ( 有人称i x 为数据库的词典) 就基本可以存放在计算机的内存中，从而 加快了查询速度；其次，静态索引技术与被索引原文的更新周期是相适应的，比如d i a l o g 系统，它的更 新周期以周、半月来计算，况且它的机器比较高档，每隔一周、半月之后，重新装入一次索引，也不觉 得是个负担。像d i a l o g 这样的联机检索系统，追求的是检索响应时间，每天都有几万人次访问，它的 查询速度必须很快才行。但是，随着互联网的迅速发展，数字资源建设的突飞猛进，仅仅依赖于静态索 引技术，还是很不够的。 1 4 河北工业大学硕士学位论文 1 x ( i n v e r t e di n d e x ) i f ( i n v e r t e df i l e ) i f 记出现偏m x 指 录号次数移针 卜 1 0 061 0 0 0 l f ) 182 0 0 i 1 0 22 03 0 0 l 2 0 032 0 0 1 2 0 l1 0 1 0 0 0 2 0 23 03 0 0 1 2 0 33 08 0 0 0 2 0 42 06 0 0 0 m x ( m a s t e ri n d e x ) m f 指针删除m x 记录号 标记 卜一 1 0 0 0 01 0 0 0 5 0 0 0 0 8 0 0 0 m f ( m a s t e rf i l e 、 文献标识内肝记录 容 幅e d j 0 0 0 0 v c s d w5 0 0 0 0 4 - 1 2 动态索引技术 图4 1 静态索引技术示意图 f i g 4 1s k e t c hm a po f t h es t a t i ci n d e xs t r u c t u r e 所谓的动态索引技术【2 ，就是假定被索引的原文是频繁变化的，一旦被索引的原文更新，索引程序 只是对新添加或修改后的原文进行索引，以前的索引( 即对应原文未被改变的那部分索引) 不必重做，也 有人称这种索引方式为增量式索引。 静态索引模型缺乏动态性主要是索引文件( i f ) 是连续的，这样，在要对新加入的文件集添加索引 时，必须要打乱原来的索引，导致所有索引需重新排序。这主要是数组的缺点。因此人们根据数据结构 中的链接表思想，提出了索引分块技术。 基本思想是：把索引分割成字节数相等的若干部分。如图4 2 所示( x 代表部分己填写了数据 代表该部分尚未填写数据) l x ) 【) ( x x x x x x ) 【) (x x x x x x x x x x x 图4 2 索引分块技术示意图 f i g 4 2s k