数码

基于树库统计信息广覆盖汉语完全句法的分析器及研究.pdf文档全文免...

尕藏扎西 安见才让

摘 要： 句法分析是自然语言处理中一个很复杂的研究内容。藏语句法分析更是目前藏文信息处理中的一个基本问题，许多藏文信息处理任务都依赖着句法分析的精确度。文章根据常用的藏文短语，总结出一套基于短语结构语法的藏文单句规则库，然后在Windows平台上用C#实现基于CYK算法来分析和生成句法树的藏语句法分析器。实验结果表明，在人工标注的测试集上，藏语单句的句法分析准确率达到了81%。

关键词： 规则库； CYK算法； 乔姆斯基范式； 句法树； 句法分析

中图分类号：TP39 文献标志码：A 文章编号：1006-8228（2018）06-53-04

Research and implementation of Tibetan sentence analyzer of CYK algorithm

Gazang Zhaxi， Anjian Cairang

（school of computing， Qinghai University for Nationalities， Xining， Qinghai 810007， China）

Abstract： Syntactic analysis is a very complex research content in natural language processing. The Tibetan sentence analysis is a basic problem in Tibetan information processing. Many Tibetan information processing tasks rely on the accuracy of syntactic analysis. According to the commonly used Tibetan phrases， this paper summarizes a set of Tibetan single sentence rule bases based on the phrase structure grammar. Then C# is used to implement the Tibetan sentence analyzer which uses CYK algorithm to parse and generate syntactic tree， on Windows platform. The experimental results show that the accuracy of the syntactic analysis of a single sentence in Tibetan reaches 81% on the manually labeled test set.

Key words： rule base； CYK algorithm； Chomsky paradigm； syntactic tree； syntax analysis

0 引言

目前，藏語句法分析的研究在藏文信息处理领域处于萌芽阶段，因此还要借鉴和吸收英汉语句法分析方法及相应的算法。在国外句法分析研究经历了60多年的发展历程。在此过程中句法分析方法也不断完善和改进。一般句法分析器通常有两部分组成：形式语法体系和分析控制机制[2]。句法分析的研究方法一般有基于规则和基于统计两类。CYK算法是基于短语结构语法的自动句法分析方法之一，而基于短语结构语法的自动句法分析方法是基于规则方法的。基于规则方法对自然语言的表达非常有效，且有着较好的可计算性。

在国内，藏语句法分析的研究刚起步。在句法分析之前首先要建立藏语句法规则库，规则库存放藏语语法规则。由于藏语与其他语言的句法结构有着很大区别，所以要根据藏语本身的特点来建立句法规则库。本文在文献[3]的句法规则库上扩充并把规则转换成乔姆斯基范式。用CYK算法来分析句法结构，并且在分析过程中生成句法树。

1 基于乔姆斯基范式的现代藏语语法规则

为了用短语结构语法来描述和生成自然语言，乔姆斯基提出了乔姆斯基范式：任何的由上下文无关语法生成的语言，均可由重写规则为A→BC或A→a的生成，其中A，B，C是非终极符号，a是终极符号[3]。具有这样的重写规则的上下文无关语法，它的句法树均可简化为二元形式，这样就可以采用二分法分析自然语言，采用二叉树来表示自然语言的句子结构。本文CYK算法，以乔姆斯基范式为描述对象的句法分析算法，因此，以下现代藏语的短语结构语法规则都是乔姆斯基范式的重写规则形式。

1.1 现代藏语的短语结构

现代藏语的短语[4]，它是由两个以上的词或短语按照一定的规则构成的、能在句法结构中承担某种句法成分，并能作为构成句子的语法单位。短语位于词短语和形容词性短语等五类。以下是乔姆斯基范式为描述的现代藏语的短语结构的重写规则。

⑴ 名词性短语（NP）

NP->rr（代词）|mj（数词）|pj（量词）|ff（方位词）|nn（名词）|NP AP

（形容词性短语）|NP NP|NP XN|NV（粘着动词性短语）XN| TP（时间词性短语） XN|AP XN|NP DN|NP MP（数量词性短语），XN-> gx（主格助词） NP，NV->NP ZV|NP CV| NP LV| NP NV，ZV->gz（属格助词） NV，CV->cn（从格助词） NV，LV->gl（la格助词） NV，DN->cd（介词） NP

⑵ 动词性短语（VP）

VP->vi|vt|ad| as（副词） VP |dc（状态词） VP| NP LP|TP

VP|VP UC|NP VP|VP CP|AP LP|NV LP| NP ZP，NV->vi |vt|ad| as NV |dc NV| NP ZN|NP LV|AP LV|NP NV|NV CN| NP NV|>TP NV|VP CN|NV DN| VP NV，ZP->gz VP， LP->gl VP， CP->cn VP，UC（助词）->uz| uc|up|us| qd， CN->cn NV， DN->cd NV

⑶ 时间词性短语（TP）

TP->TP XT| AP XT|NP XT|NV XT|TP DT|TP TP|tt（时间

词），XT-> gx TP，DT-> cd TP

⑷ 形容词性短语（AP）

AP->ad（形容词）|dc AP| AP LV|VP CA|AP DA| AP AP，

CA->cn AP，DA->cd AP

⑸ 数量词性短语（MP）

MP->pj mj| mj tt| rz（人称代词） mj|nn mj

1.2 现代藏语句子句型

在文献4中提到，现代藏语的句型一般可以分成两大类：N+P+V句型和N+V句型。N+P+V句型是词和词或短语和短语之间的语法关系主要通过格助词的添接来表现的藏文句子。N+V 句型词和词或短语和短语之间的语法关系没有格助词的添接，直接把词和词或短语和短语组合来表现的藏文句子。下面是以乔姆斯基范式为描述的现代藏语单句的重写规则：

S—>NP AP|NP VP|TP VP|NP YV|NP RT|NP UC|NV

VP|NP LP|NP CP|NP ZP|NP GV

GV—>gx VP，ZP—>gz VP，YV—>yy VP，RT—>gz ZV，

ZV—>gz NV，LP—>gl VP，CP—>cn VP

UC—>uz|uc|up|us|qd

2 CYK剖析算法

CYK剖析算法是J.科克（Cocke）、D.H杨格（Younge）和T.卡萨米（Kasami）三人于1967年前后各自独立地发现的，并以他们的姓氏的第一个字母命名。这是一种并行算法，不需要回溯。

2.1 CYK算法分析过程

对于藏文句子，在规则为：S→NP VP，NP→NP gx，NP→NP gl，NP→nn，VP→NP VP，VP→vt使用CYK分析法，我们可以得出分析表1。

在这个表中，行方向的数字表示单词在句子中的位置，列方向的数字表示该语言成分所包含的单词数。语言成分都装在单元格内，我们用bij来表示处于第i列第j行的单元格的位置。这样，每一个语言成分的位置就可以确定下来。比如：处于第1列第2行的NP的位置可用b12表示（NP∈b12），这种记法说明，这个NP处于句首，包含2个单词（和），也就是说，这个NP是由NP和CM规约成的；处于第3列第2行的NP的位置可用b32，表示（NP∈b32），这种记法说明，这个NP处于第3个词的位置，包含2个单词（和），也就是说，这个NP是由NP和CP规约成的；处于第5列第2行的VP的位置可用b52，表示（VP∈b52），这种记法说明，这个VP处于第5个词的位置，包含2个单词（和），也就是说，这个VP是由NP和VP规约成的；处于第1列第4行的NP的位置可用b14表示（NP∈b14），这种记法说明，这个NP处于第1个词的位置，包含4个单词（和），也就是说，这个NP是由NP（包含2个词）和NP（包含2个词）规约成的；处于第1列第6行的S的位置可用b16，表示（S∈b16），这种记法说明，这个s处于句首，包含6个单词（和），也就是说，这个S是由NP（包含4个单词）和VP（包含2个单词）组成。这些单元格里的标记，明确地说明了这个句子中的句法结构关系，因此，如果我们能够通过有限步骤造出这样的表并在b16中包含S，就等于完成了句子的句法结构分析。

2.2 句法树生产

CYK算法是自底向上的剖析方法，由小型分析树开始逐渐扩大，同样的分析树绝不重复运算，不需要进行回溯，并行运算所有不同的分析树。分析完成后所有不同的分析树中有一种分析树是最终的分析结果，这也是此句子的句法树。但是在不同的分析树中要找出最终的分析树，CYK算法本身是找不出来。本文用一种自顶向下的算法来找出CYK算法分析的所有分析树中找出最终的分析结果。CYK算法是建立在乔姆斯基范式的基础上，因此用二叉树来表示句子结构。首先要记录CYK算法来分析所有不同的分析树。因此用下面的数据结构来记录CYK算法的分析过程：

Struct Teer

{ String Ate； 当前二叉树的父节点

int Am； 当前父节点在分析表中的位置

String Bte； 当前二叉树的左孩子

int Bm； 当前的左孩子在分析表中的位置

String Cte； 当前二叉树的右孩子

int Cm； 当前的右孩子在分析表中的位置

}

然后从父节点为S，在分析表中的位置在第1列第n行的二叉树开始生产句法树。

以下描述生成树算法。

第一步：在所有二叉树中找出父节点为S，在分析表中的位置在第1列第n行的二叉树。如果找不到，此句子是不合法，没有句法树，算法结束。如果有则执行第二步。

第二步：在所有的分析树中查找当前的左孩子（Bte）为父节点（Ate）的分析树，找到后取出它的左右孩子节点绑定在当前节点（Bte）下面。重复执行第二步，如果没有左孩子（Bte）为父节点（Ate）的分析树，则执行第三步。

第三步：在所有的分析树中查找当前的右孩子（Cte）为父节点（Ate）的分析树，找到后，取出它的左右孩子，绑定在当前节点（Cte）下面。重复执行第三步，如果没有右孩子（Cte）为父节点（Ate）的分析树，则算法结束，句法树生成完成。

3 分析器模块设计与测试

3.1 模块设计

本分析器在windo7操作系统上用C#开发，整体模块设计和运行结果图如下，如图1和图2所示。

首先在大量的语料库中识别句子边界并抽取句子。

已抽取句子用CYK算法进行分析。

如果分析成功，用分析过程来生产句法树。

3.2 系统测试

在测试中，在中小学教材的文本中抽取了100个藏文单句，并做了人工标注。这些句子分成三组，每一组有40个句子，两组有30个句子。其中第一组是人工分析出来的合法的藏语句子。第二组的总词数在7个以下，而第三组的总词数在7以上。表2是CYK分析算法进行测试的结果。

测试结果表明，测试语料中的句子越长，其正确分析的句子数越少，从而准确率越低。这主要原因是藏语句子结构的复杂度随着句子长度越长而越难。另外，句法规则库不完整主要原因是短语分类的不够详细，还需要进一步完善规则库。

4 结束语

本文对现代藏语的单句用短语结构语法来建立起一套语法规则，在此基础上用CYK剖析算法来分析句子结构和生成句法树，并用计算机程序来实现藏文句法分析器。这对进一步处理藏语句法分析的研究具有重要的意义。

由于本文的句法规则库还不完善，影响了分析的结果。本系统目前只能分析单句和没有歧义的藏语句子，因此还要继续在藏语的规则库和复合句方面研究和探索。

参考文献（References）：

[1] 安见才让.藏文句子相似度算法研究[J].中文信息學报，

2011.4.

[2] 冯志伟.自然语言计算机形式分析的理论与方法[M].中国科

学技术大学出版社，2017.

[3] 完么扎西.藏语句法分析系统的研究与实现[D].西藏大学硕

士学位，2013.

[4] 吉太加.藏文句法研究[M].中国藏学出版社，2016.

[5] 华却才让等.藏文复合句的依存句法分析[J].中文信息学报，

2016.6.

[6] 华却才让等.基于判别式的藏语依存句法分析[J].计算机工

程，2013.4.

[7] 扎西加.上下文无关文法与藏语句法分析[J].西藏大学学报

（自然科学版），2013.2.

[8] 李玉萍等.基于CYK算法的关联文法语法分析的并行处理[J].

郑州轻工业学院学报（自然科学版），2010.3.

[9] 当增卓玛等.自动识别藏文整句的方法研究[J].信息与电脑

（理论版），2013.8.

[10] 李永亮等.基于浅层剖析的CYK改进算法[J].计算机应用，

2011.5.