基于CYK的藏語句法分析器研究與實現(xiàn)

尕藏扎西 安見才讓

摘 要： 句法分析是自然語言處理中一個很復(fù)雜的研究內(nèi)容。藏語句法分析更是目前藏文信息處理中的一個基本問題，許多藏文信息處理任務(wù)都依賴著句法分析的精確度。文章根據(jù)常用的藏文短語，總結(jié)出一套基于短語結(jié)構(gòu)語法的藏文單句規(guī)則庫，然后在Windows平臺上用C#實現(xiàn)基于CYK算法來分析和生成句法樹的藏語句法分析器。實驗結(jié)果表明，在人工標注的測試集上，藏語單句的句法分析準確率達到了81%。

關(guān)鍵詞： 規(guī)則庫； 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 引言

目前，藏語句法分析的研究在藏文信息處理領(lǐng)域處于萌芽階段，因此還要借鑒和吸收英漢語句法分析方法及相應(yīng)的算法。在國外句法分析研究經(jīng)歷了60多年的發(fā)展歷程。在此過程中句法分析方法也不斷完善和改進。一般句法分析器通常有兩部分組成：形式語法體系和分析控制機制[2]。句法分析的研究方法一般有基于規(guī)則和基于統(tǒng)計兩類。CYK算法是基于短語結(jié)構(gòu)語法的自動句法分析方法之一，而基于短語結(jié)構(gòu)語法的自動句法分析方法是基于規(guī)則方法的?；谝?guī)則方法對自然語言的表達非常有效，且有著較好的可計算性。

在國內(nèi)，藏語句法分析的研究剛起步。在句法分析之前首先要建立藏語句法規(guī)則庫，規(guī)則庫存放藏語語法規(guī)則。由于藏語與其他語言的句法結(jié)構(gòu)有著很大區(qū)別，所以要根據(jù)藏語本身的特點來建立句法規(guī)則庫。本文在文獻[3]的句法規(guī)則庫上擴充并把規(guī)則轉(zhuǎn)換成喬姆斯基范式。用CYK算法來分析句法結(jié)構(gòu)，并且在分析過程中生成句法樹。

1 基于喬姆斯基范式的現(xiàn)代藏語語法規(guī)則

為了用短語結(jié)構(gòu)語法來描述和生成自然語言，喬姆斯基提出了喬姆斯基范式：任何的由上下文無關(guān)語法生成的語言，均可由重寫規(guī)則為A→BC或A→a的生成，其中A，B，C是非終極符號，a是終極符號[3]。具有這樣的重寫規(guī)則的上下文無關(guān)語法，它的句法樹均可簡化為二元形式，這樣就可以采用二分法分析自然語言，采用二叉樹來表示自然語言的句子結(jié)構(gòu)。本文CYK算法，以喬姆斯基范式為描述對象的句法分析算法，因此，以下現(xiàn)代藏語的短語結(jié)構(gòu)語法規(guī)則都是喬姆斯基范式的重寫規(guī)則形式。

1.1 現(xiàn)代藏語的短語結(jié)構(gòu)

現(xiàn)代藏語的短語[4]，它是由兩個以上的詞或短語按照一定的規(guī)則構(gòu)成的、能在句法結(jié)構(gòu)中承擔某種句法成分，并能作為構(gòu)成句子的語法單位。短語位于詞短語和形容詞性短語等五類。以下是喬姆斯基范式為描述的現(xiàn)代藏語的短語結(jié)構(gòu)的重寫規(guī)則。

⑴ 名詞性短語（NP）

NP->rr（代詞）|mj（數(shù)詞）|pj（量詞）|ff（方位詞）|nn（名詞）|NP AP

（形容詞性短語）|NP NP|NP XN|NV（粘著動詞性短語）XN| TP（時間詞性短語） XN|AP XN|NP DN|NP MP（數(shù)量詞性短語），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（狀態(tài)詞） 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

⑸ 數(shù)量詞性短語（MP）

MP->pj mj| mj tt| rz（人稱代詞） mj|nn mj

1.2 現(xiàn)代藏語句子句型

在文獻4中提到，現(xiàn)代藏語的句型一般可以分成兩大類：N+P+V句型和N+V句型。N+P+V句型是詞和詞或短語和短語之間的語法關(guān)系主要通過格助詞的添接來表現(xiàn)的藏文句子。N+V 句型詞和詞或短語和短語之間的語法關(guān)系沒有格助詞的添接，直接把詞和詞或短語和短語組合來表現(xiàn)的藏文句子。下面是以喬姆斯基范式為描述的現(xiàn)代藏語單句的重寫規(guī)則：

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年前后各自獨立地發(fā)現(xiàn)的，并以他們的姓氏的第一個字母命名。這是一種并行算法，不需要回溯。

2.1 CYK算法分析過程

對于藏文句子，在規(guī)則為：S→NP VP，NP→NP gx，NP→NP gl，NP→nn，VP→NP VP，VP→vt使用CYK分析法，我們可以得出分析表1。

在這個表中，行方向的數(shù)字表示單詞在句子中的位置，列方向的數(shù)字表示該語言成分所包含的單詞數(shù)。語言成分都裝在單元格內(nèi)，我們用bij來表示處于第i列第j行的單元格的位置。這樣，每一個語言成分的位置就可以確定下來。比如：處于第1列第2行的NP的位置可用b12表示（NP∈b12），這種記法說明，這個NP處于句首，包含2個單詞（和），也就是說，這個NP是由NP和CM規(guī)約成的；處于第3列第2行的NP的位置可用b32，表示（NP∈b32），這種記法說明，這個NP處于第3個詞的位置，包含2個單詞（和），也就是說，這個NP是由NP和CP規(guī)約成的；處于第5列第2行的VP的位置可用b52，表示（VP∈b52），這種記法說明，這個VP處于第5個詞的位置，包含2個單詞（和），也就是說，這個VP是由NP和VP規(guī)約成的；處于第1列第4行的NP的位置可用b14表示（NP∈b14），這種記法說明，這個NP處于第1個詞的位置，包含4個單詞（和），也就是說，這個NP是由NP（包含2個詞）和NP（包含2個詞）規(guī)約成的；處于第1列第6行的S的位置可用b16，表示（S∈b16），這種記法說明，這個s處于句首，包含6個單詞（和），也就是說，這個S是由NP（包含4個單詞）和VP（包含2個單詞）組成。這些單元格里的標記，明確地說明了這個句子中的句法結(jié)構(gòu)關(guān)系，因此，如果我們能夠通過有限步驟造出這樣的表并在b16中包含S，就等于完成了句子的句法結(jié)構(gòu)分析。

2.2 句法樹生產(chǎn)

CYK算法是自底向上的剖析方法，由小型分析樹開始逐漸擴大，同樣的分析樹絕不重復(fù)運算，不需要進行回溯，并行運算所有不同的分析樹。分析完成后所有不同的分析樹中有一種分析樹是最終的分析結(jié)果，這也是此句子的句法樹。但是在不同的分析樹中要找出最終的分析樹，CYK算法本身是找不出來。本文用一種自頂向下的算法來找出CYK算法分析的所有分析樹中找出最終的分析結(jié)果。CYK算法是建立在喬姆斯基范式的基礎(chǔ)上，因此用二叉樹來表示句子結(jié)構(gòu)。首先要記錄CYK算法來分析所有不同的分析樹。因此用下面的數(shù)據(jù)結(jié)構(gòu)來記錄CYK算法的分析過程：

Struct Teer

{ String Ate； 當前二叉樹的父節(jié)點

int Am； 當前父節(jié)點在分析表中的位置

String Bte； 當前二叉樹的左孩子

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

String Cte； 當前二叉樹的右孩子

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

}

然后從父節(jié)點為S，在分析表中的位置在第1列第n行的二叉樹開始生產(chǎn)句法樹。

以下描述生成樹算法。

第一步：在所有二叉樹中找出父節(jié)點為S，在分析表中的位置在第1列第n行的二叉樹。如果找不到，此句子是不合法，沒有句法樹，算法結(jié)束。如果有則執(zhí)行第二步。

第二步：在所有的分析樹中查找當前的左孩子（Bte）為父節(jié)點（Ate）的分析樹，找到后取出它的左右孩子節(jié)點綁定在當前節(jié)點（Bte）下面。重復(fù)執(zhí)行第二步，如果沒有左孩子（Bte）為父節(jié)點（Ate）的分析樹，則執(zhí)行第三步。

第三步：在所有的分析樹中查找當前的右孩子（Cte）為父節(jié)點（Ate）的分析樹，找到后，取出它的左右孩子，綁定在當前節(jié)點（Cte）下面。重復(fù)執(zhí)行第三步，如果沒有右孩子（Cte）為父節(jié)點（Ate）的分析樹，則算法結(jié)束，句法樹生成完成。

3 分析器模塊設(shè)計與測試

3.1 模塊設(shè)計

本分析器在windo7操作系統(tǒng)上用C#開發(fā)，整體模塊設(shè)計和運行結(jié)果圖如下，如圖1和圖2所示。

首先在大量的語料庫中識別句子邊界并抽取句子。

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

如果分析成功，用分析過程來生產(chǎn)句法樹。

3.2 系統(tǒng)測試

在測試中，在中小學(xué)教材的文本中抽取了100個藏文單句，并做了人工標注。這些句子分成三組，每一組有40個句子，兩組有30個句子。其中第一組是人工分析出來的合法的藏語句子。第二組的總詞數(shù)在7個以下，而第三組的總詞數(shù)在7以上。表2是CYK分析算法進行測試的結(jié)果。

測試結(jié)果表明，測試語料中的句子越長，其正確分析的句子數(shù)越少，從而準確率越低。這主要原因是藏語句子結(jié)構(gòu)的復(fù)雜度隨著句子長度越長而越難。另外，句法規(guī)則庫不完整主要原因是短語分類的不夠詳細，還需要進一步完善規(guī)則庫。

4 結(jié)束語

本文對現(xiàn)代藏語的單句用短語結(jié)構(gòu)語法來建立起一套語法規(guī)則，在此基礎(chǔ)上用CYK剖析算法來分析句子結(jié)構(gòu)和生成句法樹，并用計算機程序來實現(xiàn)藏文句法分析器。這對進一步處理藏語句法分析的研究具有重要的意義。

由于本文的句法規(guī)則庫還不完善，影響了分析的結(jié)果。本系統(tǒng)目前只能分析單句和沒有歧義的藏語句子，因此還要繼續(xù)在藏語的規(guī)則庫和復(fù)合句方面研究和探索。

參考文獻（References）：

[1] 安見才讓.藏文句子相似度算法研究[J].中文信息學(xué)報，

2011.4.

[2] 馮志偉.自然語言計算機形式分析的理論與方法[M].中國科

學(xué)技術(shù)大學(xué)出版社，2017.

[3] 完么扎西.藏語句法分析系統(tǒng)的研究與實現(xiàn)[D].西藏大學(xué)碩

士學(xué)位，2013.

[4] 吉太加.藏文句法研究[M].中國藏學(xué)出版社，2016.

[5] 華卻才讓等.藏文復(fù)合句的依存句法分析[J].中文信息學(xué)報，

2016.6.

[6] 華卻才讓等.基于判別式的藏語依存句法分析[J].計算機工

程，2013.4.

[7] 扎西加.上下文無關(guān)文法與藏語句法分析[J].西藏大學(xué)學(xué)報

（自然科學(xué)版），2013.2.

[8] 李玉萍等.基于CYK算法的關(guān)聯(lián)文法語法分析的并行處理[J].

鄭州輕工業(yè)學(xué)院學(xué)報（自然科學(xué)版），2010.3.

[9] 當增卓瑪?shù)?自動識別藏文整句的方法研究[J].信息與電腦

（理論版），2013.8.

[10] 李永亮等.基于淺層剖析的CYK改進算法[J].計算機應(yīng)用，

2011.5.