劉運通，孫 華

（安陽師范學(xué)院計算機與信息工程學(xué)院，河南安陽455000）

0 引 言

當(dāng)前，在自然語言處理領(lǐng)域，語義信息的作用越來越被重視，學(xué)者們對利用語義來進行詞義消岐，做了許多有益的探索性研究。文獻［1］研究了基于利用How Net語義相關(guān)度進行詞匯語義消岐方法；文獻［2］研究了基于Word Net語義相關(guān)度的詞匯語義消岐方法；文獻［3］研究了基于維基的兩階段語義消歧方法；文獻［4］研究了基于詞語距離的網(wǎng)絡(luò)圖的語義消歧；文獻［5］研究了基于知網(wǎng)的中文信息結(jié)構(gòu)消歧研究；文獻［6］研究了基于知網(wǎng)詞匯語義相關(guān)度計算的消歧方法；文獻［7］研究了基于語義相關(guān)度的語義模型求解；文獻［8］研究了基于Word Net的詞匯語義消岐模型；文獻［9］研究了基于Word Net語義樹的語義消岐方法；文獻［10］研究了基于Word Net語義關(guān)系網(wǎng)的信息處理。

這些研究雖然取得很多成果，但并沒有形成一個比較成熟、有效的計算方法，消岐效果依然有很大的提高余地。為了能夠通過語義計算，實現(xiàn)高效、準(zhǔn)確的語義消歧，我們提出了一種基于動態(tài)規(guī)劃的簡單語義單元詞義消歧方法。先闡述了語義相關(guān)度計算模型，提出簡單語義單元的概念，分析了簡單語義單元的特點；采用動態(tài)規(guī)劃的方法，依次求出每個詞匯的所有義項的最大生成樹變量；最后求出語義修飾關(guān)系完全圖的最大生成樹；可以很容易地將最大生成樹轉(zhuǎn)化為最佳的語法分析方案和實現(xiàn)詞義消歧。

1 基本理論

1.1 語義相關(guān)度計算模型

假設(shè)一個語句（CS）中的任意實詞Wi（除去謂語中心詞）均語義修飾于另外一個實詞WGi，稱WGi是Wi語義修飾目標(biāo)，用函數(shù)match（Wi，WGi）來表示其語義相關(guān)度。

假設(shè)語句CS有m種不同的語法分析方案，在其中第i種語法分析方案Ai的情況下:假設(shè)V為謂語中心詞，S為V的施動者，O為V的承受者，Wi是語句中的一個實詞且?。╓i∈｛S，V，O｝），WGi是Wi的語義修飾目標(biāo)，那么，語句的語義相關(guān)度fAi（針對語法分析方案Ai）可以用式（1）來表示（如圖1所示）

其中，S和O的語義修飾目標(biāo)是V，n是實詞的個數(shù)（不包括S、V、O），KSVO為權(quán)值系數(shù)（KSVO＞1），KSVO應(yīng)正比于語句的長度。

圖1 語義相關(guān)度計算模型

值得注意的是:虛詞不參與計算，副詞、代詞、數(shù)詞、量詞被按照實詞計算。

最佳結(jié)果選擇規(guī)則:假設(shè)一個語句具有m種語法分析方案，最符合語義邏輯的語法分析方案Ai滿足式（2）的條件

即語義相關(guān)度最大的語法分析方案是最佳語法分析方案。

1.2 簡單語義單元

假設(shè)語句CS的語義結(jié)構(gòu)為:CS→LSLOLVL，S、V、O中間的段落為L（如圖2所示）；并假定分段L已經(jīng)被劃分到了“不包含從句”的程度，則可以根據(jù)L內(nèi)各部分語義作用的不同，將L劃分為:前置定語（用AB表示）、后置定語（用AA表示）、狀語（用PD表示）。

定義1（簡單語義單元） 在把S、V、O中間的“不包含從句”的分段L劃分為AB、AA或PD的情況下，AB＋S（或O）、AA＋S（或O）、PD＋V就是簡單語義單元（如圖2所示，假定L的語義結(jié)構(gòu)為:L→AAPDAB）。

1.3 簡單語義單元的語義特征

簡單語義單元的特點:

（1）除了所附加的S、V、O外，其它任何詞匯Wi的語義修飾目標(biāo)WGi都在簡單語義單元內(nèi)部；

（2）在語義分析時，可以作為一個整體來處理，其內(nèi)部語法結(jié)構(gòu)對語句的其余部分沒有影響；

（3）由于其中不包含從句，在語義計算時，每個詞的權(quán)重相同，無需考慮S、V、O的影響。

本文的算法，正是針對這種特點而提出的。

圖2 簡單語義單元的語義特征

1.4 AA、PD、AB的最佳界限劃分

假定一個分段L的語義結(jié)構(gòu)為:L→AAPDAB，且L包含m個詞匯；則AA、PD、AB的不同界限劃分方案共有種；可以根據(jù)式（1）與式（2）的方法，分別計算出每一種界限劃分方案的語義相關(guān)度值，然后選擇具有最佳語義相關(guān)度值的界限劃分方案作為AA、PD、AB的最佳界限劃分方案。

1.5 多義詞的語義相關(guān)度計算

針對兩個詞匯Wi和Wj（假設(shè)其為多義詞），依據(jù)How Net計算其語義相關(guān)度時，有兩種情況:

（1）按義項計算；

（2）詞匯作為一個整體進行計算。

1.5.1 義項之間的語義相關(guān)度

針對一個樹狀詞匯語義庫（在本文的實驗中，采用了How Net），兩個詞匯Wi與其語義修飾目標(biāo)WGi之間的語義相關(guān)度可用式（3）計算

1.5.2 詞匯之間的語義相關(guān)度

假如把詞匯Wi和WGi當(dāng)做一個整體，可根據(jù)式（4）來計算其語義相關(guān)度

其值為所有義項之間語義相似度的最大值。

2 簡單語義單元的語義消歧

2.1 最佳語法分析方案的語義修飾關(guān)系圖

在不考慮一詞多義的情況下:假如把簡單語義單元中的m個實詞當(dāng)做m個頂點，任意詞匯Wi與其語義修目標(biāo)WGi之間畫一條邊；由于Wi只有一個語義修飾目標(biāo)（最后一個詞匯沒有語義修飾目標(biāo)）；所以，每種語法分析方案都對應(yīng)于“m完全圖中的一顆生成樹”，如圖3所示。

圖3 每種語法分析方案都對應(yīng)于完全圖的一顆生成樹

假如“把Wi和WGi之間的邊的權(quán)值設(shè)置為Match（Wi，WGi）”，則最佳語法分析方案就對應(yīng)于“完全圖的最大生成樹”。這可以很容易地求出。

但這種方法不能實現(xiàn)“多義詞的語義消歧”，因此，也不能求出多義詞的最佳語法分析方案。

2.2 多義詞的語義修飾關(guān)系圖

自然語言中，大多數(shù)詞匯是多義詞，對簡單語義單元進行語法分析和語義消歧時，可以先畫出其語義修飾關(guān)系圖，其中，多義詞的所有義項形成一個集合，每個義項是該義項集合中的一個點。假設(shè)其的詞匯序列L＝Wm…Wi…W…Wp…W…W0，如圖4所示，在某個語法分析方案中，Wi的語義是其第j個義項，Wp的語義是其第q個義項，并且語義修飾于；則在語義修飾關(guān)系圖中的和之間，畫一條有向線段；在詞匯序列L上也畫一條有向線段。

圖4 多義詞的語義修飾關(guān)系

在圖4中，假如把每個詞匯的“義項集合”看成一個“廣義頂點”，義項看成一個“義項頂點”，則有以下特點:

（1）任意“廣義頂點”只有一個語義修飾目標(biāo)，其出度為1，最后一個“廣義頂點”除外；

（2）每種語法分析方案，其語義修飾關(guān)系圖必然為一個“廣義頂點完全圖”的一顆“生成樹”；

（3）在每個“義項集合”中，“生成樹”的所有邊，必須關(guān)聯(lián)同一個“義項頂點”；

（4）根據(jù)語義計算模型，具有最大語義相關(guān)度的語法分析方案，其語義修飾關(guān)系圖是“廣義頂點完全圖”的“最大生成樹”。

2.3 最大生成樹變量

可以用窮舉法直接求取“廣義頂點完全圖”的“最大生成樹”，但其計算復(fù)雜度將是指數(shù)級別的，理論上不可行。

為了解決這個問題，我們采用了動態(tài)規(guī)劃法，可以解決這個問題。首先，需要定義一個“最大生成樹變量”（如圖5所示），其含義為:針對詞匯Wi，其第j個義項有多個生成樹，其中各邊權(quán)值之和最大的生成樹，用MT（）表示，MT（）必須包含所對應(yīng)的點。

圖5 最大生成樹變量

2.4 求最大生成樹的動態(tài)規(guī)劃算法

先將所有“廣義頂點”劃分為U、V兩個集合:

U＝｛所有未計算出MT的“廣義頂點”｝

V＝｛已經(jīng)計算出MT的“廣義頂點”｝

動態(tài)規(guī)劃算法（算法1）:

步驟1 初始化

設(shè)置V＝｛W1，W0｝，其中的W0只有一個義項，就是簡單語義單元中的S或V或O；由于只有兩個“廣義頂點”，因此很容易算出W1的任意義項的最大生成樹:

MT（）＝｛到W0的邊｝

MT（W0）＝max｛WT（）｝所對應(yīng)的生成樹。

步驟2 計算U中詞匯Wi的最大生成樹變量

針對U中最后一個詞匯Wi，其每個義項與V中的任意義項之間，都可以計算出一個語義相關(guān)度，按照式（5），選擇能夠使MT（）達到最大的那個義項（如圖6所示），更新的最大生成樹變量MT（）的值

步驟3 對Wi的所有生成樹進行逆排序

在求Wi的最大生成樹變量的過程中，需要窮舉Wi的所有生成樹，在窮舉的時候，按照由大到小的順序，保存Wi的所有生成樹序列，用TList表示，則

圖6 計算集合U中義項的最大生成樹變量

步驟4 更新V中所有義項的最大生成樹變量

當(dāng)求出U中最后一個詞匯Wi的每個義項的最大生成樹變量后，可以考慮把Wi加入集合V；但這將致使V中每個義項的最大生成樹變量發(fā)生極大的變化，因此，在將Wi加入集合V之前，必須更新V中所有義項的最大生成樹變量。

更新算法的思路如圖7所示，從TList中找到Wi的最大生成樹（用粗線畫出），其在V中所相關(guān)的6個義項，就是“第1次更新的義項集合”；接下來，從TList中找到W i的第2大生成樹，其在V中所相關(guān)所有義項中，有4個義項沒有更新過，這4個義項就是“第2次更新的義項集合”；以此類推，直至V中的所有義項都被更新過。其過程可以用算法2來描述。

圖7 更新集合V中所有義項的最大生成樹變量

算法2:

步驟5 將詞匯Wi加入V

更新完V中的所有義項的最大生成樹變量之后，就可以將Wi加入集合V了。

步驟6 循環(huán)處理，直至U為空

返回步驟2，進行循環(huán)，直至U為空。最后選出詞匯Wm的最大生成樹即可。

2.5 計算復(fù)雜度分析

假設(shè)簡單語義單元包含m個詞匯，每個詞匯平均有t各義項。假如用窮舉法求解:理論計算復(fù)雜度為O（m2＊tm）。

假如用動態(tài)規(guī)劃法求解:

（1）共有m個詞匯；

（2）求Wi的最大生成樹變量時，平均有t個義項；

因此，本方法的理論計算復(fù)雜度為:O（m＊t＊（m＊t/2））＝O（（m＊t）2）。

3 實驗結(jié)果及分析

本文的實驗中，以How Net作為詞匯語義計算時所依據(jù)的資源。選取了100個語句進行實驗，先人工對其分析，將其劃分為406個簡單語義單元，并得到語義消歧的正確結(jié)果，然后與算法計算所得到的結(jié)果進行對比。實驗情況如下:

（1）不分義項計算:用Prim算法求最大生成樹，得到最佳語法分析方案，不能實現(xiàn)語義消歧。

（2）分義項計算:分別使用窮舉法、動態(tài)規(guī)劃法進行計算，可以得到最佳語法分析方案，還可以確定多義詞的義項，從而實現(xiàn)語義消歧。

3.1 語法分析實驗情況

語法分析指的是“求出每個詞匯W的語義修飾目標(biāo)WG”的過程。實驗環(huán)境為:Windows XP，Xeon E5－2403四核，主頻2.2GHz，8G內(nèi)存，實驗情況見表1、圖8與圖9。

在表1中，窮舉法、動態(tài)規(guī)劃法的正確率計算標(biāo)準(zhǔn)有兩個:

表1 每個簡單語義單元平均計算時間（毫秒，語義消歧正確率閥值＝0.5）

圖8 正確率對比

圖9 窮舉法時間/動態(tài)規(guī)劃法時間

（1）語法分析方案正確；

（2）語義消歧的正確率大于設(shè)定的閥值0.5。表1每個簡單語義單元平均計算時間（毫秒，語義消歧正確率閥值＝0.5）。

從實驗結(jié)果可以看出:

（1）不分義項計算的情況下，由于它沒有實現(xiàn)語義消歧，正確率最高。

（2）窮舉法、動態(tài)規(guī)劃法的計算結(jié)果一致，因為實現(xiàn)了語義消歧，其正確率有所降低。

（3）隨著簡單語義單元長度的增加，正確率逐漸下降。

（4）隨著簡單語義單元長度的增加，窮舉法計算所需的時間急劇增加；而動態(tài)規(guī)劃法所需時間一直保持在可以接受的范圍內(nèi)，實踐上可行。

3.2 語義消歧實驗情況

窮舉法和動態(tài)規(guī)劃法的計算結(jié)果一致，可以實現(xiàn)語義消歧。語義消歧的實驗情況見表2與圖10。

表2 語義消歧實驗情況（總個數(shù)＝406）

由實驗結(jié)果可知，雖然本方法能實現(xiàn)語義消歧，但其正確率還不太高，有待進一步的提高。

4 結(jié)束語

本文研究了基于動態(tài)規(guī)劃的簡單語義單元詞義消歧方法，先把語句劃分、轉(zhuǎn)化為簡單語義單元，通過態(tài)規(guī)劃的方法，求出其語義修飾關(guān)系完全圖的最大生成樹，并將其轉(zhuǎn)化為最佳的語法分析方案，同時也實現(xiàn)了詞義消歧。最后通過實驗，對本文的方法進行驗證，結(jié)果表明本文的方法具有一定的效果。從理論上講，本方法可以較為有效地進行語義消歧，但實際的計算效果并不十分理想，其主要原因是所依據(jù)的How Net的語義準(zhǔn)確度、多義詞的語義細致程度等，有很多欠缺和不足。另外，本文研究的前提是“不考慮簡單語義單元中的任何語法規(guī)則”；這是不符合實際情況的，至少有3種情況需要考慮:①具有連接、分段作用的虛詞，其語法作用不容忽視；②后向修飾規(guī)則，這是漢語中最常見的默認語義規(guī)則；③不越界規(guī)則，即W1～WG1之間的詞匯Wi的語義修飾目標(biāo)WGi，應(yīng)該位于W1～WG1之間。這些問題都有待在下一步研究中加以解決。

［1］WANG Guangzheng，WANG Xifeng.Word sense disambiguating method based on How Net semantic relevancy computation［J］.Journal of Anhui University of Technology（Natural Science），2008，25（1）:71－75（in Chinese）.［王廣正，王喜鳳.基于知網(wǎng)語義相關(guān)度計算的詞義消歧方法［J］.安徽工業(yè)大學(xué)學(xué)報（自然科學(xué)版），2008，25（1）:71－75.］

［2］Deepesh Kumar Kimtani，Jyotirmayee Choudhury，Alok Chakrabarty.Improvement in word sense disambiguation by introducing enhancements in English Word Net structure［J］.International Journal on Computer Science and Engineering，2012，4（7）:1366－1370.

［3］Chenliang Li，Aixin Sun，Anwitaman Datta.TSDW:Twostage word sense disambiguation using Wikipedia［J］.Journal of the American Society for Information Science and Technology，2013，64（6）:1203－1223.

［4］YANG Zhizhuo，HUANG Heyan.Graph based word sense disambiguation method using distance between words［J］.Journal of Software，2012，23（4）:776－785（in Chinese）.［楊陟卓，黃河燕.基于詞語距離的網(wǎng)絡(luò)圖詞義消歧［J］.軟件學(xué)報，2012，23（4）:776－785.］

［5］ZHANG Ruixia，ZHUANG Jinlin，YANG Guozeng.Chinese message structures disambiguation based on How Net［J］.Journal of Chinese Information Processing，2012，26（4）:43－60（in Chinese）.［張瑞霞，莊晉林，楊國增.基于知網(wǎng)的中文信息結(jié)構(gòu)消歧研究［J］.中文信息學(xué)報，2012，26（4）:43－60.］

［6］LI Shengqi，TIAN Qiaoyan，TANG Cheng.Disambiguating method for computing relevancy based on How Net semantic knowledge［J］.Journal of the China Society for Scientific and Technical Information，2009，28（5）:706－711（in Chinese）.［李生琦，田巧燕，湯承.基于知網(wǎng)詞匯語義相關(guān)度計算的消歧方法［J］.情報學(xué)報，2009，28（5）:706－711.］

［7］LIU Yuntong，LIANG Yanjun.The k－pruning algorithm for semantic relevancy calculating model of natural language［J］.Computer Engineering and Design，2013，34（8）:2939－2943（in Chinese）.［劉運通，梁燕軍.自然語言語義相關(guān)度計算模型的k枝剪求解法［J］.計算機工程與設(shè)計，2013，34（8）:2939－2943.］

［8］Kostas Fragos.Modeling Word Net glosses to perform word sense disambiguation［J］.International Journal on Artificial Intelligence Tools，2013，22（2）:1345－1352.

［9］Minca A，Diaconescu S.An approach to knowledge－based word sense disambiguation using semantic trees built on a Word Net lexicon network［C］//The 6th Conference on Speech Technology and Human－Computer Dialogue，2011:1－6.

［10］Suvitha D S，Janarthanan R.Enriched semantic information processing using Word Net based on semantic relation network［C］//International Conference on Computing，Electronics and Electrical Technologies，2012:846－851.