（轻工技术与工程专业论文）文本自动分词方法研究.pdf

文本自动分词方法研究 摘要 汉语分词是中文信息处理的基础，它是由计算机自动识别文本 中的词边界的过程。从计算机处理过程上看，分词系统输入的是连 续的字符串( c , c ：c 。c 。) ，输出的是汉语的词串( w 。w ：w 3 w ) ，这 里，w ；可以是单字词也可以是多字词。然而，由于汉语文本和英文 文本这两种语言自身的书写方式不同，英文是以词为单位的，词和 词之间是靠空格隔开，而中文是以字为单位，句子中所有的字连起 来才能描述一个意思，词与词之间并没有明确的分隔标记，而是连 续的汉字串。随着计算机技术的发展，对于计算机的文本处理能力 提出了更高的要求，诸如智能拼音语句输入、手写和语音自动识别 输入：文章的校对；简体和繁体中文的自动转换；信息检索和信息 摘录；文本分类和自动文摘；语音合成；自然语言的理解和自动翻 译；自然语言接口等。而所有这些中文处理功能都要建立在对汉语 文本的分词处理这一基本功能之上。 本文首先阐述了汉语自动分词研究的现实性和可能性，接着介 绍其研究现状，并扼要评价了十几年来产生的各种方法，围绕该研 究中的其中的一个基本问题切分算法的改进展开了重点讨论，提出 一种新的电子词表数据结构，它不仅支持首字h a s h 和标准的二分查 找，而且不限词条长度，其查找效率很高；然后介绍了相应的分词 算法一一近邻匹配法，它是一种改进的m m 算法，可以大大降低分词 过程中的匹配次数，理论分析表明，该算法的效率优于其它方法； 接着对其产生的歧义提出了相应的解决策略；最后就这个问题以后 的发展谈了一点个人看法。 【关键词】汉语自动分词、切分歧义消解、最大匹配算法 t h es t u d yo fm e t h o d o nt h ec h i n e s et e x ts e g m e n t a t i o n a b s t r a c t c h i n e s ew o r d s e g m e n t a t i o n i sa p r e r e q u i s i t e t oc h i n e s e i n f o r m a t i o n p r o c e s s i n g i t i s w e l lk n o w nt h a tc h i n e s ew o r d s e g m e n t a t i o n i s d i s t i n g u i s h w o r db o u n d a r i e sf r o mas e n t e n c e a u t o m a t i c a l l yb yt h ec o m p u t e r w es e ef r o mt h ep r o c e s so ft h ec o m p u t e r ， t h e i n p u t o f t h ew o r ds e g m e n t a t i o n s y s t e m i sa c o n s e q u e n t c h a r a c t e r s ( e x a m p l e c l c 2 c n ) ，o u t p u ti sc h i n e s ew o r d s ( w j w 2 w 3 w m ) ，t h e r e ，w im a y b eas i n g l e l e t t e ro rw o r dc o n s i s t e do ff e w l e t t e r s b u tt h e h a n d w r i t i n gs t y l e o ft h e e n g l i s h t e x ta n d c h i n e s et e x ti s d i f f e r e n t ，t h ee n g l i s ht e x t i sb a s e do nw o r d s ，t h e s e w o r d si sd i v i d e db yt h es p a c e ，b u tt h ec h i n e s et e x ti sb a s e do nt h e l e t t e r s a 1 lt h e s el e t t e r sm u s tb ec o n n e c t e d ，t h e nw ec a n c l e a r l y d e s c r i b ea m e a n i n g i t sw e l lk n o w nt h a tt h e r e a r en os e p a r a t o r s b e t w e e nw o r d si nc h i n e s et e x t w i t ht h e d e v e l o p m e n t o ft h e c o m p u t e rt e c h n o l o g y ，e v e nh i g h e rd e m a n d sh a v eb e e np u tf o r w a r df o r t h ec a p a b l i t ya b o u tt h ec o m p u t e rd e a lw i t ht h ec h i n e s et e x t e x a m p l e i n t e l l i g e n tp i n y i ni n p u t 、h a n d w r i t i n ga n dv o i c ea u t o m a t i cd i s t i n g u ! s h ， a r t i c l e p r o o f r e a d e r 、c h i n e s e t oc h i n e s ec o n v e r s i o n 、i n f o r m a t i o n r e t r i e v a la n di n f o r m a t i o ne x t r a c t 、t e x tc l a s s i f i c a t i o n 、v o i c ec o m p o u n d 、 n a t u r a l l a n g u a g eu n d e r s t a n d i n g 、a u t o m a t i c t r a n s l a t i o n 、n a t u r a l l a n g u a g e i n t e r f a c ee t c a l lt h e s em u s tb a s eo nt h ec h i n e s ew o r d s e g m e n t a t i o n i nt h i sp a p e r ，t h er e a l i t ya n dp o s s i b i l i t ya b o u t t h ec h i n e s e s e g m e n t a t i o n i s e x p o u n d e d ，a n d i n t r o d u c e si t s p r e s e n t s i t u a t i o n ， r e v i e w sv a r i o u sk i n d so fm e t h o d si nt h ep a s ty e a r s a t t a c hi m p o r t a n c e t ot h eb a s i c q u e s t i o n a b o u t t h ew o r ds e g m e n t a t i o nm e t h o d ，a h i g h l ye f f i c i e n t d a t as t r u c t u r ef o rc h i n e s et h e s a u r u si si n t r o d u c e d ， w h i c hs u p p o r t ss t a n d a r db i n a r ys e a r c ha n dh a s h i n go p e r a t i o nb ym e a n s o ft h ef i r s tc h i n e s ec h a r a c t e ri nas t r i n g ，w h i l et h el e n g t ho fe v e r yw o r d i sn o tl i m i t e d b a s e do ns e a r c h i n gaw o r dc o m p o s e do ft w oc h a r a c t e r s q u i c k l y ，t h ew o r di n c l u d i n gm u l t i p l ec h i n e s ec h a r a c t e r sc a nb ef o u n db y u t i l i z i n gt h e a l g o r i t h m ，w h i c ha c h i e v e sh i g hp e r f o r m a n c e i nc h i n e s e w o r d s e g m e n t a t i o n b y i n v o k i n gn e i g h b o r h o o dm a t c h i n g a n d a d v a n c e sa t a c t i c st os o l v et h ea m b i g u i t y i nt h ee n d ，p u t so u t a l i t t l e p e r s o n a li d e a s 【k e yw o r d s lw o r ds e g m e n t a t i o no fc h i n e s es e n t e n c e ，d e a l i n g o f a m b i g u i t y ，u n k n o w nw o r d s 4 第一章前言 1 1 汉语自动分词的重要性与实现的可能性 自然语言处理作为人工智能的一个分支，无论是机器翻译，还是智能接口， 都需要它的支持，因此受到许多科学工作者的重视。“对自然语言的理解”是 自然语言处理的重要组成部分。要想理解一个自然语言书写的句子，一般要对 其作词法、语法及语义分析，其中的词法分析是整个理解过程的基础。特别是 对于象汉语这样的自然语言显得尤为关键。我们知道，中文信息处理就是要“用 计算机对汉语的音、形、义进行处理。” ，汉语中词是最小的能够独立活动 的有意义的语言成分，在一个汉语句子中，词与词之间没有明显的分隔符( 如： 空格) ，而是连续的汉字串，这为词法分析带来了更多的困难。因此，汉语的 词法分析除了具有同型异义词、异型同义词及词型变化等特征以外，其核心在 于分词，即把输入的汉语句子分解成单词序列，说得通俗一点，就是要由机器 在中文文本的词与词之间自动加上空格，并为每个单词附加上相应的词法信 息，供以后的语法和语义分析使用。 汉语自动分词是对汉语文本进行自动分析的第一个步骤。我们知道，英语 文本是小字符集上的已充分分开的字符串，而汉语文本是大字符集上的连续字 串，把字串分成词串就是自动分词要做的。此过程的一个主要问题是对大量歧 义现象的处理。计算机的所有语言知识都来自机器词典( 给出词的各项信息) 、 句法规则( 以词类的各种组合方式来描述词的聚合现象) 以及有关词和句子的 语义、语境、语用知识库。汉语信息处理系统只要涉及句法、语义( 如检索、 翻译、文摘、校对等应用) ，就需要以词为基本单位。对连续文本切分为词以后 再在词的层面上进行处理，处理的确定性就大大提高了。在更高一级的文本处 理中，例如句法分析、语句理解、自动文摘、自动分类和机器翻译等，更是少 不了词的详细信息。 汉语自动分词是任何中文自然语言处理系统都必须面对的第一个最基本 的问题。具体来说，自动分词在很多现实应用领域( 中文文本的自动检索、过 滤、分类及摘要，中文文本的自动校对，汉外机器翻译，汉字识别与汉语语音 识别的后处理，汉语语音合成，以句子为单位的汉字键盘输入，汉字简繁体转 换等) 中都扮演着极为重要的角色 汉语文本在计算机内部表示时，词与词之间并没有明显的切分标志，但是 在进行中文信息处理的许多重要领域如篇章理解、机器翻译、文本检索、文本 的语音输入输出、文本校对、自动标引等都是在词这一平面上来进行的，因而 自动分词已成为中文信息处理中的基础课题，只有解决好这个问题，各种中文 处理系统才能得以向智能化发展，构建于词平面之上的各种语言分析手段才能 更好的展示。 虽然这一问题本身所具有的难度，使其很难从根本上解决，但是随着我国 全面推广信息化，i n t e r n e t 上中文网页数量急剧增加和中文电子出版物、中文 数字图书馆的迅速普及都说明了这一点。这就使得中文自然语言的处理研究进 入了一个非常肘期，在以后很长时间内它将受到人们的广泛关注，其重要性日 益显著。 迄今为止，我们尚不能下一个完全肯定的结论，但经过科学工作者十几年 不懈的探索，这个答案的轮廓还是大体凸显出来了。毕竟词平面上的研究与句 法平面和语义平面的研究相对比，本身难度要小得多，并且无论是在计算机语 言学方面还是在普通语言学方面，所取得的成果也要成熟、扎实得多。现有的 工作积累已经达到了可以厚积薄发的程度。如果说面向非受限文本的汉语句 法、语义自动分析还是可望而不可及的话，那么，面对相同对象的汉语自动分 词，已经取得了一定的成绩。s p r o a tr a n ds h i hc l ，e ta 1 ( 1 9 9 6 ) 及s u n m s a n ds h e nd y e ta 1 ( 1 9 9 7 ) 的汉语自动分词原型系统已初具处理非 受限文本所需的种种功能。他们沿着正确方向跨了一大步。 1 2 汉语自动分词系统的研究现状 经过多年的探索与研究，人们已经开发完成了一些初见成效的自动分词系 统。下面对其中几个具有代表性的做一简单介绍。 1 、几个早期的自动分词系统 自8 0 年代初中文信息处理领域提出了自动分词以来，一些实用性的分词系 统逐步得以开发，其中几个比较有代表性的自动分词系统在当时产生了较大的 影响。 c d w s 分词系统是我国第一个实用的自动分词系统，由北京航空航天大学计 算机系于1 9 8 3 年设计实现，它采用的自动分词方法为最大匹配法，辅助以词 尾字构词纠错技术。其分词速度为5 1 0 字秒，切分精度约为1 6 2 5 。基本满 足了词频统计和其他一些应用的需要。这是汉语自动分词实践的首次尝试，具 有很大的启发作用和理论意义。 a b w s 是山西大学计算机系研制的自动分词系统，系统使用“两次扫描联 想一回溯”方法，运用了较多的词法、句法等知识。其切分正确率为9 8 6 ( 不 包括非常用、未登录的专用名词) ，运行速度为4 8 词分钟。 c a s s 是北京航空航天大学于1 9 8 8 年实现的分词系统。它使用的是一种变 形的最大匹配方法，即正向增字最大匹配，运用知识库来处理歧义字段。其机 械分词速度为2 0 0 字秒以上，知识库分词速度1 5 0 字秒( 没有完全实现) 。 书面汉语自动分词专家系统是由北京师范大学现代教育研究所于1 9 9 l 前 后研制实现的，它首次将专家系统方法完整地引入到分词技术中。 2 、清华大学s e g 分词系统 该系统提供了带回溯的正向、反向、双向最大匹配法和全切分一评价切分算： 法，由用户来选择合适的切分算法。其特点则是带修剪的全切分一评价算法。j 系统考虑到了切分盲点的问题( 某些字串永远不会被某种分词方法匹配出来) ， 由此提出了全切分的概念，即找出输入字串的所有可能的子串，然后利用某种 评价方法从所有这些可能的子串中选出最佳子串序列作为分词结果。由于全切 分的结果随着句子长度的增加呈指数增长，时空开销非常大。为了解决全切分 所带来的组合爆炸问题，又引进了对全切分过程进行修剪的方法，强制性地终 止某些全切分的进行。用户在使用时，对于歧义较少的语料，可采用正向或反 向最大匹配法；对于有较多交叉歧义的语料，可使用双向最大匹配法；对于其 它歧义较大的语料，则采用全切分一评价算法，并需要采用一个合适的评价函 数。由于对具体语料的统计参数设置了不确切初值，全切分一评价算法在第一、 二遍切分过程中的正确率较低，随着切分的多遍进行，评价函数逐渐得以矫正， 系统的切分精度逐步得以提高。经过封闭试验，在多遍切分之后，全切分一评 价算法的精度可以达到9 9 左右。 9 3 、清华大学s e g t a g 系统 该系统着眼于将各种各类的信息进行综合，以便最大限度地利用这些信息 提高切分精度。系统使用有向图来集成各种各样的信息，这些信息包括切分标 志、预切分模式、其他切分单位。为了实现有限的全切分，系统对词典中的每 一个重要的词都加上了切分标志，即标志”c k ”或”q k ”。”q k ”标志表示该词可进 行绝对切分，不必理会它是否产生切分歧义；”c k ”标志表示该词有组合歧义， 系统将对其进行全切分，即保留其所有可能的切分方式。 系统通过这两种标志并使用几条规则以实现有限的全切分，限制过多的切 分和没有必要的搜索。规则包括： ( 1 ) 无条件切出q k 类词： ( 2 ) 完全切分c k 类词( 保留所有可能子串) ； ( 3 ) 对没有标记( q k 或c k ) 的词，若它与别的词之间存在交叉歧义，则作 全切分；否则将其切出。 为了获得切分结果，系统采用在有向图d a g 上搜索最佳路径的方法，使用 一个评价函数e v a l u a t ep a t h ，求此评价函数的极大值而获得最佳路径p m a x 。 所运用的搜索算法有两种，“动态规划”和“全切分搜索+ 叶子评价”，使用了 词频、词类频度、词类共现频度等统计信息。通过实验，该系统的切分精度基 本上可达到9 9 左右，能够处理未登录词比较密集的文本，切分速度约为3 0 字 秒。 4 、国家语委文字所应用句法分析技术的汉语自动分词 该分词模型考虑了句法分析在自动分词系统中的作用，以更好地解决切分 歧义。切词过程考虑到了所有的切分可能，并运用汉语句法等信息从各种切分 可能中选择出合理的切分结果。其过程由两步构成： ( 1 ) 对输入字串进行处理，得到一个所有可能的切分字串的集合，即进 行( 不受限的) 全切分； ( 2 ) 利用句法分析从全切分集合中将某些词选出来，由它们构成合理的 词序列，还原为原输入字串。 系统使用一个自由传播式句法分析网络，用短语文法描述句法规则，并将 其表示为层次化网络图，通过此网络的信息传递过程来进行选词。网络的节点 分为词类节点( 终结符节点) 和规则类节点( 非终结符节点) 。词类节点保存 1 0 词的信息：规则类节点对信息进行合并和句法、语义分析，生成新的信息，并 将本节点的信息传递出去( 也就是用文法产生式进行归约，并进行属性计算一 作者注) 。网络运行的初态是所有节点状态为n o ，各种可能切分的字串进入响 应相应的词类节点( 终结符节点) ，然后开始运用文法进行计算。当网络的最 高层节点s ( 文法起始符号) 达到稳定状态o k 时，计算结束，在最高节点处输 出最后的切分结果。 从一般的角度来看，应用句法分析技术进行切词的方法是一种“生成一测 试”方法，它是一种常用的a i 问题求解方法，包括两个步骤：生成步一找出所 有可能的解( 假设) ；测试步一对各个假设进行检验，找出合格者。在应用句法 分析进行切词时，其测试步是使用汉语的句法规则检验某种切分结果是否构成 合法的汉语句子。这样可以将句法分析理论的各种成果用于切词之中，有多种 句法分析技术可以应用，常见的是a t n 分析、c y k 分析( c h a r tp a r s i n g ) 、g - l r 分析等。可以将这种方法称做“切词一句法分析一体化”方法。随着软硬件水 平的不断提高，直接运用时空消耗比较大的句法分析来检查分词结果的方法正 在日益显现其优越性。 5 、复旦分词系统 该系统由四个模块构成。 ( 1 ) 预处理模块，利用特殊的标记将输入的文本分割成较短的汉字串，这 些标记包括标点符号、数字、字母等非汉字符，还包括文本中常见的一些字体、 字号等排版信息。 ( 2 ) 歧义识别模块，使用正向最小匹配和逆向最大匹配对文本进行双向扫 描，如果两种扫描结果相同，则认为切分正确，否则就判别其为歧义字段，需 要进行歧义处理。 ( 3 ) 歧义字段处理模块，此模块使用构词规则和词频统计信息来进行排歧。 ( 4 ) 此系统还包括一个未登录词识别模块。 实验过程中，对中文姓氏的自动辨别达到了7 0 的准确率。系统对文本中 的地名和领域专有词汇也进行了一定的识别。 6 、哈工大统计分词系统 该系统是一种典型的运用统计方法的纯切词系统，它试图将串频统计和词 匹配结合起来。 系统由三个部分构成： ( 1 ) 预处理模块，利用显式和隐式的切分标记( 标点符号、数字、a s c i i 字符以及出现频率高、构词能力差的单字词、数词+ 单字常用量词模式) 将待 分析的文本切分成短的汉字串，这大大地减少了需要统计的( 无效) 字串的数 量和高频单字或量词边界串。 ( 2 ) 串频统计模块，此模块计算各个已分开的短汉字串中所有长度大于 1 的子串在局部上下文中出现的次数，并根据串频和串长对每个这样的子串进 行加权。根据经验，局部上下文中取为2 0 0 字左右。局部上下文的串频计算使 用一个滑动窗口( 为一个队列式缓冲区，保存当前待切分汉字串及其前后2 0 个短串) ，当当前待切分汉字串处理完之后，窗口下移一个短串( 中心变为相 邻下一个短串) 。系统采用一个外散列表来记录窗口中的短串，以加快窗口中 串频计数。散列函数取为汉字的g b 一8 0 位码( 二级汉字共用入口9 5 ) ，每个桶 中保存窗口中每一行( 短串) 上的汉字位置：( 短串的行号，汉字列号) ，并且 对于在窗口中出现多次的汉字位置用一个链指针连接起来，则计算某个字串在 窗口中出现的频度时，不必将该字串与窗口中的短串逐个匹配，而只需统计在 该字串中的各个汉字所对应的位置链表中能够相邻的位置的序列的个数即可。 此外，还需要根据词缀集( 前、后缀集合) 对字串的权值进行提升，例如”处 理器”中”处理”的权值很高，但由于对。处理器”的权值作了提升( 达到或超过 了处理”) ，就不会切成”处理器”。如果某个汉字串的权值超过某一阂值d ( 取 为4 0 ) ，则将此汉字串作为一个新识别的词，将其存入一临时词库中。 ( 3 ) 切分模块，首先用临时词库对每个短的汉字串进行切分，使用的是 逐词遍历算法，再利用一个小型的常用词词典对汉字短串中未切分的予串进行 正向最大匹配分词。对于短汉字串中那些仍未切分的子串，则将所有相邻单字 作为一个权值很低的生词( 例如”玛”、”莉”) 。其中每个模块都对待分析的文 本进行了一次扫描，因而是三遍扫描方法。此系统能够利用上下文识别大部分 生词，解决一部分切分歧义，但是统计分词方法对常用词识别精度差的固有缺 点仍然存在( 例如切出”由来”、”语用”、”对联”等) 。经测试，此系统的分 词错误率为1 5 ，速度为2 3 6 字秒。 7 、杭州大学改进的m m 分词系统 系统的词典采用一级首字索引结构，词条中包括了“非连续词”( 形如c t 1 2 宰c n ) 。系统精度的实验结果为9 5 ，低于理论值9 9 7 3 ，但高于通常的m m 、 r m m 、d m m 方法。 考虑到汉语的歧义切分字段出现的平均最大概率为i 1 1 0 ，因而纯机械分 词的精度在理论上能够达到卜1 1 1 0 = 9 9 1 。那么是否还有更一般、精度更高 的机械分词系统呢? 根据统计，汉语的局部( 词法一级) 歧义字段占了全部歧义的8 4 ，句法 歧义占1 0 ，如果提高系统处理这两类歧义的准确率，则可以大幅度提高切分 精度。这方面的改进导致了改进的m m 分词算法。将其阐述如下。 通过对交叉歧义字段的考察，发现其中8 0 以上可以通过运用一条无需任 何语言知识的“归右原则”( 交叉歧义字段优先与其右边的字段成词) 就可以 获得正确切分，一这是因为在多数情况下汉语的修饰语在前、中心词在后，因 而“归右”好于“归左”。“归右原则”可以使机械分词的精度上升到9 9 7 0 。 这种考察给出了鼓舞人心的结果，有可能使机械分词系统达到这样的理论精 度。不过”归右原则”还有需要修正的地方，既对于”连续型交叉歧义”会发生错 误，需要补充一条”左部结合”原则：若a b c d e 为连续型交叉歧义字段，”归右 原则”产生切分abcde 再由”左结合原则”( 合并最左边的a 、b ) 而得到a b ! cd e 。 。 例如”结合成分子”一 ”结合成分子匕 ”结合成分子”。但是仍然还有 例外，例如”当结合成分子时”一 ”当结合成分子时”：为此引入”跳跃匹配”， 在词典中定义”非连续词”( 实际上为串模式一作者注) ”当 时”，然后在切分时 首先分出”当结合成分子时”，然后再用”归右+ 左结合”切分中间的歧义字段。 以上3 项技术将机械分词的理论切分精度提高到了9 9 7 3 。 综合以上思想，就建立了如下改进的m m 分词算法： 正向扫描+ 增字最大匹配( 包括”跳跃匹配非连续词”) + 词尾歧义检查 ( 逐次去掉首字做m m 匹配以发现交叉歧义字段) + ”归右原则”( 对于”连续 型交叉歧义”还需要”左结合原则”) 。 系统的词典采用一级首字索引结构，词条中包括了”非连续词”( 形如 c i c n ) 。系统精度的实验结果为9 5 ，低于理论值9 9 7 3 ，但高于通常的 m m 、r m m 、d m m 方法。 8 、m i c r o s o f tr e s e a r c h 汉语句法分析器中的自动分词 微软研究院的自然语言研究所在从9 0 年代初开始开发了一个通用型的 多国语言处理平台n l p w i n ，据报道，n l p w i n 的语法分析部分使用的是一种双 向的c h a r tp a r s i n g ，使用了语法规则并以概率模型作导向，并且将语法和分 析器独立开。实验结果表明，系统可以正确处理8 5 的歧义切分字段，在 p e n t i u m2 0 0p c 上的速度约6 0 0 - 9 0 0 字秒。 9 、北大计算语言所分词系统 本系统由北京大学计算语言学研究所研制开发，属于分词和词类标注相结 合的分词系统。由于将分词和词类标注结合起来，系统可利用丰富的词类信息 对分词决策提供帮助，并且在标注过程中又反过来对分词结果进行检验、调整， 同时将基于规则的标注排歧与基于语料库统计模型的排歧结合起来，使规则的 普遍性与灵活性得到统一，而且对未登入词的估算到达了相当高的准确率。系 统的处理过程包括了自动切分和初始词性标记、切分歧义字段识别、组词和标 注预处理、词性标记排歧、切分和词性标注后处理等过程。系统的算法综合了 多种数据组织和搜索技术，以很低的时空开销实现了高速匹配和查找，同时采 用了当代计算语言学的统计方法，运用隐m a r k e r 过程进行词类标注和排歧， 对算法的效率和稳固性都作了尽可能的优化。 此系统的一大特色是对通用性的强调，将最稳定、最常用的4 万6 千余条 现代汉语基本词汇( 即将扩充到7 万多条) 及其有关属性组织成为基本词典。 这些词的基本地位都是由汉语语言学家逐一检验认可的，这是本系统通用性的 保证；在此词典的基础上充分利用汉语构词法的研究成果，可以识别出大部分 的常用词。同时本系统对用户词典机制作了最大限度的扩展，允许用户加入3 部到3 0 部以上的自定义词典，并允许用户对这些词典的优先顺序自由排列， 这样就可以用较小规模的多个特殊词典更有针对性地解决具体领域的文本处 理。因此本系统的语言模型实现了通用性与多样性的有效结合，并到达了极高 的效率。经过最近在搜索算法上的改进，系统的分词连同标注的速度在p e n t i u m 1 3 3 h z 1 6 m b 内存机器上的达到了每秒3 千词以上，而在p e n t i t l m1 1 6 4 m b 内存 机器上速度高达每秒5 千词。白本系统开发以来，已先后向国内和国外十多家 单位进行了转让，获得了普遍的好评。 在1 9 9 8 年4 月进行的8 6 3 全国智能接口评测会上，该系统有良好的表现。 由于系统对待词的兼类问题的理论观点与评测标准有一些差别，所测得的标注 准确率没有达到自测试的水平。该系统的词语分类体系一方面承认汉语词存在 兼类现象，一方面又不主张扩大兼类现象，尽量把相同语法功能的词类当作是 一个词类，而把词的具体语法属性留到后续过程处理。这些观点与评测标准有 所不同。国内还有很多单位开发了分词系统，但大部分都没有参加这一具有极 强可比性的评测。 1 3 论文主要内容 文本自动分词是汉语信息处理的前提。本论文的主要工作内容有： ( 1 ) 本课题分析和比较了几种主要的汉语自动分词方法，阐述了各种分词 方法的技术特点。在此基础上，提出文本自动分词的设计目标和原则。 ( 2 ) 对于基于词典的分词方法，词典的组织是汉语自动分词的基础，词典 机制的优劣直接影响到中文分词的速度和效率。根据计算机多以内码形式处理 中文文档和汉语中双字词较多的特点，提出一种新的词典机制。 ( 3 ) 在上述词典的组织形式下，提出将一种改进的正向最大匹配切分算法 与邻近匹配法结合的新思路，可以有效提高查询的速度。 ( 4 ) 为消除歧义提出了校正策略的思路，并在此基础上结合统计方法处理 未登录词。 第二章文本自动分词概述 2 1 主要的自动分词算法 目前己有很多分词算法，如：正向最大匹配法( m m ) 、逆向最大匹配法( r m m ) 、 逐词遍历匹配法、设立切分标志法、正向最佳匹配法和逆向最佳匹配法等。近 几年又提出了很多新的方法，旨在提高分词的精度和分词的速度，如：生成测 试法：通过词法和语义之间的相互作用来进行歧分问题的决策，以提高分词的 精确性：改进的m m 分词算法：采用正向增字最大匹配法和跳跃匹配法，结合词 尾语义检查和归右原则以消除类型歧义：基于神经网络的分词方法则尝试利用 神经网络来处理歧分问题，但同时又引入一个问题即训练样本的选取，由于自 然语言的复杂性，如何选取训练样木还需要作深入的研究。 归纳起来现有的分词算法主要可分为三大类：基于字符串匹配的分词方 法、基于理解的分词方法和基于统计的分词方法。 2 1 1 基于字符串匹配的分词方法 这种方法又叫做机械分词方法，它是按照一定的策略将待分析的汉字串 与一个“充分大的”机器词典中的词条进行匹配，若在词典中找到某个字符串， 则匹配成功( 识别出一个词) ，否则失败。按照扫描方向的不同，机械分词方 法可分为正向匹配和逆向匹配：按照不同长度优先匹配的原则，可以分为最大 ( 最长) 匹配和最小( 最短) 匹配；按照是否与词性标注过程相结合的原则， 又可以分为单纯分词方法和分词与标注相结合的一体化方法。常用的几种机械 分词方法如下： ( 1 ) 正向最大匹配 通常简称为m m 法。其基本思想为：设d 为词典，m a x 表示d 中的最大词条 的长度，s t r 为待切分的字串。m m 法是每次从s t r 中取长度为m a x 的子串与d 中的词条进行匹配。若成功，则判定该子串为词，指针后移m a x 个汉字后继续 1 6 匹配，否则子串逐次减一字进行匹配。 假设有句子：s = c c ：c 。 词：w ，= c 。c 。c 。m 为词典中最长词的字数。 m m 算法描述 0 ) 令i = o ，当前指针p 。指向输入字串的初始位置，执行下面的操作： 1 ) 计算当前指针p 。到字串末端的字数( 即未被切分字串的长度) n ， i fn = 1 ，转3 ) 。否则，令m = 词典中最长词条的字数，i f 1 1 f i l ， 令m = 1 3 ； 2 ) 从当前指针p ； 起取m 个汉字作为词w ；，作如下判断： i )如果w ；确实是词典中的词，则在w ；后添加一个切分标志，转i i i ) ； i i )如果w 。不是词典中的词且w ；的长度大于l ，将w 从右端去掉一 个字，转2 ) 中的i ) 步；否则( 即w 的长度等于1 ) ，则在w 后 添加一个切分标志，将w 。作为单字词添加到词典中，执行i i i ) ； i i i ) 根据w 。的长度修改指针p 。的位置，如果p 指向字串末端，转3 ) ， 否则，i = i + 1 ，返回1 ) ； 3 ) 输出切分结果，结束分词程序。 ( 2 ) 逆向最大匹配 通常简称为r m m 法。r m m 法的基本原理与m m 法相同，不同的是分词的扫描 方向，它是从右至左取子串进行匹配。每次取最末端的m a x 个字作为匹配字段， 匹配失败则去掉最前面的一个字，这种方法需配备逆序分词词典。 统计结果表明，单纯使用正向最大匹配的错误率为1 1 6 9 ，单纯使用逆向 最大匹配的错误率为l 2 4 5 ，r m m 法在切分的准确率上比m m 法有很大提高。 例如：他是研究生物化学的。 洲切分结果：他ii 是1i 研究生| | 物化il 学i | 的| | 。 r m m 切分结果：他ii 是ii 研究ii 生物ii 化学ii 的li 。 总结： 最大匹配法优点： 程序简单易行，开发周期短。 仅需要很少的语言资源( 词表) ，不需要任何词法、句法、语义资源。 最大匹配法弱点： 切分歧义消解的能力差。 切分正确率不高，一般在9 5 左右。 李东，2 0 0 3 ( 3 ) 最短路径法( 使每一句中切出的词数最小) 基本思想：采用动态规划方法找出词图中起点到终点的最短路径。 设待分字串s = c 。c 。c 。，其中c 。( i = 1 ，2 ，n ) 为单个的字，n 为串的长度， n i 。建立一个节点数为n + l 的切分有向无环图g ，各节点编号依次为v 。，v l ，”， v 。，如下图所示： 6 卜o o 斗 c lc 2 c i lc i c j cj + j c n 求n 一最短路径：贪心法或简单扩展法。 算法：( 1 ) 相邻节点v 。，v v 。之间建立有向边 ，边对应的词默认 为c t ( k = 1 ，2 ，n ) 。 ( 2 ) 如果w = c ；c 。c j ( o i - + 斗d k 一寸o c lc 2 c i - c j + i ”c 。 ( 3 ) 重复上述步骤( 2 ) ，直到没有新的路径( 词序列) 产生。 ( 4 ) 从产生的所有路径中，选择路径最短的( 词数最少的) 作为 最终分词结果。 短句有向图示例： 母 宄 生白起澍 q 2 p ( a ，b c ) 则按a b c 切分，否则按a b c 切分。 通过实践人们逐渐形成了基本的共识，这就是歧义切分消解必须有充分 的语言知识来支持。词频、词法、音节、语素性质、语法结构关系、语义甚至 语用信息，都能够在歧义切分消解中起作用。消除歧义时分析的层次越深，计 算机对语言知识的质量和规模的要求就越高。 3 1 切分歧义的基本类型 切分歧义是汉语自动分词研究中的一个关键问题。梁南元( 1 9 8 7 ) 最早 对这个现象进行了比较系统的考察。他定义了两种基本的切分歧义类型： 定义1汉字串a j b 被称作交集型切分歧义，如果满足a j 、j b 同时为词( a 、 j 、b 分别为汉字串) 。此时汉字串j 被称作交集串。 例 交集型切分歧义：“结合成” ( 1 ) a 结合i 成b 结i 合成其中a = “结”，j = “合”，b = “成”。 定义2汉字串a b 被称作多义组合型切分歧义，如果满足a 、b 、a b 同时 为词。 例 多义组合型切分歧义：“起身” ( 2 ) a 他站i 起i 身i 来。b 他明天i 起身l 去北京。 定义3一个交集型切分歧义所拥有的交集串的集合称为交集串链，它的 个数称为链长。如，交集型切分歧义“结合成分子”、“结合”、“合成”、“成 分”、“分子”均成词，交集串的集合为( “合”，“成”，“分”) ，链长为3 。 梁南元( 1 9 8 7 ) 对一个4 8 ，0 9 2 字的自然科学、社会科学样本进行了统计： 交集型切分歧义5 1 8 个，多义组合型切分歧义4 2 个。据此推断，中文文本中切 分歧义的出现频度约为1 2 次1 0 0 字，交集型切分歧义与多义组合型切分歧义 的出现比例约为1 2 ：l 。而刘挺、王开铸( 1 9 9 8 ) 的调查却显示了与梁南元截 然相反的结果：中文文本中交