（系统工程专业论文）文本信息处理中汉语句法分析方法研究.pdf

大连理_ 】= = 大学硕十研究生学位论文 摘要 随着计算机和i n t e r n e t 的推广应用，由数据处理、信息处理发展到知识处理，对语言 文字处理要求的深度和广度越来越高。汉语句法分析是中文信息处理领域内的一个重要课 题，它的发展能带动其它相关语言学应用的发展。 汉语作为自然语言的一种，具有自然语言所共有的最本质的特征，因此汉语句法分析 有必要借鉴和吸收成熟的语言学理论。同时，由于汉语的特殊性，决定了汉语句法分析不 可能照搬现成的方法，必须从汉语自身特点出发，以先进的语言学理论为指导，研究和开 发适合汉语的句法分析技术。 本文的核心工作可以概括为以下三个方面： 1 对现有的一些句法分析算法和模型进行了比较、综合。在总结前人研究成果的基础 上，对传统的汉语句法分析算法加以改进，采用了自底向上与自顶向下相结合的线图分析 方法，提高了分析效率，也使得分析结果的准确率有一定的提高。 2 设计了一套常用的汉语句型库作为研究基础，根据实际应用，确定了一套词性标记 集和短语标记集，并根据常用的句型，设计了一套基于上下文无关的语法规则库。 3 分析、设计和实现了一个汉语句法分析原型系统，实现了基于最大词长匹配算法的 分词模块和基于相对频率训练的统计方法的词性标注模块i 实现了基于改进的线图分析算 法的句法分析模块。 本文使用北大计算语言研究所制作的p f r 人民日报标注语料库作为训练样本，根据本 文确定的词性标记集和短语标记集，以及本文设计的一套语法规则库，使用v c + + 6 0 开发 工具，实现了一个汉语句法分析原型系统，并进行小规模中文文本试验测试，验证本文改 进的分析算法可行有效。 关键词：文本信息处理；汉语句法分析；线图分析法；句法解析器；句法结构 朱国华：文本信息处理中汉语句法分析方法研究 s t u d yo fs y n t a c t i ca n a l y s i sm e t h o df o rc h i n e s et e x tp r o c e s s i n g a b s l x a c t w i t ht h ee x t e n s i v ea p p l i c a f i o n so fc o m p u t e ra n di n t e m e t ，n om a t t e rt h ed a t ap r o c e s s i n ga n d i n f o r m a t i o np r o c e s s i n gi nt h ep a s to rt h ek n o w l e d g ep r o c e s s i n go nt h eu p s w i n g ，t h e ya l ld e m a n d t h em e t h o do fl a n g u a g ep r o c e s s i n ga n dt h er e q u i r e m e n t sa b o u tt h ed e p t ha n de x t e n to ft h a ta r e i n c r e a s i n g l ye n h a n c e d t h ec h i n e s es y n t a xp a r s i n gi sa ni m p o r t a n tp r o b l e mo ft h ed o m a i no f 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 g ；w h i c hc a l la l s o p r o m o t et h ed e v e l o p m e n to fo t h e rr e l a t e d l i n g n i s t i c s a san a t u r a ll a n g u a g e ，c h i n e s eh a st h em o s te s s e n t i a lc h a r a c t e r sl i k et h eo t h e rn a t u r a l l a n g u a g e s ，s oi t sn e c e s s a r yt om a k e f u l lu s eo fa n da b s o r bm a t u r el i n g u i s t i ct h e o r i e sf o rc h i n e s e s y n t a xp a r s i n g m e a n w h i l e ，c o n s i d e r i n gt h ep a r t i c u l a r i t yo fc h i n e s e , i t su n w i s et oi e u s et h e e x i s t e dt e c h n i q u e s ，s oi t sw i s ea n dn e c e s s a r yt or e s e a r c ha n dd e v e l o pn e wa n d c o m p a t i b l ec h i n e s e s y n t a xp a r s i n gf r o mt h ep o i n to ft h ec h a r a c t e ro fc h i n e s ei t s e l f , c o n d u c t e db yt h ea d v a n c e d l i n g u i s t i c st h e o r i e s t h ek e m e l w o r ko f t h i sa r t i c l ec a nb eg e n e r a l i z e dt ot h r e ea s p e c t sa sf o l l o w s ： ( 1 ) c o m p a r i s o n sa n ds y n t h e s i sa r ed r a w nf r o ms o m ee x i s t e da l g o r i t h m sa n dm o d e l sa b o u tt h e s y a t a xp a r s i n g b a s e do nt h ee x i s t e dr e s e a r c ht h e o r i e s ，i m p r o v e m e n t so nc h i n e s es y n t a xp a r s i n g h a v e 咖e i lb ya d o p t i n gm e t h o d so fb o t hb o t t o mu pa n dt o pd o w n ，w h i c hh a v ee n h a n c e dt h e e f f i c i e n c ya n dt h ep r e c i s i o no fa n a l y s i s ( 2 ) as e to fu s u a lc h i n e s es y n t a xl i b r a r yi sd e s i g n e da st h er e s e a r c hb a s i sa n das e to fp a r to f s p e e c ha n dp h r a s e sm a r k e rs e t sa r ec o n f i r m e da c c o r d i n gt oa c t u a la p p f i c a t i o n s w h a t sm o r e ， a n o t h e rs y n t a xr u l eh b r a r yb a s e do nc o n t e x t - i r r e s p e c t i v ea r ed e s i g n e da c c o r d i n gt ou s u a ls y n t a x e s ( 3 ) o n ep r o t o t y p es y s t e mf o rc h i n e s es y n t a xp a r s i n gi sa n a l y z e d , d e s i g n e da n da c h i e v e d , w h i c hi sc o m p o s e do ft h r e em o d u l e s t h e ya r ep a r t i c i p l em o d u l eb a s e d0 ns u i t e da l g o r i t h mo f m a x i m a lw o r dl e n g t h ，p a r to fs p e e c hm a r k e rm o d u l eb a s e do ns t a t i s t i c a lm e t h o do ft r a i n i n go f r e l a t i v ef i e q u e n c y ，a n dt h es y n t a xp a r s i n gm o d u l e ，w h i c hb a s e do ni m p r o v e dc h a na n a l y s i s a l g o r i t h mr e s p e c t i v e l y t h ea n n o t a t e dc o r p u s - 一p f ro f p e o p l e sd a i l ym a d eb yi n s t i t u t eo fc o m p u t a t i o n a l l i n g u i s t i c so c l ) o fp e k i n gu n i v e r s i t yi su s e da st r a i n i n gs a m p l e si nt h i sa r t i c l e a c c o r d i n gt ot h e p a r to fs p e e c ha n dp h r a s e st a g g e ds e t sa n dt h es y n t a xr u l el i b r a r ym e n t i o n e da b o v e ，t h ep r o t o t y p e s y s t e mf o rc h i n e s es y n t a xp a r s i n gi s a c h i e v e di nv i r t u eo fv c + + 6 0 ，w i t hw h i c hs m a l l s c a l e - 大连理工大学硕士研究生学位论文 c 1 1 i n e s et e x tt e s t sa r ec a r r i e do u ti i lo r d e rt ov a l j d a t et i l ee f f i c i e n c ya 1 1 df e a s i b i l i 哆0 ft h ei m p r o v e d a l g o f i t h mm e n t i o n e da b o v e k e yw o r d s ：t e np r o c e s s i n 嚣c m n e s es y n t a e t i ea n a i y s i s ；c h a r ta l g o r i t h m ；s y n t a e f i e p a r s e r ；s y n t a xs t r u c t u r e 独创性说明 作者郑重声明：本硕士学位论文是我个人在导师指导下进行的研究工 作及取得研究成果。尽我所知，除了文中特别加以标注和致谢的地方外， 论文中不包含其他入已经发表或撰写的研究成果，也不包含为获得大连理 工大学或者其他单位的学位或证书所使用过的材料。与我一同工作的同志 对本研究所做的贡献均已在论文中做了明确的说明并表示了谢意。 作者签名：日期：巧7 j ，如 大连理工大学硕士研究生学位论文 大连理工大学学位论文版权使用授权书 本学位论文作者及指导教师完全了解“大连理工大学硕士、博士学位论文版权使用 规定”，同意大连理工大学保留并向国家有关部门或机构送交学位论文的复印件和电子 版，允许论文被查阅和借阅。本人授权大连理工大学可以将本学位论文的全部或部分内 容编入有关数据库进行检索，也可采用影印、缩印或扫描等复制手段保存和汇编学位论 文。 作者签名： 导师签名： 绋经 肆 2 亟年陵月主立日 大连理工大学硕士研究生学位论文 l 绪论 1 1 问题的提出 语言文字是信息的首要载体。我们日常工作中的信息，绝大部分是以语言文字表达、 记载、传播和交换的。语言现象看似简单，实际上却反映了人类智慧中最复杂也最本质的 特点。自然语言理解的研究不仅仅是一种方法和工具，而且对我们了解人类语言的奥秘、 开启人类的智慧之门有着重要的影响。因此，随着计算机和i t c m c t 的推广应用，由数据 处理、信息处理发展到知识处理，对语言文字处理要求的深度和广度越来越高。可以认 为，一个国家的语言文字的信息处理水平和处理量基本上代表了这个国家进入信息社会的 程度，其语言文字信息的处理能力直接关系到它在网络社会和网络经济中的国际竞争能 力。目前，网络社会和网络经济正以我们难以预料的速度在全世界发展，其阻碍发展的首 要瓶颈问题就是自然语言的处理问题。网络社会也是人类社会，网络经济也是人类经济， 需要以自然语言作为社会交际工具，一旦基于网络的自然语言处理问题得到突破，网络社 会和网络经济将会突飞猛进i l j 。 自然语言理解是人工智能的一个研究分支，经过几十年的研究，计算机处理自然语言 的理论基础日趋成熟，应用范围也越来越广，初步形成了面向各种不同应用和研究的技术 体系。 句法分析在自然语言处理领域中具有十分重要的地位，同时它也是公认的一个研究难 题。汉语不同与其他西方语言，有许多特殊之处，吸收其它语言研究成果的时候需要结合 汉语的特点研究。目前，汉语主要按照词、句子和篇章三个层次来开展研究，其中句子的 处理在三个层次中具有承上启下的作用，所以句子处理是一个中心课题。就目前来说，句 子处理以自动分词为基础，以句法分析和语义分析为核心。 目前国内很多有代表性的句法分析系统的汉语句法分析模块都是通过改进已有的经典 句法分析算法设计的，不少己在实践中取得了很好的效果1 2 j 。在这中间，传统的基于规则 的方法又占了主导地位。这是因为基于规则的方法从汉语句子最本质的特征出发，例如构 词法、词组构造法、造句法等，从宏观上总结出句法规则。无论汉语的旬式结构多么自 由，其中蕴涵的最基本的规则是相对稳定的。规则易于表达汉语句子成分的构成规律。其 次，经过长时间的发展和不断改进，这类方法已较为成熟，应用在一些实用化的系统中有 较高的效率。 朱国华：文本信息处理中汉语句法分析方法研究 句法分析就是应用句法规则和其它知识，将输入句子中的词之间的线性次序变换成语 法树那样的数据结构。本文将对一个句子进行句法分析的过程分成：分词、词性标注、句 法树生成几个阶段。 1 1 2 国内外研究现状 1 2 1 问题背景与相关工作概述 根据我们的句法分析系统完成的工作的需要，分别按照分词、词性标注、句法分析三 个部分来介绍。 1 。分词的研究现状 汉语的形态不丰富，书面语的单词基本没有形态的变化，在这种情况下，汉语词法分 析的主要任务是进行单词的自动切分。词是语言中最小的独立运行单位，利用计算机把汉 语的一个句子的切分之后，才可以对汉语开展进一步的分析，因此，汉语的自动分词是汉 语语言理解的基础和前提。 目前采用的分词方法大体上分为如下几种1 3 1 ：最大匹配方法、反向最大匹配方法、逐 词遍历法、设立切词标记法、最佳匹配法、有穷多层次列举法、二次扫描法、基于词频的 统计的分词方法、基于期望的分词方法、双向扫描法、专家系统方法、最少分词词频选择 方法、神经网络方法等。同时各个研究机构也已经实现多个分词系统，例5 1 1 4 1 ：清华大学 s e g 分词系统、清华大学s e g t a g 系统、复旦分词系统、北大计算语言所分词系统等。 并且分词系统需要得到合理词库的支持，词库中的词需要进行词性标注或者语义标注，注 咀是什么词性，出现的概率有多大等等。分词系统使用词库进行汉字字符串的匹配，从而 得到一系列的词语。在建立词库方面，也要探索一种科学的方法，目前，词汇主义己成为 当今语言学研究的倾向之一，在整个语法理论中词库的地位已变得越来越重要了。 2 词性标注的研究现状 词性标注是对切分出的每介词根据其在句子中的作用标上其相应的词性，也是自然语 言处理的基础。 国外对英语语料库的自动词类标注研究可以分为以下几个阶段【5 - 7 1 ：7 0 年代初，主要 采用了基于规则的处理方法。其代表是t a g g i t 系统它主要利用了3 3 0 0 条上下文框架规 贝l j ( c o n t e x tf r a m er u l e s ) 对1 0 0 万词次的b r o w n 语料库进行了自动词类标注，处理正确率达 到了7 7 。七十年代末到八十年代初，随着经验主义方法在计算语言学研究中的不断流 行，基于统计的词类排歧方法开始得到应用。1 9 8 3 年的语料库标注系统c l a w s 最先采用 了s h a n n o n 的噪声信道模型思想进行词类自动标注。通过利用b r o w n 语料库的正确标注语 大连理工大学硕士研究生学位论文 料训练参数，达到了9 6 的正确率。从此以后，随着正确标注语料数量的不断增长和统计 处理技术的不断完善，基于统计的方法在英语语料库的自动词类标注器设计中占有了主导 地位。 相比之下，国内对汉语语料库的词类标注研究则起步较晚。近几年来，清华大学和山 西大学对基于统计的汉语语料库自动标注方法进行了一些研究和探索，提出了一套用于汉 语语料库标注的词类标记集，标注正确率也达到了9 5 左右1 8 1 。但由于训练语料规模的限 制( 约2 0 万字) ，并没有进一步进行大规模汉语语料库的标注。 目前，通过研究者不断的探索已经形成一些比较完善的标记集和一套标注规范： 1 北大人民日报语料库词性标记集f 9 】： 2 北大2 0 0 2 新版词性标记集【1 叫； 3 清华大学汉语树库词性标记集1 1 1 】； 4 中国科学院计算所词性标记集【1 2 】： 5 美国宾州大学中文树库( c h i n e s ep e r mt r e e b a n k ) 讵 性标记集【1 3 】： 3 句法分析的研究现状 早期的句法分析工作始于2 0 世纪5 0 年代，1 9 5 0 年w e a v e r 设计实现了一个以简单 “查字典”为基础的机器翻译原型系统，该系统的失败使人们认识到机器翻译的过程需要 更高水平的知识表示方法，由此展开了句法分析的研究【1 4 i 。目前，句法分析的研究大体分 为两个途径，基于规则的方法和基于统计的方法，这里主要着重介绍基于规则的方法。 在句法分析的研究中，基于规则的方法一直是句法分析的主要方法旧。从5 0 年代开 始，出现了一些有代表性的以规则为基础的系统。5 0 年代末到6 0 年代初，c h o m s k y 的转 换语法和形式理论为下一代的自然语言处理提供了一种新的解决方案。如s a d s a m 利用 c h o m s k y 形式化理论生成的可以处理大约1 7 0 0 个词和有限的英语语法的句法分析器，但 s a d - s a m 存在着低效率及对词汇和语法过多的限制。 6 0 年代自然语言处理的主要技术是关键词和模式匹配方法。比如b a s e b a l l 系统、s i r 系统、s t u d e n t 系统都采用了在文本中查找简单的模式或者某种正则表达式的方法【。模式 的特点是：凡是模式中包含的语言现象都可以得到较好的处理，一旦遇到模式中没有考虑的 语言现象，则做缺省处理，缺省的效果往往较差。因此在处理大领域的语言问题时，模式 的方法难以胜任。 7 0 年代初，w o o d s 提出了转移扩张网络法( a r g u m e n t e dt r a n s i t i o nn e t w o r k s ) ，增加了 正则表达式的能力，同时克服了用有限状态机表达上下文无关文法时存在的限制，然而 a t n 方法严格依赖于特定的应用领域，移植非常困难。 朱国华：文本信息处理中汉语句法分析方法研究 在这期间，上下文无关文法( a 1 g ) 由于有高效的分析算法而成为广泛使用的自然语言 句法分析方法。但是c f g 处理自然语言时有生成能力过强的缺陷，使用它进行句法分析 容易产生多种有歧义的分析结果。 自此以后，国内外学者相继研究一系列基予规则的改进算法，以提高句法分析的正确 性。近年来，国内很多研究人员结合汉语特点通过改进国外的一些成熟高效的句法分析算 法开发了很多实用化的汉语句法分析器，他们主要使用两种算法旧：l r 分析算法、c h a r t 分析算法。也有一些学者吸收两个算法的优势来达到追求高效率的分析算法的目标。下面 是它们的优缺点对比，参见表1 1 ： 表1 1 c h a r t 算法与l r 算法的比较 t a b l e1 1a c o m p a r i s o nb e t w e e n c h a r ta n dl r a l g o d t h m c h a r t 算法l r 算法 空间效率高时间效率比较高 优点较好的增量化性质不易产生较多的冗余 具有直观灵活的特点 时间效率低空间效率低 缺点 冗余较多不具有增量化性质 由此可见，使用c h a r t 算法开发句法分析器具有一定优势。因为在c h a r t 算法中，一 种很常用的优化技术是b e s t f i r s t 技术 1 8 1 。其主要思想是在分析调度器( a g e n d a ) 的控制下， 每次尽可能选择最佳的成份边进行组合扩展，从面迅速得到句子的最佳分析树，极大地提 高了分析效率。由于基于这个机制，更方便了消歧方法的引入。 1 2 2 汉语句法分析面临的困难和常用的解决策硌 1 2 2 1 汉语句法分析面临的困难 有人把世界上的语言分成孤立语、曲折语、黏着语、复杂语四种类型，汉语是孤立语 的代表，俄语是曲折语的代表。曲折语的特点是严谨，表现为主语与谓语，形容词修饰语 与中心语的组合有严格的一致关系。动词对它所支配的宾语也有特定的要求，而孤立语的 特点是缺乏词形变化，语法规则较为灵活。 4 大连理工大学硕士研究生学位论文 作为一种孤立语( 又称分析语) ，汉语的根本特点是缺乏严格意义上的形态标志和形 态变化。同西方语言相比，汉语的句法分析将面临以下困难p j ： 1 汉语缺少形态标志，汉语的句子组成通常依赖虚词和词序，而不靠形态变化。但是 虚词在很多场合下并不是必不可少的，常常被省略掉；而灵活的词序又使得汉语的词类与 句子成分之间不存在简单的一一对应的关系。结果，汉语中的同一个句法成分可以由属于 不同词类的词来充任，同一个词在句法结构中又可以作不同的句子成分，形式上却没有任 何不同的标志。因此，汉语的词性兼类问题更为突出、更难解决。 2 词语边界识别是汉语句法分析首先要解决的问题。由于汉语的书写习惯是基于字 的，在汉语文本中，词与词之间除了标点、分段等符号外，没有其它显性的界限标志。要 分析汉语的句法结构，第一步要做的就是如何识另词语的边界。 3 如何在句法歧义消解中引入词汇，特别是语义信息。上述分析表明，汉语句法结构 歧义产生的根本原因之一就是句法分析中缺乏足够的语义信息。因此，引入语义模式是解 决汉语句法歧义的重要途径之一。 4 知识获取问题是汉语句法分析实现大规模开放应用的瓶颈之一1 2 ”。汉语可以利用的 语言资源相对匮乏。同英语相比，汉语语言资源包括可计算的机器可读词典( m r d ) 和熟 语料建设相对滞后，特别是经过句法标注的大规模汉语树库，这在一定程度上阻碍了汉语 句法分析的发展。 1 2 2 2 常见的消减歧义的方法 歧义的自动化解可以说是句法分析的主要任务，常见的歧义化解方法有三种： 1 一基于结构的歧义化解 基于结构的歧义化解【2 2 】根据造成不同意义的语法结构的特点，给不同的结构确定不同 的优先级，从而确定哪一个意义的可能性最大。这是一种最简单的歧义化解方法，它不需 要任何语义学和上下文的信息，基于结构的歧义化解方法中最著名的两个原则是： f 1 ) 向右结合：一个语法成份优先附着于一个己存在的最低的语法非终结符节点。 ( 2 ) 最小附着：一个语法成份趋向附着于一个己存在的非终结符结点，从而使得该附 着所需要使用的语法结点最少。 向右结合原则对于英语这种倾向于右结合的语言来说，有定的应用价值，但是汉语 右结合的倾向性并不明显，左结合和右结合存在的比例不相上下，因此对汉语而言，右结 合原则意义不大。 朱国华：文本信息处理中汉语句法分析方法研究 2 基于规则的歧义化解 一些专家对基于规则的歧义化解做了详细的研究，详细的分析了各种不同的歧义结 构，并具体给出了各种不同歧义结构的化解规则。然而基于规则的方法存在以下缺陷 2 3 l ： ( 1 ) 需要人工构建，工作量大，同时还可能引入错误和不一致性。 很难覆盖所有的语法歧义。 ( 3 ) 规则的方法的引入是一种硬限制 a r dc o n s t r a i n ) ，但就句法分析而言，采用软限 制( s o f tc o n s 扛a i n ) 似乎更好，保留某些不符合规则的结构，对以后的分析有好处。 3 基于统计的歧义化解 基于统计的歧义化解方法，主要从统计意义上赋予各种结构一个分值，分析程序根据 分值选择一个最优的结构。 1 2 3 汉语句法分析研究的发展趋势和实际意义 汉语句法分析的研究一直是汉语处理领域的研究重点。在汉语句法分析方面，中国科 学院计算技术研究所、清华大学、北京大学等著名院校的专家学者，从语法理论到实际应 用的不同角度对汉语的句法分析进行了研究和探讨，并取得了部分成果【”。但是，由于汉 语本身的特点，与英语句法分析研究所取得的长足进展相比，汉语句法分析的研究还很薄 弱。 目前，统计的方法是句法分析研究的主流技术，汉语句法分析的研究也仍然以统计方 法为主。尽管英语句法分析已经出现了许多句法分析模型，但汉语的语言特点又要求研究 人员在借鉴已有句法分析模型优点的同时，根据汉语的特殊要求进行特殊处理。 汉语是一种分析型语言，汉语的分析过程是一个语法知识、语义知识以及常识性知识 公用的过程。如何在语料中表示句子中蕴涵的复杂知识，如何使用机器学习的方法获取这 些复杂的不同层次的知识，并把它应用于句法分析也是一个热点问题。通过知识工程师书 写包含语义、语言学常识等的规则，将基于规则的方法与基于统计的方法结合成为句法分 析研究的必然p j 。 句法分析算法是实现句法分析模型的基础，构建的句法分析模型是否是可行的，最终 由句法分析算法决定【2 6 】。因此，在根据汉语的特点构建适合汉语分析的句法分析模型时， 还需要根据模型的要求，研究相应的句法分析算法。如何满足句法分析模型的要求，实现 高效的句法分析算法也是一个需要研究的问题。 经过以上分析表明，句法分析在自然语言处理领域中具有十分重要的地位，同时它也 是公认的一个研究难题。句法分析的好坏影响了句子进行语义的分析。汉语作为自然语言 的一种，具有自然语言所共有的最本质的东西，因此汉语句法分析有必要借鉴和吸收成熟 大连理工大学硕士研究生学位论文 的语言学理论。同时，由于汉语的特殊性，决定了汉语句法分析不可能照搬现成的方法， 必须从汉语自身特点出发，以先进的语言学理论为指导，研究和开发适合汉语的句法分析 技术。 因为汉字是种图形文字，它的信息特征比拼音文字复杂得多。因此实现中文信息处 理更困能。但是，汉语是中国及世界范围内的主要交际工具和信息载体，使用计算机进行 中文信息处理既是步入信息化社会的需要，也是衡量国家综合实力及其现代化程度的一项 重要指标。特别是当前n t e m e t 迅速发展，在面向二十一世纪的网络通讯时代，以文本信 息的智能化处理为对象的语言工程，已经成为i 蓍际关注热点。另一方面，当前使用的国际 互连网以英语为主导语言，在一定程度上限制了中国用户在网络上进行信息交换和共享资 源的能力。因此对中文信息处理理论和技术的研究是迫切而需要的。本课题的研究在中文 信息处理中具有重要的实际应用意义。 1 3 本文的研究思路以及研究工作 本文的内容组织如下： 第一章是对汉语的特点、句法分析相关技术的发展概况、研究背景、发展趋势和实际 意义做了详细的介绍。 第二章汉语句法分析模型与分析算法，介绍了形式语法体系，统计语言学模型及其模 型之间的比较，以及句法分析模型的结构设计方法。详细介绍了线图分析方法及其不足， 并改进了传统的线图分析方法，采用将自底向上与自顶向下的分析方法相结合的分析方法 提高分析效率。 第三章句法分析系统的总体结构设计，是对实现系统的整体结构设计的说明，以及设 计原则和实现的关键技术的介绍。 第四章句法分析系统的设计与实现，说明了系统的设计路线和功能模块，并从分词和 词性标注模块、句法分析模块分别描述了具体的实现方法，最后进行了小规模试验，验证 了改进的分析算法可行有效。 第五章结论和展望，对本文做的工作的总结和对未来的展望。 目前，主要完成了以下几项工作： 1 设计了一套常用的汉语句型库作为研究基础。 2 报据实际应用，确定了一套词性标记集和短语标记集。 3 根据常用的句型，设计了一套基于上下文无关的语法规则库。 4 实现了基于最大词长匹配算法的分词模块。 朱国华：文本信息处理中汉语句法分析方法研究 5 实现了基于改进的线图分析算法的句法分析模块和基于相对频率训练的统计方法的 词性标注模块。 6 实现了改进方法，主要体现在将自底向上与自顶向下的分析方法相结合。 以上任何一方面都关系到一个句法分析器实际性能。分析效率和正确率是衡量分析器 性能的重要指标。要提高分析的正确率就必须完善句法分析规则、句法分析方法和歧义消 解机制，而这往往会降低分析的效率，反之亦然。不同的系统对这两个指标有不同的要 求，关键要在两者之间找到合理的平衡。 大连理工大学硕士研究生学位论文 2 汉语句法分析模型与分析算法 为了实现句法分析器，需要预先赋予计算机两项内容。 第一个是语法。通常语言学教材中的语法是面向人的，为了让机器分析句子，需要让 机器知道这些语法，这种面向机器处理的语法也称为形式语法，它是规定语言中允许出现 的结构的形式化说明。其中很重要的是如何表示形式语法，即形式语法的表示方式。 第二个是语法分析算法。机器依据形式语法来识别和分析句子并决定其结构的方式。 在计算机自然语言处理中，我们更多地关心句法分析器的算法，因为句法分析器比识别器 具有更强的能力，能够提供更多的信息。句法分析算法还应包括其中采用的数据结构的构 造，在分析之后如何表示句子的句法结构等各个方面。在通常的人类自然语言中，未经分 析的句子是线性的符号串表示。 2 1 汉语句法分析模型 美国语言学家乔姆斯基在5 0 年代创造了形式语法，形式语法是乔姆斯基用数学方法 研究自然语言和人工语言的语法理论。 句法分析一般都依赖于某种语法体系。语法体系的形式丰富多彩，各种语法形式都有 各自的特点。不同的语法体系产生的句法结构形式不尽相同。最常见也最直观的句法结构 形式是句法树。其他主要的形式有依存关系树( 依存语法、范畴语法) 、有向图( 链语 法) 、特征结构( h p s g 、l f g ) 等等。 2 1 1 短语结构语法与乔姆斯基层次体系 2 1 1 1 1 短语结构语法 为描述短语结构语法，需要首先介绍重写规则。重写规则是一种形式化表示方法，可 以用来描述规则，例如：s n pv p 就是个重写规则。其中，s 代表一个句子，n p ， v p 表示两个短语，n p 表示一个名词短语，v p 表示一个动词短语。该规则的意思是说左 边的符号s 所代表的项可以被合乎语法的替换成右边符号所代表的两个项，即被重写为右 边两项的组合。 一个形式语法可以包含若干条重写规则。通常一些重写规则的集合用p 来表示。除此 之外，组成一个完整的形式语法还有另外几个要素：其一是所谓终结符号集合，用t 来表 示，一个终结符号代表一个这样的项，它在此语法中不能再被重写为其他项的组合，通常 是该形式语法所描述的语言中的词汇的语法类别( 如n ，v ，a d j 等等) ，或者就是该语 朱国华：文本信息处理中汉语句法分析方法研究 言中使用的词汇；其二是非终结符号集合，用n 来表示，一个非终结符号代表一个这样的 项，它在此语法中可能再被重写为其他项的组合，如果上述终结符号指的是语言中的词汇 本身，那么非终结符号也包括词的语法类剐；其三是个特殊的非终结符号s ，表示句 子。因为句法分析针对的单位均为句子，因而s 就十分重要，它通常是对句子进行句法分 析的开始或结束符号。 这样，一个完整的用来描述一种语言的形式语法就可以表示为四元组 ，r ，n ，s ，p ，且 t n n - - - ( d ，即一个符号不能同时既是终结符号又是非终结符号。词汇表v = t u n ，v 表示 由v 中的符号所构成的全部符号串( 包括空符号串$ ) ，而v + 表示v + 中除之外的一切 符号串的集合。p 中的每条规则形如：a b ，其中a 扩，b v ，且a b 。 短语结构语法的基本思想是【镐】：句子是由短语结构组成的。从整体句子开始，到句子 符号, 亭y e j 的产生，可以通过短语结构规则一步步推导出来。所以用短语结构语法来对句子 进行句法分析，就意味着是寻找一个从起始符到该句子的推导，这个推动到通常表现为一 棵句法树。如果句子是歧义的，也就是说它存在几种推导，那么将有几颗句法树。举例来 说，我们有下面一部语法： s n p n p n n p r n p a d j n p v _ p - v n p r 一我 v 一喜欢 a d j 一红 n 一苹果 那么句子“我喜欢红苹果”的推导是： s n pv p rv p rvn p rva d jn 我va d jn 我喜欢a d jn 我喜欢红n 大连理工大学硕士研究生学位论文 我喜欢红苹果 它所对应的句法树是： s 芦p 火 r v 少l a d j n lj 我喜欢红苹果 图2 1 句法树示意图 f i g - 2 1s k e t c hm a po fs y n t a xt r e e 这就是用短语结构语法分析句子的简单模型。 2 1 1 2 乔姆斯基层次体系 所谓乔姆斯基层次体系( c h o m s k yh i e r a r c h y ) ，指的是乔姆斯基定义的四种形式语 法，这四种语法所产生的语言依据包含关系构成了严格的层次体系【矧。乔姆斯基层次体系 第一次严格地描述了形式语法、语言和自动机之间的关系，在数学、计算机科学和语言学 建立起了一道沟通的桥梁。 乔姆斯基层次体系的四种形式语法类型分别是： 1 正则语法( 3 型语法) 正则语法分为左线性语法和右线性语法。 在左线性语法中，所有重写规则必须采用如下的形式：a b t 或a t ，其中，a ，b 是非终结符号，t 为终结符号。 而在右线性语法中，所有重写规则必须采用如下的形式：a t b 或a t 。 正则语法是乔姆斯基层次体系中生成能力最弱的一个，一些常见的语言现象都不能用 正则语法来生成。个简单的例子是任意符号“x ”两边成对匹配添加括号，通过不断嵌 套的方式可以实现一系列句子： x ， ( x ) ，( ( x ) ) ，( ( ( x ) ) ) 为了生成这种语言的句子，当生成到“x ”时，必须知道前面已经生成了多少个 “( ”，以便能生成同样数量的“) ”相匹配。而对于正则语法，无论是左线性语法还是 右线性语法，都只能独立的生成“x ”某一侧的符号，无法进行匹配。 朱国华：文本信息处理中汉语句法分析方法研究 在自然语言中，也存在着类似的匹配模式。例如：“如果a ，那么”、“因为 a ，所以”等句子结构( 其中a 表示一个符号串) ，通常都需要匹配出现，这种模式 也可以进行不断的嵌套形成复杂句子： 如果a 那么，如果如果a 那么那么， 同样，当生成到a 时，也必须知道已经生成了多少个“如果”，以便能生成同样数量 的“那么”相匹配。 2 上下文无关语法( 2 型语法) 在上下文无关语法中，每一条规则都采用如下的形式：a x ，其中a 是非终结符 号，x v 。这种规则的应用不依赖于a 出现在什么上下文环境中，因此称为上下文无关 语法。 上下文无关语法比正则语法具有更强的生成能力，能反映更多的自然语言现象。但 是，还有一些自然语言现象不能由上下文无关语法来描述，有些情况下，一条重写规则的 应用是受上下文制约的。 3 上下文有关语法( 1 型语法) 在上下文有关语法中，每一条重写规则都是这样的：x y ，其中x ，y v ，且y 的长 度( 即符号串中的符号个数) 总是大于或等于x 的长度。 上下文有关语法的重写规则也可以这样来表示：a y x _ z ，其中a 是非终结符号，y e v ，x ，z e v ，在这种表示中，可以很明显的看出所谓上下文有关的含义来：如果a 出 现在上下文xz 中，即前面紧挨着符号串x ，后面紧挨着符号串z ，则a 可重写为y 是有 上下文约束的。 4 无约束短语结构语法( o 型语法) o 型语法对规则没有任何约束，其定义的语言可能不是递归的，因而就不可能设计一 个程序来判另u 一个输入的符号串是否是0 型语法中的一个句子，所以，0 型语法很少被用 来处理自然语言。 乔姆斯基四种形式语法所导出的语言具有以下关系：语法的型号越高，对重写所附加 的限制也就越多，所以3 型语法是2 型语法的一个子集，2 型语法是1 型语法的个子 集，依此类推，有0 型语法_ d 1 型语法三2 型语法三3 型语法。从语法生成能力来看，0 型语 法最强，1 型到3 型依次递减，3 型最弱。 大连理工大学硕士研究生学位论文 表2 1 乔姆斯基层次体系四种形式语法的比较 t a b l e 2 1 a c o m p a r i s o n a m o n g f o u r k i n d s o f o f m o d a ls y n t a x o f c h o m s k y h i e r a r c h y 层级语法识别自动机产生式规则形式例子 0 型不受限短语结构语法图灵机口? p 线性有界自 1 型上下文敏感语法a a p ? d 第 矿矽p 动机 2 型上下文无关语法下推自动机app a ”扩 a ? a b 3 型正规语法有限状态机 口 apa 图2 2 乔姆斯基层次体系的四种形式语法 f i g 2 2f o u rk i n d so fm o d a ls y n t a xo fc h o m s k yh i e r a r c h y 在上述乔姆斯基层次体系的四种语法中，上下文无关语法是计算语言学的重要研究对 象。由于其描述能力强，足以描述自然语言中的大部分结构，同时又是可递归的，可以构 造有效的句法分析器来进行句子的分析，因此，目前大多数计算机处理用的语法都是基于 上下文无关语法的。 朱国华：文本信息处理中汉语句法分析方法研究 2 1 2 常用的统计语言学模型的比较 语言是一种符号系统，而任何符号系统都包含形式和意义两个方面1 3 0 】。因此语言模型 就是对语言的形式和意义的描述。最简单的语言模型就是列出该语言的所有句子，而高级 语言模型可以描述语言的结构和意义。 语言模型分为两种类型：概率型语言模型和基于语法的语言模型。概率型语言模型f 概 率型语法m ) 将传统语法对一个“串”是否为一个合乎语法的句子的肯定或否定的判别推 广为概率的判别，于是由概率型语法产生的语言是“串”上的概率分布p 伍iu ，其中x 是任意一个“串”，l 是一个特定的语言。概率型语法m 是对这种分布的描述，它产生的 语言是h m ) 。一般隋况下，认为表示“分布”的语言和表示“描述”的语法是一致的，即 p ( xil ) = p ( xi _ ( m ) ) 。语言学家用语法描述语言，并认为所有人类语言的构造都是有层次 的，汉语语言的层次结构为：字一词一词组一句子一段落，即由字组合成词，由词组合成 词组，由词组组合成句子，由句子组成段落。每一层级的组合都存在某种限制，这就是词 法和句法。乔姆斯基将这种层级结构以规则的形式表示出来，而规则的集合就是语法。 统计语言建模是本文进行汉语基本短语分析的重要基础，因此下面对现有的语言模型 进行论述，以提出适于本研究的策略。 1 n 元文法模型 如果假定，在一个语句中第i 个词出现的概率，条件地依赖于它前面的n - 1 个词，即 将一个词的上下文定义为该词前面出现的n - 1 个词，这样的语言模型就叫做n 元文法统计 模型( n - g r a m ) 。设符号串s 由l 个符号v r l ，w 2 ，w l 组成，s 发生的概率为 l p ( s ) i p ( w 1 ) p ( w 21w o p ( w 3 w 2w 1 ) p ( w l w 1 w l - 1 ) 丌p ( w ；1 w 1 w i 。) ( 2 1 ) o n 元模型假设每个词w i 的出现只与它前面相邻的n - 1 个词w i - q , t - 1 卜w i 1 有关，即 上 p ( s ) = 几p ( w i l w l w ) r l = p ( w 1 ) p ( 、2iw 1 ) p ( w n - 1w l w e - 2 ) 丌p ( w j t w l w )( 2 2 ) 皇l 于 n 元模型相当于n 1 阶马尔可夫模型。 2 n p o s 模型 如果将词按功能进行分类，得到的分类就称为词性( p a n o f - s p e e c h ) 。这样，一个语句 中第i 个词类出现的概率，条件地依赖于它前面的n - 1 个词类，由此得到