（模式识别与智能系统专业论文）汉语句法分析方法研究.pdf

摘要 句法分析是自然语言处理中的关键性问题之一，其主要任务就是自动识别句 子的句法结构，即句子包含的句法单位以及这些句法单位相互之间的关系。句法 分析问题的解决对于机器翻译、自然语言理解、信息抽取和自动文摘等自然语言 处理系统都有着极其重要的意义。在基于统计的句法分析方法中，最关键的两个 问题是句法分析算法和歧义消解模型的设计，他们决定着句法分析系统的效率和 分析正确率。本文从事的工作则从这些方面入手，实现了一个高效的中文句法分 析器，主要研究工作如下： 1 在句法分析算法方面，对传统的句法分析算法从处理策略，算法的时间 和空间复杂度等方面进行了综合分析和比较。并在此基础上，详细研究了c h a n 算法的一个改进算法“角色反演算法”。针对该算法，本文在两方面提出进 一步的改进。首先改进了算法中采用的静态数据表的构造方法，使得该算法能处 理的原始输入词性标记从最小的句法单元词，扩展到更高一级的句法单元 短语和句子，以很小的额外空间消耗为代价，提高了算法的处理能力和效率。 然后，引入规则的概率信息对静态表排序，有利于后续分析的搜索和剪枝过程。 2 针对复杂长旬句法分析的困难，通过分析标点符号在长旬构成上的作用 和规律，针对长旬提出了一种分层的句法分析方法。该方法把标点符号分为分割 标点和普通标点两类，根据分割标点将复杂长旬分割为句子单元序列独立进行第 一级分析，然后把第一级分析得到的结果作为第二级分析的输入，最终输出结果 为完整的句法分析树。另外，通过提取含有所有两类标点符号的文法规则，在一 定程度上帮助了句法结构歧义的消解。实验证明该算法大大降低了长句分析的时 恻复杂度，并且比传统的一遍搜索方法的正确率和召回率均提高了7 。 3 在歧义消解模型方面，在传统的概率上下文无关文法( p c f g ) 模型的基 础上，提出了一个包古内部成分结构信息的p c f g 模型，并进一步引入中心词信 息，得到包古内部结构成分信息和中心词信息的词汇化p c f g 模型。并且，本文 提出了根据内部成分结构标记确定中心词的方法，此方法比传统的中心词确定方 法具有更高的f 确性和直观性。 a b s t r a c t p a r s i n gi so n eo ft h ef u n d a r n e n t a lp r o b l e m si nn a t u r a l l a n g u a g ep m c e s s i n g h sm a i n t a s ki st oa u t o m a t i c a l l yr e c o g i l i z et h es y n t a c t i cs t r u c t u r eo fs e m e n c e s m o s to fn a t u r a l l a l l g u a g e 印p l i c a t i o n ss u c ha sm a c h m et r a i l s l a t i o n ，n a t u r a l l a l l g u a g eu n d e r s t a n d i n g ， i n f o r m a t i o ne x t r a c t i o na n da u t o m a t i cs u m m a r i z a t i o n 、帕u l db e n e n tf m mt l l ea c c u r a t e p a r s i n gr e s u l t s i nt h ep a r s i n ga p p r o a c hb a s e do nt h es t a t i s t i c a lm o d e l ，t h e r ea r et w o k e yi s s u e s ：p a r s i n ga l g o r i t 胁d e s i g n i n ga n dp a r s i n gm o d e l i n gf b rd i s a l l l b i g u a t i o n ， w h i c hd e c i d en l ee 街c i e n c ya n da c c i l r a c yo f ap a r s i n gs y s t e m t h i s 也e s i si sm a i n l yi n m e s ea s p e c t sa n dc o n s t r u c t sa ne 伍c i e mp a r s i n gs y g t e m t h em a i nc o n t r i b u t i o n sa r e s l l n l m a r i z e da sf o l 】o w s ： 1 1 1 1p a r s i n ga l g o r i t l l m ，m o s tm l d i t i o n a lp a r s i n ga l g o r i t l l m s 盯ea n a l y z e da n d c o m p a r e dm a i n l yi nt h ep r o c e s s i n gs t r a t e g y t i m ec o n s u m p t i o n a 1 1 ds p a c ec o n s u m p t i o n a r o l ei n v e r s ea l g o r i l h m ”w h i c hi sa ni m p r o v e dv e r s i o no f c 王l a r tp a r s i n ga l g o r i t h mi s s t u d i e dd e t a i l e d l 矿b a s e do n 也i sa l g o r i t ，t h i st h e s i sp r o p o s e dt w oa s p e c t so f i m p r o v e m e n t f i r s t l y ，t h es t a t i cm l et a b l e sa r ee x t e n d e d ，s om a t l eo r i g i n a li n p u to f t h ea l g o r i m mc a l le x t e n df 沁mw o r d st op h r a s e s 趾ds e m e n c e s i nt 1 1 i sw a y ，t 1 1 e p m c e s s i n ga b i l i t ya n de 伍c i e n c yo fm ea l g o r i t h mw i l lb ei m p r o v e d s e c o n d ly ，t h e p r o b a b i l i t i e so fg r a m m a rr u l e sa r eu s e dt os o r t 也em l et a b l e s ，w h i c hw i l la v a i l 出e l a t t e rp r u n i n g 2 i no r d e rt os o l v e 廿1 ed i 衔c u l 够o fp a r s i n gl o n gc h i n e s cs e n t e n c e s ，t h eu s a g ea n d f h n c t i o no fc h i n e s ep u n c t u a t i o n s 盯es t u d i e di ns 螂t i cp 盯s i r 培趴dah i e r a r c h i c a l p a r s i n ga p p m a c hi sp r o p o s e d i td i 仃e r e r n i a t e sf r o mm o s to ft h ep r e v i o u sa p p r o a c h e s m a i n l y i nt 啪a s p e c t s f i r s t l y c h i n e s e p u n c t u a t i o n s a r cc i 鹊s 讯e da s d i v i d e p u n c t u a t i o i l sa i l do r d i n a r y o n e s l o n gc o m p l e xs e n t e n c e sw h i c h i n c l u d et h e c a t e g o r i e so f d i v i d e d p u n c t u a t i o i l sa r eb r o k e ni n t os l l i t a b l eu n i t s ，s ot h ep a r s i n gw i l l b ec a r r i e do u ti nt 、v os t a g e s t h i s d i v i d e - a n d m l e s t i 砒e g yg r c a t l yr e d u c e sm e d i f f i c u l t yo fa c q u i r i n gt h eb o u i l 捌e so fs u b s e n t e n c e sa i l ds y n t a c t i cs t r u c t u r eo f s u b s e n t e n c e so rp h r a s e ss i m u l t a i l e o u s l yi no n c e - l e v e lp a r s i n gs t r a t e g yo fm o s to f p r e v i o u sa p p r o a c h e s s e c o n d l y ag r a n u n a rm l e ss y s t e mi n c l u d i n ga up u n c t l l a t i o n si s b u i l tt ob eu s e di np a r s i n ga n dd i s 撇b i g u a t i n gs e n t e n c e s e x p e f i m e n t ss h o wt h a to u r 印p r o a c hc a l ls i g n 谪c a n t l yr e d u c et h et i m ec o n s u m p t i o na n dn 啪b e r so fa r n b i g u o u s e d g e so ft r a d 撕o n a im e 出o d s ，a n d 也ea c c u r a c ya n dr 以lr a t eo ft f a d i t i o a a lm e t h o di s i n c r e a s e db y7 b yo u rm e t h o d ，w h c np a 商n gi o n gc o r 叩1 e xs e n t e n c e s 3 i np a r s i n gm o d u l ef o rd i s a m b i g u a t i o n ，b a s e do nac l a s s i c a lp r o b a b i l i t yc o m e x t - 矗e g r a m m a r ( p c f g ) m o d u l e ，t l l ei n n e rs t n l c t u r ei n f o m l a t i o ni sj n c o i p o r a t e di n t op c f g m o d u l et of b n nan e wm o d u l e t h eh e a dw o r di n f b r n l a t i o ni sn l ! 也e ri n d d u c e di n t o a b o v em o d u l e t 1 1 e n al e x i c a lp c f gm o d u l ew h i c hi n c l u d e si n n e rs t r u c t u r e i n f o m l a t i o na n dh e a dw o r di n f 0 珊a t i d ni sc o n s t n j c t e d a tl 踮t ，t 1 1 i sm e s i sp m p o s e da n e wm e t l l o dt of i n dt h eh e a dw o r d s ，w l i c hi ss i m p l ea 1 1 dh a sg r c a t l yh 追h e ra c c u r a c y t h a nm o s to f o t h e rm e t h q d s 独创性声明 本人声明所成交的论文是我个人在导师指导下进行的研究工作及取得的研究成果。尽我所知， 除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成果。与 我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确地说明并表示了谢意。 签名导师签名：日期：丝堕! 塑 关于论文使用授权的说明 本人完全了解中国科学院自动化研究所有关保留、使用学位论文的规定，即：中国科学院自 动化研究所有权保留送交论文的复印件，允许论文被查阅和借阅：可以公布论文的全部或部分内 容，可以采用影印、缩印或其他复制手段保存论文。 ( 保密的论文在解密后应遵守此规定) 签名 导师签名蛳良 日期： 一r ，、翻 第一荜绪苦 1 1 引言 第一章绪言 句法分析( s ”t a c t i c p a r s i n g ) 是自然语言处理研究中的关键技术之一，句法 分析结果的好坏直接影响到对自然语言句子的理解。而自然语言理解又是机器翻 译、自然语言理解、信息抽取、信息检索以及语料自动处理等众多语言处理技术 的基础。在当前条件下，句法分析在语言信息处理系统中仍然具有举足轻重的作 用( 俞士汶，1 9 9 7 ) 。同时，句法分析中所使用的技术还可以用于解决生物信息 识别领域诸如r n a 分子结构探测( s a k a l 【i b a r ae ta 1 ，1 9 9 4 ；g r a l e ，1 9 9 5 ) 等与句法 分析相似的问题。因此，自然语言句法分析技术的研究具有重要的理论意义和实 用价值。 1 2 句法分析的任务和目标 自然语言句法分析的任务是利用语言知识自动识别句子的语法结构，即甸子 所包含的句法单位以及这些句法单位相互之间的关系。 相对于计算机语言等人工语亩，自然语言存在着很大的不确定性。这种不确 定性造成了自然语言句法歧义现织的普遍存在，歧义消解问题成为句法分析的主 要难题之一( 冯志伟，1 9 9 6 ) 。因此，对于同一个语句，通常存在着多个语法上 正确的分析结果( 尽管很多结果在语义上是没有意义的) 。在这种情况下，句法 分析的任务就包括从多种分析结果中选出正确的一种。然而，即使对于一个简单 的自然语言句子，也可能存在着上百万种不同的语法上正确的分析结果，这就使 得无论从排歧方法、分析精度，还是从时间、空间复杂度上，自动句法分析都面 临着巨大的挑战。 因此，评价一个句法分析方法优劣的标准主要在于两方面：分析的效率和分 析结果的正确率。而这两方面的性能是由句法分析算法、句法歧义消解模型以及 搜索策略所共同决定的。句法分析的相关研究工作则是从这些方面展开，以获得 大覆盖度高效率高精度的鲁棒性句法分析方法为目标。 一 堡堡塑堡坌堑塑婆竺窒 1 3 句法分析的相关研究综述 自然语言句法分析工作始于2 0 世纪5 0 年代，经过研究者们五十多年的努力， 这项研究已经获得长足的进展。然而，在通往实际应用的路上仍然遍布着荆棘。 在英语方面，目前报道的最好的句法分析器的正确率为9 0 ( b i k e l ，2 0 0 4 ) ， 而汉语方面最好的结果还不到8 0 ( l e v yc t a l ，2 0 0 3 ) ，因此对于句法分析的研 究仍然任重而道远。 迄今为止，句法分析的研究大致经历了两个阶段：以规则方法为主导的阶段 和以统计方法为主导的阶段。 1 3 。l 基于规则的方法 2 0 世纪5 0 年代木乔姆斯基的文法理论的提出，奠定了基于规则方法的基础。 在此后3 0 多年的时间里，出现了一些有影晌力的基于规则的系统，例如早期的 b a s e b a l l 系统、s i r 系统、s t u d e n t 系统以及后来的转移扩张网络法等。 在中文处理方面，( z 1 1 0 u ，2 0 0 0 ) 提出了一种典型的基于规则的句法分析方 法。该方法采用短语结构的局部分析和依存分析相结合的方法。在句法分析的过 程中，首先通过短语分析来对句子进行适当地抽象，减少处理时的句子结点数目， 最后通过手工书写的规则来进行依存分析。他共定义了11 类短语和1 7 类依存关 系，制定了1 0 0 0 多条短语识别规则和3 0 0 多条依存分析规则。 基于规则的方法主要通过人工组织语法规则、人工建立知识库，解决句法结 构歧义的方法是通过一些条件约束和检查来实现的( 越l e n ，1 9 8 7 ) 。这种基于 规则的方法在某一限定领域的应用是可行的。然而，规则方法本身存在着较大的 缺陷，主要表现在： 1 规则刻画的知识颗粒度过大，无法使用有限的规则来刻画几乎是无限的自然 语言现象，而且很难处理自然语言结构的不确定性。 2 不能保证各种自然语言规则问的相容性和一致性，随着系统中规则数量的增 加，规则之间常常会发生矛盾和冲突。 3 规则的获取是一个十分繁琐的过程，它完全依赖于开发规则的工程师的语言 知识和经验，因此获取一套完整而周详的大规模语法规则非常艰难。 基于上述原因，单纯使用规则方法无法解决处理大规模真实文本对自然语苦 的高度复杂性和歧义性。因此，进入2 0 世纪9 0 年代以后，句法分析的主流方法 已从规则方法转向以统计方法为代表的经验主义方法。 第一章绪吉 1 3 2 基于统计的方法 统计方法以数学模型和大规模语料库为基础，其核心思想是建立数学模型以 表述某一种语言现象，然后在大规模语料库中对模型进行训练，使其满足已经获 知的经验知识，然后用训练好的模型对于未知的现象进行预测。几乎所有基于统 计的方法都可以归结到上述的框架中去。与传统的基于规则的方法相比，统计方 法有下述优点： 1 它不依赖于人主观的先验知识，这也是本文认为统计方法最重要的优点。大 规模语料库实际上和规则一样，都是一种知识的表征形式，不同的是语料库 相比规则而言，有更强的独立性和客观性。 2 统计方法将知识和算法分离。前面已提过，规则往往是由某方面的专家针对 某一特定的应用所书写的指导原则，而同一个语料库可以为多种算法、多种 应用服务，它是很独立的知识库。这样语料库的建立和完善可以和算法的设 计并行，不仅节省了人力物力，7 也给一些标准化测试提供了基础。另外这项 优点给基于统计方法的系统的维护和更新带来了很大的方便。随着应用的扩 展，我们往往要考虑到新的语言现象，这时基于统计方法的系统只需要用更 大的语料库重新训练一下模型就可以了，而基于规则的方法则需要增加大量 的规则，而如上文以前提过的，这并非一件容易的事情。 3 统计方法通过语料库给每条语言规则加上概率值，使得语言规则的使用便有 了“柔性”，不再是“说一不二”、“非此即彼”。 近十几年来，随着计算机硬件设备的飞速发展，其单位存储和计算成本大幅 度降低，使一些基于大规模搜索和迭代的复杂算法能够在个人计算机上广泛地实 现和应用；雨随着行业信息化的普及和网络资源的迅猛膨胀，可用语料资源也大 为丰富，这一切给基于大规模语料库的统计自然语言处理方法的实现提供了必要 的硬件和软件环境。 在这种条件下，大规模地收集语料并用计算机处理成为可能，语料库的建设 和语料库语言学成为计算语言学新的分支而迅速崛起。作为统计句法分析基础的 树库的建设也获得巨大的发展。 在英语方面，以美国宾夕法尼亚大学开发的宾州树库( p e n nt r e e b a l l k ) 较为 著名，该树库从1 9 9 1 年第一版发布以来的十余年时间里，经过不断地维护和修正， 目前已达到几百万字的规模，被公认为具有较高的一致性和标注准确性，是目i j i 研究英语句法分析所公认的标注训练集和测试集。 在汉语方面，巾文的树库建设在近年来也到了广泛的重视和巨大的发展。如 美国宾夕法尼亚大学的宾州中文树库，目前发布的树库规模为l o 万汉语词。台 湾中研院的中文句结构树库，增加了对句子语义信息的描述，如句子的施事 ( a g e n t ) 和受事( p a t i e n t ) 等，目前发布的树库规模为约2 4 万汉语词。由中文 汉语句法分析方法研究 语言资源联盟( c h i n e s el d c ) 建设的树库( t c t9 7 3 ) 的规模为1 0 0 万汉字，是 到目前为止规模最大的中文句法树库之一( h 卸：w 、v w c h 证e s e l d c o r g ) 。 大规模树库的建设和发展为统计句法分析提供了很好的知识获取来源和测 试平台。当前，大多数成功的统计句法分析方法都是利用语料库来获得分析所需 要的知识。其基本思想是：1 、使用语料库作为唯一的信息源，所有的知识( 除 了统计模型的构造方法) 都是从语料库中获得的。2 、语言知识在统计意义上被 解释，所有的参量都是通过统计处理从语料库中自动习得的( 周强，1 9 9 6 ) 。 概率方法的广泛应用是统计方法的显著特点之一。概率方法的本质就是利用 不同语言现象的统计分布来描述语言使用的一般模式，并由此选择输入句子的最 可能的分析结果，更适合大规模文本的自然语言句法分析。根据采用信息的不同， 可以把统计方法分为下面五类。 1 3 2 1 概率上下文无关文法 概率上下文无关文法( p c f g ) 模型是最典型的一种基于结构的概率方法。 2 0 世纪8 0 年代以来，国内外学者对p c f g 进行了深入的研究，包括对p c f g 参 数的推导和学习以及分析算法的研究。国外的研究起步较早，研究得也比较广泛。 ( l a r ie ta 1 ，1 9 9 0 ) 首先采用l n s i d e o u t s i d e 算法自动估计p c f g 参数：( b l a c k e ta 1 ，1 9 9 2 ) 等人以自底向上的c k y 算法总结出p c f g 的各种算法，包括 i n s i d e o u t s i d e 算法、v i t e r b i 算法等：( s t o l c k e ，1 9 9 5 ) 将e a r l e y 算法与p c f g 结 合，给出了概率化的e a r l e y 算法。此外，( c o r a z z a ，1 9 9 4 ) 对如何利用p c f g 进 行句法分析和计算句子的概率进行了深入细致的研究。国内的很多学者对p c f g 用于汉语句法分析也做了大量的工作。( 王挺，1 9 9 7 ) 和( 周强，1 9 9 8 ) 用 i n s i d e o u t s i d e 算法研究了汉语的p c f g 自动推导，在匹配分析机制上实现了无指 导的e m 迭代训练算法。( 朱胜火等，1 9 9 8 ) 对原有的g l r 分析表加以改造， 能够利用分析过程的控制结构来计算有关的概率，实现了一种有效的概率上下文 无关文法的分析算法。 虽然p c f g 具有形式简洁、参数空间小和分析效率高的优点，但是它忽略了 消歧所需的上下文信息，因此其消歧能力有限。针对p c f g 的问题，出现了下面 几种模型：增加结构信息的概率模型，包含词汇依存关系的概率文法，引入语义 信息的模型和依据历史的模型，分别在下面几节详细介绍。 1 3 2 2 增加结构信息的模型 实验表明，结构信息的引入有助于提高句法分析的结果。 第一章绪者 ( b r i s c o e 吼a 1 ，1 9 9 2 ) 将合一语法同概率广义l 建表( p r o b a i l i s 矗cg e n e r a l i z e d l r ) 算法结合，以增加p c f g 的上下文描述的能力。( s i m m o n se tc 1 1 9 9 2 ) 首 次提出上下文依存文法( t 1 1 ec o n t c x t d e p e n d e mg m m m a r s ，c d g s ) ，并基于c d g 针对英语受限子集实现了一个英语句法获取和分析系统。( s c h a b e s ，1 9 9 2 ) 提 出了一种概率树邻接文法( p m b a b i l i s t i ct h e a d j o i n i n gg r a m m a r s 。p t a g s ) 。这 种文法在上下文无关文法中的标准替换规则的基础上，增添了一种附加原则，以 提高规则的上下文敏感性，并且还改进了】ns i d e o u t s i d e 算法使之能无指导地估 计p t a g 概率。( s u e ta 1 ，1 9 9 5 ) 提出了一种基于简单上下文相关文法的厶，r 。 模型，该模型将归约项目左边m 个符号和右边个符号作为规则的上下文，同 时认为紧随移进的归约动作是高度相关，而不考虑相邻动作的约束。 面向数据的句法分析技术( d o p ) 由( b o de ta 1 ，1 9 9 7 ；2 0 0 3 ) 首先提出，后逐 渐深入和发展。该处理技术建立在包含大量语言现象的树库基础上。把经过标注 的树库看作一个语法，从树库中抽取部分树并构造一个部分树的数据库。当处理 新的语言现象时，通过重新组合这些部分树的方式来构造句法分析树。d o p 方 法与人们对句法分析的直觉相一致，但对给定的句子，其推导的搜索空间与句子 长度成指数增长。b o d 应用m o n t e c a r l o 技术在多项式时间内找到最优的句法树， 但实际的句法分析的时间消耗仍然很大。 在国内，( 张浩，2 0 0 2 ) 研究了p c f g 独立性假设的局限性，并在p c f g 的基 础上提出了三个逐层递进的与结构上下文相关的概率句法分析模型，它们考虑了 分析树当中每个派生结点的结构上下文条件。( 盂遥，2 0 0 3 ) 设计了一个包含复 杂特征的统计句法分析模型，综合考虑了上下文无关规则的结构特性、所处的上 下文环境即复杂特征信息。 1 3 2 3 基于词汇的概率方法 基于词汇的句法分析方法根据包含在句子中的词的特性来区分句子的不同 句法分析候选。 基于词汇的句法分析的一种思路是考虑词汇之间的搭配关系某些词的某 特殊组合比各自的其它偶然出现的组合更容易在句子中出现，也就是说，这些词 汇的同现概率比较高。同现概率越高的词汇，越容易出现在同一句法结构中。这 种同现关系通常采用互信息进行量化。 ( m a g e r r n a l le ta l ，1 9 9 1 ) 提出了一种基于广义互信息模型的短语自动划分 算法。它依赖于下面的一个假设：绘定句子中的短语成分边界可以通过分析句子 中词类n g r 锄组合的互信息值加以确定。它的实验结果说明：这种方法对于短句 的分析效果较好，而对并列结构以及长句子的分析则不够理想。 汉语句法分析方法研究 然而，单纯依靠词性信息很难获得理想的句法分析结果。因此，将词汇语法 理论和概率结合产生出词汇语法的概率版本是件很自然的事情。 ( a l s i m w ie ta 1 ，1 9 9 6 ) 提出了种基于核心词的概率句法分析模型，他认 为一棵句法分析树由核心词及它的左右修饰成分组成。 ( g o o d m a l l ，1 9 9 7 ) 在概率上下文无关文法中引入了复杂特征，他规定所有 规则前项只有两个结点，即二分形式的规则。每个非终结结点由一组属性值对 表示，允许表示词汇的合一关系，以及远距离的依赖关系。 ( c o l l i n s ，1 9 9 9 ；c h a m i a l 【，1 9 9 7 a ；1 9 9 7 b ) 等人采用中心词驱动的概率模型的 方法，是近年来句法分析词汇化的典型代表。其基本思想是：句子是围绕着中心 词来组织的，规则中的每一个非终结符结点与其核心词相联系，通过规则的概率 体现核心词之间的依存关系。c 0 1 1 i n s 于1 9 9 9 年得到的句法分析结果是目前公认的 英语的最好结果之一。本文将在第四章详述这种模型的构造思想。 在汉语方面，( b i k e l ，2 0 0 0 ) 在4 0 0 0 句宾州中文树库上实验了c 0 1 l i n s 的头 驱动句法分析模型和一个概率1 a g 句法分析模型的汉语句法分析效果。 ( 付国 宏，2 0 0 0 ) 结合汉语的特点，把语义信息引入到汉语句法分析中，提出了一个基 于词义的概率上下文文法( l p c f g ) 的汉语句法分析模型，构造了一个以词义搭 配模式为品质因数的b e s t - f i r s t 线图算法。 1 3 2 4 基于历史的模型 基于历史的文法最早由( b l a c ke ta 1 ，1 9 9 2 ) 提出，其核心思想是把句法分 析过程看作自顶而下、从左向右的非终结结点的扩展过程，非终结结点的扩展相 当于一系列的产生式使用过程，产生式的概率依赖于句子中当前分析点的整个分 析历史。( j e l i n e ke ta 1 ，1 9 9 2 ) 描述了一个相似的历史模型，不同在于b l a c k 采 用的是手工书写的规则，而j e l i n e k 采用的规则是从树库中自动提取的。 ( m a g e 咖a n ，1 9 9 4 ；1 9 9 5 ) 是j e l j n e k 工作的延续，他采用的决策树方法使得系统 性能得到了较大提高。( r a m a p 蚓k l l i ，1 9 9 7 ) 采用最大熵的方法构造了一个基于 历史的模型。 1 3 2 5 语义辅助的句法分析模型 语义辅助的模型把语义信息引入到句法分析模型当中。 ( s e k i n ee t a l ，1 9 9 2 ) 描述了一个由语义辅助的句法分析器，它分析的过程 考虑由核心词、语法关系以及谓词论元所组成的三元组。 6 第一麝绪言 ( j o n e se ta 1 ，1 9 9 2 ) 设计的句法分析器在扩展结点的过程中不仅计算了规 则的句法概率，而且考虑了其语义概率，语义以谓词论元的形式表示。 ( a l s h a w ie ta 1 ，1 9 9 4 ) 描述的句法树由语法关系、属性以及语义搭配等组 成，并给出了多个句法分析结果。 综上所述，句法分析的研究表明，句法结构歧义的消除必须依赖多种信息， 句法分析过程中勺上下文结构信息，弼犯信息以及语义信息都有动于歧义结构静 消解。但如何很好地练合利用这些信息，需要根据所处语言的特点以及资源情况 而定。 1 4 汉语句法分析的研究现状、难点和解决方案 如前文所述，目前已知最好的汉语句法分析效果同其他西方语言相比还有一 定的差距。而造成这种差距的主要原因之一是汉语语言本身的特点增加了对其进 行分析的难度。汉语句法分析的主要困难可以总结为如下几点： 1 、汉语的词性兼类问题非常普遍。汉语是一种孤立型语言，缺少形态标识，汉 语韵句子组成通常依赖虚词和词洋，而不靠形态变化，僵是虚词在汉语句子 中并没有实际的意义，常常被省略掉；而次序又相当灵活，使得汉语的词类 与句子成分之问不存在简单的一一对应关系，相同意思的句子就会对应多个 结构，也就是多个词序的甸子。所以，汉语中的同一个语法成份可以由属于 不同词类的词来构成，同一个词在句法结构中又可以作为不同的句子成份。 因此，汉语的词性兼类问题更为突出且难于解决( 俞士汶，t 9 9 8 赵铁军， 2 0 0 0 ) 。 2 汉语句法分析存在着一个特殊的分词问题。由于汉语句子的书写方式是以字 为单位的，在汉语文本中，字与字之间除了标点、分段等特殊符号外，没有 其它明显的界限标志。句法分析主要是以词为最小单元进行处理的，因此在 分析汉语的句法结构之前，首要的任务就是对汉语文本进行自动分词处理， 其切分的好坏必然影嫡句法分析的效果。 3 ，汉语句法结构分析歧义产生的一个重要原因是单纯依靠词类信息无法解决 一些固有的歧义问题。引入词汇信息、语义信息是解决汉语句法歧义的重要 途径之一。 4 。大规模、包含多种信息的知识库的建立是汉语句法分析实现大规模开放应用 的瓶颈之一。由于汉语的复杂性和需要更多的预处理，目前己经建立的并可 以利用的语言资源与英语相比，相对比较匮乏。汉语语言资源中可计算的完 备的机器词典，尤其是大规模的语义词典和熟语料的建立相对滞后，这在一 定程度上阻碍了汉语句法分析的发展。 汉语句法分析方法研究 正如上述问题的存在，要彻底解决这些问题，并实现句法分析研究的最终目 标还有很长的路要走。国内外学者们对此进行了不断的探索和研究，提出了在当 前条件下解决上述问题的可能的方案和发展方向，主要可以归纳为如下几点： 1 统计方法已成为主流技术，尽管英语方面出现许多较为成熟的统计模型，可 以为汉语分析所借鉴，但汉语的语言特点使得研究人员在借鉴其优点的同 时，还应该结合汉语特点进行特殊处理。 2 实现多方法、多特征或多知识源相结合的混合模型。这是句法分析研究发展 的必然，是为了更好地解决句法分析过程的歧义问题。大量的实验证明，单 一方法、单一知识很难有效地解决句法分析歧义问题。p c f g 模型在句法分 析中得到广泛的研究，但是为了提高算法的分析能力，如何描述超出p c f g 模型的上下文约束的概率模型是目前句法分析研究的热点之一( 冯志伟， 1 9 9 6 ) 。 3 句法分析算法是实现句法分析模型的基础，模型的可行性，最终由分析算法 决定。因此，如何提高分析算法的效率，这是决定句法分析能否实际应用的 关键技术之。 4 汉语是一种分析型语言，汉语的分析过程是一个语法知识、语义知识和常识 性知识共用的过程，充分利用所有可能的复杂知识，通过书写包含语义或者 语言学常识的规则，将基于规则的方法和基于统计的方法相结合成为句法分 析研究的必然。 1 5 论文研究内容 1 5 1 研究内容 本文对自然语言句法分析的理论和相关方法进行了研究，重点研究三方面内 容：句法分析算法、基于统计的句法分析模型以及针对复杂长旬的分析方法。这 三个方面是相互独立而又互相联系的。句法分析算法保证在时间允许的条件下， 能够获得所有可能的分析树结构。复杂长句分析的困难和句法结构歧义消解的困 难，是影响句法分析系统效率和正确率的两大难题。针对这两大难题，分别通过 对长旬引入标点符号的分层处理方法和设计合适的统计分析模型得到一定程度 的解决。 笫一帝绪言 1 5 2 论文总体结构安排 本文其余章节的安排如下： 第二章主要研究句法分析算法，对主要的经典句法分析算法从算法处理策 略、时间和空间复杂度等方面进行了综合的分析和比较。并且在此基础上，详细 研究了c h a n 分析算法的一个改进算法“角色反演算法”。针对该算法，本 文在两方面提出进一步的改进：一个是利用文法规则的概率信息进行分析表的排 序，另一方面改进了算法中采用的静态数据表的构造方法，使得该算法能处理的 原始输入词性标记从最小的句法单元词，扩展到更高一级的句法单元短 语和句子，以很小的额外空间消耗为代价，提高了算法的处理能力和效率。然后 介绍了我们采用的两种搜索和剪枝策略：o n e _ b e s t 策略和n b e s t 搜索策略，对每 一级子树不仅保留最大概率结果，并且保留满足条件的n 个最优结果，使得算 法最终的结果在保证获得最大概率树的同时获得n - b e s t 的结果。 第三章针对复杂长旬句法分析的困难，通过分析标点符号在长句构成上的作 用和规律，针对长旬提出了一种分层的句法分析方法。该方法把标点符号分为分 割标点和普通标点两类，根据分割标点将复杂长旬分割为子句和短语序列独立进 行分析，然后经过子树合并和第二级分析，最终获得完整的句法分析树。另夕 ， 提取含有所有两类标点符号的文法规则在一定程度上帮助进行句法歧义的消解。 实验证明该算法大大降低了长句分析的时间复杂度，并且比传统的一遍搜索方法 的正确率和召回率均提高了7 。 第四章主要研究统计分析和歧义消解模型，首先分析主要的句法歧义类型， 然后介绍统计模型中的主要理论和问题，然后对现有的主要模型从利用的知识颗 粒度大小的角度进行了分类和比较。最后，在一个传统的概率上下文无关模型的 基础上，提出了一个包含内部成分结构信息的模型，并进一步引入中心词信息， 得到包含内部结构成分信息和中心词信息的词汇化p c f g 模型。并且，本文提出 了根据内部成分结构标记确定中心词的方法，比传统的中心词确定方法具有更高 的币确性和直观性。 第五章是结论和展望。旨在对论文工作进行总结，并指出下一步研究可能的 方向。 汉语句法分析方法研究 2 1 引言 第二章句法分析算法的研究 句法分析的最终目标是对于给定的句子，生成一棵带有句法功能标记的短语 结构树，句法分析的过程也可以理解为句法树的构造过程。因此，句法分析算法 是实现句法分析目标的基础和关键。 由于句法分析算法的任务是要在一定的时间内，找到满足一定语法条件的所 有可能的分析结果，因此，算法的处理能力和时间、空闯效率就成了设计算法所 要考虑的关键因素。本章则从这些方面入手，研究已有分析算法的搜索策略和处 理方法，并对一种典型的分析算法进行了改进。 2 2 句法分析算法概述 目前使用的主要句法分析算法是由处理人工语言的句法分析算法发展而来 的，由于人工语言的文法是上下文无关文法，所以句法分析算法的研究主要基于 上下文无关文法。但后来用于自然语言处理的实践表明，这些算法经过适当的改 进，能够很好的应用于自然语言句法分析当中。其中，有代表性的典型句法分析 算法包括l r 算法、g l r 算法( 又叫t o i l l i t a 算法) 、e 础e y 算法、c y k 算法以 及图表( c h a n ) 算法等，下面分别阐述这几类算法的思想。 标准l r 分析算法是一个典型的基于下推自动机( p d a ) 原理的分析算法，用 下推自动机来描述l r 算法的工作过程为：自动机的读头自左至右扫描输入串， 一边把输入符号移入栈内，一边检查位于栈顶部的一串符号是否与某产生式右部 相同，如果相同就把栈顶的符号替换成相应的产生式左部非终结符，这种替换就 称之为归约，归约出来的非终结符作为句子成分；如果不相同就继续向栈内移入 符号，并继续判断直至输入串结束或者拒绝接收( 此时说明输入句子不符合l r 文法) 。l r 算法包含四个基本动作：移进、归约、接收和报错。l r 分析器又被 称为“确定性下推自动机”，它不允许回溯，只能分析无歧义的人工文法，难以 直接用它分析有歧义的自然语言。 ( t o m i t a ，1 9 8 5 ) 对标准l r 算法进行改进，提出了g l r ( g e n c r a l i z c d l r ) 算法，和l r 算法一样，g l r 算法( 也叫t o m 妇算法) 也是一种移进一归约式 ( s h i f r c d u c e ) 算法。g l r 算法对传统l r 算法的改进主要体现在( 刘群，2 0 0 2 ) ： l o 第二章f d 注卦析簟法的嗣眦 1 ) g l r 分析表允许有多重入口( 即一个格子罩有多个动作) 这样就克服了 传统i 且算法无法处理歧义结构的缺点： 2 ) 将线性分析栈改进为圈分析找处理分析动作的歧义( 分叉) ： 3 ) 采用共享子树结构来表示局郝分析结果，节省空间开销； 4 1 通过结点合并，压缩局部歧义。 e a r l e y 算法在1 9 6 8 年由e a d e y 提出( e a r l e y l1 9 6 8 ) ，是一种典型的臼项丽 下的分析方法。该算法的中心思想是首先构造一个关于上下文无关文法规刘的分 析歹0 裘，这就相当于把对输入句子的所有可能的分析状态构造出来，然衙再根据 分析列表列出分柝结果。 c y k 算法是由c o 豳e 、芟a s a m i 和y o u i l 叠c r 提出的( k a s 啪i ，1 9 6 5 ) ，它是一 个自底而e 的列表性质的分析算法，标准c v k 处理的规则必须表示为乔姆斯基 范式的形式。c y k 算法采用广度优先的搜索策略，是一种并行算法不需要回 溯，没有冗余的操作。所谓“表”是用柬存放分机中闻结果的数据结构。 圈表( c h a m 算法使用线圈结构作为关键数据结构，用来存故分析，巾间结果的 数据。c h 槲分折算法非常灵活，通过修改c h a r t 算法中的分析肇略，根容易模 拟很多种形式的其他算法，实现自顶向下的分析、自底向上的分析以及左角分析 算法等等。这也是c h a r t 分析算法得到广泛应用的原因之一( 刘群，2 0 0 2 ) 。本 文采用的分桥算法也是基于c h a n 算法的，我们将在本章静后面部分详细介缨该 算法。 2 3 句法分析算法的比较 在这一节壁，我们对r 节介绍的典型算法，结合形式语言当中的其它主要分 析算法作一概要的总结，将各种分析方法分门别类。采用不同的分类标准，从不 同的角度对这些方法进行一些比较。 首先，按照处理输入串的方式把这些方法分成两大类：蠢方向盼和秃方向的 分析方法。有方向的分析方法从输入串的头部( 从左向右) 或尾部( 从右到左) 一个一个地处理语法符吼如l r 算法、g l r 算法等。无方向豹分析方法可以在 输入串的任何一个位置上进行分析处理，因此它需要先将整个输入串读入存储区 中，典型的例子如c y k 算法。 其次，从语法产生式的应用上，我们可5 蔓继续分出两类；囊底向l 帮自强向 f 的分析方法。自底向上的方法试图将整个输入串归约到语法的开始符，不断地 用产生式的左边代替输入串中与产生式右边匹配的部分，典型的如c y k 算法； 自项舟下的方法则试图从语法的开始符出