（计算机软件与理论专业论文）基于二元组合文法的概率消歧模型设计与实现.pdf

山东大学硕士学位论文 摘要 随着社会信息化迅速发展，自然语言处理作为人工智能的重要研究领 域之一。句法分析已成为自然语言处理中的关键问题，因此长期以来一直 是自然语言处理领域的重要课题。句法分析主要在机器翻译、信息抽取等 方面有着重要的意义，并能极大地提高系统的智能性和实用性。其主要任 务就是自动对句子进行句法分析，生成满足句法分析模型的所有句法分析 树。句法分析结果的好坏直接影响到系统的准确性。 由于汉语言自身的结构、语义复杂性，当前存在多种句法分析方法。 本文继承前人的些有效、经典的思想方法，结合汉语言自身的特点，在 二元组合文法的基础上提出了一种基于规则和统计相结合的汉语分析方 法。 句法分析算法是句法分析器的重要组成部分，它直接影响了句法分析 的准确性和时间效率。本文介绍了几种传统的句法分析算法，并且从工作 原理、时间复杂度、搜索策略等方面进行比较和分析。其中，重点介绍了 经典c y k 句法分析算法，首先，根据b c g 文法的特性将二元运算关系优 先级融合到算法中，实现了分析过程中的剪枝和一定程度上的歧义消解， 其最终产生的分析结果树的数量和花费的时间均明显低于传统的c y k 算 法。其次，本文的图算法以表格方式存储分析过程的中间结果，分析树可 以共享空间，降低分析算法的时间花费。并在此基础上对算法进行改进， 提出了基于二元组合文法的概率c y k 算法。 歧义消解是句法分析研究中的重点，本文针对歧义消解问题建立了概 率歧义消解模型。在传统的概率上下文无关文法模型的基础上，提出了一 个包含中心词信息、语义信息、二元运算关系信息、词间距以及从大规模 语料库中抽取出来的概率信息的消歧模型。本文使用基于动态规划思想的 t e r b i 算法在句法分析过程中动态剪掉不可能导致最优分析结果的无用 边，降低了分析算法的时间花费，同时记录下旬法分析的路径，反向回溯 输出了最佳分析树结果：采用最大似然估计的方法，为文法规则选择概率， 山东大学硕士学位论文 使得训练句子的概率最大：并改进分值计算方法，重新定义计算公式。 通过对系统的测试发现，该模型处理1 2 个字长内和1 6 个字长内句子 的句法分析准确率达到了7 2 4 和8 1 o ，能够较好的保证句法分析的准 确性。因此，本文所提出的基于二元组合文法的句法分析模型具有一定的 研究意义和实用价值。 关键词：自然语言处理：句法分析：c y k ：b c g ：歧义消解 i i 山东大学硕士学位论文 a b s t r a c t a sr a p i dp r o g r e s so fi n f o r m a t i o nt e c h n o l o 舒n a t u r a l l 锄g u a g ep r o c e s s i n g i sa ni m p o r t a n tr e s e a _ r c hf i e l do fa r t i f i c i a li n t e l l i g e n c e p a r s i n gi so n eo fm e f 吼i 锄e n t a lp r o b l e m si nn a t u r a l l a i l g u a g ep r o c e s s i n g ，s o “i s 锄i i n p o n a i l t p r o b l e mo fd o m a i no fc 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 m a c h i n et r a i l s l a t i o n a n da l l t o m a t i cs u m m 甜i z a t i o nw i l lb e n e f i tf r o ma c c u r a t ep 甜s i n gr e s u l t ，w h i c h c a ne n h 锄c et h ei n t e l l i g e n c ea n d 印p l i c a b i l i 锣o ft h es y s t e m s i t sm a i nt 嬲ki s t 0r e c o g n i z et h es t m c t u r eo fs e n t e n c e sa n dg e ta l lt h et r e e sw h i c hs a t i s 矽t h e p a r s i n gm o d e l t h er e s u l t s 甜f e c tt h ea c c u r a c yr a t e d u r i n gt 0s t m c t u r eo fc h i n e s ea n ds e m a j l t i cc o m p l e x i 饥t h e r ea r em 锄y p a u r s i n gm e t h o d i nt l l i sp a p e r w h i c hi n h e r i t ss o m ee a e c t i v e 锄dc l a s s i c a l t e c h n i q u e ，、eo 毹rn e w r e s e a r c hm e t h o db a s e do nr u l e 趾ds t a t i s t i c s 1 1 1 “st h e s i s ，w eb r i n gi nb i n 哪c o m b i n a t o r i a lq 锄m 盯( b c g ) ，、) v l i c h i sa d v a n c e db yx i a oy 抽ga tt l l es a m et i m e ，w ea d v 锄c ec o n c 印t i o no f b i n a 呵 o p e r a t i o nr e l 撕o n sa n db c ga r c h i t e c t l l r e p a u r s i n ga l g o r i t h m ，w h i c ha 蜀f e c t sa c c u r a c yr a t e sa l l dt h ee 衔c i e n c y i st h e i m p o r t 锄tp a no fa n a l y z e r d i s a n l b i g u 撕o n w ei n t r o d u c es o m et r a d i t i o n a l a l g o r i t h m s ， 锄da l l a l y z ea u l dc o m p a r et h et h e o t i m ec o n s u m p t i o n锄d p r o c e s s i n gs t r a t e g y w ei n t r o d u c e c l a s s i c a lc y kp a r s i n ga j g o r i t h m ，w e a d v a n c ep r o v e dc y ka l g o r i t h mb a s e db i n a 巧c o m b i n a t o r i a lg r a m m a rp a r s i n g f i r s t l y ，a c c o r m n gt 0m ec h a r a c t e “s t i co fb c gg r a m m a r ，m eb i n a d ，o p e r a t i o n r e l 撕o n sp r e c e d e n c ei sf u s e dt oa l g o r i 也mt 0d 0p r u n i n gi n l ep a r s i n g 锄dt o r e s o l v ed i s a n l b i g u 撕o n a l lo fm es p e n tt i m e 觚dr e s u l tt r e e si nc h a r tb 船e d b c gp a r s i n ga r el e s st l l 趾t r a d i t i o n a lc y ka l g o r i t h m s e c o n d l y ，a j le d g e s p r o d u c e di nt h ep a r s i n gp r o c e s sa r es t o r e db y at a b u l a rs t r u c t u r ei nt l l e a l g o r i t h mt or e d u c et h es p a c es p e n t d i s 锄b i g u a t i o ni s t h ei m p o n a n to fp a r s i n g b a s e do n ac l a s s i c a l i 山东大学硕士学位论文 p r o b a b i l i 够 c o n t e x t f r e e g r a m m a r( p c f g ) m o d u l e ， m ei n n e rs t m c t u r e i n f o m a t i o n ，h e a d 、0 r da n dp r o b a b i l i t ) ，i n f o r m a t i o ne x t r a c t i n gf r o mb 锄ki s i n c o r p o r a t e dt of o r man e wr n o d u l e w eu s ev i t e r b ia l g o r i t h mt 0p m n i n ga l l d a c q u i r et h eb e s ts y n t a c t i cp a r s i n gt r e e a tl a s t ，、v eu s ea l g o r i t h mt oc h o o s et h e p r o b a b i l i 锣o f t h er u l ei no r d e rt og a i nt h em a x i m a lp r o b a ：b i l i 锣 t h ee x p e r i m e n t a lr e s u l t ss h o wt h a tt h ep r e c i s i o na b o v e7 2 4 肌d8 1 0 d u r i n gp r o c e s s i n gs e n t e n c e so fl2a n d16 a ni na l l ，m ep a r s i n gm e t h o db a s e d o nb c gh a sc e r t a i nr e s e 孤c hm e a n i n g 肌da p p l i e sw o r t h i n e s s k e yw o r d 8 ： n a t u r a i l a n g u a g ep r o c e s s i n g ：p a r s i n g ：c y k ：b c g ： d i s a m b i g u a t i o n 原创性声明和关于论文使用授权的说明 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独 立进行研究所取得的成果。除文中已经注明引用的内容外，本论文不 包含任何其他个人或集体已经发表或撰写过的科研成果。对本文的研 究做出重要贡献的个人和集体，均已在文中以明确方式标明。本声明 的法律责任由本人承担。 论文作者签名：丕& j 墼。日期：2 盟基：生x 关于学位论文使用授权的声明 本人完全了解山东大学有关保留、使用学位论文的规定，同意学 校保留或向国家有关部门或机构送交论文的复印件和电子版，允许论 文被查阅和借阅；本人授权山东大学可以将本学位论文的全部或部分 内容编入有关数据库进行检索，可以采用影印、缩印或其他复制手段 保存论文和汇编本学位论文。 ( 保密论文在解密后应遵守此规定) 论文作者签名：椒导师签名：掷审期：衄 山东大学硕+ 学位论文 1 1 研究现状 第一章引言 句法分析( s y n t a c t i cp a r s i n g ) 1 】是自然语言处理中的关键问题，其主要 任务就是利用计算机自动识别句子中的句法结构，即生成一棵带有句法功 能标记的短语结构树，得到句子中包含的句法短语以及句法短语之间是如 何关联的。因此，句法分析结果的好坏直接影响到对自然语言句子的理解。 而句法分析又是机器翻译、信息抽取、信息检索以及语料自动处理等众多 语言处理技术的基础。当前，句法分析在汉语言信息处理系统中仍然具有 举足轻重的作用【2 1 。因此，自然语言句法分析技术的研究具有重要的理论 意义和实用价值。 自然语言与机器语言最显著的一个区别就是自然语言中存在大量的歧 义现象。由于自然语言中存在歧义现象，比如，词性歧义、结构歧义、语 义歧义等等，句法分析的研究也受到很大影响。句法分析可以归结为歧义 消解( d i s a m b i g u a t i o n ) 、划分问题( c h i l i l k i n g ) 和次生成问题 ( 岫d e r - g e n e r a t i o n ) 。消歧主要是消除存在于语法和语义等语言层次的歧义， 划分问题即句法分词，次生成问题是指人名、地名、机构名等命名实体的 识别【3 1 。在句法分析过程中，分词过程中会产生短语边界歧义、次生成的 过程中由于命名实体未识别也产生一些歧义问题。由此可见句法分析的三 个问题可以广义的看作歧义消解问题，句法分析可以看作是一个句法歧义 消解的过程。歧义消解的效果直接决定了句法分析的效率和准确度，所以 歧义消解是句法分析的核心问题。 经过多年的汉语歧义消解研究，虽然在一定程度上取得一定的成果， 但是从总体效果上来看存在着很多不足，还未能满足当前中文信息处理的 各种需要。在歧义消解方面，目前存在多种研究方法。从采用的策略方面 看，可以大致归为两类：基于文法规则的研究和基于统计的研究【4 】。 基于文法规则的句法分析系统是比较传统的一种分析方式。在这种方法 山东大学硕士学位论文 中，将句子用手工归纳的规则形式化描述出来，并建立规则库。文献【5 】在格 语法基础上提出了一种中心词驱动的分析方法。把汉语句子看成中心词和它 的附属成分组成的递归结构，利用中心词和附属成分的语义联系和约束关系， 对句子进行语义句法分析。文献【6 1 提出了_ 种生成具有复杂特征集的多 叉树( m m t ) 的汉语句法分析方法。它在短语结构语法的基础上，定义了汉 语句法结构。文献【_ 7 】实现了一种基于句法语义特征的汉语句法分析器。它将 语义信息加入句法规则中，使句法分析从一种符号推理变成了一种实体推理。 文献【8 9 】以二元组合文法( b c g ) 为语言模型的基础，提出了一种句法分析策 略：基于中心动词和其他成分间的二元运算关系实现了句子成分过滤，使用 语义驱动的二元关系确定汉语句子中各个成分之间的关系，同时还采用二元 运算关系优先级在句法分析过程中进行剪枝。 以上几种基于规则的分析方法都不同程度地将语义信息引入句法分析 中，同时采取了一定的手段来限制句法规则过强的生成能力，在一定程度 上解决了句法分析中的歧义消解问题。早期在语料库出现之前，句法分析 主要是基于文法规则的，而文法规则的获取完全依赖于知识工程师的语言 知识和经验。但是规则的获取和规则的完备性都是一个比较复杂、困难的 事情。同时，基于规则的方法对不合规范的句子、长词、生词等方面比较 脆弱。因此，单纯使用规则方法无法解决大规模真实文本的高度复杂性和 歧义性【1 0 】。进入2 0 世纪9 0 年代以后，句法分析的主流方法已从规则方法 转向以统计方法为代表的经验主义方法。 基于统计的分析方法，即面向语料库的方法，与基于规则的方法不同， 它不是人工编制句法分析规则，而是用统计的方法获得句法标注，将句法 标注作为语法规则存在于语料库中。文献 1 4 】介绍了一种基于语料库的汉 语句法分析系统。该方法采用依存语法，在句法分析时，根据输入句子的 每个词，搜索知识库，建立各个词之间的依存链。然后搜索所有可能的句 法分析树，边搜索边修剪，最后根据评价函数产生正确的语法树。文献【l l 】 用基于变换的方法标注中文句子词汇的句法功能。所谓基于变换的方法， 就是首先对训练语料库进行初始标注，然后将标注结果与正确的文本进行 2 山东大学硕士学位论文 比较，从中选出效果最好的变换，获取成为变换式的标注规则，然后用该 规则重新标注语料库，重复上述过程，每次循环得到一个新规则，直到没 有新的规则为止，从而完成规则的获取工作。在文献1 2 1 中，提出了一种以 d o p 技术为基本框架，同时利用基于相似的概率评估技术，实现汉语句法 分析的方法。其中，对于输入语句，首先需要经过词汇层与词性层两层初 选。然后对于已构建的知识源，获取输入语句的片段组合形式。最后，对 输入语句与初选结果进行相似性评估，完成输入语句的组合分析过程。文 提出了一种基于依存文法的融合语料库、规则方法和统计方法的汉语分 析模型c r s p 。该模型的特点是将依存文法分析看作是与词性标注过程等价 的一个基于统计的标注过程。文【1 4 】提出了利用局部优先信息对汉语分析算 法进行优化的新方法，通过利用从语料库中自动获取的结构优先关系数据 作优先判断依据。本方法的基本分析框架是在目前的汉语概率分析器中采 用的匹配分析算法【1 5 】，而局部优先信息则利用了从语料库中自动获取的结 构优先关系数据。此方法是目前的汉语概率分析器的整体效率提高了近 3 0 。 以上介绍的都属于基于统计的句法分析方法，概率方法的广泛应用是 统计方法的显著特点之一。概率方法的本质就是利用不同语言现象的统计 分布来描述语言使用的一般模式【1 6 】，并由此选择输入句子的最可能的分析 结果，更适合大规模文本的自然语言句法分析【1 7 1 。但是，统计的方法也存 在一定的缺陷：在某些情况下，难以避免时间、空间的组合爆炸，难以表 达语言的确定性现象，而且大批语料的标注需耗费大量的人力和财力等等。 1 2 歧义消解的困难 歧义消解是汉语信息处理的关键问题，直接决定了句法分析的有效性、 准确性以及实用性。由于基于规则的消歧已经遇到了文法规则描述性不完 备、文法规则冗余等瓶颈问题，基于文法规则和统计相结合的歧义消解方 法越来越成为消歧的研究热点。 目前，由于汉语言自身的复杂性、灵活多变性等特点，汉语的歧义消 山东大学硕士学位论文 解又有其特殊的困难，具体将面临以下困难【1 8 】： ( 1 ) 缺乏明显的特征标志，如单复数、时态等。同时，汉语中的同一个 在句法结构中可以以不同的句子成分出现，但是形态上没有标志区别，因 此，汉语的词性兼类问题很难解决。 ( 2 ) 分词识别是歧义消解的基础。由于汉语书写习惯，词与词之间除了 标点之外没有其它符号作为词或者短语的分界符。要进行歧义消解首先要 识别词语边界。 ( 3 ) 当前句法歧义产生的一个原因就是句法分析中缺乏足够的语义信 息，因此，引入语义信息是解决句法歧义的重要途径之一。 ( 4 ) 缺乏大规模标注的汉语语料库在一定程度上影响了歧义消解的发 展。 1 3 本文的创新点 经过对国内外歧义消解模型研究发现，已有的歧义消解方法主要存在 以下问题： ( 1 ) 歧义消解的自动化程度不高，需要人工获取大量文法规则，但仍然 难 以涵盖所有的语言现象。 ( 2 ) 无法避免由分词引起的歧义消解问题，并且大多数方法不能有效地 解决歧义消解问题。 ( 3 ) 通常只考虑了词法、句法在消歧中的作用，而忽略了短语概率信息。 针对以上问题和歧义消解中的难点，本文在杨潇【9 1 提出的基于二元组 合文法的句法分析系统的基础上，提出了一种基于规则和统计相结合的解 决方案。该方法采用概率模型，其基本思想是：在课题组原有的句法分析 系统上，采用概率c y k 算法计算得到给定句子的每一个分析结果的概率 值，并找到最有可能的分析结果即最佳分析树。系统中的词以及文法概率 均是从大规模语料库中抽取得到的。 针对真实句子和真实语料库进行句法分析的过程中遇到一些问题。本 4 山东大学硕士学位论文 文针对这些具体问题提出了一些解决方案，并取得一定的效果，提高歧义 消解的准确率。主要有以下几个方面： ( 1 ) 针对汉语的具体特点，使用了更适合描述以及计算的概率二元组合 文法( p b c g ) 。 ( 2 ) 在原有的句法分析系统上采用概率计算方法，从而达到消歧的目 的。 ( 3 ) 由于两个短语在各个句子中距离不同，得到的上层句法结构就有可 能不同，本文将词间距信息引入到概率模型中，达到消歧的目的。 ( 4 ) 针对句法分析中普遍存在的数据稀疏问题，本文采用了新的评分模 式和数据平滑技术，增强了模型的概括能力，解决数据稀疏问题。 1 4 本文的组织结构 本文围绕歧义消解问题展开分析，组织结构如下： 第1 章阐述了本文的研究背景和研究现状，说明了歧义消解的难点， 并介绍了本文的研究内容、创新点以及本文的组织结构。 第2 章介绍了本文的文法基础一b c g 。 第3 章介绍了句法分析相关算法，并提出了改进了的概率c y k 算法。 第4 章介绍已经存在的基于统计的汉语句法分析系统，并且建立统计 模型，描述了概率消歧模型在句法分析系统中的实现框架，并改进了分值 计算方法。 第5 章详细介绍了歧义消解的运行实例，对句法分析系统进行测试， 分析消歧中的错误原因，并与他人的研究工作做了比较。 第6 章总结了本文的工作，并对下一步研究方向进行展望。一个教师 管理系统为例，详细说明界面设计及实现的详细过程。 山东大学硕士学位论文 第二章相关知识 2 1 为何引入二元组合文法 前面说过，目前世界比较流行的句法分析系统都是采用基于规则和统 计相结合的方法。本课题组所实现的句法分析也是基于规则和统计结合的 方法。文中使用的文法规则是杨潇在文8 ，9 1 提出的二元组合文法( b c g ) 。 由于二元关系可以反映语言的层次性以及帮助语言的理解，并且该方法有 助于分析某些歧义结构；同时二元关系在自然语言中是客观存在的，可以 很好的覆盖自然语言现象，所以二元组合文法适合用来歧义消解。这种文 法是对上下文无关文法的一种扩展，采用句子的词之间的二元语义关系来 驱动句子的分析，同时在二元关系中添加中心词信息和关系优先级信息解 决句法分析中的歧义消解问题。 b c g 不仅可以很好地描述汉语句法结构，同时基于上下文无关文法的 经典句法分析算法均适用于b c g ，为本课题提供了良好的理论基础。 2 2 二元组合文法介绍 汉语句子中每一个成分都会和其他成分存在一定的关系，比如主谓、 动宾等，因此我们把词之间的这种关系定义为二元语义关系。在“二元语 义关系 的基础上，提出了“二元运算关系”概念1 9 】。“二元运算关系 不仅描述了词或者短语之间的语义属性关系，也描述了句子的结构特征。 因此，在“二元运算关系”的基础上，总结出了可以更好地描述汉语言语 法规则的二元组合文法。二元组合文法的基本概念【9 1 如下： 定义1 二元关系。是指隐含在语言中的、两两相邻的成分间存在的二 元的句法关系。 定义2 关系匹配模版( r e l a t i o nm a t c h i n gp a 钍e m ，i m 口) 用来匹配节点 属性以得到节点间的二元关系。啪用来匹配节点属性以得到节点间的二 元关系。定义为：i m 但= ( o ，a l ，a r ，r n i r t ，【c s c 】) 。其中0 为模版匹配的 6 山东大学硕士学位论文 二元关系名称；么l 和彳r 分别为关系的左、右属性，其中a = ( sa | w i rc s ) 可 以为词性s a 、个性词w ，也可以为具体的关系0 ，c s 表示关系组合时受到 的条件约束；c s c 则表示检查选择限制知识，“【】表示可省略项，某些二 元关系不需要检查选择限制，即词汇语义的约束时，该项可省略。 定义3 节点腚义为节点，可以是词节点陟也可以是关系节点i 淑。词 节点为输入词和词属性的一个词对w = ( w ，a ) ；关系节点为分析过程中组合 产生的节点，定义为r n = ( h ，h a ，n l ，n r ) ，其中h 为节点的中心词，可以 在关系组合过程中根据算子0 和输入词串唯一确定；h a 为中心节点的属 性：n l 和r 分别为关系节点的左右孩子节点。为简化起见，如果不特别声 明，文中的词节点用词代替，关系节点一般由节点代替。分析过程中产生 的所有的节点和所有的词节点定义为n s e t = ，为所有运算 数的集合，相当于p s g 文法中的所有非终结符和所有终结符的集合。 定义4 二元组合文法( b i n a 巧c o m b i n a t o r i a lq 锄m 砜b c g ) 即为语言中 存在的所有的二元关系和匹配模版的集合。 二元组合文法的算法优先特点在句法分析过程中不仅可以解决一部分 结构歧义问题，还可以剪枝大大提高时间效率。 我们需要建立很多二元关系覆盖复杂的汉语结构。那么在汉语中应该 设立多少种二元关系呢? 例如”动”关系可以分为“动量”、“副动”、“动 名 等子关系。这样做既可以全面、细致地描述汉语的复杂现象，又可以 满足完备性、准确性的要求。汉语的二元结构关系过于庞大，句法分析处 理的代价过高，同时使用大规模真实语料库句法会产生数据稀疏问题。因 此在文法描写深度、广度和句法分析经济性之间做出折衷，通过牺牲文法 描写深度和广度从而提高句法分析的时间效率和经济效率。在b c g 文法 中，二元关系根据其中心词的属性可将其分为“名、“动”、“介 、“副 等2 5 类。同时每个类中又包含多个分类，比如“名”关系包含“形 的) - 名”、“名量名 、“名代名等3 1 个分类，因此在b c g 中一共包含1 6 5 个二元关系分类。二元关系的划分按照其内部语义属性组成而不是外部功 能，既可以全面地描述汉语结构，又有利于使用大规模真实语料库抽取概 7 山东大学硕士学位论文 率信息。b c g 中的2 5 个二元关系类如表2 1 所示： 二元关系名短语例子 ”名”关系一部书 ”动”关系吃雪糕 ”副”关系就一向 程副”关系很不 ”名方”关系屋子南边 ”量”关系 一一k ”代副”关系这怎么 ”时方”关系昨天前 ”介”关系在餐厅 ”连”关系蓝天和 ”象似”关系小猫似的 ”形”关系不热 ”补”关系完了 ”数”关系二十五万 兼语关系请他吃饭 ”的”字结构熟了的 ”地”关系狠狠地 ”得”关系红得发紫 ”把”关系把爱心放在心里 ”被”关系被咬了 ”是”关系花儿是红的 ”代”关系他学习用功 ”拟声”关系哞哞 ”后缀”关系小孩儿 ”所”关系所关心 山东大学硕士学位论文 i - 有”关系 i 有成绩 i 表2 1 二元关系类 并且，根据二元关系中两元素的主次特点，描述了有关二元关系的中 心。根据二元关系中心的词性，我们把二元关系分为4 类：名词词性的约 束关系、动词词性的约束关系、形容词词性的约束关系、其它类的约束关 系。下面分类加以说明： ( 1 ) 名词词性的约束关系： 约束关系量名偏名名方同位并列 中心名词名词名词月盯后 ( 2 ) 动词词性的约束关系： 约束关偏动补动量动宾连动兼语宾动主谓 系动 中心动动词动词动词后日u动词动词 词 ( 3 ) 形容词词性的约束关系有： 约束关系形偏程补程副 中心形容词形容词形容词 ( 4 ) 其它类的约束关系有： 约束关系 介名数量 中心 刖 后 这里的二元关系是语义上的，但是由于它驱动的是句子的结构的划分， 因此它有时也明显带有结构特征。如：“动宾 关系和“宾动 关系，表达 的都是动作和受动者之间的关系，但由于它们在句子中的相对位置不同， 我们把它们划分为不同的关系。因此我们把以上的这些关系统一命名为二 元关系。对于其它二元关系，其语义关系的内容和它的名字是一致的。引 9 山东大学硕士学位论文 入了二元关系以后，我们可以用棵二叉树来描述一个句子的层次关系。 也就是说，用二元语义关系驱动的句法分析所得的句法树是一棵二叉树。 并且，具有同一特征的句子在句法树中具有相同的结构片段。因此，这种 句法分析很适合在计算机上进行处理。 2 3 面向二元组合文法的词性标注 根据前面已经介绍了二元组合文法，下面将给出一个对汉语句子进行 词性标注的例子。例句“他喜欢吃红苹果。 可以通过句法分词器得到的标 注样本： 标注为： l他代词 2 喜欢副词 3吃 动词 4 红 形容词 5 苹果名词 6。 结束符 其中，第一列是该单词在句子中的序号，第二列是该中文单词，第三 列是该单词的词性标注。 2 4 本章小结 本章主要介绍了本文研究所需的各种文法知识。首先提出了引入二元 组合文法的理由；其次，对二元组合文法进行简单介绍；然后阐述了可以 描述汉语现象的二元文法关系，并把二元文法关系归纳为2 5 种：最后，基 于二元组合文法对例句进行词性标注。 l o 山东大学硕士学位论文 第三章句法分析方法和算法 句法分析主要是判断输入的单词序列能否构成满足语法的句子，并且 抽取满足语法的句子的句法结构。也就是应用文法规则、语料库、语义库 等知识将输入的线性词序列组成非线性的树结构( 基于c f g 文法) 或者有 向无环图( 基于依存文法) 。在句法分析过程中，句法分析方法和句法分析 算法是关键。 3 1 句法分析方法 至今为止，句法分析的研究大体分为两种途径：一种是基于规则的方 法，句法的分析和生成都是基于一些给定的规则推理实现的；一种是基于 统计的方法，从语料库中抽取概率信息来表示短语成分之间的组合概率。 这两种方法在1 2 节已经做了介绍，在此不再详细说明。 3 2 句法分析算法综述及其比较 句法分析的最终目标是对于给定的句子，生成一棵带有句法功能标记 的短语结构树，句法分析的过程也可以理解为句法树的构造过程。因此， 句法分析算法是实现句法分析目标的基础和关键【2 0 】。 由于句法分析算法的任务是要在一定的时间内，找到满足一定语法条 件的所有可能的分析结果。因此，算法的处理能力和时间、空间效率就成 了设计算法所要考虑的关键因素【2 1 1 。本节则从这些方面入手，研究己有分 析算法的搜索策略和处理方法【2 2 ，2 3 1 。 3 2 1 句法分析算法综述 经典的句法分析算法主要包括l r 算法、g l r 算法、c 算法【2 4 j 、e a r l e y 算法【2 5 1 、以及c h a n 算法等。这些算法大致分为两类【2 6 】：一种是基于下推 自动机原理的算法( 如：l r 算法和g l r 算法) ，算法的空间复杂度是线性 的，但是时间复杂度是指数级别的。另外一种是基于表的分析算法( 如： 山东大学硕士学位论文 e a r l e y 算法、c 算法以及c h a r t 算法) ，空间复杂度是句子长度的平方，时 间复杂度是句子长度的立方。除了这些经典算法之外，一些算法都是在这 些算法进行改进的，比如引入路径搜索策略的启发式c y k 算法，还有将 c y k 算法与p c f g 结合的基于概率的c y k 算法。 l r 分析算法是典型的基于下推自动机( p d a ) 原理的分析算法，其工 作过程为：从左至右依次扫描输入串，一边把输入符号移入栈一边检查栈 项的符号串是否在产生式右部集合。如果在其中就把栈顶符号串替换成产 生式左部非终结符，即归约：如果不在其中，就继续扫描符号并且移入栈 中，直到扫描到输入串结尾。l r 分析算法是目前使用最广泛的“移进一 归约”算法，并且这种算法是无回溯的。它是一种表驱动分析算法，由分 析栈、控制程序和分析表组成，其中分析表是l r 算法的核心部分。分析 表包括“动作 ( a c t i o n 表) 和“状态转换 ( g o t o 表) 。它们都是二维 数组，a c t i o n 【s ，a 】规定了当状态s 面临输入符号a 时应采用什么动作，g o t o s ，x 】 规定了状态s 面对文法输入符号时的下一个动作是什么。因此，l r 算法包 括四种基本动作：移进、归约、接受和报错。 g l r 算法也是一种“移进一归约”算法，是传统l r 算法的改进。这 种算法允许有多重入口，即一个二维数组元素里面有多个动作，并且将原 有的线性分析栈改进为图分析栈，同时还采用共享子树表示局部分析结果。 e a f l e y 算法是e a u r l e y 提出的一种自顶向下的分析方法。该算法的核心 是一个从左到右的传递，它填充一个成为线图( c h a r t ) 的数组。对于句子 中每个单词的位置，线图包含一个状态表来表示已经生成的部分分析树。 在句子的结尾，线图把对于给定输入的所有可能的分析结果简洁地进行编 码。每个可能的子树只表示一次，并且这个子树表示可以被需要他的所有 分析共享。 c y k 算法是由c o k e ，y 0 u n g e r ，k 嬲s a m i 这三个人提出来的，所以称 为c y k 算法。这种算法是一种自底向上的分析算法，使用动态规划表( 用 来存放分析过程中结果的数据结构) ，不需要回溯，也没有冗余操作。在处 理词汇化的语法时非常有效。 山东大学硕士学位论文 c y k 算法如下： 输入：w l ，w 2 ，、n 维护一个二元数组n 大小为( n + 1 ) 牛( n + 1 ) n 中的元素为文法符号的集 合 f o ri 1t 0nd o n ( i - 1 ，i ) = w i ) f o re a c hr ：a 寸w i a d d a t on ( i 一1 ，i ) f o r l e n = 2t ond o f o r j = 0t on - l e nd o f o rk = j + lt o j + l e n - 1d o f o re a c hr ：a 争b c i f bi nn ( j ，k ) a n dci nn ( k ，j + l e n ) t h e n a d d a t on ( i ，j + l e n ) i fsi nn ( o ，n ) r e t u mt r u e ； r e t 啪f 酊s e ； 算法3 1c y k 算法 本文采用的分析算法也是基于c y k 算法的，我们将在本文3 3 节详细 介绍改进后的算法。 c h a n 算法是一种线图自底向上算法，用线图这种数据结构存放中间数 据结果。算法的核心是：将线图表示成点和边的集合。节点对应输入串中 的每个字符串；边表示成 的形式。从输入串开始一步 步构造线图最终得到一条可以覆盖全部节点的边，并且边上标记为文法开 始符s ，表示整条句子分析结束。 3 2 2 句法分析算法比较 本节主要讨论上文介绍的几种句法分析算法，并且从搜索过程、时间 山东大学硕士学位论文 复杂度等方面进行一些优缺点比较。 首先，按照句法分析的搜索过程可以分为方向相反的两类，一个是自 顶向下，另一个是自底向上【2 7 1 。自项向下的方法是从开始符号出发，算法 通过搜索并应用语法中的重写规则来不断改变算法的状态序列，即不断使 用产生式的右边代替与产生式左边相同的非终结符，最终得到整个输入串。 e a r l e y 算法就属于自顶向下的分析算法。另外一种经典分析算法c y k 算法 则属于自底向上的分析算法。自底向上和自顶向下算法本质的差别在于文 法规则的应用方式。在自底向上算法是从输入字符串开始不断使用产生式 的左边代替输入串与产生式右边匹配的部分，减少符号串的长度以组成更 大的句子成分，直至组成符号s 。因此，自项向下的分析方法叫做基于预 测的分析方法，即先对后面要出现的成分进行合理的预期，然后通过逐步 移入的字符串进行验证。如果预期得到验证，就说明分析的句法结构是合 理的，否则说明预期错误，则需要更换为其他的预期，即回溯。而自底向 上的分析方法叫做基于规约的分析方法。这种方法是逐步输入字符串，从 局部层层规约为整体，如果输入字符串被规约为开始符号s ，那么分析成 功，否则回溯。 其次，根据时间复杂度可以将算法分为线性的和非线性的( 指数级别 的) 。线性的分析方法保证了分析时间随着输入串长度的增加而线性增加。 比如e a r l e y 算法、c y k 算法以及c h a n 算法均使用了动态规划的原理，消 除了回溯方法中固有的子问题重复求解的弊病，使得句法分析的时间复杂 度为句子长度的立方。非线性的分析方法通常时间复杂度会随着句子长度 成指数级别增长的，比如l r 算法和c l r 算法。本文在句法分析中采用了 基于概率的c y k 分析算法，大大降低了时间复杂度。 3 3 概率分析算法 3 3 1 概率c y k 算法 由于c ( 算法是自底向上图分析算法的基础，同时是具有二元的特 征的一种并行算法，不需要回溯，本文采用c y k 算法计算分析结果树的 1 4 山东大学硕士学位论文 最优解。上文提到的c c e l l i ，j 】 x 】p r o bt h e n c e l l 【i ，j 】 x 】p r o b ：= m a x c e l l i ，p 】n o d e r 】：= r c e l l p + 1 ，j 】n o d e 【k 】：= k 山东大学硕士学位论文 e n d 算法3 2 本文根据以上算法依次填充矩阵单元格内容，c e l i 【1 ，n 】中存放分析树最 项层节点，我们可以根据顶层节点最大概率反向回溯找到句法分析结果树 的最优解。基于二元组合文法的c y k 详细算法见文献 9 】。c y k 图算法对同 样的分析结果不需要重复计算，不需要回溯【3 8 】，且算法的分析过程是基 于二元运算的，这与b c g 文法的特点相吻合，辅以优先级的约束，可完成 部分的歧义消解任务。并且算法的时间复杂度为d 4 ) ，证明如下。 定理1 ：对于n 个词的切分序列，算法的时间复杂度为d 仞4 ) 。 证明：一个词或者关系节点的属性最大数目应该是常数，则g e t r e l 最 多得到严个关系节点，g e t h e a d 、c r e a t e 、a p p e n d 的复杂度为d ( 1 ) 。又因为c e l l 【i j 】 左右子节点分别为c e l l 【i ，p 】，c e l l 【p + 1 ，j 】，f p 歹，所以f i l l c e l l 的复杂度为 d 仍) 。t e r b i f o r p b c g 的复杂度也为d o ) ，因此c o m b i n e 的时间复杂度为 d 伽2 ) 。由于c 算法从对角线依次填至左上角，一共有以0 + 1 ) 2 个格子， 所以算法时间复杂度为d 仞4 ) 。 3 3 2v it e r b i 算法 句法分析算法的任务是找到满足文法的所有可能句法分析树，而如何 能够在分析过程中动态剪掉不可能导致最优分析结果的无用边，并且最终 获得一棵概率最优的句法树，是我们的分析系统所要实现的目标，该目标 需要通过合理的搜索算法和剪枝算法来完成。在自然语言处理中，局部最 优并不能代表全局最优。在句法分析中，最优分析结果树未必是句子中最 佳的短语结构组合。既然最佳的句法结构分析序列并不是由每个最优结构 短语组合成的。如果采用全搜索算法策略，则时间复杂度随着句子长度成 指数级别增长。为了降低计算时间复杂度，在本系统中采用一种动态规划 算法：v i t e r b i 算法。 在b c g 模型中使用了v i t e r b i 算法得到最佳句法分析序列。算法描述 如下： 山东大学硕+ 学位论文 ( 1 ) 初始化 ( 2 ) 跌代 ( 3 ) 终止 ( 4 ) 回溯 3 4 本章小结 瓯( 1 ) = 万i 6 f 。l 缈。( 1 ) = o lsi n 1 i n t o + 1 ) = m 4 ( r ) 口扩h l j n ，l t t - l o + 1 ) = a 唱m a x 巧( f ) 吻。 1 j n ，1 t t - l x r = a r g m a ) 【暝仃) i x ，= y o + 1 ) z 1 p ( x ) = a r g m a x 4 ( r ) f 由于句法分析算法的任务是要在一定的时间内，找到满足一定语法条 件的所有可能的分析结果，因此，算法的处理能力和时间、空间效率就成 了设计算法所要考虑的关键因素。本章则从这些方面入手，首先介绍了几 种经典句法分析算法，并对各个算法在时间复杂度、策略等方面进行比较， 最后详细介绍了本文使用的概率c y k 算法和t e r b i 算法。 山东大学硕士学位论文 第四章p b c g 歧义消解模型 句法分析的目的主要有两个，一个是确定句子的组成成份之间的关系， 另一个是解决句法分析中的歧义问题得到最优分析结果。其具体详细内容 包括：对句子进行切分确定句子中包含哪些词；确定各个词语的语法范畴 和语义范畴；确定句子中各成分间的关系。 自然语言与人工语言的不同在于自然语言中包含着大量的歧义。自然 语言处理的过程实质上就是一个解决歧义的过程。而句法分析的过程可以 解决自然语言处理过程中存在的一部分歧义问题，比如：词性歧义、生词引 起的歧义、并列结构歧义、介词短语的附着对象歧义、代词的指代歧义、 句子连词歧义等。这样，歧义的解决无疑可以对进一步的自然语言处理提 供强有利的帮助。因此对自然语言句法分析的研究将是自然语言处理的一 个核心内容，歧义消解问题又是句法分析中的关键【2 引。 4 1 系统分析目标 汉语句法分析的最终目标是建立一个能有效地使用大量语言知识的汉 语句法处理系统。传统的上下文无关句法分析器虽然能够较好的分析汉语， 但对于中文句法分析还存在着某些缺陷，难以处理中文中大量复杂、细微 的语法语义现象。因此，我们在传统的上下文无关文法上添加语义信息、 中心词信息、概率信息等形成了新的语法模型，并修改传统的c ( 算法， 来对中文进行句法分析。从而达到提高句法分析正确率的目的。 课题考虑的重点是建立一个尽可能完善的系统。从设计上，为将来大 量的语言知识扩充提供一个具有开放性的框架。本系统的设计以以下几个 原则为目标： (