（计算机应用技术专业论文）基于语境的汉语自动分词技术研究及实验分析.pdf

匠春工业大学硕 ：学位论文 摘要 当代科技革命的主要特征，是以计算机为支持手段进行信息处理。随着计算机的 广泛应用，计算机已由过去的数据处理、信息处理发展到现在的知识处理，对语言文 字的信息处理。而语言是人类最重要的交际工具，是信息最主要的负荷者。在我国， 将计算机应用于事务处理、办公自动化、印刷排版、情报检索、机器翻译、人机对话 等方面，都离不开中文，因为所有这些方面的信息，都是以中文作为其载体的，因而 语言文字的信息处理成为我国信息化建设的“瓶颈”。 中文信息处理技术是重要的计算机应用技术，它已渗透到计算机应用的各个领域， 如计算机网络、数据库技术、软件工程等。国务院制定的国家中长期科技发展纲领中 明确指出：“中文信息处理技术是高新技术发展的重点”。我国软件产业发展的重点是 中文信息处理软件，中文信息处理的发展已经得到国家的重视。 自然语言处理是人工智能的重要分支。词是自然语言处理系统中重要的知识载体 与基本操作单元。在书面汉语中词与词之白j 没有明显的切分标志。于是在中文信息处 理中汉语自动分词这一研究领域应运而生，并成为中文信息处理中的基础课题。 书面汉语自动分词是中文信息处理中的重要步骤，它是文本校对、机器翻译、文 本分类、文本检索、计算机人机接口等诸多中文信息应用领域的基础。通过对自动分 词技术的深入研究，开发出高质量，多功能的分词系统，必将促进中文信息处理系统 更加广泛的应用。 汉语自动分词是汉语信息处理的前提，是目前中文信息处理中的难点之一，它也 是中文自然语言理解、机器翻译中最基本的一步。而汉语自动分词的难点在于对歧义 字段的切分。这主要是因为汉语自动分词的划分往往存在着歧义性，需用到一定的语 境知识，需要在一定的语境上下文参照下确定它的真实含义，而语境上下文的利用反 过来又依赖于一个个切分好的词，这样就有一个分词与语境相互依赖的关系。 为了进一步提高汉语自动分词的准确性，本文通过分析汉语特点，提出了基于语 境的汉语自动分词方法。通过改进的最大分词算法来对中文进行初切分，然后对于有 歧义切分句子进行消歧处理，运用词的语境知识，也就是上下文信息来处理，同时对 未登录词也进行了相应的处理。这样，分词不仅考虑了汉语的词法知识，还考虑到了 汉语分词过程中词所在的语境知识，即上下文信息，进而提高分词的准确率。 关键词：自动分词语境最大分词 k 春工业大学硕上学位论文 a b s t r a c t a tp r e s e n t , t h ep r i n c i p a lc h a r a c t e r i s t i co fs c i e n t i f i ca n dt e c h n o l o g i c a lr e v o l u t i o ni st o p r o c e s si n f o r m a t i o nw i t hc o m p u t e r w i t ht h eg e n e r a lu s eo fc o m p u t e r , i th a sd e v e l o p e df r o m t h ed a t ah a n d l i n ga n dt h ei n f o r m a t i o np r o c e s s i n gt o k n o w l e d g et r e a t m e n t h o w e v e r , l a n g u a g ei st h em o s ti m p o r t a n tc o m m u n i c a t o nt o o lo fh u m a nb e i n ga n dt h ep r i m a r yc a r r i e r o fi n f o r m a t i o n i no u rc o u n t r y , t h ec o m p u t e rw a sa p p l y e dt ot h ea f f a i rt r e a t m e n t ，o f f i c e a u t o m a t i o n ，p r i n t i n gl a yo u t ，i n t e l l i g e n c er e t r i e v a l ，m a c h i n et r a n s l a t i o n ，a n dm a n m a c h i n e c o n v e r s a t i o na n ds oo n a l lo ft h e mc o u l d n td ow e l lw i t h o u tc h i n e s ep r o c e s s i n g b e c a u s e a l lt h e s ei n f o r m a t i o nf i r es t o r e di nc h i n e s e ，t h ec h i n e s ei n f o r m a t i o np r o c e s s i n gb e c o m e st h e “b o u l e n e c k ”o f i n f o r m a t i o nc o n s t r u c t i o ni n0 1 1 1 c o u n t r y t h ec h i n e s ei n f o r m a t i o np r o c e s s i n gt e c h n o l o g yi sa ni m p o r t a n tc o m p u t e ra p p l i c a t i o n t e c h n i q u e ，i ta l r e a d ys e e p st h r o u g he a c hf i e l d so fc o m p u t e ra p p l i c a t i o n s ，s u c h 嬲c o m p u t e r n e t w o r ld a t a b a s et e c h n o l o g y , s o f t w a r ee n g i n e e r i n ge t e t h el o n gr a n g es c i e n c ea n d t e c h n o l o g yd e v e l o p i n gc o u n c i lo ft h es t a t em a d eb yt h es t a t ed e p a r t m e n tp o i n t so u t ：“t h e c h i n e s ei n f o r m a t i o np r o c e s s i n gi se m p h a s i si nt h eh i g ha n dn e wt e c h n o l o g yd e v e l o p i n g f i e l d t h ep r i m a r yt a s ko fs o f t w a r ei nd e m o s t i ci sc h i n e s ei n f o r m a t i o np r o c e s s i n g ，w h i c h h a sa l r e a d yg o to u rc o u n t r y sr e c o g n i t i o n n a t u r a ll a n g u a g ep r o c e s s i n gi sa ni m p o r t a n tb r a n c ho fa r t i f i c i a li n t e l l i g e n c e i nt h e 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 m ，w o r di st h ei m p o r t a n tk n o w l e d g ec a r t i e ra n db a s i c o p e r a t i o nc e l l b e t w e e nw o r da n dt h en e x tt oi t ，t h e r ei sn oo b v i o u ss y n c o p a t i n gs i g n s oa sa b a s i c p r o b l e mi n t h ec h i n e s ei n f o r m a t i o np r o c e s s i n g ，t h ec h i n e s ea u t o m a t i cw o r d s s e g m e n t a t i o nh a sb e c o m eah o ts p o t t h ec h i n e s ea u t o m a t i cw o r d ss e g m e n t a t i o ni sa ni m p o r t a n ts t e pi nt h ec h i n e s e i n f o r m a t i o np r o c e s s i n g i ti st h eb a s i so ft e x tp r o o f r e a d e r , m a c h i n et r a n s l a t i o n ，t e x tc l a s s i f i e s ， t e x tr e t r i e v a l ，c o m p u t e rm a n m a c h i n ei n t e r f a c ea n de t c b yd e e p l yr e s e a r c h i n gi nc h i n e s e a u t o m a t i cw o r d ss e g m e n t a t i o n ，w ec a l ld e v e l o p eam u l t i f u n c t i o n a lw o r d ss e g m e n t a t i o n s y s t e mw i t hh i g hq u a l i t y , w h i c hw i l lc e r t a i n l yc o n t r i b u t et od e v e l o p m e n to ft h ec h i n e s e i n f o r m a t i o np r o c e s s i n gs y s t e m t h ec h i n e s ea u t o m a t i cw o r d ss e g m e n t a t i o ni sap r e r e q u i s i t ef o rc h i n e s ei n f o r m a t i o n p r o c e s s i n g i ti sa l s oo n eo ft h ed i f f i c u l tp o i n t sa n dt h em o s tf u n d a m e n t a ls t e pi nn a t u r a l l a n g u a g ep r o c e s s i n ga n dm a c h i n et r a n s l a t i o n t h ed i f f i c u l tp o i n to fc h i n e s ea u t o m a t i cw o r d s s e g m e n t a t i o nl i e si nc u t t i n go f fd i f f e r e n tm e a n i n g ss y l l a b l e t h ep r i m a r yr e a s o n sa r et h a t c h i n e s ea u t o m a t i cw o r d ss e g m e n t a t i o nh a sm a i n l yd i f f e r e n tm e a n i n g s ，a n dn e e d s a r r i v i n ga t 长春工业大学硕l 学位论文 c e r t a i nc o n t e x tk n o w l e d g e ，e n s u r et h et r u em e a n i n gw i t ht h ec e r t a i nc o n t e x t ，b u tc o n t e x t u a l m a k i n gu s eo fc o n t e x ti sd e p e n d e n to ne v e r yw o r df i n i s h e ds e g m e n t a t i o n , t h i sw a ya b o u t p a r t i c i p l ea n dt h ec o n t e x ti si n t e r d e p e n d e n ts o m e t h i n gt od of i g h ta w a y i no r d e rt oi m p r o v et h ea c c u r a c yr a t eo ft h ec h i n e s ea u t o m a t i cw o r d ss e g m e n t a t i o n , w e p u tf o r w a r dac h i n e s ea u t o m a t i cw o r d ss e g m e n t a t i o nm e t h o db a s e do nl a n g u a g es i t u a t i o n a f t e ra n a l y z i n gt h ec h i n e s ec h a r a c t e r i s t i c a tf i r s tw ed i v i d es e n t e n c et ow o r d sw i t ht h e i m p r o v e dm a x i m u ms e g m e n t a t i o na l g o r i t h m ，t h e ns e n t e n c e sw i t hd i f f e r e n tm e a n i n g sw a s p r o c e s s e dw i t hd i s a m b i g u a t i n ga l g o r i t h m i tm e a n st h a tw ep r o c e s s i n gt h es e n t e n c e sw i t h d e f f e r e n tm e a n i n g sb a s e do nl a n g u a g es i t u a t i o n i no r d e rt oi m p r o v et h ea c c u r a t er a t eo f c h i n e s ea u t o m a t i cw o r d ss e g m e n t a t i o n , t h ep a r t i c i p l eh a sn o to n l yc o n s i d e r e dc h i n e s e m o r p h o l o g yk n o w l e d g e ，b u ta l s oc o n s i d e r e dc o n t e x tk n o w l e d g ei n t h es e g m e n t a t i o n p r o c e s s i n g ，w h i c hi sn a m e dl a n g u a g es i t u a t i o n k e yw o r d s ：a u t o m a t i cw o r d ss e g m e n t a t i o n ；l a n g u a g es i t u a t i o n ；m a x i m u mp a r t i c i p l e 长春工业大学顾l 学位论文 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进行研究工作 所取得的成果。除文中已经注明引用的内容外，本论文不含任何其他个人或集体已经 发表或撰写过的作品或成果。对本文的研究做出重要贡献的个人和集体，均已在文中 以明确方式标明。本声明的法律结果由本人承担。 论文作者签名：量k 永闵1 日期：2 d 口7 年多月多7e t 氏春工业大学硕上学位论文 第一章绪论 1 1 问题的提出 自然语言处理是当前计算机领域的一个研究热点。语言作为交流工具，在人类活 动中有着举足轻重的作用，因此，人们在大量应用计算机来替代自己工作的同时，也 期待计算机在自然语言的处理上能接近甚至达到人的水平。自然语言处理( n l p ) 的目 标是使计算机在各种各样的自然语言交流中成为流利的对象。显然，如果没有足够深 刻的领域知识，计算机不可能满足人类的要求。 汉语自动分词是中文信息处理中的重要环节。汉语是以字而不是词作为语言的基 本构造单位，尤其是在书面汉语中，词与词之间完全缺乏形态上的界限。自然语言理 解是语言处理的最终目标，而汉语分词处于词法、句法、语义等语言层次的最低层， 是中文信息处理中最基本也是很重要的基础环节。 掘统计，在信息领域中8 0 以上的信息是以语言文字为载体的。这些语言信息的 自动输入和输出，文本的校勘和分类，信息的提取和检索以及语言翻译等语言工程， 都是国民经济和国防信息化建设的重要基础。中文信息处理涵盖了字词、短语、句子、 篇章等多层面的信息加工处理任务。 由于中文文本是按句连写的，词间无间隙，因而在中文文本处理中，首先遇到的 问题是词的切分问题。按句连写转换成按词连写，词的正确切分是进行中文文本处理 的必要条件。在八十年代中期，自动分词技术就受到重视，陆续有各种分词模型和软 件提出。近年来，随着国民经济信息化的不断发展以及i n t e m e t 的普及应用，在中文信 息处理的广泛应用中，迫切要求实现汉语词典和语料库等中文信息的共享和复用，对 自动分词技术的要求也越来越高。在信息产业需求的强大动力推动下，自动分词已经 引起多方面的关注，成为中文信息处理的一个前沿课题。 1 2 汉语自动分词国内外研究现状 汉语自动分词算法的研究最早可追溯到上世纪5 0 年代后期的俄汉机器翻译时期， 大约在1 9 6 0 年左右，苏联学者首先提出了“6 5 4 3 2 1 ”的正向最大匹配分词方法， 它的基本思想是先取一句话的前六个字查字典，若不是一个词，则删除六个字中的最 后一个，然后再查字典，这样一直查找下去直到找到一个词为止，对句子剩余部分重 复此工作，直到把所有词切分出来为止。这种方法中的匹配思想成为后来许多分词方 法的基础。反向最大匹配法和正向最大匹配法思想一样，不同之处在于它从句子的最 后六个字开始切分，每次匹配不成功时，去掉汉字串最前面的一个字。梁南元首次将 这个方法大规模应用到汉语自动分词系统c d w s 中i i i c d w s 是我国第一个实用性的 自动分词系统，是北京航空航天大学计算机科学与工程系于1 9 8 3 年设计的。它采用最 长春工业人学硕i ：学位论文 大匹配( m m ) 的机械分词方法，辅助以词尾字构词检错技术，使用知识库进行纠错。 c d w s 的分词精度约为i 6 2 6 。 揭春雨提出了机械匹配分词方法的形式化描述模型，讨论了基于字符串的机械匹 配分词算法的结构( 最大匹配和最小匹配，正向扫描和反向扫描，增字匹配和减字匹配) 及其时间复杂度等问题，并指出最大匹配法较为实用【2 l 。 从最大匹配法出发导出了“双向最大匹配法”，即f m m + r m m 。s u nm s 和 b e n j a m i nk t 注意到：汉语文本中9 0 0 左右的句子，f m m 和r m m 的切分完全重合 且正确，9 0 左右的句子f m m 和r m m 切分不同，但其中必有一个是正确的( 歧义检 测成功) ，只有不到1 o 的句子，或者f m m 和r m m 的切分虽重合却是错的，或者 f m m 和r m m 切分不同但两个都不对( 歧义检测失败) 1 3 】。这正是双向最大匹配法在实 用中文信息处理系统中得以广泛使用的原因所在。 吴胜远分析了最大匹配法、最小匹配法、逐词遍历法、最佳匹配法，并提出基于 最大匹配的单扫描分词方法，该方法的时间复杂度为2 8 9 ，比当时分词方法的时间复 杂度1 2 3 2 小很多【4 】。黄德根、朱和合等提出了一种基于最长次长匹配的汉语自动分词 算法i5 1 。陈桂林、王永成等介绍了一种高效的中文电子词典数据结构，该词典支持首字 h a s h 和标准的二分查找，且不限词条长度。然后提出一种改进的快速分词算法，该算 法在快速匹配词典查找二字词的基础上，利用近邻法匹配方法来查找多字词，明显提 高了分词效率【6 】。李振星等通过对汉字编码体系、汉语词特点的分析，提出了一种新的 词典结构，该词典支持首字h a s h 和完全二分查找，并在此基础上，提出了全二分最大 匹配快速分词算法，有效地提高了分词速度f 7 j 。这些方法都是基于词典匹配来实现自动 分词的。 人工智能和专家系统的迅速发展，使得许多人工智能领域的计算手段应用到书面 汉语的自动分词中来，如：专家系统法、神经网络法、有限状态自动机法、隐m a r k o v 模型法、b r i l i 式转换法等。这些新的探索体现了自动分词研究的不同侧面，在一定范 围内取得了各自的成效。 为克服知识规则和人工智能方法的弊端，研究人员将概率统计方法应用到书面汉 语自动分词中，该方法是建立一个自动分词的统计模型，获取模型的各种参数，然后 从各种可能的词串中挑选概率最高的词串作为输出结果。 通过不断的实践，汉语自动分词的发展经历了一个由浅入深，由简单到复杂的演 变过程，其中最大匹配法和最大概率法是最基本的两种自动分词算法，而基于词典的 最大匹配分词算法因开发周期较短，程序实现较为容易，在实际应用领域中常常被用 来预处理分词，然后再利用统计方法切分歧义和识别未登录词。 1 3 本文研究的目的和意义 近几年，网上信息爆炸式地增氏，其内容也千变万化。如何从海量信息中有效地 2 k 春工业人学硕上学位论文 提取有用信息，这是迫切要解决的问题。文本挖掘抽取有用、可理解的、散布在文本 文件中的有价值知识，需要一定的自然语言处理能力，因此对自然语言处理的深入研 究，将有助于文本挖掘效率的提高，进而推动网页信息提取技术的发展。 自然语言处理是人工智能的重要分支。词是自然语言处理系统中重要的知识载体 与基本操作单元。在书面汉语中词与词之间没有明显的切分标志。于是在中文信息处 理中汉语自动分词这一研究领域应运而生，并成为中文信息处理中的基础课题。 近年来，随着计算机技术的发展，基于统计的自然语言处理已成为计算语言学学 科中一个研究热点。随着对自然语言理解的深入研究，出现了一门新的学科一计算语 言学。计算语言学的任务就是利用统计的方法对真实的自然语言进行处理，以获取自 然语言的各种有用信息，最终达到理解自然语言的目的。然而，随着科技的发展，计 算机从速度、容量方面都有大幅度提高，计算机程序和软件的不断丌发应用加快了语 料库的建设，使随机语料可以大量得到。计算机软件和硬件的发展使得统计方法在切 分和词性标注等领域获得了极大的成功，随之出现的基于统计方法的语料库技术也成 为当今研究的热点。所谓语料库就是含有自然语言各种语言事实和规律的大规模真实 文本。语料库研究机器可读的自然语言文本的采集、存储、检索、统计、分词、词性 标注、语法标注、句法一语义分析等。 然而，汉语自动分词仅仅是中文信息处理任务的手段，并不是最终目标。因此， 应该更加关注自动分词在汉语分析与理解、机器翻译、中文文献自动标引、中文信息 检索、汉字识别、汉语语音识别与合成、中文简繁体自动转换及文本处理和中文文稿 自动校对等领域中的广泛应用。 1 4 本文研究内容 汉语词语的划分往往存在着歧义性，需要在一定的语境上下文参照下才能确定， 而语境上下文的利用反过来又依赖于一个切分好的词，这样就有一个分词与语境相互 依存的问题。本文是基于词典的分词方法和统计的方法相结合，即采用词典方法中的 最大匹配方法和统计方法中的互信息、极大似然原则m l p 法，三者相结合。同时将词 语所在上下文中的语境信息应用到分词当中，提高分词的准确率。 长春工业人学硕r j 二学位论文 第二章汉语自动分词基本模型和性能评价体系 2 1 汉语自动分词的基本模型 2 1 1 分词的形式模型 首先，我们给出几个汉语分词中用到的定义： ( 1 ) 一个汉字是一个符号。设全体汉字组成的集合为； ( 2 ) 对于确定正整数n ，且a 1 ，a 2 ，a f l ，将按顺序构成的符号串 w = a l a 2 a l l ，称w 为上的一个汉字串； ( 3 ) d 是一个己知的确定的w 的有限集，对于任意元素w e d ，w 都是汉语中的一 个词，称d 为词典； ( 4 ) 对于任意m n ，w l ，w 2 ，w m ed ，将按顺序构成的符号串w l w 2 w m 成 为d 上的一个词串。 根据以上定义，汉语自动分词就是在词典d 指导下，由一个普通的汉字串a l a 2 a l l 到词串w l w 2 w m 的归约问题。 对于句子s = a l a 2 a n 若存在两个或两个以上不同的归约式，即s = w 1 w 2 w m 词 串是不唯一的，则称s 存在关于词典d 的歧义归约。 下面以一个例子来说明分词的归约过程。 假设有= a l ，a 2 ，a 3 ，a 4 d = w i ，w 2 ，w 3 ，w 4 ，w 5 ，w 6 ，其中： w 1 = a l a 2 a 3 w 2 = a 2 a 3 a 4 w 3 = a l a 2 w 4 = a 3 a l w 5 = a i w 6 = a 2 可以用一个状态图来表示词典d ： 图2 1 词典的状态图 设s = a l a 2 a 3 a 4 ，以最大匹配法为例演示一次归约的过程。从s 0 丌始沿a 1 a 2 a 3 春t 业大学硕上学位论文 匹配得到w l ，s = w l a 4 ：由于不存在路径“，只有从w i 回溯到w 3 ，s = w 3 a 3 a 4 ： 此时，a 1 a 4 路径不存在，继续由w 3 回溯到w 5 ，s = w 5 a 2 a 3 a 4 ；现在，可以沿路 径a 2 a 3 a 4 匹配得到w 2 ，故最后的归约式为s = w 5 w 2 ，归约结束。整个过程如图2 2 所示 图2 2 最人匹配法规约过程 带回溯的最大匹配法，每次遇到归约死结时只进行一步回溯。可以看出，这种方 法的归约结果是唯一的。实际上，由于汉语本身的特点，汉语切分是存在歧义的。 2 1 2 汉语自动分词的基本算法 汉语自动分词基本算法，也叫初切分算法。从目前能得到的结果看，汉语自动分 词的算法数量不下几十种，但归结起来，汉语自动分词方法大致可以分为三类：基于 词典和规则的方法，基于统计的方法以及基于统计和规则相结合的方法。 1 基于规则的分词方法 基于词典和规则的方法以词条匹配为基础，以经验建立的规则库为标准，完成歧 义消除和切分结果的确定。最长次长匹配法口】采用的就是基于规则的分词方法，将可能 出现的歧义字段收集起来，形成一个交集型歧义字段库，根据所建立的歧义字段库信 息来处理切分歧义。在消除交集型歧义字段时，遵循如下优先顺序： ( 1 ) 个性规则处理。与句法分析阶段复杂的规则系统相比，分词阶段的个性规则比 较简单。对于用语法搭配规则( 也称共性规则) 无法解决的歧义字段词，根据其左右特 定的单词分布情况，建立相应的歧义消除规则。进行歧义处理时，先扫描个性规则库， 如果歧义字段的相邻单词满足其个性规则中的条件，则按规则所标记的路径进行切分。 如果个性规则库中没有满足条件的规则，则转下述语法搭配规则。 ( 2 ) 词法搭配规则。主要有：动词十名词( v + n 型) 、形容词+ 名词( a + n 型) 、动词+ 代词( v + t 型) 、动词十量词( v + q 型) 、介词十名词( p + n 型) 。如“一只白天鹅”中的“白 天鹅”，有2 种切分：“白天鹅”和“白天鹅”，其中，“白天鹅”为“a + n ”类型， 而“白天鹅”不属于上述搭配规则，因此选择路径“白天鹅”。 k 春工业人学硕j ：学位论文 ( 3 ) 选择最长匹配。若上述2 条规则均无法消除切分歧义，则选择最长词。 组合型歧义字段的处理需要利用语义知识和上下文信息，两个简单的语法语义知 识如下： ( 1 ) 数词+ 量词组合优先，解决了类似“一个人”的组合歧义。 ( 2 ) 介词+ 名词组合优先，解决了类似“把手举起来”的组合歧义。 基于规则的方法遇到了很多困难，主要原因是语言现象过于庞杂，存在许多特殊 的语言现象，现有的方法理论和语言规则无法有效地表达所有语言现象，从而严重影 响了这些系统对开放语料的适应性1 8 】。而且，我们最终的目的是面向大规模真实文本的 自然语言处理，规则方法适应性方面的缺陷更加凸现出来。 规则方法的优点是： 1 ) 需要的语言资源少，程序实现简单，开发周期短。 2 ) 对自然语言的表达比较深入，具有较强的概括性，表达的知识容易理解。 3 ) 受限领域应用效果较好，对于某些特殊的歧义组合，可以通过对语境中的词语 及特征信息的深入细致的描述，获得很好的排歧效果。 规则方法的缺点是： 1 ) 一致性不好。由于自然语言本身的复杂性，在构建规则库的过程中不可避免地 会出现一些错误，难以保证规则的一致性。 2 ) 鲁棒性较差。基于规则的系统对于规则描述以外的语句无法处理，面向大规模 真实文本处理时，可能会产生错误的结果。 3 ) 处理歧义的能力差。 2 基于统计的分词方法 基于统计的方法的核心是通过某种途径得到能够反映语言特征的统计数据，并以 此作为切分的评价。一般的基于统计的分词模型的评价函数，都是根据贝叶斯公式， 同时结合系统本身的资源限制，经过一定的简化近似得来的。 设s l ，s 2 ，s k 是s 的所有可能切分，我们分词的目的就是在s l ，s 2 s k 中找到一 个t ，使得s 。满足： p ( s js ) = m a x p ( s , is ) ，p ( s 2s ) ，p ( s ks ) 即寻找估计概率值最大的词串。根据贝叶斯公式，有： p ( s 。is ) ：p ( s , ) p ( s i s o ( 2 1 ) p 【s ) 对于s 的多种切分方案，p ( s ) 是一常数，而p ( s l s i ) 是在给定词串的条件下出现字串 的概率，故p ( s i s i ) = i 。所以，我们用p ( s i ) 来代替p ( s i s ) 。 最直接的估计p ( s i ) 的方法是利用词的n - g r a m 。在处理一个词串时计算第j 个词的 边界，往往要考虑前j 一1 个词的出现情况。如果认为第j 个词的出现只与紧接着的第j 个词的前面的很少的n 1 个( n = 1 ) 个词有关，则问题就大大简化了。这样的模型称为n 6 长春工业人学硕j 二学位论文 元语法( n g r a m ) 模型，实际上是一个马尔可夫过程。常用的有一元语法( u n i g r a m ) ( n = i ) 模型、二元语法( b i g r a m ) ( n = 2 ) 模型和三元语法( t r i g r a m ) ( n = 3 ) 模型。 这样，每一个词出现的概率不再与前面的全部历史有关，而只与前面n 1 个最近 的词有关，句子的概率改为： m p ( s i ) = i p ( w j lw j n “w j 一2 w j 1 ) ( 2 2 ) i 由于n g r a m 的统计数据量是指数增长的，考虑到汉语的特点以及现有的硬件资源， 目前，普遍采用基于2 元语法模型，最高有基于三元语法模型1 9 j 的分词。 基于统计的分词方法存在的一个问题是缺乏对语言内部的深入理解，导致正确率 受到极大的限制。另一个问题是模型要求大规模语料库和人工标注工作量过大的矛盾。 解决第一个问题的方法是引入部分规则机制来弥补对语言理解的不足，也就是规则和 统计相结合的汉语自动分词；解决第二个问题可通过引入开放学习机制，不断修正统 计数据，弥补语料统计数据的局限性。 统计方法有下列优点： 1 ) 提供了数学理论基础，并提供了消歧的方式。 2 ) 运用大规模语料库更容易，大规模语料库能提供足够的实例模型化知识。 3 ) 如果训练的语料足够大，能更客观反映语言学中的规律。 4 ) 一致性好。 5 ) 统计方法处理自然语言的健壮性好，能够覆盖的范围较大。 统计方法的缺点： 1 ) 对自然语言的处理和表示比较肤浅。 2 ) 需要大规模的标注语料库。 3 ) 表达的知识难理解。 3 统计和规则相结合的分词算法 统计方法和规则方法各有优缺点。规则方法不够灵活，但可以很好的处理特例情 况( 特例可以以规则形式确定下来) 。统计方法易于实现，比较灵活，但是对特例情况 却无能为力。因此，人们丌始尝试改进传统的汉语分词，用统计出的这些规律指导汉 语分词，即把规则方法和统计方法结合起来进行汉语自动分词。 在规则和统计结合的方法中，首先运用基于规则的方法作一种初步切分，再对切 分的边界处进行歧义探测，发现歧义，然后用统计方法对歧义部分进行处理，对统计 不能解决的或难以确定的( 两个结果的概率非常接近) ，再利用规则进行处理。它结合 了统计和规则方法的优点。 目前这种方法可以解决汉语中最常见的歧义类型：单字交集型歧义。并对人名、 地名、机构名、后缀、动词、形容词重叠、衍生词等词法结构进行识别的处理，基本 解决了分词所面临的最关键问题。如果使用优秀的词典结构和算法设计，分词速度非 长春工业大学硕l j 学位论文 常快。缺点是不能解决其它类型的交集型歧义和组合型歧义。 2 1 3 影响分词系统的几个主要因素 对于汉语自动分词系统，影响分词系统效果的因素有很多。目前来看，主要的因 素包括词典的完备性、切分盲点的避免、分词知识的组织、学习机制等等。 词典的完备性是针对语料而言，完备性词典保证对切分范围内所有的语料都可切 分：完全性词典是针对词而言，完全性词典包含所有可能出现的词。显然，构建完备 性词典比完全性词典更实际一些，汉语构词的难预期性决定了完全性词典构造的难度 较大。但如果在专有名词、离合词、外来语等方面做出更多的努力，可以得到接近于 完全性的完备性词典，从而大大减少词典造成的错误切分。 切分算法是汉语分词领域中研究的一个核心也是热点问题。最大匹配法、最小匹 配法等只能产生唯一的切分结果，是存在大量切分盲点的切分算法：而全切分算法给 出一个汉语句子的所有可能的切分方式，即任何匹配词典中词的字串都被加入到全切 分结果集合当中。在词典确定的情况下，全切分是避免出现切分盲点最好的切分算法。 例如，对于“中国人民”，全切分算法得到的结果为： 中国人民 中国人民 渖融 k 民| 邙国k 民| 中国人民 博悟 k 民 而最长匹配法得到的切分结果为确定的。中国人民”。 汉语自动分词系统至少应包括以下几个方面的知识，即词典知识、规则知识和管 理知识。其中： ( 1 ) 词典知识主要指存放在词典中的内容，它包括汉语中的词、词性及其它特 征如单复数和及物性等。词典本身结构方面的知识。 ( 2 ) 规则知识它包括两类规则，一类是单纯的字符串匹配规则，另一类是指利 用汉语中词法、句法、语义和语用等方面知识进行分词的规则。在基于统计的分词中， 各种统计数据可以归为此类知识。 ( 3 ) 管理知识主要指系统维护方面的知识，诸如对规则和词典中内容添加、修 改及删除等操作所包括的知识。 汉语自动分词知识的组织对汉语自动分词方法的切分速度、精度都有一定的影响， 并且分词知识的组织形式与系统的维护难易程度密切相关【1 0 l 。 自然语言理解本身就与人工智能有密切的关系，因此学习机制也对分词系统有很 重要的影响。由于汉语言。的特点，我们还很难做到完全的机器自主学习，还必须在人 8 长春工业大学硕】。学位论文 工的干预下，进行有导师的学习。我们应该认识到，即使是从一个较小规模的人工分 词语料库中学习得到的数据也一般会比从大规模语料库中通过非监督学习而获得的数 据要准确。但是，非监督的学习因为其自动化的性质同样具有很重要的价值。 2 2 汉语自动分词的性能评价 汉语自动分词系统的总目标是建立一个开放的，具有较高通用性和实用性的现代 书面汉语自动分词系统。汉语自动分词是一项重要的任务，许多实际的语言技术应用， 如机器翻译和信息检索，都需要将中文文本划分成为一些词的序列，使用词作为基本 的处理单元，所以一个好的分词器是非常重要的。但拥有一个好的分词器是很困难的， 完美地对一个句子进行分词几乎是不可能的。事实上，分词的歧义判断和未登录词识 别是困难的，为了找到最优的适合中文信息处理实际应用的分词方法，我们需要对现 有的分词系统的性能进行评估。评价一个分词系统的性能优劣主要看两个方面：分词 精度和分词速度。 分词精度也称分词正确率，是分词系统性能的核心指标。分词系统的正确率只有 达到9 9 9 以上才能基本满足上层使用的需要。 1 分词j 下确率： 口= 鬻枷。 亿。， 2 识别未登录词准确率： 口：雩罂掣塑擎塑婺l o o ( 2 4 ) 系统识别为未登录词数 。 3 识别未登录词的召回率： y ：型掣磐塑掣1 0 0 ( 2 5 ) 72 甬丽琛蚕荪酉州 喵w 分词速度是分词系统性能的另外一个重要指标。影响分词速度的主要因素是分词 词典的组织结构。分词词典的查询速度依赖于词典的组织结构。由于自动分词需要的 各类知识都要从分词词典中获取，系统在进行分词处理时需要频繁查询分词词典，分 词词典的查询速度将直接影响分词系统的速度。 在不同的应用中，对分词系统性能的要求侧重点各有不同。例如：在机器翻译中， 对分词精度的要求非常高( 9 9 以上) ，对分词速度则要求一般。而在搜索引擎中，对 分词的速度则要求很高，分词的精度只要一般就可以了。 此外，自动分词系统还应具有易扩充性、可维护性和可移植性；能支持不同地区、 不同应用领域的不同应用目标；词表和处理功能、处理方式上能灵活组合装卸，从而 提高系统处理精度和处理速度；还有，要建造一个同信息处理用现代汉语分词规范 相配合的常用或通用现代汉语分词词表。 9 k 春工业大学硕j ：学位论文 第三章分词设计思想 3 1 词典机制 高效的分词词典机制是自动分词算法的基础。国内自上世纪8 0 年代中后期就开始 了中文电子词典的研制，文献】给出了三种典型的分词词典机制： ( 1 ) 基于整词二分的分词词典机制，该机制的词典结构分为词典正文、词索引表、 首字敞列表等三级。词典正文是以词为单位的有序表，词索引表是指向词典正文中每 个词的指针表。通过首字散列表的哈希定位和词索引表很容易确定指定词在词典正文 中的可能位置范围，进而在词典正文中通过整词二分进行定位。 ( 2 ) 基于t r i e 索引树i 幢j 的分词词典机制，t r i e 索引树是一种以树的多重链表形式 表示的键树。基于t r i e 索引树的分词词典机制由首字散列表和t r i e 索引树结点两部 分组成。t r i e 索引树的优点是在对被切分语句的一次扫描过程中，不需预先知道待查 询词的长度，沿着树链逐字匹配即可：缺点是它的构造和维护比较复杂，而且都是单 词树枝( 一条树枝仅代表一个词) ，浪费了一定的空间。 ( 3 ) 基于逐字二分的分词词典机制，这种词典机制是前两种机制的一种改进方案。 逐字二分与整词二分的词典结构完全一样，只是查询过程有所区别：逐字二分吸收了 t r i e 索引树的查询优势，即采用的是“逐字匹配”，而不是整词二分的“全词匹配”， 这就一定程度地提高了匹配的效率。但由于采用的仍是整词二分的词典数据结构，使 效率的提高受到很大的局限。文献【l3 】在前述三种分词词典的基础上，根据汉语中双字 词语较多的特点提出了一种新的分词词典机制双字哈希机制，双字哈希词典机制 根据汉语中双字词语较多的特点，词典采用前两字逐个哈希索引、剩余字串有序排列 的结构，查询过程采用逐字匹配的方法，提高了中文分词的速度。但词典规模较大时， 查询效率并没有得到最大限度的提高。 分析和比较以上四种词典机制，我们得到如表3 1 所示的结论： 表3 1 现有词典机制比较 词典机制优点缺点 基丁整词_ 二分的分词数据结构简单、1 1 i f l j 空间小，由丁采j j 全匹f l d f l ；j 布询过程， 词典机制词典构建及维护简单易行 冈而卉洵效率低f 基丁：t r i e 索引树的采的查洵过榉是“逐字匹数据结构复杂、空间浪费较为 分词词典机制配”，所以夯询效率较高严重，树的构造和维护也较为 繁琐 基丁| 逐字二分的分词词典机采i j 的卉洵过枰是“逐字匹没有改进“锆词_ 二分”的数据 制配”，一定拌度地提高了匹配结构，使效率的提高受到很大 的效率的局限 双字哈希分词词典机制采川“双字哈希”和“逐字匹词典规模较人时，夯咖效率爿。 配”，一定拌度地提高了中文没有得到较人的提高 分词的速度 i o 长春1 = 业人学硎l 学位论文 中文信息处理的各个领域对汉语自动分词的速度提出了越来越高的要求，而分词 词典的查询速度直接影响到分词系统的速度，因此分词词典必须满足快速查询的要求。 3 2 分词词典的设计 本文所设计的汉语自动分词算法是基于词典的分词方法。分词词典是汉语自动分 词系统的一个基本组成部分，自动分词系统的各类信息都要从分词词典中获取。基于 词典的分词作为分词技术的主流，其分词精度依赖于词典的精度和歧义的有效切分， 而分词速度则取决于所设计的词典结构。在对汉字编码体系和本文所设计算法要求的 基础上，提出一种分词词典机制首字h a s h 索引分词词典机制。这种