（模式识别与智能系统专业论文）基于词平面的现代汉语高效分词方法研究.pdf

中国科学技术大学硕士学位论文中文摘要 摘要 汉语分词是中文信息处理的一项基础性研究课题，其重要性不言而喻。虽然 汉语分词相关研究已有2 0 多年，但仍有一部分问题没有得到解决，这也是研究 人员至今仍然对该课题进行研究的原因。 目前汉语分词的困惑主要是：l 、分词算法要么切分速度快，而正确率较低， 如最大匹配法；2 、要么切分正确率较高，而切分速度较慢。针对这个两难的问 题本文给出了一个基于词平面的一体化切词算法，该方法有效提高了分词的速 度，同时保证切分词语的准确率。同时该算法还提出了特定领域支撑系统的方法， 有效解决了农业等特定领域词汇切分出错的问题。 基于词平面的一体化切词算法对分词速度的改进主要在三个方面。这三个方 面分别为：词典结构、切词算法、最短路径搜索算法。区别于以往的分词词典结 构，本研究提出了双数组t r i e 的汉语词典结构，该结构有效提高了一元和二元 词典的检索效率，同时降低词典的空间复杂度。在切词算法上，本研究提出了基 于局部歧义词网格的切词算法，该算法可以有效过滤掉切分过程中的“碎词”， 这样降低了后续最短路径计算的工作量。在最短路径搜索上，区别于以往采用的 d i j k s t r a 最短路径搜索算法，本研究采用了基于斐波那契堆的最短路径搜索算法。 关于本研究所提的每部分都有相关对比实验，通过这些对比实验来验证本文 所提方法的有效性。最后本研究提出了一些需要进一步深入研究的方向。 关键字：词典结构、切词算法、词网格、特定领域、最短路径 中国科学技术大学硕士学位论文 英文摘要 a b s t r a c t c h i n e s ew o r ds e g m e n t a t i o ni sab a s i cr e s e a r c hp r o j e c to fc 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 t si m p o r t a n e ei ss e l f - e v i d e n t a l t h o u g ht h ec h i n e s ew o r ds e g m e n t a t i o n r e s e a r c ho v e t2 0y e a r s ，b u tt h e r ea r es t i l ls o m ei s s n e 皓h a v en o tb e e nr e s o l v e d , t h i s r e s e a r c hi ss m lc o n d u c t e do nt h er e a s o n a tp r e s e n t , t h em a i np u z z l e so fc h i n e s ew o r ds e g m e n t a t i o na r c 1 ，s e g m e n t a t i o n a l g o r i t h m se i t h e rc u ts p e e d l y , b u ta c c u r a c yr a t el o w e ，s u c ha st h em a x i m u mm a t c h i n g m e t h o d ；2 ，o rs e g m e n t a t i o nc o r r e c tr a t ei sh i g h , b u tc u ts l o w l y i nt h ep e r p o t oc r a c k t h i s r e a ld i l e m m a , t h i sp a p e rg i v e saw o r df i a tb a s e di n t e g r a t e ds e g m e n t a t i o n a l g o r i t h m ，t h em e t h o de f f e c t i v e l yi m p r o v e st h es p e e do f t h ew o r ds e g m e n t a t i o n , w h i l e g u a r a n t i n gt h ew o r ds e g m e n t a t i o na c c u r a c y m e a n w h i l e ，t h i sa l g o r i t h mh a sas p e c i f i c a r e as u p p o r t i n gs y s t e m ，w h i c he f f e c t i v e l ya d d r e s s e st h e s p e c i f i c a r e a s sw o r d s e g m e n t a t i o ne 1 t o l t h ew o r df l a tb a s e di n t e g r a t e ds e g m e n t a t i o na l g o r i t h mi m p r o v e sc h i n e s ew o r d s e g e m e n t a t i o n ss p e e di nt h r e em a j o ra s p e c t s t h e s et h r e ea s p e c t sa r e ：d i c t i o n a r y s t r u c t u r e ，s e g m e n t a t i o na l g o r i t h m , s h o r t e s tp a t ha l g o r i t h m d i f f e r e n tw i mp r e v i o u s d i c t i o n a r ys t n l g t u r e s ，t h ep a p e rg i v e sac h i n e s ed o u b l ea r r a yt i l es t r u c t u r e ，w h i c h i m p r o v e st h er e t r i e v a ls p e e do fu n i g r a ma n db i _ g r a m , w h i l er e d u c i n gt h ed i c t i o n a r y s p a c ec o m p l e x i t y i nt h es e g m e n t a t i o na l g o r i t h m , t h i sp a p e rg i v e sal o c a la m b i g u o u s w o r d sg r i ds e g m e n t a t i o na l g o r i t h m , t h i s a l g o r i t h mc a ne f f e c t i v e l yf i l t e rt h e s e g m e n t a t i o ng e n e m t e d ”b r o k e nw o r d s ”。a n dt h i sr e d u c e st h ef o l l o w i n gs h o r t e s tp a t h s c o m p u t a t i o nw o r k l o a d s e a r c ht h es h o r t e s tp a t h , d i f f e r e n tf r o mt h ep r e v i o u sd i j k s t r a s s h o r t e s tp a t ha l g o r i t h m t h i sp a p e rg i v e sad i j k s t r aa l g o r i t h mw h i c hb a s e do nt h e f i b o n a e c ih e a p e v e r yr e s e a r c hp a r tm e n t i o n e dh a ss o m er e l a t e de x p e r i m e n t s t h r o u g ht h e s e e x p e r i m e n t st ov a l i d a t et h ee f f e c t i v e n e s so ft h ep r o p o s e dm e t h o d f i n a l l y ，w ep r o p o s e an u m b e ro ff i e l d sn e e d e df o rf l l r t h e ri n - d e p t hr e s e a r c h k e yw o r d s ：d i c t i o n a r ys t r u c t u r e ；s e g m e n t a t i o na l g o r i t h m ；w o r dg r i d ；s p e c i f i c f i e l d s ；s h o e s tp a t h i i 中国科学技术大学硕士学位论文 第一章绪论 本章主要回顾了汉语分词发展的历史，同时介绍了汉语分词发展过程中所涉 及的各种分词相关的切词算法。通过介绍这些切词算法后，进一步介绍了汉语分 词发展过程中由国内科研单位所开发的若干分词系统。在以上这些回顾和分析工 作的基础上，得出目前汉语分词主要的问题是切词速度较慢，无法满足大规模的 中文信息处理的应用需求，同时在切分特定领域词汇时易出错。基于这两个迫切 需要解决的问题，本章在最后部分给出本论文的章节安排。 1 1 分词发展的历史 近几十年来，中国社会信息化发展迅速，其突出表征是i n t e r n e t 上中文网页 的急剧增加和中文电子出版物、中文数字图书馆的迅速普及，中文自然语言处理 研究也得到了迅速发展。汉语分词是任何中文自然语言处理系统都难以回避的第 一道基本“工序”，其重要性不言而喻。自动分词在很多现实应用领域( 中文文 本的自动检索、过滤、分类及摘要，中文文本的自动校对。汉外机器翻译，汉字 识别与汉语语音识别的后处理，汉语语音合成，以句子为单位的汉字键盘输入， 汉字简繁体转换等) 中都扮演着极为重要的角色u j 。 汉语自动分词的相关研究始于2 0 世纪8 0 年代初，迄今已有2 0 多年的发展 历史。研究出了很多各具特色的方法，从简单的模式匹配机械分词方法、基于规 则的方法t 2 - 4 1 、基于理解的方法、到基于统计的方法t 5 - i o 。 1 1 1 基于模式匹配的分词方法 基于模式匹配的方法可分为：正向最大匹配法( f m m ) 、逆向最大匹配法 ( r m m ) 。 1 1 1 1 正向最大匹配方法( f m m ) 该方法的基本思想是：假设自动分词词典中的最长词条所含汉字个数为i ， 则取被处理材料当前字符串序数中的1 个字作为匹配字段，查找分词词典。若词 典中有这样的一个i 字词，则匹配成功，匹配字段作为一个词被切分出来；如果 词典中找不到这样的一个i 字词，则匹配失败。匹配字段去掉最后一个汉字，剩 下的字符作为新的匹配字段，进行新的匹配，如此进行下去，直至切分成功为止。 中国科学技术大学硕士学位论文 绪论 亦即完成一轮匹配切分出一个词，然后按上面的步骤进行下去，直到切分出所有 的词为止。 例如短语“计算机科学和工程”，假设词典中最长的词为7 字，则先取“计 算机科学和工”为匹配字段，查找分词词典以匹配这个字段。由于词典中没有该 词，故匹配失败。去掉最后一个汉字成为“计算机科学和”作为新的匹配字段， 查找分词词典以匹配这个字段，同样匹配失败。再取“计算机科学”作为新的匹 配字段进行查找，假定词典中有“计算机科学”这词，则匹配成功，切分出第 一个词“计算机科学”。用同样的方法还可以切分出第二、第三个词。 根据梁南元的统计，f m m 方法的错误切分率为1 1 6 9 。目前，f m m 方法虽 然作为一种基本的方法已被确定下来，但是由于它的错误切分率比较大，故一般 不单独使用，而是与其他方法配合使用。如对“结合成分子时”使用f m m 切分 结果为“结合成分，子时”，出现了切分错误。 1 1 1 2 逆向最大匹配方法( b m m ) 与f m m 方法相对应的方法是b m m 。它的分词过程与f m m 方法相同，不 过它是从句子( 或文章) 的末尾开始处理，每次匹配不成功时去掉的是最前面的 一个汉字。b m m 方法的精度要高一些，她的切分错误率为1 2 4 5 。 例如“计算机科学和工程”，首先取“计算机科学和工程”作为匹配字段来 查找分词词典，由于词典中没有该词，故匹配失败。去掉最前面的一个汉字，即 “算机科学和工程”作为新的匹配字段进行查找，同样匹配失败，如此进行下去， 最后取“工程”作为匹配字段来查找分词词典，由于分词词典中有“工程”一词， 则匹配成功，切分出一个词“工程”。 但是使用b m m 切分“结合成分子时”时，也出现了切分错误，其切分结果 为“结合成分子时”。因此，目前b m m 方法虽然也作为一种基本被确定下来， 但是很少被单独使用。 基于模式匹配的分词方法在一定程度上模拟了人工分词的心理过程。根据心 理语言学的研究，人脑里也存有一部词典，虽然每个人大脑里的内部词典各不相 同，但是使用同一种语言的人，他们的内部词典应该是有很大共性的。人工分词 时，碰到一个汉字串也必然要去查自己的内部词典，只不过一般情况下这个查询 速度非常快，人们不怎么觉得有一个查词典的过程。但是碰到疑难时，我们就会 有些踌躇，这就清楚地说明人工分词时也确实是一个查词典的过程。我们说基于 模式匹配的分词方法在一定程度上模拟了人工分词的心理过程，是因为人工分词 时，还调用了除词形、词长以外的语言学知识，这些知识的使用，在基于模式匹 中国科学技术大学硕士学位论文 配的分词方法中没有得到反映。 1 1 2 基于规则的分词方法 基于规则的分词方法主要是在分词的过程中加入词法规则、语法规则甚至语 义规则来提高分词的质量：基于规则的方法，一般都是人工添加规则，或者在人 工添加的基础上再从有限的训练语料库中得到分词规则，而对于在词典中添加分 词规则主要是人工添加完成。人工添加的最大缺陷就是人本身作用的影响太大， 具体表现在：( 1 ) 人所能想到的规则一般不可能是很完善的，或多或少地会遗漏； ( 2 ) 这些规则也或多或少地依赖于各个人，不同的人添加规则时对规则的认识与 理解也是不一样的。 同时随着时间的推移和语言的不断演化原有的规则的可能不再适用，这就需 要语言学家重新制定规则。而且基于规则的分词方法需要语言学家和计算机科研 人员的紧密配合，因此开发一个基于规则的分词系统需要大量的人力和物力。同 时随着语言学家制定规则的增多，原来规则库中已有的规则可能和现在的规则之 间产生冲突。因此目前基于规则的分词方法虽然作为一个基本的分词方法被确定 了下来，但一般不单独使用。 1 1 3 基于理解的分词方法 通常的分析系统，都力图在分词阶段消除所有歧义切分现象。而有些系统则 在后续过程中来处理歧义切分问题，其分词过程只是整个语言理解过程的一小部 分。其基本思想就是在分词的同时进行句法、语义分析，利用句法信息和语义信 息来处理歧义现象。它通常包括三个部分：分词子系统、句法语义子系统、总控 部分。在总控部分的协调下，分词子系统可以获得有关词、句子等的句法和语义 信息来对分词歧义进行判断，即它模拟了人对句子的理解过程。这种分词方法需 要使用大量的语言知识和信息。由于汉语语言知识的笼统、复杂性，难以将各种 语言信息组织成机器可直接读取的形式，因此目前基于理解的分词系统还处在试 验阶段。 。 1 1 4 基于统计的分词方法 该方法通常需要一个加工好的热语语料库做为系统的原始统计数据的支撑。 利用该熟语语料库，我们可以在其基础上，通过分析该语料库中的文本串，从其 中抽取出所有的词，及这些词的出现频率信息，该词及词频数据的集合即为统计 中国科学技术大学硕士学位论文 语言模型中常有的一元语言模型：同时利用该熟语语料库，我们还可从中抽取出 所有的两个词组合的短语及该短语出现的频率信息，该短语及频率信息即为统计 语言模型中的二元语言模型。 基于统计的分词方法一般使用该一元语言模型作为词典信息，二元语言模型 用于消除切分歧义。首先使用一元语言模型和字符串匹配法，对一个待分词的句 子进行分析，从中找出该句子包含的所有可能的词，并利用这些词构成一个网格， 该网格可能包含一个句子多种可能的切分方式，具体确定为何种切分方式需要使 用一元语言模型和二元语言模型的统计信息，利用这些统计信息和平滑算法，即 可以确定出该该词网最优的路径，该路径包含的词即为句子最终的切分结果。 从上面分析过程可以看到基于统计的分词方法完全依赖于一个加工好了( 即 人工分好词) 的语料，所有的统计信息也是以该语料为基础抽取出来的。所以统 计的分词方法与语料有密切的关系。一般而言语料规模越大，语料越平衡切分效 果越好。目前分词研究使用的语料基本是：由北京大学计算语言研究所和日本富 士通公司联合开发并公布的人民日报1 9 9 8 年1 月份的语料。 1 2 现有的分词系统【1 1 】 自8 0 年代初中文信息处理领域提出了自动分词以来，一些实用性的分词系 统逐步得以开发，下面是这二十多年的发展过程中，其中几个比较有代表性的自 动分词系统。 1 2 1c d w s 分词系统 该分词系统是我国第一个实用的自动分词系统，由北京航空航天大学计算机 系于1 9 8 3 年设计实现，它采用的自动分词方法为最大匹配法，辅助以词尾字构 词纠错技术。其分词速度为5 1 0 字，秒，切分精度约为1 6 2 5 ，基本满足了词频 统计和其他一些应用的需要。这是汉语自动分词实践的首次尝试，具有很大的启 发作用和理论意义。例如，它比较科学地阐明了汉语中的歧义切分字段的类别、 特征以及基本的对策。 1 2 2 清华大学s e g t a g 系统 此系统着眼于将各种各类的信息进行综合，以便最大限度地利用这些信息提 高切分精度。系统使用有向图来集成各种各样的信息，这些信息包括切分标志、 预切分模式、其他切分单位。为了实现有限的全切分，系统对词典中的每一个重 4 中国科学技术大学硕士学位论文 绪论 要的词都加上了切分标志，即标志“c k t 或”q k i 。“q k l i 标志表示该词可进行绝对切 分，不必理会它是否产生切分歧义；”c k ”标志表示该词有组合歧义，系统将对 其进行全切分，即保留其所有可能的切分方式。系统通过这两种标志并使用几条 规则以实现有限的全切分，限制过多的切分和没有必要的搜索。规则包括： 1 、无条件切出q k 类词： 2 、完全切分c k 类词( 保留所有可能子串) ； 3 、对没有标记( q k 或c k ) 的词，若它与别的词之间存在交叉歧义，则作全切 分：否则将其切出。 为了获得切分结果，系统采用在有向图d a g 上搜索最佳路径的方法，使用 一个评价函数e v a l u a t e ( p a t h ) ，求此评价函数的极大值而获得最佳路径p m a x 。 所运用的搜索算法有两种，”动态规划”和”全切分搜索+ 叶子评价”，使用了词频、 词类频度、词类共现频度等统计信息。通过实验，该系统的切分精度基本上可达 到9 7 左右，能够处理未登录词比较密集的文本，切分速度约为3 0 字，秒。 1 2 3 哈工大统计分词系统 该系统是一种典型的运用统计方法的纯切词系统，它试图将串频统计和词匹 配结合起来。 系统由三个部分构成： 一、预处理模块，利用显式和隐式的切分标记( 标点符号、数字、a s c i i 字 符以及出现频率高、构词能力差的单字词、数词+ 单字常用量词模式) 将待分析 的文本切分成短的汉字串，这大大地减少了需要统计的( 无效) 字串的数量和高 频单字或量词边界串； 二、串频统计模块，此模块计算备个已分开的短汉字串中所有长度大于1 的 子串在局部上下文中出现的次数，并根据串频和串长对每个这样的子串进行加 权，加权函数为( f 为串频，l 为串长，即串中汉字个数) 。根据经验，局部上 下文中取为2 0 0 字左右。局部上下文的串频计算使用一个滑动窗口( 为一个队列 式缓冲区，保存当前待切分汉字串及其前后2 0 个短串) ，当当前待切分汉字串处 理完之后，窗口下移一个短串( 中心变为相邻下一个短串) 。系统采用一个外散 列表来记录窗口中的短串，以加快窗口中串频计数。教列函数取为汉字的g b 8 0 位码( - - 级汉字共用入口9 5 ) ，每个桶中保存窗口中每一行( 短串) 上的汉字位 置：( 短串的行号，汉字列号) ，并且对于在窗口中出现多次的汉字位置用一个链 指针连接起来，则计算某个字串在窗口中出现的频度时，不必将该字串与窗口中 的短串逐个匹配，而只需统计在该字串中的各个汉字所对应的位置链表中能够相 邻的位置的序列的个数即可。此外，还需要根据词缀集( 前、后缀集合) 对字串 5 中国科学技术大学硕士学位论文 的权值进行提升，例如”处理器”中”处理”的权值很高，但由于对”处理器”的权值 作了提升( 达到或超过了”处理”) ，就不会切成”处理器”。如果某个汉字串的权 值超过某一阈值d ( 取为4 0 ) ，则将此汉字串作为一个新识别的词，将其存入一 临时词库中； 三、切分模块，首先用临时词库对每个短的汉字串进行切分，使用的是逐词 遍历算法，再利用一个小型的常用词词典对汉字短串中未切分的子串进行正向最 大匹配分词。对于短汉字串中那些仍未切分的子串，则将所有相邻单字作为一个 权值很低的生词( 例如”玛”、”莉”) 。其中每个模块都对待分析的文本进行了一 次扫描，因而是三遍扫描方法。此系统能够利用上下文识别大部分生词，解决一 部分切分歧义，但是统计分词方法对常用词识别精度差的固有缺点仍然存在( 例 如切出”由来”、”语用”、”对联”等) 。经测试，此系统的分词错误率为1 5 ， 速度为2 3 6 字秒。 1 2 4i c t c l a s 分词系统 该分词系统有北京计算所开发，系统使用了基于统计的分词方法，很好地解 决了切分歧义问题。该系统整体采用了基于层叠隐马尔科夫的结构，系统采用了 两个核心词典( 一个一元词典和一个二元词典) ，实际分词过程首先使用一元词 典进行字符串匹配，得到一个句子的包含的所有可能词：然后采用二元词典进行 切分歧义的消歧处理。通过国家9 7 3 专家组于2 0 0 2 7 月份组织的测评，测评结 果显示该系统分词正确率为9 7 5 8 ，分词速度为3 1 5 k b ，s 。 1 3 目前还存在的问题 尽管分词研究已经开展了2 0 多年，取得了很多地成绩，并且在分词正确率 上得到了很大的提高：但分词速度却随着分词系统的切分正确率的提高而极大地 降低了，因此看来分词问题始终是没有能够得到最终解决的问题。这也是人们长 期围绕其开展研究的原因。本课题提出了一种“基于词平面的现代汉语高效分词 算法”，该算法的目标是：在不影响分词系统切分正确率的情况下，极大地提高 分词系统的切分速度，这样来达到高效分词的目的。 然而，目前的基于统计的汉语分词方法的时间复杂度都过高，切分速度还不 够理想，如对机助翻译和语音识别等对实时性要求较高的应用系统来说，响应速 度较慢。汉语分词系统的切分速度主要受以下几个方面的影响： 1 、汉语分词系统的切分速度与词典结构有很大关系。要切分出汉语句子所 有可能的词串，首先必须查词典。所以词典的结构对分词速度有着重要的影响。 6 中国科学技术大学硕士学位论文 国内外不少研究学者曾对此做过深入的研究，并提出了许多的方法。如基于首字 哈希的二分查找的词典结构等。以基于首字哈希的二分查找的词典结构为例，该 词典结构的优点是每个词的第一个字通过哈希函数直接定位其在词典中的位置， 缺点是词的后续字串需通过二分查找实现，而且查找词的过程存在冗余查找的缺 点。因此看来基于首字哈希的二分查找的词典结构在词条检索所需的时间复杂度 上明显过高。因此研究高效的词典结构，是本研究的重要内容之一。 2 、汉语分词系统的切分速度与分词方法也有很大关系，同时分词方法对分 词系统的最终切分正确率也有很大的影响。目前使用的方法基本可以分为：最大 匹配法、逆向最大匹配法、双向扫描法、最少分词法、全切分分词法等。其中最 大匹配法、逆向最大匹配法和双向扫描法无法完全解决所有的交集型歧义问题， 同时还会造成所有的组合型歧义，所以目前一般不单独使用这三类方法；最少分 词法虽然可以减少一部分的交集型歧义问题，但是对组合型歧义切分字段也无能 为力，所以目前也没有得到单独的应用。全切分分词法可以切出所有的交集型和 组合型歧义切分字段，但由于其切分过程中引入了很多碎词，为后续的概率计算 加重了运算的时间复杂度。因此，寻求一种合适的方法，来保证切分正确率的同 时解决切分速度，是我们需要重点研究的问题。 3 、汉语分词系统的切分速度与切分生成的词网格所包含的词条数，也即词 网格的顶点数有很大关系。针对该问题，目前未见研究学者有相关研究。汉语分 词系统的切分速度与切分生成的词网格主要在两个方面存在关系：、词网格包 含的词条数越多，需要查找n g r a m 词典的次数越多! 通过分析可知：当一个词 条自身或与前后语境不构成歧义切分时，查找n g r a m 词典是完全没有必要的， 因为查找n g r a m 词典的目的就是排歧。因此看来如果不加分析地对词网格中的 每个词条都去查找一遍n g r a m 词典，将导致严重的时间浪费。、词网格包含 的备选词条数越多，词网格顶点数也就越多，进而导致的结果是计算该词网格的 最短路径时，计算复杂度的提升。但问题的关键是词网格的最短路径的确定只和 歧义切分字段发生处的路径有很大关系。因此看来如果不加分析地将整个词网格 看成一个图来计算其最短路径，将导致严重的时间浪费。从上面分析可以看出， 如果能将这两个问题处理好，将极大地提升汉语分词的切分速度同时不影响其切 分正确率。 4 、汉语分词系统的切分速度与最终分词结果的确定算法有很大关系。最终 分词结果的确定问题在基于统计的分词系统中就是一个确定最优分词路径问题。 确定最优分词路径问题可以归为两个问题：查找n 元概率；从所有的可能 的分词路径找出最优路径。对于第一个问题，即查找n 元概率问题，现有的分 词系统中n 元词典和一元词典分开存储。因此使用目前的n 元词典来查找n 元 中国科学技术大学硕士学位论文 绪论 短语的概率时，时间复杂度基本和第一次进行词切分时的时间复杂同样大小，这 样就多了一步查找历史短语的时间，也就是增加了时间消耗。对于第二个问题， 即从所有的可能的分词系统路径找出最优路径问题，基本采用的都是d i j k s t m 算 法，该算法的时间复杂度为0 【俨+ d ，( 矿代表句子的备选单词数) ，当一个句子 包含的单词数较多的时候，矿2 将远大于矿。矿2 级别的时间消耗非常高。从以上 两个方面可见，目前采用的方法所需的时间复杂度都是比较高的。 5 、现有的分词系统遇到一些特定领域词时会出现切分错误，而且这些领域 词汇的切分错误还可能导致与其关联的词的切分错误的出现。这两个方面的原因 会最终导致切分正确率的下降。 1 4 本文所做的工作及研究目的 本研究将针对上述五个方面的问题，在处理汉语高效分词问题所涉及的词典 结构、切词方法、词网格、路径搜索、特定领域词汇切分等几个主要技术方面做 进一步研究。以解决词检索、碎词过滤、歧义分析、最短路径、特定领域词汇问 题，达到在保证切分正确率的情况下提高现有分词系统切分速度的目的。 因此本文针对上述几个问题共分为如下几章： 第一章绪论：本章主要回顾了目前使用的一些分词方法，及各方法的优缺 点，并回顾了一些分词系统的特点。通过回顾，指出了目前分词方法存在的一些 问题，同时将这些问题细化为五个方面； 第二章分词统计理论：本章主要介绍基于统计的分词方法所用的统计理论，及 这些理论的实现方法； 第三章分词系统词典结构：本章主要分析了几种主要的词典结构的优缺点，同 时介绍了本文所采用的词典结构，相对现有词典结构的优点； 第四章分词切词相关算法：本章主要分析了基于统计的分词方法所涉及的相关 切词算法，同时分析了本文所采用的算法的优点： 第五章分词系统结构和对比实验：本章主要介绍了分词系统结构。同时进行了 相关的对比实验分析，通过实验结果实际证明本研究开发的分词系统高效性： 第六章总结和展望：本章主要对全文所做工作的总结，同时也对以后汉语分词 进一步研究进行了探索。 1 5 本章小结 本章主要分析了目前分词领域常用的一些分词方法，及国内比较有影响的一 些分词系统。同时分析了这些方法和系统的优点，及其中的不足之处。针对这些 不足之处给出本文的研究重点，并将这些研究内容分章节地安排到各个章节中。 8 中国科学技术大学硕士学位论文 分词统计理论 第二章分词统计理论 本章主要介绍汉语分词领域中涉及到的相关的统计理论知识，同时介绍了汉 语分词中常用的处理数据稀疏问题的平滑算法。最后介绍了汉语分词中词典模型 即一元语言模型和二元语言模型的训练方法。 2 1 分词常用统计方法 概率统计论为很多领域发现真理提供了最直接的研究手段。当我们发现某一 事件在大量的重复试验的情况下，发生概率较高时，我们可以说该事件发生的可 能性较大，反之我们则说，该事件发生的可能性较小；如果在该重复试验中，某 一事件从来没有发生过，我们可近似地认为该事件不太可能发生，当一个事件没 有发生的可能时，我们称该事件为“不可能事件”；当某一事件在该重复试验中， 一定发生时，我们称该事件为“必然事件”。 借用概率统计论的这些知识，我们可将其成功地应用于分词领域。如在“我 们去吃饭”这一句话中，通过统计，我们可以说“我们”这个词发生的频率较高， 而“们去”发生的频率较低或为零。利用这些知识我们就可以在分词的时候从句 子中切分出“我们”这个词，而不会切分出“们去”这个词来。 下面是一些统计自然语言处理中常涉及到的三个概率统计方法。 2 1 1 最大似然估计 一般把“通过观察一个事件发生的频率，然后使用该频率来估计其发生概率” 的方法，叫做最大似然估计( m a x i m u ml i k e l i h o o de s t i m a t e ) 。 最大似然估计定义：若事件a 在相同的条件下进行的n 次实验中出现了r 次，则称 ( 彳) ：一r ( 2 1 ) n 为事件a 在n 次试验中的最大似然估计，称r 为事件a 在n 次试验中出现的频 数( f f e q u e n c e ) 。 最大似然估计一般用于估计一个语料库中，每一个词的概率。通过观察每个 词的频率，然后用该频率近似替代该词的发生概率。 因此通过上面的分析和公式( 2 1 ) ，我们很容易发现，在数据稀疏的情况下， 对事件的估计往往会出现如下情况： ( 1 ) 对于未观察到的事件，估计过低( 概率为零) 。如自然语言处理中常要 9 中国科学技术大学硕士学位论文 分词统计理论 涉及到的语料库规模较小的情况下，用最大似然估计方法来估计一些词的概率可 能会出现不符合该词真正的发生概率的情况。如当某一词在该语料库中从来没有 发生过时，使用最大似然估计必然导致对该词概率的估计为零，然而真实情况是 该词在别的语料库中是有可能存在的，只不过当前语料中由于数据稀疏，导致该 词未出现； ( 2 ) 对于观察到的事件，估计也不完全正确( 概率过高或过低) 。我们还举 上面的语料库的例子，当某一词发生次数与真实发生的次数相比偏低时，使用最 大似然估计就会导致对该词概率估计过低；反之当某一词发生次数与真实发生的 次数相比偏高时，使用最大似然估计就会导致对该词的估计过高。 因此使用最大似然法时，一般都会结合平滑算法。这样对事件的概率估计会 更加合理。 2 1 2 条件概率 在实际问题中，除了要知道事件4 的概率p ( 4 ) 外，往往还要知道在事件口出 现条件下事件出现的概率，称这种概率为事件口出现条件下事件彳的条件概率 ( c o n d i t i o n a lp r o b a b i l i t y ) ，记为e ( a i 动。当预钡0 一个事件的出现时，如果已经 具备一些关于该事件的信息或者知识，就可以使用条件概率来反映这种情况。不 考虑先决条件( 信息或者知识) 而得到的该事件的概率，通常称为该事件的先验 概率( p r i o rp r o b a b i l i t y ) 。在具备该事件出现的信息或者知识的条件下，得到的该 事件的概率，通常称为该事件的后验概率( p o s t e r i o rp r o b a b i l i t y 。 在事件b 已知的出现的条件下，事件a 出现的条件概率记为e ( a lb ) ，由下 式计算： 尸( 4b ) ：p ( a c = 、一8 ) ( 2 - 2 ) ，【占) 上式中，当b = q 时，p 似nq ) = e ( a ) ，p ( f 2 ) = i ，于是，p ( a l 蛹= p ( a ) ， 也即条件概率转换为无条件概率。可见，可以把一般概率看作是必然事件出现条 件下的条件概率。 条件概率在汉语分词的统计语言模型中有非常重要的应用。当一个句子的前 几个词已知时，可用于确定在历史词的基础上，当前备选词的概率。这里举一个 简单的例子，如句子“中国人民”，如果我们已经知道了“中国”，根据该历史词， 我们可以得到在其基础上，词“人”和“人民”的概率，分别可用条件概率表示 为：p ( 人l 中国) 和p ( 人民1 中国) 。该条件概率即统计自然语言处理中的二元统 计语言模型。 中国科学技术大学硕士学位论文 分词统计理论 2 1 3 全概率公式和贝叶斯公式 在计算某复杂事件出现的概率时，如果直接计算事件的概率比较困难，可以 将该事件划分为若干彼此独立的简单事件之和。 定义：称事件族b l ，吃，b 。为样本空间q 的一个划分( 也称岛，b 2 ，b n 为 玎 一个完备的事件组) ，如果满足岛n b j = ( f - ，) 且u 易= q 。进而，如还有 i = l p ( 岛) o ，i = 1 , 2 ，则称且，b 2 ，b n 为样本空间q 的一个正划分。 定理l( 全概率公式) 设事件b 1 ，b 2 ，b n 为样本空间q 的一个正划分，则对 任何一个事件4 ，有 p ( a ) = p ( b 1 ) p ( 4 l 蜀) + p ( b 2 ) p ( 4 l b 2 ) 4 - 4 - 烈玩) p ( 彳i 玩) h = p ( e ) p ( 4 l e ) f i i ( 2 - 3 ) 与全概率公式密切相关的另一个重要公式称为贝叶斯公式( b a y e s i a n f o r m u l a ) ，它在统计自然语言处理中占据着举足轻重的地位。当直接计算条件概 率p ( a l 矗) 比较困难，而p ( b 1 4 ) 已知或者容易计算时，可以用贝叶斯公式通过 e ( a j 彳) 来计算p ( a i b ) 。 定理2 ( 贝叶斯公式) ：设毋i ，b 2 ，b n 为样本空间q 的一个正划分，事件4 满足 p c 4 冷0 ，则 酬舻萼铲 ；， 若将它与全概率公式结合起来，就是b a y e s 公式的以下的常用形式 e ( b , i 彳) ：? 旦盟( i ：1 ，2 ，n ) ( 2 - 5 ) 尸( 乃) p ( 4 f 毋 j l 贝叶斯公式在统计自然语言处理中常被简单地应用为如下形式： a r g ，m a x p ( b i 爿) = a r g 。m a x ! ：! ：! ：；竽= a r g 。m a x p ( 彳ib ) p ( 曰) ( 2 6 ) 上式中，a r g m a x f ( x ) 表示使f ( x ) 取最大值的x 。 中国科学技术太学硕士学位论文分词统计理论 2 2 统计语言模型 2 2 1 统计语言模型定义 大多数人接触一个新的概念的时候，大脑的直接反映就是：这个概念到底指 什么，而它所指的内容又有什么作用? 我想对一个概念最好的解释莫过于：先实 际观察一个实际的例子，并从该例子中得到该概念的一个初步的印象，然后再接 触该概念的理论定义。其实这一过程，也正是人们实际发现和掌握真理的科学方 法论运用的过程。既然这样，那也让我们实际通过一个例子，来引出统计语言模 型至6 底是什么。 我想现实生活中，我们或多或少都遇到过这样的情况：“当我们和朋友或家 人等一些比较熟悉的人谈话时，他们一句话还没有说完，我们就已经知道他们要 说的这句话的剩下的内容了。”如他们可能说了如下这样一句话的前半部分： “今天天真” 很多时候我们就能猜测到他后面要说的词可能是“热”、“凉快”等之类的。 我们可能不会想到“美丽”或者其他的一些不可能出现在该位置的词来。 从上面的这个通过前面几个词来预测下一个词的例子，我们可以得到如下对 统计语言模型的规范化的定义：根据历史n 1 个词，来预测第n 个词的统计模型， 称为n 元模型，又叫统计语言模型( s t a t i s t i c a ll a n g u a g em o d e l ) 。 2 2 2 一元语言模型【1 2 】 一元语言模型又称为上下文无关模型。之所以称一元语言模型为上下文无关 模型，是因为，该模型仅考虑当前词自身的概率，而不考虑词所对应的上下文环 境。因此一元语言模型是一种最为简单的语言模型，但是由于其没有考虑上下文 语言环境，该模型实际说来没有太大的实用价值。但是一元语言模型却是统计自 然语言的处理基础，而且所有高阶的语言模型都以该模型为基础，当数据稀疏比 较厉害的时候，这些高阶的语言模型都退化为低阶的语言模型，甚至为一元语言 模型。 汉语分词中也常常会使用一元语言模型，来统计一个训练集中所有词的频数 及其频率，然后用该频率近似代替该词的概率。 一元语言模型一般用如下公式刻画： p ( w l = w 1 日) = p ( w j = ，) ( 2 - 7 ) 其中i - 1 代表词w f 的历史。采用最大似然法p ( = w ) 可表示为： 中国科学技术大学硕士学位论文分词统计理论 p ( w l = w ) = 鲁 ( 2 - 8 ) 其中， 0 代表词嵋在训练集中出现的总次数。代表训练集的总词数。 一元统计语言模型的优点是它所需的训练数据集较小；缺点是没有考虑到上 下文统计信息。因而在实际应用中，单纯使用该模型时，系统地精确度往往不高。 汉语分词研究学者曾做过统计，使用一元统计语言模型，分词正确率为9 2 。 2 2 3 马尔科夫过程【1 3 1 一个符号串w l ，w 2 ，如果其中每个的出现概率都只跟前面出现的，个 符号有关，那么，这样的符号变化( 或状态转移) 过程叫做马尔科夫过程。 考虑最简单的一阶马尔科夫过程，其中每个符号只跟前面出现的一个符号相 关，则p ( w l ，w 2 ，w n ) = p ( w o p ( w 21 w o p ( i - i ) 如果虚设，可以简单地 表示为： p ( w l ，w 2 ，) = 兀p ( 獭l i - i 其中“n ”表示求n 项乘积 1 - 1 类似地在二阶马尔科夫过程中，一个符号只跟前面出现的两个符号相关，符 号串的概率为： h p ( w l ，w 2 ，) = n p ( mi 嵋- 2 w t - i ) ( 2 一l o ) l t l 这样，我们就把符号串的概率计算转化为串中每个符号的条件概率的计算问 题。将马尔科夫过程用于自然语言处理，如汉语分词，就演变成了n 元语言模型。 n 元语言语言模型是指当前符号的条件概率取决于从前面n 一1 个符号到它的转移 概率。因此，三元语言模型相当于二阶马尔科夫过程，二元语言模型相当于一阶 马尔马科夫过程，n 元语言模型相当于n - 1 阶马尔科夫过程。如果认为一个符号 串的概率就是其中每个符号的概率的乘积，那就是一元语言模型。 2 。3 数据稀疏和平滑方法【1 2 1 统计自然语言处理需要大规模的语料，但实际情况是很多时候，我们常常无 法得到足够大的语料，因此由于语料的不足常常会导致数据稀疏问题。假设我们 目前手头有一个语料，该语科有l o 万个词，如果按语料规模来说，该语料库已 中国科学技术大学硕士学位论文 分词统计理论 经是一个数据比较稀疏的语料了，而且该语料本身也常常出现数据稀疏。拿二元 举例来说，如果该语料要包含所有的二元短语，所需覆盖的二元短语为1 0 ”，但 真实情况是，该语料由于数据稀疏问题，常常无法覆盖如此大规模的数据量。 因此为了使用在自然语言处理中引入统计的方法，同时又不影响其效果，统 计自然语言处理学家在大量实验和观察的基础上，提出了一系列的统计平滑处理 方法来解决数据稀疏问题。 2 3 1l a p i a o e 平滑算法【1 4 l l a p l a c e 平滑算法也许是统计自然语言处理中最简单的一种平滑算法，虽然 实际使用中没有太多的价值，但它却为其他平滑算法的发现奠定了基础。因此 l a p l a c e 平滑算法，对统计自然语言平滑处理的研究具有很重要的影响。 l a p l a c e 平滑算法又称为加l 平滑算法。该算法是由l i d s t o n e ，j o h n s o n 和 3 e f f r e y s 等人提出的。该算法主要用来解决当一元或n 元短语出现次数为零时 的情况。对于一元短语来说，有如下公式： 一 t ： ( m ) 2 j 而# 1 - 1 ( 2 一i i ) 其中q 为词川出现的次数，为语料库所有词出现的总次数，1 即为平滑常 数，矿为语料库中词的种类数。 从上面的公式，我们可见l a p l a c e 平滑算法较为粗糙，因此在实际使用中性 能一般来说较差。 2 3 2g o o d t u rin g 平滑算；去【1 5 l 【1 6 1 许多平滑算法的思想是：将我们所观察到的事物的出现次数，部分地折扣到 那些我们没有观察到，而实际却真实存在的事物上去。g o o d - t u r i