概率CYK算法的分析研究

作     者：李鹏程 

作者单位：太原理工大学 

学位级别：硕士

导师姓名：马建芬

授予年度：2010年

学科分类：08[工学] 081202[工学-计算机软件与理论] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主      题：句法剖析 上下文无关语法 概率上下文无关语法 概率CYK算法 

摘      要：本文将简要介绍单词的分类与词类标注的相关内容,在此基础上介绍句法处理的一个计算机模型:上下文无关语法。上下文无关语法又称为短语结构语法,是模拟自然语言成分结构的最常用的数学系统。此时就可以对句子进行句法剖析了,也就是根据上下文无关语法识别一个句子并给句子指派结构。很多句子有一个以上的结构,即这些句子是有歧义的,上下文无关语法可以有效地表示这种歧义,但是它没有提供手段来消解歧义。概率上下文无关语法可以提供对这个问题的解决方法:从歧义中选择概率最大的解释。由于歧义非常普遍,因此概率剖析器在大多数剖析或自然语言处理工作中起着重要的作用。 在现存的剖析算法中,概率CYK算法是用于概率上下文无关语法剖析的一个标准算法,它具有以下特点: 1.概率CYK算法要求Chomsky范式的概率上下文无关语法。Chomsky范式的规则只有两种形式:A→BC或A→x(这里A、B、C是非终结符,x可以是非终结符或终结符)。由于每个上下文无关语法都可以转化成弱等价的Chomsky范式的语法,因此概率CYK算法可以应用于任何一个概率上下文无关语法。 2.概率CYK算法本质上是一种自底向上分析法,采用广度优先的搜索策略。 3.概率CYK算法是一种动态规划算法,并行进行不需要回溯,没有冗余的操作,时间复杂度为O(n 3),n为单词个数。 基于概率CYK算法自底向上分析的特点,传统的语法规则排列顺序实际上制约了剖析的速度,可以重新排列语法规则并建立索引表对概率CYK算法进行改进,通过减少中间搜索步骤所需的时间来提高算法的效率。本文最后编程实现改进的概率CYK算法,并剖析一些句子以验证这种方法的有效性。