（计算机应用技术专业论文）基于双数组的分词词典研究与实现.pdf

大连理工大学硕士学位论文 摘要 分词词典是汉语自动分词系统的一个基本组成部分，词典的查询速度直接影响到分 词系统的处理速度。在因特网上的中文文本检索、汉字与汉语语音识别系统的后处理以 及中文文语转换系统的前处理等，均对分词速度提出了更高要求，因此建立高效快速的 分词词典具有显著的现实意义。 目前信息处理用的词典机制主要有整词二分、t r i e 索引树、逐字二分等j l 种方法，其 中t r i e 索引树和逐字二分机制查询效率较高。这儿种词典机制都是以排序的线性表来提高 查询效率，数据结构比较复杂且查询速度较慢。本文主要工作是分析了几种常用词典构造 方法的优缺点，针对分词中特定的查询条件，设计并实现了基于双数组的分词词典，同时 分析了基于双数组的分词词典的性能。本文将双数组方法与其它几种词典构造方法进行了 对比分析。在双数组词典构造方法与p a t 树方法的对比实验中，可以看出双数组方法的查 询速度要好于p a t 树及其变型树的查询性能。 本文最后给出了分词词典实现的数据存储模型，并详细分析了该模型的优缺点。该模 型的主要特点是将存储的数据分为两种不同长度信息进行存储，这样可以大大减少对文本 的读取操作，能够加快分词的执行速度。对于文中提到的未登录词问题，本文也做了简单 的尝试，利用p a t 树的动态性特点以及统计模型的优点，从大规模文本中查找词频高于一 定阈值的高频词，从而识别出一部分的未登录词，进而部分解决分词过程中未登录词过多 的切分问题。p a t 算法和d o u b l e - a r r a y 算法具有不同的有缺点，可以满足不同场合的需要， 也可以组合起来使用，解决词典查询的速度和动态性这两个较困难的问题。 关键词：分词词典；双数组：p a t ；词典机制 人连理r 大学硕上学位论文 a s t u d ya n dr e a l i z a t i o no fd o u b l e a r r a yb a s e d s e g m e n t a t i o nd i c t i o n a r y a b s t r a c t t h ed i c t i o n a r ym e c h a n i s ms e r v e sa so n eo ft h eb a s i cc o m p o n e n tsi nc h i n e s ew o r d s e g m e n t a t i o ns y s t e m s i t sp e r f o r m a n c ei n f l u e n c e st h es e g m e n t a t i o ns p e e ds i g n i f i c a n t l y m a n y a p p l i c a t i o n s ，s u c h a st e x t sr e t r i e v a lo ni n t e r n e t ，p o s t - p r o c e s so fr e c o g n i t i o no fc h i n e s e c h a r a c t e ra n ds p e e c ha n dp r e p r o c e s so ft e x tt os p e e c h ，n e e dh i g h - s p e e ds e g m e n t a t i o n t h u s ，i t i ss i g n i f i c a n tt pc o n s t r u c ta ne f f e c t i v es e g m e n td i c t i o n a r y n o w a d a y s ，t h e r ea r es e v e r a ld i c t i o n a r ym e c h a n i s m sf o ri n f o r m a t i o np r o c e s s ，a n dt h e ya y e b i n a r y s e e k b y - w o r d ，t r i ei n d e x i n gt r e ea n db i n a r y s e e k - b y - c h a r a c t e r t h el a s tt w om e t h o d s h a v eh i g h e ri n q u i r y e f f i c i e n c y a l l o ft h ea b o v et h r e em e t h o d si m p r o v et h e i r i n q u i r y e f f i c i e n c yu s i n gs o r t e dl i n e rt a b l ew i t hc o m p l e xd a t as t r u c t u r e sa n dp o o ri n q u i r ye f f i c i e n c y i n t h i sp a p e r , a d v a n t a g e sa n ds h o r t c o m i n g sa r ea n a l y z e d i no r d e rt os a t i s f yt h es p e c i a li n q u i r yi n c h i n e s es e g m e n t a t i o nw ed e s i g na n di m p l e m e n tas e g m e n td i c t i o n a r yb a s e do nd o u b l e a r r a y a n da n a l y z et h ep e r f o r m a n c e a tl a s t ，w ec o n d u c tc o m p a r i s o n so fd o u b l e a r r a yw i t ho t h e r s e v e r a ld i c t i o n a r ym e c h a n i s m s e x p e r i m e n t ss h o wd o u b l e a r r a yh a sh i g h e ri n q u i r ye f f i c i e n c y t h a np a l1 i e e t h ep a p e rf i n a l l yp r o d u c e dt h ed a t as t o r a g em o d e lo fs e g m e n t a t i o nd i c t i o n a r y ，a n dd e e p l y a n a l y z e dt h i sm o d e lg o o da n db a dp o i n t s m a i nc h a r a c t e r i s t i co ft h em o d e li sd e v i d e dt h ed a t a i n t ot w ok i n do fd i f f e r e n tl e n g t hi n f o r m a t i o n ，l i k ei tm a yg r e a t l yr e d u c et h eo p e r a t i o no ft h e t e x tr e a d i n ga n dw r i t i n g ，c a ns p e e du pt h es e g m e n t a t i o ns p e e d t h ep a p e ra l s om a k e st h e s i m p l e a t t e m p tt o t h eq u e s t i o no ft h en o tr e g i s t e rw o r d s ，u s e dt h ep a tt r e e sd y n a m i c c h a r a c t e r i s t i ca sw e l la st h es t a t i s t i c a lm o d e lm e r i ls e a r c h e dt h ew o r df r e q u e n c yf r o mt h eb i g s c a l et e x tw h i c hi sh j i g h e rt h a nt h ec e r t a i nt h r e s h o l dv a l u e ，t h u sd i s t i n g u i s h e do n ep a r tn o t r e g i s t e rw o r d ，t h e ni nt h ep a r t i a ls o l v e dn o tr e g i s t e rw o r d sq u e s t i o n t h ep a ta l g o r i t h ma n d t h ed o u b l e a r r a ya l g o r i t h mh a sd i f f e r e n t l ym e r i t ，m a ys a t i s f yt h ed i f f e r e n tn e e d ，a l s om a y c o m b i n e t o g e t h e rt os o l v ed i c t i o n a r yi n q u i r ys p e e da n dt h ed y n a m i cs p e c i a l t yt h e s et w om o r e d i f f i c u l tq u e s t i o n s k e y w o r d ：s e g m e n t a t i o nd i c t i o n a r y ；d o u b l e - a r r a y ；p a t ；d i c t i o n a r ym e c h a n i s m 独创性说明 作者郑重声明：本硕士学位论文是我个人在导师指导下进行的研究工 作及取得研究成果。尽我所知，除了文中特别加以标注和致谢的地方外， 论文中不包含其他人已经发表或撰写的研究成果，也不包含为获得大连理 工大学或者其他单位的学位或证书所使用过的材料。与我一同工作的同志 对本研究所做的贡献均已在论文中做了明确的说明并表示了谢意。 作者签名：，菱必 日期：塑笠：坐 人连理工大学硕士学位论文 大连理工大学学位论文版权使用授权书 本学位论文作者及指导教师完全了解“大连理工大学硕士、博士学位论文版权使用 规定”，同意大连理工大学保留并向国家有关部门或机构送交学位论文的复印件和电子 版，允许论文被查阅和借阅。本人授权大连理工大学可以将本学位论文的全部或部分内 容编入有关数据库进行检索，也可采用影印、缩印或扫描等复制手段保存和汇编学位论 文。 作者签名：参哆 导师签名：叠! 垒望二 垦竺!年z 月型l 日 大连理l 一大学硕士学位论文 1 绪论 分词词典是信息处理所需的重要知识源，它以机器可读形式存储。信息处理过程中 的静态信息绝大部分来自分词词典。一部好的分词词典既要包含信息处理所需的丰富知 识f 如：词形、词性、句法、语义以及搭配信息等1 ，又要有灵活的信息组织结构及查询 效率，这些在很大程度上都影响着信息处理的结果f “。 1 1 分词词典构造的研究意义 在信息处理系统的实用化进程中，分词词典已经成为人们开发的焦点。因为信息处 理的基本信息都来自词典语言知识库。包括两大块内容，其中之一就是词典，另外一块 是语法语义等规则也叫文法，而规则也正是依据分词词典中给出的种种信息才一步步运 算出对自然语言理解的种种结果来。因此可以蜕分词词典是语言工程化的基础，没有好 的分词词典任何语言工程都无法进行。 在现代语言学理论中语言事实的描写已从语法规则转移到词库上来，即所谓的词汇 语义( 1 e x i c a l i s m ) 。随着词汇地位的提高，词典在语言信息处理中变得越来越重要，单就 汉语信息处理来说已在字词处理的基础上进一步发展到句处理阶段。要在句处理上有所 突破必须建立大规模的语言知识库，语言知识库主要包括词的语法属性，词的语义属性、 语法语义规则，其中非有语法分词词典、语义分词词典不可。随着计算机应用领域的拓 宽，知识工程的发展信息量的急剧增长，词汇资源日益引人注目。在计算语言学界越来 越多的语言学家和计算语言学工作者视分词词典建筑的规模和质量为信息处理系统 ( n a t u r a ll a n g u a g ep r o c e s s i n gs y s t e mn l p s ) 的瓶颈，把其看作是信息处理的支柱和语言 工程的基石i 。 近年来词典的研制已经成了一种专门的学问即分词词典( e l e c t r o n i c d i c t i o n a r y ) 。分词 词典是信息处理系统工程化的一个重要方面，因此国外近年来非常重视分词词典的研究 和建设，一些发达国家的政府和企业界投入了巨额资金和大量人力。 1 9 8 6 年日本提出了一个信息处理用的分词词典研究计划。这个计划的目的是实现大 型的、高水平的分词词典，以满足下一代信息处理的需要。为了实现这个目标，日本政 府投资一亿美元并成立了只本分词词典研究所( 简称e d r ) ，计划在九年时间内，开发包 括r 语和英语的十部分类词典和概念描写词典等。种类包括基本词典、术语词典、搭配 词典、概念分类词典和概念描写词典等。 欧洲共同体也资助了多项分词词典的研究课题。其中a c q u i l e x a 课题( t h e a c q u i s i t i o no fl e x i c a lk n o w l e d g e ) 的目标是通过多部机器可读词典( m r d ) 来自动获取词 姜鹏：基于双数组的分词词典研究与实现 汇知识，以便建立一个能用来支持信息处理的多语种的词汇知识库( l k b ) 。台湾中央研 究院也成立了中文词库小组，已建造汉语分词词典作为主要目标。 在大陆，七五期间北京大学研制了一个现代汉语语法信息库；八五期间北京大学有 开发了一个现代汉语语法分词词典；北京语言学院、清华大学、北京人学、河南财经学 院等单位联合研制汉语语义词典：中国人民大学林杏光等人用手工方法对汉语1 0 0 0 多 个常用动词的3 0 0 0 多个义项进豹二了研究和描述，并据此编成了动词用法大词典， 然后在此基础上与清华大学合作，共同开发了汉语述语动词分词词典。事实证明，分词 词典的建立已经成了语言信息处理工程巾的重头戏，在信息处理的分析、生成阶段都必 须与分词词典做交互p 1 。 1 2 分词词典的常用构造方法 目前建造分词词典主要有两类研究方向：第一类着眼于对现有已经总结好的语法语 义知识的运用，主要依赖于大量人工的参与来描述词条信息；另类着眼于对各种各样 大规模真实文本的分析，以获取有关的词汇信息来构建分词词典，依赖的方法主要是概 率统计及相对简单的语言模型。 在实际建造分词词典时，所采用的方法也就分别从属于这两类研究方向，这一般有 三种方法。第一种方法是在机器辅助下，主要依靠人工的输入来生成词典，其投入大量 的人力来描述词条信息，耗资巨大。典型的例子如：日本的分词词典开发计划( e d r ) ， 还有美国普林斯顿大学认知科学实验室的m i l l e r 、b e c k w i t h 等众多知名的心理语言学家 历时8 年所构造的，有名词、动词、形容词组成的带有同义、上下义、反义等语义义位 系统性信息的w o r d n e t 。第二种方法是从现有词典的印刷版本出发，将之转化为机器版 本( m r d ) ，然后从中抽取各种词汇知识建立分词词典m t d ( m a c h i n et r a c t a b l e d i c t i o n a r y ) ；第三种方法，是通过对大规模真实文本的分析，即对语料库的分析，来获 取有关词汇信息来构造分词词典。 通过分析，上述三种方法中，前两种应归属与第一个研究方向之下，因为它们主要 借助的还是语言学知识，同时依靠计算机的处理分析：而第三种方法则显然归属与第二 个研究方向。 以上三种方法各有其优缺点，从目前国内研究现状看，专家们对第一种方法着力较 多提出了，很多对词汇、短语、句子、知识的分类标准并在各自的分类标准上建立自己 的语义信息库，鉴于蚓外的经验，用这种方法建立词典周期长、耗资大，而且由丁- 语言 学家和计算语言+ 学家在语言现象的具体问题上还有许多分歧，因此在短时间内投入实际 应用的可能性不大【“。第二种方法f = = ；j 前看来是最适用的，冈为词典本身就是为提供语言 大连理工人学硕士学位论文 上的各种信息而编写的，它的释义文本经过语言学家的概括和提炼，具有一定的规律性。 可喜的是，目前国内外对由分词词典中提取信息生成机用词典的研究正在逐渐深入，并 已取得了一定的成效i ”。第三种方法的资料来源于语料库，具有一定的真实性和客观性， 但这种方法最根本的缺点在于它所使用的概率统计模型与语言知识之间缺乏直接的关 联，归根到底，数学方法的实现仍然要靠定义语言上的规则。 1 3 本文的主要工作 本文主要针对双数组结构的分词词典及其实现进行研究，主要贡献分为以下三个方 面： ( 1 1 双数组结构的词典机制 详细说明了双数组t r i e 机制的主要性能特点及制作方法，分析了算法的时阳j 空间 复杂度，为今后的应用提供了理论依据。 ( 2 ) p a t 算法及其改进 再现p a tt r e e 算法的基础上，同时给出了几种与t r i e 结构相关的词典检索方法， 通过实验，说明了这些方法优缺点及其适用范围，为今后构建基于p a tt r e e 的词典提 供了实验数据。 ( 3 ) 分词词典信息组织策略 根据信息处理系统对信息的处理要求，结合分词词典的信息查询方法，给出了分词词 典的具体信息组织方法。本文设计的分词词典信息组织方法能够加快信息的提取过程，改 善信息处理系统的整体性能。 姜鹏：基于烈数组的分词词典研究与实现 2 常用分词词典机制 词典机制考虑的是信息查询的方法。经常使用的几种基本的查询方法有：顺序查询、 二分查询、哈希查询、哈希加链表和t r i e 树方法。分词词典采用的查询机制大体上都 是使用这几种方法的不同组合来实现高效的查询。 本文所介绍的分词词典机制主要是用来进行信息处理的，因此词典的构造机制需要 满足信息处理系统的查询要求。以下部分将分别介绍信息处理用分词词典的构造机制， 并详细分析了这些机制的性能特点，为构造分词词典提供帮助。 2 1 常用的三种分词词典机制 常用的分词词典机制有：基于整词二分的词典机制、基于t r i e 索引树的词典机制 和基于逐字二分的词典机制【6 】。 针对分词系统的特点，可以将分词词典的查询操作大致分为三种基本方式： 查询方式1 ：在分词词典中查找指定词w ( i i 7 在分词词典中的定位1 ，这是一种最基 本的查询方式。给定词w 并返回它在分词词典中的位置，以便得到它的各类附属信息。 此时词条w 是确定的，可以简单地给出结果。 查询方式2 ：根据分词词典，在汉字串s 中查找从某一指定位置f 开始的最长词， 该方式( 对应最大匹配分词法) 有别于查询方式1 ，这里最长词w f 和长度无法预知，需要 在查询过程中动态地确定。通常的做法是尝试始于位置f 的所有可能长度的词，多次运 用查询方式1 来完成查询。 查询方式3 ：根据分词词典，在汉字串s 中查找从某一指定位置i 开始的所有的词 w j ，w 2 ，w i ，m a x o 寸应全切分分词法) 类似查询方式2 ，但返回结果通常不唯一。 2 ，1 1 整词二分的分词词典机制 这是一种广为使用的分词词典机制，其结构通常分为三级，前两级为索引( 见图2 1 ) 。 大连理t 大学硕十学位论文 首字散列表啊阿大鼾噗 入【：_ _ | 项指针 第一项指针 词索引衰 词典币义指 针 词典正文 l 0 0 5 0 8 97 9 4j 0 0 2 | 0 0 0 l、t | 卜 7 啊啊哈啊呀 啊哟扣唷l 阿 啊0鼾睡j ll 图2 1 整词二分的分词词典机制 f i g 2 1s e g m e n t a t i o nd i c t i o n a r ym e c h a n i s mo fe n t i r ew o r d sd i m i d i a t e n 1 首字散列表 词首字散列函数根据汉字的国标区位码给出，通过一次哈希运算即可直接定位汉字 在首字散列表中的序号。 首字散列表的一个单元包括两项内容： 入口项个数似字节) ：以该字为首字的词的个数； 第一入口项指针f 4 字节1 ：指向第一入口项在词索引表中的位置。 ( 2 ) 词索引表 因为词的长度可变( 实际系统中还包括附属于该词的各类信息1 ，故选择不定长存储 为宜，此外必须实现对词的随机访问，这两条决定了必须建立词索引表。 词索引表的一个单元仅含一项内容； 词典正文指针( 4 字节) ：指向词在词典正文中的位置。 ( 3 1 词典正文 以词为单位的有序表。通过词索引表和词典正文的配合，很容易实现指定词在词典 正文中的整词二分快速查找。 此种分词词典机制比较适合于查询方式1 ，而在查询方式2 和3 中，对任一位置f ， 通常不得不预先主观设定一个词的可能最长长度f ( 一般取词典中最长词的长度) ，然后截 取子汉字串s i ，i + 1 1 1 作为假想词，在词典中进行整词二分查找。不成功则词长f 递减 一并循环，直至匹配成功。由于一、二、三和四字词分别占词典的3 6 、6 4 0 、1 6 o 和1 4 0 ，它们覆盖了真实文本绝大部分，因此这种盲目尝试方法效率很低。 例如查询字串水怪大白天现形个多小时这个令人惊异的消息不胫而走”中从 “大”字，r 始的最跃词。 姜鹏：基于烈数组的分词词典研究j 实现 取“大”字开头的最长可能的汉字串：w 。，m a x - - - “大白天现形一个多小时这个令人 惊异的”( 词典中最长词为1 7 个汉字1 ； 用整词二分法在词典中查找候选词嘶，t n a x 失败： 去掉w 。m a x 减去最后一个字，重复步骤，失败； 经过1 4 次的错误尝试w ，m a x 最终消减到“大白天”，查找成功，于是返回w f ， m a x - - “大白天”。 21 2i r i e 索引树的分词词典机制 t r i e 索引树是一种以树的多重链表形式表示的键树1 7 】。面向英文的t r i e 索引树一 般以2 6 个字母作为关键字，树结点包含个数相同的指针。汉字接近7 0 0 0 个，如果采用 同样的策略构造中文词典，显然将造成指针的大量浪费，面向中文的t r i e 索引树的结 点应允许指针个数变化。 基于t r i e 树的分词词典由两部分组成f 见图2 2 ) ： 首字散列表 啊阿 大 鼾 入口项指针 第一项指针 关键字 子树大小 子树指针 t 大 夫， 坝 图2 ，2 基丁t r i e 索引树的分词词典机制 f i g 2 2s e g m e n t a t i o nd i c t i o n a r ym e c h a n i s mo ft r i e b a s e dt r e e 鼾 睡 人连理上大学硕士学位论文 f 1 ) 首字散列表 同基于整词二分的分词词典机制，首字散列表的一个单元是所对应汉字的t r i e 索 引树的根结点。 ( 2 ) t r i e 索引树结点 t r i e 索引树结点是以卜述结构为单元的、按关键字排序的数组：关键字( 2 字节) ， 单一汉字；子树大小f 2 字节1 ，以从根结点到当前单元的关键字组成的子串为前缀的词 的个数；子树指针( 4 字节) ，子树大小非0 时，指针指向子树，否则指向叶子。在t r i e 索引树上查询任意一个词w p ，n 1 的过程为： 根据首字散列表得到研1 】的t r i e 索引树，沿相应指针移动至目标结点n o d e x ： f = 2 ： 在n o d e x 的关键字域中对汉字研司进行二分查找。如果与n o d e x 的第f 个单 元的关键字匹配不成功，退出此过程；否则沿该单元的子树指针移至目标结点，并令该 结点为新的n o d e x ：i = i + 1 ；重复该步骤，直至n o d e x 为叶子结点； 如果抵达叶子结点时i n ，则查询成功，研j 一】为分词词典中的一个词，否则查 询失败。 与整词二分法形成鲜明对照的是，基于t r i e 索引树的分词词典机制每次只比较一 个汉字，不需预知待查询词的长度，且在对汉字串s 的一遍扫描过程中，就能得到查询 方式2 和3 的结果。这种由短词及长词的确定性工作方式避免了整词二分分词词典机制 中不必要的多次试探性查询。 由于t r i e 索引树已蕴涵了词条信息，因此词典中不必再显式地罗列词条，可直接 存储词的附属信息，叶子指针直接指向这些信息。 例如查询水怪大白天现形一个多小时这个令人惊异的消息不胫而走”中从“大”字 开始的最长词及所有词。 首先通过首字散列表得到以“大”字开头的词的t r i e 索引树结点死 由于结点r 中包含关键字“”( 表示空字符，下文同) ，因此“大”是一个词。在结点 t 中用二分法查找关键字“白”，其指针指向的目标结点设为乃； 结点乃中包含关键字“”，因此“大白”也是一个词。在结点乃中继续用二分法 找关键字“天”，此时“天”的目标结点已是叶子结点，“大白天”也是一个词，查询结束。 最后得到“大白天”为最长词，中间过程识别的“大”、“大白”和“犬白天”均为从“大”字丌 始的词。 t r i e 索引树分词词典机制的主要缺点是其构造及维护比整词二分复杂。 姜鹏：基。于双数组的分词词典研究与实现 2 1 3 逐字二分的分词词典机制 针对整词二分和t r i e 索引树的不足，这里设计了一种改进方案：基于逐字二分的 分词词典机制( 见图2 3 ) ，逐字二分与整词二分在数据结构上完伞一致，不同的仅仅在于 查i l 过程，不再将整个词作为关键字进行比较，而是类似t r i e 索引树的情形，每次仅 仅比较单个的汉字。因而其效果同t r l e 索引树完全一样。 例如查询水怪大白天现形一个多小时这个令人惊异的消息不胫而走，中从“大，字 开始的最长词及所有词。 ( 1 ) 通过首字散列表可知：以“大”字丌头的词位于索引表的第1 4 2 8 5 到1 5 0 7 8 项范 围内，并且其中的头一项“大”为一个单字词； ( 2 ) 通过二分法在第1 4 2 8 5 到1 5 0 7 8 项的范围内查找第二个字为“白”的词，可知以“大 白”丌头的词位于索引表的第1 4 2 9 2 到1 4 2 9 7 项范围内，并且其中的头一项“大白，为一 个二字诃： ( 3 ) 通过二分法在第1 4 2 9 2 至01 4 2 9 7 项的范围内查找第三个字为“天”的词，可知以“大 白天”开头的词位于索引表的第1 4 2 9 6 到1 4 2 9 7 项范围内，并且其中的头一项“大白天” 为一个三字词； ( 4 ) 通过二分法在第1 4 2 9 6 到1 4 2 9 7 项的范围内查找第四个字为“现”的词，此范围 为空，查询结束。最后得到“大白天”为最长词，中间过程识别的“大”、“大白”和t t 大白天” 均为从“大”字开始的词。 首字索引词索引表 图23 基丁逐字二分的分词词典机制 f i g 2 3s e g m e n t a t i o nd i c t i o n a r y 。fl i t e r a ld i m i d i a t em e c h a n i s m 啊 入 大案 大白 大白菜 人白话 大白鼠 大白天 大白天说梦皤 夫鲵 大连理t = 大学硕士学位论文 2 2 三种分词词典机制的实验结果 从时间和空间角度对第二节所述的分词词典机制进行了实验比较： 空削： ( 1 ) 词表( 仅含词条，不计词条所含的各类信息) 占用空间7 8 2 6 7 8 字节； ( 2 ) 首字散列表：每个单元占8 字节，共7 6 1 4 个单元( 包括一和二级汉字及某些图 形符号1 ，故首字散列表占用空间7 6 1 4 3 8 = 6 0 9 1 2 字节； ( 3 1 词索引表：每个词占4 字节，共1 1 29 6 7 个词，故索引表占空间1 1 2 9 6 7 s 4 = 4 5 1 8 6 8 字节； ( 4 ) t r i e 索引树：每个t r i e 索引树结点单元占8 字节，共含1 2 9 5 8 8 个索引项，故 t r i e 索引树占用空间1 2 9 5 8 8 ；8 = 1 0 3 6 7 0 4 字节。 基于整词二分和逐字二分的分词词典机制包括( 1 ) 、( 2 ) 和( 3 ) 项开销。而基于t r i e 索 引树的分词词典机制包括项( 2 ) 和( 4 ) 项开销。 时间： 对每种分词词典机制，均设计了四个不同类型的测试： ( 1 ) 对字典的所有词依次查询1 次( 第一类查询) ： ( 2 ) 对字典的所有词依次查询，查询次数与词频成正比( 第一类查询，模拟真实文本 环境1 ； ( 3 ) 从语料库中任意取一段测试文本，用最大匹配分词法切分该文本( 第二类查询) ； ( 4 ) 从语料库中任意取一段测试文本，用全切分分词法切分该文本( 第三类查询) 。 针对( 3 ) 和( 4 ) ，从人民日报中随机选取了长度为3 0 6 6 k 字节的文本作为测试文 本。则关于空间、时间的实验结果总汇如下： 表2 1 时间空间的比较结果 t a b 2 1c o m p a r i s o nr e s u l to ft i m ea n ds p a c e 从实验结果来看，三种分词词典机制的窄间效率差不多。而基于t r l e 索引树和逐 字分的分词词典机制的时间效率大致相同，较基1 。整词二分的词典机制均有大幅度的 改善。由于基于逐字_ 分的词典机制的实现比t r i e 树简单，所以认为就综合性能而言， 姜鹏：基于双数组的分词词典研究与实现 前者较后者更为优越。由表中可见，对最大匹配分词法和全切分分词法，基于逐字二分 的分词词典机制的处理速度较基于整词二分的处理速度分别提高了1 5 3 倍和1 6 6 倍， 效果十分显著。 通过对目前常见词典机制的比较，可以得出这三种词典机制的优缺点： f 1 1 整词二分法 结构：首字散列表、词索引表、词典正文； 优点：数据结构简单、占用空间小； 缺点：全词匹配，效率相对来说不高。 ( 2 ) t r i e 索引树法 结构：首字散列表、t r i e 索引树结点； 优点：分词中，不需预知待查询词的长度，沿树链逐字匹配； 缺点：构造和维护比较复杂，单词树枝多，浪费了一定的空间。 ( 3 ) 逐字二分法 结构：同整词二分法； 优点：查询采用逐字匹配，提高了一定的匹配效率； 缺点：由于词典结构未改变，效率的提高有限。 2 3 基于t r l e 结构的p a t 树 p a t r i c i a ( p r a c t i c a la l g o d t h mt or e t r i e v ei n f o r m a t i o nc o d e di na l p h a n u m e r i c ) 是由 m o r r i s o n r z 在1 9 6 8 年首次提出的，g o n n e t 在9 0 年代将p a t r i c i a 应用到全文查询领域， 发展成p a t t r e e 并获得很大的成功【8 】o 它是t r i e 树的一种，将在以下具体介绍该种算 法的实现方法及原理。 2 3 1tr | e 的概念及结构 t r i e 是一种搜索树，采用h a s h 结构，可以支持词的快速查询。但是该算法有很多 的变型，p a tt r e e 算法就是其中的一种。 t r i e 搜索树具有以下一些特点【9 】： ( 1 ) 从字符串的头开始顺序查询，能够找到以该头开始的全部可能的单词； ( 2 ) 输入字符串的长度是搜索速度的决定囚素； ( 3 ) 到达t r i e 的末端，如果与查嘲坩象的文字没有对应的树枝，那么就结束探索； 用图2 , 4 来表示t r i e 的存储和索引结构。 大连理工大学硕士学位论文 b a b y b a c hb a d e 图2 4t r i e 的索引和存贮结构 f i g 2 4i n d e xa n ds t o r a g es t r u c t u r eo f t r i e 该结构表明，为了存贮b a c h e l o r ，b o d y ，b a d g e ，j a r 等四个单词，t r i e 树中的每个 节点都是一个可以容纳2 6 个字母的h a s h 表结构，通过h a s h 索引可在该结构中直接查 找到要查找的字母位置。同时为了判断路径是否是一个独立的词，将t r i e 树中每个叶 子节点都置为空，表示搜索到了该词的末尾1 9 j 。 t r i e 的缺点：存储器效率差。在树的下方，大部分的节点只有少数的树枝，节点 的数据结构中只使用了其中的一部分，其他的都为空。当存储的不是字母是汉字时，该 存储方法不能满足存储的要求。 考虑到汉字的结构特点，不能采用像t r i e 一样的数据结构。采用二进制数值表示 全部的文字，那么每个节点只有2 个树枝( 对应o 和1 1 。例如字母a 、b 和c ，每个字母 用8 个二进制位来表示。则有关树枝的无用的节点能大幅度削减，不过其中仍然含有不 少的无用的节点。具体的例子如图2 5 所示： 姜鹏：基丁双数组的分词词典研究与实现 图2 5 按位索引图 f i g 2 5i n d e xp i c t u r eo fb i t 图2 5 详细说明了每个字符的二分索引结构，但是发现，有些字符如a 和b 存在相 同的前缀路径，而这些前缀路径不能对词的区分产生任何作用。只会造成该结构的节点 数目过于庞大，因此考虑是否能将相同的前缀路径去掉，而用一个数值来表示字符二进 制的第几位发生了分叉，从该处来区分不同的字符。具体做法如图2 6 所示： o 臣圃 匹囹 j e 圃 。 图26 压缩t r i e 树( p a t ) f i g 2 6c o m p r e s s e dt r i es t r u c t u r e ( p a t ) 从图2 6 可以看到，a 、b 和c 三个字符在第7 位不同，因此第7 位可以把b 、c 和a 分开，将7 写到该节点中去。字符b 和字符c 因为第8 位不同，所以在第8 位可以把这 两个字符分丌，并将分丌的位置写到节点中去。这样以米，就可以将其中的无用节点大 大减少，在实现时只需要考虑其中会产生不同字符的节点，这样的。棵t r i e 树，就把 ；查垄型三奎堂堡主堂篁堡壅 它称为压缩t r i e 树，也就是要深入探讨的帕特丽夏树( p a t r i c i at r e e ) 与2 分t r i e 树 比较，p a t r i c i at r e e 只在树枝出现分歧的地方设置节点，字符的记忆效率则大幅度提 高。各个节点，只与指定位置的比特0 、1 进行比较核对，并不与字符串进行比较核对， 在最终查询成功的时刻需要重新进行查询文字的对照，因此减少了字符串的比较次数， 大大提高了比较速度。 23 2p a t 树的数据结构 p a t r i c i a t r e e 本质上是一种压缩的_ _ _ = 叉查询树结构，它将关键词作为二进制位串 记录在树的结构中，从根结点到叶子结点的每一条路径都代表一个关键词位串。在 p a t r i c i a t r e e 中，关键词的具体信息都保存在叶子结点上，p a t r i c i a t r e e 的内部结 点则用来记录关键词的路径，它有三个基本的数据项：比较位、左指针和右指针，其中， 左指针和右指针分别指向该结点的左和右子树，比较位记录的是从根结点到达该结点的 所有位串中第一个不相同位的位置。由于比较位的存在，途经该结点的位串将选择不同 的后继路径，比较位为0 时，指针转向左子树，比较位为1 时，指针转向右子树。 p a t 树的数据结构如下所示： s t r u c tu n i t c h a r c h 【2 】； o n ec h i n e s ew o r d u n s i g n e ds h o r tc m p b i t ；c o m p a r eb i t u n i t + l p s t r ； l e f tp o i n t e r u n i t r p s t r ；| | r i g h tp o i n t e r ) 该结构单元每个共需1 2 个字节。内部节点的c m p b i t 表示要比较的位数，叶子节点 的c m p b i t 表示该词在词典中的位置，根据位置值来确定该词的附加信息。 实现过程注意的环节： 在本文中，汉语词典中关键词的位串是由其计算机内码和字符串结尾标志o ( 二进 制表示为0 0 0 0 0 0 0 0 1 构成。关键词以o 结尾，是为了避免出现某个关键词位串是另一 个关键词位串前缀的情况。图2 7 所示的是一个具有四个关键词的p a t r i c i at r e e ，其 中圆代表内部结点，圆中的数字为比较位，方框代表叶子结点。 姜鹏：基于烈数组的分词词典研究与实现 内部节点， 关键词l ： 位串1 ：1 1 关键例2 ： 位串2 ：1 1 关键侧3 ： 位串3 ：1 0 关键词4 ： 位串4 ：1 0 ( a ) 关键词 幽2 7p a t r i c i at r e e 数据结构 f i g 2 7d a t as t r u c t u r eo fp a t r i c l a t r e e 在图2 7 中，第2 位是所有关键词位串的第一个不同位，因此根结点的比较位为2 ， 第2 位为零的关键词3 ，关键词4 便转向根结点的左子树，而关健词1 ，关键词2 便转 向右子树。由于关键词3 ，关键词4 在第1 7 位不同，在左子树的根结点中比较位为1 7 ， 同样，关键词1 ，关键词2 在第5 位不同，在右子树的根结点中比较位就为5 。 由于引人了比较位，避免了对关键词的逐位比较，保证了p a t r i c i at r e e 中每一个 内部结点都有左、右两棵子树，所以，p a t r i c i at r e e 为满二叉树。这也就表明，当 p a t r i c i at r e e 中存有n 个关键词即n 个叶子结点时，其内部结点为，1 1 个，总结点数 为2 ，l 一1 ，所以p a t r i c i a 的空间复杂度为o 伽) 。 2 3 3p a t 树的查询及性能分析 确定词条查询： 判断查询词是否存在于词典中，只须从p a t r i c i a t r e e 的根结点出发，根据查询词 位串f 包括结尾处的0 1 在p a t r i c i at r e e 中寻找路径。 ( 1 ) 若比较完所有位后，查询词的位串不能到达叶子结点，则可以断定该查询词不 在词典中。 ( 2 ) 在查询词的位串到达叶子结点时，由于只对查询词中某几位进行了比较，并不 能保证查询词与叶子结点中的关键词一定是相同的，在这种情况下，还要对两者进行一 次字符串的比较。 例如在图2 7 的p a t r i c i at r e e 中查询“金子”。 ( 1 ) 形成查询词“金子0 ”的位串s 。 “1 0 1 1 1 1 0 1 1 1 1 1 0 0 0 0 1 1 0 1 0 1 1 1 1 1 0 1 0 0 1 1 0 0 0 0 0 0 0 0 ” f 2 1 根据位串s ，在p a t r i c i at r e e 中寻找路径。 火连理工大学硕十学位论文 因为s 的第二位为0 ，则从根结点到达其左子树的根结点，此时比较位为1 7 ，s 的 第1 7 位为1 ，下一步就到达叶子结点“金属0 ”。 f 3 1 比较查询词与叶子结点。 由于字串“金子o ”与“金属o ”不等，町断定“金子”不在词典中。 最长词条查询和前缀词条查询： 在进行讨论之前，需要先分析一下诸如“中”、“中华”和“中华人民共和国”等存在前 缀关系的词条在p a t r i c i at r e e 中位置关系。由于彼此存在相同的位申，它们在 p a t r i c i at r e e 的路径有一部分是相重的。由于每个关键词在存人p a t r i c i at r e e 时都 后添了一个结尾字符0 ，这些路径将在o 的第一位处出现分叉，其比较位为1 6 * n + l ( 每 个汉字有1 6 位) ，盯为自然数。如果将其中最长词条的路径称为主干，则其它较短词条出 现在比较位为1 6 * n + l 的分枝上，如图2 8 所示： 图2 8 存在前缀词条的词在p a t 树中的关系 f i g 2 8r e l a t i o n s h i po fe q u a lp r e f i xw o r d si np a t t r e e 利用p a t r i c l at r e e 做最长词条查询，方法与确定词条查询类似，都是根据输人位 串，从p a t r i c i a t r e e 的根结点开始在树中寻找路径。但在寻径的同时，需要记录下比 较位为1 6 * n + l 的内部结点n o d e f ，当路径到达主于的叶子结点n o d e n 时，由内部结点 n o d e j ，n o d e 2 一，n o d e “所辖的最左叶子结点与n o d e 。就构成了所谓的“路径记录表”。“路 径记录表”记录的是出现在主干的前后分枝上的、具有前缀关系的关键词，所以“路径记 录表”自然是以词长为序的，短词在前，长词在后。同时也可以得出结论：路径记录表 实际上就是自口缀词条查询和最长词条查询的结果候选集，一旦与输人匹配的最长词条被 确定，这两种查询就同时完成了【9 j 。所以