楊進(jìn)才,謝 芳,王中華,胡金柱

(1. 華中師范大學(xué) 計(jì)算機(jī)學(xué)院，湖北 武漢 430079;2. 湖北工業(yè)大學(xué) 計(jì)算機(jī)學(xué)院，湖北 武漢 430068)

?

復(fù)句關(guān)系詞規(guī)則生成系統(tǒng)中的沖突檢測與處理

楊進(jìn)才1,謝 芳2,王中華1,胡金柱1

(1. 華中師范大學(xué) 計(jì)算機(jī)學(xué)院，湖北 武漢 430079;2. 湖北工業(yè)大學(xué) 計(jì)算機(jī)學(xué)院，湖北 武漢 430068)

復(fù)句中的關(guān)系詞對研究復(fù)句中各分句的語義關(guān)系有著重要意義，在基于規(guī)則的關(guān)系詞自動(dòng)識別中需要大量的規(guī)則，并且規(guī)則庫是動(dòng)態(tài)變化和不斷完善的，向規(guī)則庫中入庫規(guī)則時(shí)會(huì)出現(xiàn)規(guī)則沖突和入庫錯(cuò)誤的情況，該文探討如何在入庫時(shí)識別產(chǎn)生沖突的規(guī)則,并對規(guī)則進(jìn)行相關(guān)的處理。對復(fù)句的普通規(guī)則、連用詞規(guī)則、普通句式規(guī)則、連用句式規(guī)則四類規(guī)則進(jìn)行了形式化的表示與存儲，在此基礎(chǔ)上設(shè)計(jì)了關(guān)系詞檢測、約束類型檢測、約束條件檢測、結(jié)論檢測的檢測流程。提出了兩種沖突處理方式——優(yōu)先級方式和有向無環(huán)圖方式，對兩種方法進(jìn)行了比較。利用該檢測方法和有向無環(huán)圖的處理方式，入庫了千余條規(guī)則。實(shí)驗(yàn)表明，利用該方法沖突規(guī)則的檢測和處理正確率達(dá)到100%。

復(fù)句關(guān)系詞；規(guī)則沖突；有向無環(huán)圖

1 引言

中文信息處理可以概括的分為三個(gè)平臺：字處理平臺、詞處理平臺和句處理平臺，其中每一個(gè)平臺都是以前一個(gè)平臺為基礎(chǔ)[1]。從目前的進(jìn)展來看，字、詞處理已經(jīng)取得很多研究成果，尤其是2003年Bakeoff[2]分詞評測開展以來，中文分詞技術(shù)獲得了長足的進(jìn)步[3]。而句和篇章方面的研究雖然已取得了句子相似度度量[4]、情感分析[5]、構(gòu)建語義依存關(guān)系樹庫[6]等的若干研究成果，但是目前還處于初級階段。從語法單位來講，復(fù)句的研究屬于“句處理”階段的研究，目前研究得較多的是復(fù)句層次關(guān)系的自動(dòng)識別，也是從“句處理”層面進(jìn)行的應(yīng)用研究。

關(guān)系詞(又稱關(guān)聯(lián)詞、關(guān)系標(biāo)記)在現(xiàn)代漢語復(fù)句領(lǐng)域中起著重要的作用，是復(fù)句中標(biāo)識關(guān)系的一個(gè)重要構(gòu)件，是復(fù)句在語表形式上的關(guān)系標(biāo)記，它在很大程度上影響著分句的語義，也影響著層次關(guān)系的識別[7]。由于語言的復(fù)雜性和多樣性，通過完全的句法分析或語義分析來識別復(fù)句，現(xiàn)在的技術(shù)還很難實(shí)現(xiàn)?；谝?guī)則的方法早期用于漢語語法規(guī)則的自動(dòng)構(gòu)造[8]，隨后在文本分類、自動(dòng)文摘、短語識別等方面得到廣泛使用[9-12]，基于規(guī)則的關(guān)系詞標(biāo)識仍是目前一種比較有效而且實(shí)用的方法?；谝褬?gòu)建的漢語復(fù)句語料庫和復(fù)句關(guān)系詞庫，挖掘關(guān)系標(biāo)記在復(fù)句中充當(dāng)關(guān)系詞的特征規(guī)律，再將特征規(guī)律整理為規(guī)則，據(jù)此建立相應(yīng)的關(guān)系標(biāo)記規(guī)則庫，是研究關(guān)系詞計(jì)算機(jī)自動(dòng)標(biāo)識方法和實(shí)現(xiàn)策略的關(guān)鍵。從句中發(fā)現(xiàn)與制定規(guī)則之后，需要對規(guī)則進(jìn)行形式化后入庫,在入庫時(shí)要對待入庫的規(guī)則與庫中的規(guī)則進(jìn)行分析比較，防止重復(fù)、矛盾的規(guī)則入庫。同時(shí)，也需要判斷具有包含關(guān)系的規(guī)則，并將這些規(guī)則與庫中的規(guī)則進(jìn)行歸并。本文研究對規(guī)則入庫的檢測與可能的處理。

2 規(guī)則的表示與規(guī)則的沖突

2.1 規(guī)則的表示形式

結(jié)合句法理論與關(guān)系詞分詞處理結(jié)果，我們將規(guī)則分為四類：普通規(guī)則、連用詞規(guī)則、普通句式規(guī)則、連用句式規(guī)則[13]。在規(guī)則數(shù)據(jù)庫中，以四張表對應(yīng)四類規(guī)則。四類規(guī)則除了各自具有特有的字段外，公有字段包括：規(guī)則號(ID)、關(guān)系標(biāo)記(Keymarks)、約束類型(ConstraintType)、約束條件(Constraints)、結(jié)論(Result)、備注(Remarks)。其中，規(guī)則號唯一標(biāo)識一條規(guī)則；關(guān)系標(biāo)記表示需要判斷的關(guān)系詞；約束類型表示規(guī)則涉及到的約束條件的類型；約束條件表示符合規(guī)則的復(fù)句應(yīng)滿足的復(fù)句特征；結(jié)論表示判斷的結(jié)果；備注用來補(bǔ)充說明復(fù)句應(yīng)具備的特征。沖突進(jìn)行檢測是通過公有的字段來進(jìn)行的。例如，一個(gè)普通規(guī)則的表示形式如表1所示。

表1 一個(gè)普通規(guī)則的表示

其中，約束類型分為12種[13]，用數(shù)字1～12表示。若該約束類型涉及多種，用“+”號來連接。同樣用“+”連接多種約束條件。

2.2 規(guī)則沖突

造成沖突事件的規(guī)則叫做沖突規(guī)則，規(guī)則沖突可以分為三類： 規(guī)則重復(fù)、規(guī)則矛盾、規(guī)則包含。

若有兩條規(guī)則A、B；它們的關(guān)系標(biāo)記分別記為Key(A)、Key(B)；約束類型分別記為T(A) 、T(B)；約束條件分別記為C(A)、C(B)；結(jié)論分別記為R(A)、R(B)。

定義1 若C(A)=C(B)∧R(A)=R(B)，則稱規(guī)則重復(fù)，形式化表示為A≌B。

定義2 若C(A)=C(B)∧R(A)≠R(B)，則稱規(guī)則矛盾，形式化表示為A>

定義3 若C(A)?C(B)∨C(A)?C(B)，則稱規(guī)則包含。若C(A)?C(B)稱為規(guī)則B右包含規(guī)則A， “?”稱為右包含，反之若C(A)?C(B)稱規(guī)則A左包含規(guī)則B，“?”稱為左包含。

定義4 約束左包含與約束右包含 若規(guī)則A、B的約束條件語義存在C(A)?C(B)，稱為約束左包含；C(A)?C(B)，則稱為約束右包含。否則，則稱為約束不包含，記為C(A)?C(B)

定義5 約束相等 若規(guī)則A、B的約束條件語義存在C(A)=C(B)，稱為約束相等。

定義6 規(guī)則沖突?A、B，?Key(A)=Key(B)∧(A≌B∨A>

規(guī)則重復(fù)使規(guī)則庫中出現(xiàn)冗余，規(guī)則矛盾使規(guī)則引擎調(diào)用不同的規(guī)則時(shí)得出不同的結(jié)論。所以，應(yīng)該排除規(guī)則重復(fù)與規(guī)則矛盾。對于規(guī)則包含，則允許其存在，可以通過優(yōu)先級等方式將包含的關(guān)系區(qū)分開。

3 規(guī)則的沖突檢測

規(guī)則庫是一個(gè)動(dòng)態(tài)的數(shù)據(jù)庫，當(dāng)向其中添加每一條規(guī)則時(shí)，都可能出現(xiàn)規(guī)則的重復(fù)，規(guī)則的矛盾或者規(guī)則的包含，所以在規(guī)則入庫時(shí)必須進(jìn)行沖突檢測。

規(guī)則的檢測可以分為關(guān)系詞檢測、約束條件類型檢測、約束條件檢測和結(jié)論檢測等四個(gè)層次，如圖1所示。

圖1 沖突檢測整體流程圖

3.1 關(guān)系詞檢測

關(guān)系詞檢測就是對將要入庫的規(guī)則(記為規(guī)則A)的關(guān)系標(biāo)記(keymarks)字段進(jìn)行檢測。

規(guī)則沖突只可能發(fā)生在關(guān)系標(biāo)記相同的規(guī)則之間，因此首先篩選出關(guān)系標(biāo)記相同的規(guī)則。

關(guān)系詞檢測步驟為： 連接規(guī)則庫，在將要入庫的規(guī)則表中查找是否有和規(guī)則A的關(guān)系標(biāo)記詞完全相同，如果存在這樣的規(guī)則或者規(guī)則集合，則進(jìn)入到下一層檢測(約束條件類型檢測)；否則，表明不存在與規(guī)則A相沖突的規(guī)則。

3.2 約束類型檢測

根據(jù)約束類型的不同來進(jìn)行沖突的進(jìn)一步判斷。

假設(shè)要對將要入庫的規(guī)則A與庫中的關(guān)系標(biāo)記相同的規(guī)則B進(jìn)行沖突檢測，規(guī)則A和規(guī)則B的約束類型的關(guān)系可以分為以下幾種：

a)T(A)∩T(B)=?；

b)T(A)=T(B)；

c)T(A)?T(B)∨T(A)?T(B)

d)T(A)∩T(B)≠?；

若規(guī)則A、B滿足a) 、d)的情形，則可以直接判斷A⊕B；若滿足b)、c)的情形，兩規(guī)則的約束類型存在這包含關(guān)系，則它們的約束條件有可能也存在著包含關(guān)系，所以同樣得不沖突檢測的結(jié)論，需要進(jìn)入下一層繼續(xù)檢測。

3.3 約束條件檢測

約束條件檢測就是兩條規(guī)則在確定約束類型存在包含或者相等之后，進(jìn)一步確定兩規(guī)則的約束條件之間的關(guān)系。

約束條件檢測又分為兩類，一類通過語義檢測的約束條件，語義的檢測主要包含跨度的檢測和語義關(guān)聯(lián)度[12]的檢測；另一類通過表示形式上檢測約束條件。

最后綜合上面兩類檢測的結(jié)果得出這一層的最終檢測結(jié)果，若得不出檢測結(jié)果，還是需要進(jìn)入下一層的沖突檢測。約束條件檢測的整體流程圖如圖2所示。

圖2 約束條件檢測整體流程圖

3.3.1 規(guī)則形式檢測

規(guī)則形式檢測主要是檢測字符串是否匹配。例如，sameClause(要是,就)與sameClause(就,要是)[10]，應(yīng)判斷這兩個(gè)單一約束條件是相等的。

假設(shè)要檢測的規(guī)則A和庫中的規(guī)則B，現(xiàn)在要對兩條規(guī)則的同一類型中進(jìn)行單一約束條件的檢測，判斷同一個(gè)類型中的約束條件的關(guān)系步驟如下：

Step1 將規(guī)則A、B的當(dāng)前類型的約束條件拆分成單一的約束條件集合，并存儲在A和B中；

Step2 ?a∈A若?b∈B∧a=b，則相等數(shù)目eNum= eNum+1；

Step3 若eNum≠min(|A|，|B|)，則在這個(gè)類型中不存在包含關(guān)系；否則，執(zhí)行Step4；

Step4 若|A|=|B|，則在當(dāng)前類型中是相等關(guān)系，否則，執(zhí)行Step5；

Step5 若|A|= min(|A|，|B|)，則在這個(gè)類型中是右包含關(guān)系，否則就是左包含關(guān)系。

3.3.2 規(guī)則語義檢測

進(jìn)行語義方面的檢測前，先進(jìn)行規(guī)則約束條件的預(yù)處理，對關(guān)系標(biāo)記詞的跨度進(jìn)行規(guī)約處理，將規(guī)則規(guī)范化。例如，對于跨度有D(word1,word2)>1∧D(word2,word1)<4，我們將他們規(guī)約成11∧D(word3,word4)<4，我們將他們處理成1

進(jìn)行預(yù)處理之后，將規(guī)則A 中的涉及到的約束條件和規(guī)則B中的進(jìn)行分析判斷，語義關(guān)聯(lián)度的處理原理與跨度處理的原理一樣，同樣通過比較語義的包含范圍來確定是否存在包含關(guān)系，此處僅以跨度類型為例進(jìn)行說明，包含關(guān)系判斷依據(jù)如下：

? (n1

? D(word1,word2)

? (n1=n1∧n2

? n1=num3∧n2 <=num4)∨(n1<=num3∧n2>=num4))，則二者之間存在包含關(guān)系。

根據(jù)上述規(guī)則的處理，進(jìn)一步分析所有的單一包含關(guān)系是否是一個(gè)方向的包含，若都是一個(gè)方向的包含就確定在這類約束類型中是包含關(guān)系，否則，就判斷它們在這個(gè)類型中不存在包含沖突。

當(dāng)要比較規(guī)則A和規(guī)則B對應(yīng)類型中的約束條件是否存在包含關(guān)系時(shí)，分別用lNum、rNum、eNum表示約束左包含數(shù)目、約束右包含數(shù)目、約束相等數(shù)目。規(guī)則A、B在當(dāng)前類型中的單一約束條件數(shù)目分別為T_A,T_B，minNum=min(T_A, T_B)。判斷這個(gè)單一類型中的包含關(guān)系的依據(jù)如下：

? 若lNum ≠0∧rNum ≠ 0，則此類型中不存在包含的關(guān)系；

? 若lNum = 0∧rNum ≠ 0∧rNum + eNum = minNum，則此類型中是右包含關(guān)系；

? 若rNum = 0∧lNum ≠ 0∧lNum + eNum = minNum，則此類型中是左包含關(guān)系；

? 若rNum = 0∧lNum = 0∧eNum = minNum∧T_A≠ T_B，若minNum= T_A則此類型中是右包含關(guān)系；若minNum= T_B則此類型中是左包含關(guān)系；

? 若rNum = 0∧lNum = 0∧eNum = minNum∧T_A = T_B，則此類型中是相等關(guān)系；即此類型中兩條規(guī)則的約束條件是相等的， 這種情況既可以看作是此約束類型的左包含關(guān)系，也可以看作右包含關(guān)系；

? 如果不符合上面任一種情況，就判斷兩條規(guī)則在此類型里面是不存在包含關(guān)系的。

3.3.3 約束條件的包含關(guān)系的確定

經(jīng)過所有單一約束類型的檢測之后，將所有類型檢測的結(jié)果綜合考慮，得出整個(gè)約束條件(約束條件集合)的關(guān)系，綜合判斷的原理和單類型的判斷原理相同，考慮兩條規(guī)則涉及到的約束類型的數(shù)目T_A和T_B,以及其中左包含關(guān)系數(shù)目lNum，右包含關(guān)系數(shù)目rNum，相等關(guān)系的數(shù)目eNum之間的關(guān)系。

? 若lNum+eNum=T_A∨lNum+eNum=T_B，則C(A)?C(B)。

? 若rNum+eNum=T_A∨rNum+eNum=T_B，則C(A)?C(B)。

? 若rNum≠0∧rNum≠0，則C(A)?C(B)。

? 若rNum=0，rNum=0∧eNum≠min(T_A,T_B), 則C(A)?C(B)。

? 若rNum=0，rNum=0∧eNum=min(T_A,T_B),若eNum= T_B，則左包含關(guān)系；若eNum= T_A，則右包含關(guān)系；eNum=T_A=T_B則C(A)=C(B)。

根據(jù)上面涉及到的約束條件相等的情況，可以直接判斷產(chǎn)生了沖突，涉及到的包含關(guān)系的情況需要進(jìn)一步的結(jié)論層檢測。

3.4 結(jié)論檢測

結(jié)論的檢測與規(guī)則形式方面檢測的方式相同，如果C(A)=C(B)∧R(A)≠R(B)，可以判斷產(chǎn)生了規(guī)則矛盾沖突A>

4 規(guī)則的沖突處理

規(guī)則的沖突處理重點(diǎn)是處理那些約束條件存在包含關(guān)系的規(guī)則, 常見的規(guī)則沖突處理方法有： 依照規(guī)則存儲順序、定義規(guī)則的優(yōu)先級、最長匹配策略、先入先出策略、元知識。其中最為簡單實(shí)用的是優(yōu)先級方法，Drools 規(guī)則引擎采用的就是優(yōu)先級方法，利用優(yōu)先級來區(qū)分各條規(guī)則的匹配優(yōu)先順序。

4.1 優(yōu)先級的確定策略

待入庫的規(guī)則A與規(guī)則庫中的某條規(guī)則B沖突，規(guī)則A的優(yōu)先級確定策略如下(n代表沖突的次數(shù))：

? 若C(A)?C(B)，比較兩條規(guī)則的優(yōu)先級P(A),P(B)；若P(A)>P(B)則將P(A)= P(B)-1

? 若C(A)?C(B)，比較兩條規(guī)則的優(yōu)先級P(A),P(B)；若P(A)

采用這種方法處理可能會(huì)出現(xiàn)“優(yōu)先級鐘擺問題”。例如： 設(shè)庫中已有規(guī)則A和B，而且A,B的關(guān)系標(biāo)記相同，B的優(yōu)先級高于A，P(B)=P(A)+1?，F(xiàn)在有一條規(guī)則C要入庫，經(jīng)檢測C的關(guān)系標(biāo)記與A,B相同，則需要進(jìn)一步檢測，如果發(fā)現(xiàn)C與A有沖突，且C比A的約束條件更嚴(yán)格，即C的優(yōu)先級高于A，于是A的優(yōu)先級加1；然后再將C與B進(jìn)行沖突檢查，如果出現(xiàn)C的約束條件比B的約束條件寬松，即B的約束條件是C的約束條件的子集，這時(shí)就應(yīng)該降低C的約束條件，即B的優(yōu)先級減1。這時(shí)候C的優(yōu)先級就又回到了和A的優(yōu)先級一樣了，就破壞了第一次沖突檢測的修改結(jié)果。這樣優(yōu)先級就像鐘擺一樣的來回變動(dòng)，永遠(yuǎn)也配不平衡，這就是所謂的“優(yōu)先級鐘擺問題"。

解決優(yōu)先級鐘擺問題的方法是將優(yōu)先級的增量或減量不定為一個(gè)恒量，而是當(dāng)入庫發(fā)生多次沖突時(shí)，修改時(shí)增量(或減量)，取上一次沖突的增量(或減量)的1/2。

? 若C(A)?C(B)，比較兩條規(guī)則的優(yōu)先級P(A),P(B)；若P(A)>P(B)則將P(A)= P(B)-1/2n。

? 若C(A)?C(B)，比較兩條規(guī)則的優(yōu)先級P(A),P(B)；若P(A)

對于上述規(guī)則A、B、C，若默認(rèn)優(yōu)先級是5，A、B先后入庫優(yōu)先級分別為5、6，C入庫時(shí)，先與A沖突優(yōu)先級變?yōu)?，增量為1，然后與B沖突，減量為0.5(上次沖突1的1/2)，所以檢測完成，最終入庫結(jié)果優(yōu)先級為6-0.5=5.5。

為了實(shí)現(xiàn)上面的方法，我們需要給每條規(guī)則增加一個(gè)優(yōu)先級(priority)字段，規(guī)則的表示形式為：

Rule(ID, keymarks, priority, constraintType, constrants, result, remarks)

4.2 有向無環(huán)圖(DAG)方式

規(guī)則的約束條件在語義上面存在著包含關(guān)系，我們將這種包含關(guān)系以有向弧的形式表示，將每條入庫的規(guī)則用圖中一個(gè)節(jié)點(diǎn)表示。節(jié)點(diǎn)之間的有向弧表示弧線兩端的規(guī)則的一種包含關(guān)系，而且這種包含關(guān)系是真包含，所有關(guān)系標(biāo)記相同的規(guī)則入庫后形成一個(gè)有向無環(huán)圖DAG。

我們采用的表示方式是弧首的規(guī)則包含弧尾的規(guī)則，即弧首的規(guī)則的約束條件比弧尾的規(guī)則的約束條件更寬松，弧尾的規(guī)則表示的集合是弧首的規(guī)則表示集合的真子集。

例如，下面有兩條包含關(guān)系的規(guī)則Rule1、Rule2，為了方便，我們只列出兩條規(guī)則的約束條件:

Rule1:sameClause(不僅,同時(shí))

Rule2: sameClause(不僅,同時(shí))^backword(同時(shí))=‘具有’

Rule1的范圍比Rule2的范圍更加廣，Rule2的約束更加嚴(yán)格，所以規(guī)則連接弧(關(guān)系弧)應(yīng)該是由Rule1指向Rule2(Rule1 —> Rule2)。

以關(guān)系標(biāo)記“如果/那么”為例進(jìn)行說明有向無環(huán)圖的形成過程：

首先，庫中沒有涉及到“如果/那么”的規(guī)則，有向無環(huán)圖為空；插入第一條關(guān)系標(biāo)記“如果/那么”，形成了一個(gè)有向無環(huán)圖，圖中只有一個(gè)規(guī)則結(jié)點(diǎn)，沒有弧。

然后，試圖向庫中插入另一條關(guān)系標(biāo)記“如果/那么”，這時(shí)，需要對庫中的有向無環(huán)圖中的規(guī)則元素進(jìn)行檢測，查找插入的位置。

查找規(guī)則Node的插入位置是一個(gè)復(fù)雜的過程，我們的遍歷策略是深度優(yōu)先遍歷[13]，步驟如下：

Step1 選取一個(gè)沒有直接前驅(qū)的節(jié)點(diǎn)，依次深度遍歷它的后繼，直到找到包含Node的節(jié)點(diǎn)Node1和指向Node1的節(jié)點(diǎn)Node2；

Step2 若規(guī)則Node包含Node2，則將Node插入到Node1與Node2之間，否則就將Node作為Node1的一個(gè)新前驅(qū)；

Step3 回溯到Node1選取另一個(gè)未遍歷的后繼節(jié)點(diǎn)遍歷，直至這個(gè)沒前驅(qū)的節(jié)點(diǎn)下的所有連通節(jié)點(diǎn)都遍歷或找到了插入點(diǎn)為止；

Step4 繼續(xù)選取另一個(gè)沒有前驅(qū)的節(jié)點(diǎn)，重復(fù)步驟1、2、3，尋找插入點(diǎn)插入；

Step5 如果遍歷完所有節(jié)點(diǎn)，沒有找到包含Node的節(jié)點(diǎn)，但是Node卻包含某個(gè)沒有后繼的節(jié)點(diǎn)，就將Node作為這個(gè)沒有直接后繼的節(jié)點(diǎn)的后繼；

Step6 如果Node和所有節(jié)點(diǎn)不存在包含關(guān)系，那么就將Node獨(dú)立出來，形成一個(gè)單獨(dú)的孤立的節(jié)點(diǎn)。

通過上面的構(gòu)造我們就能形成一個(gè)邏輯的有向無環(huán)圖。而規(guī)則引擎在調(diào)用時(shí)正好與規(guī)則插入的遍歷順序相反，所以在插入時(shí)，應(yīng)該利用兩條方向相反的有向弧來生成圖。

DAG的存儲結(jié)構(gòu)需要給每條規(guī)則增加前驅(qū)(precursor)和后繼(subsequent)兩個(gè)字段。前驅(qū)用來指向包含自身的規(guī)則，后繼用來指向被包含的規(guī)則，規(guī)則的格式為：

Rule(ID, keymarks, constraintType, constrants, precursor, subsequent, result, remarks)

4.3 兩種方式的比較

兩種方式各有自己的優(yōu)缺點(diǎn)：

優(yōu)先級方式表示簡單，實(shí)現(xiàn)起來容易，同時(shí)也節(jié)省存儲空間，但是它存在優(yōu)先級鐘擺的問題。而為了解決優(yōu)先級鐘擺問題我們采用的優(yōu)先級增(減)量指數(shù)級遞增(減)的方法。

有向無環(huán)圖方式的表示更加直觀，實(shí)現(xiàn)起來比較困難，而且需要更多的存儲空間來存儲規(guī)則之間的關(guān)系。優(yōu)點(diǎn)是在規(guī)則引擎調(diào)用規(guī)則進(jìn)行解析時(shí)，不需要對圖中的所有規(guī)則都進(jìn)行解析，只需要(沿著實(shí)線有向圖遍歷)找到最后一條符合規(guī)則的解析結(jié)果即可，這樣就節(jié)省了規(guī)則解析的過程和時(shí)間。而且在進(jìn)行入庫檢測時(shí)也不需要對庫中的每一條規(guī)則進(jìn)行檢測，同樣只需要(沿著虛線有向圖遍歷)檢測到第一條存在包含關(guān)系的規(guī)則后，就找到了在這條路徑里的插入位置。

下面以關(guān)系標(biāo)記“一邊/一邊”為例說明規(guī)則沖突處理的過程，并對兩種處理方式的性能進(jìn)行定量的比較。“一邊/一邊”涉及的6條規(guī)則如表2所示(基于表格篇幅限制，表中只列出規(guī)則約束條件)。

表2 涉及“一邊/一邊”的規(guī)則

續(xù)表

假設(shè)庫中不含有“一邊/一邊”的規(guī)則，若按照表中的規(guī)則的順序入庫(不同順序入庫結(jié)果不同)。

優(yōu)先級方式入庫的步驟如下： ①入庫規(guī)則1，由于庫中沒有相同關(guān)系標(biāo)記的規(guī)則，所有直接入庫，默認(rèn)優(yōu)先級設(shè)置為5；②入庫規(guī)則2，先檢測庫中規(guī)則，發(fā)現(xiàn)規(guī)則1包含規(guī)則2，因此規(guī)則2的優(yōu)先級為P(2)=P(1)+(1/2)1-1=6；③入庫規(guī)則3，與庫中規(guī)則1、2不存在沖突，直接入庫，優(yōu)先級為默認(rèn)值5；④入庫規(guī)則4，依次檢測規(guī)則1、2、3，與規(guī)則1約束包含，因此優(yōu)先級為P(4)=P(1)+(1/2)1-1=6；⑤入庫規(guī)則5，依次檢測規(guī)則1、2、3、4，依次與規(guī)則1、2約束包含，因此優(yōu)先級為P(5)=P(2)+(1/2)2-1=6+(1/2)2-1=6.5；⑥入庫規(guī)則6，依次檢測規(guī)則1、2、3、4、5，依次與規(guī)則1、2、5約束包含，P(6)=P(5)+(1/2)3-1= 6.75。

經(jīng)過優(yōu)先級沖突處理后，六條規(guī)則的優(yōu)先級如表3所示。

表3 六條規(guī)則的優(yōu)先級

有向無環(huán)圖方式入庫的步驟如下： ①入庫規(guī)則1，直接入庫；②入庫規(guī)則2，檢查庫中規(guī)則1，規(guī)則1約束包含規(guī)則2，因此虛線由規(guī)則2指向規(guī)則1；③入庫規(guī)則3，依次檢測規(guī)則2、1，不存在沖突，直接入庫；④入庫規(guī)則4，依次檢測規(guī)則2、1、3，規(guī)則1約束包含規(guī)則4，虛線由規(guī)則4指向規(guī)則1；⑤入庫規(guī)則5，依次檢測規(guī)則2、4、3，規(guī)則2約束包含規(guī)則5，所有不需要檢測規(guī)則2的直接或間接后繼(虛線方向)，因此虛線規(guī)則5指向規(guī)則2；⑥入庫規(guī)則6，依次檢測規(guī)則5、2、4、3，發(fā)現(xiàn)規(guī)則2約束包含規(guī)則6，規(guī)則6約束包含規(guī)則5，所有將有規(guī)則5指向規(guī)則2的虛線改為規(guī)則6指向規(guī)則2和規(guī)則5指向規(guī)則6。

有向無環(huán)圖入庫的步驟圖解如圖3所示。

圖3 有向無環(huán)圖入庫步解

通過上面兩種方式對“一邊/一邊”的6條規(guī)則進(jìn)行入庫，從入庫步驟可以看出，優(yōu)先級方式簡單易實(shí)現(xiàn)，但是不直觀。有向無環(huán)圖方式，雖然入庫相對來說要更復(fù)雜一些，但是能夠很好的表示出規(guī)則之間的那種包含關(guān)系。從存儲空間的角度考慮，優(yōu)先級只需要增加一個(gè)“優(yōu)先級”的屬性字段，而有向無環(huán)圖方式需要增加“前驅(qū)”和“后繼”兩個(gè)字段，字段類型也不同，前者是一個(gè)數(shù)字，后者是一個(gè)集合，所有從空間考慮優(yōu)先級方式更節(jié)省空間。但從時(shí)間的角度考慮，主要是比較入庫的規(guī)則匹配次數(shù)，通過表4所示，總的比較次數(shù)有向無環(huán)圖方式比較次數(shù)要低，因此入庫要快。而且這種方式對規(guī)則的調(diào)用也是產(chǎn)生同樣的效果，節(jié)省規(guī)則匹配的時(shí)間。

表4 “一邊/一邊”規(guī)則兩種入庫方式比較

從表中的數(shù)字可以看出，當(dāng)表中的相關(guān)規(guī)則比較少時(shí)(只入庫了規(guī)則1、2、3、4時(shí))，在入庫時(shí)規(guī)則的匹配是次數(shù)是一樣的，隨著規(guī)則的增加，有向無環(huán)圖的時(shí)間優(yōu)勢就體現(xiàn)出來了。規(guī)則5入庫節(jié)省了25%，規(guī)則6入庫節(jié)省了20%的匹配時(shí)間。因此隨著規(guī)則庫的擴(kuò)大，有向無環(huán)圖的沖突處理方式的性能優(yōu)勢更能體現(xiàn)出來。

5 系統(tǒng)檢測處理的結(jié)果與分析

規(guī)則的挖掘分成三個(gè)步驟： 使用分詞軟件對語料庫中的復(fù)句進(jìn)行分詞、對照關(guān)系詞及搭配庫進(jìn)行關(guān)系詞識別、提取句子特征填寫以關(guān)系詞為索引的規(guī)則項(xiàng)。雖然三個(gè)步驟每個(gè)步驟均借助計(jì)算機(jī)完成，但三個(gè)步驟單獨(dú)進(jìn)行，沒有形成“自動(dòng)”的過程，在規(guī)則項(xiàng)生成時(shí)依靠“人工”總結(jié)規(guī)則項(xiàng)。這樣“人工挖掘”的規(guī)則總共有1 029條。其中連用規(guī)則表中150條，普通規(guī)則表482條，普通句式表157條，連用句式表240條。根據(jù)前期的規(guī)則分類，我們將規(guī)則依次分類入庫，規(guī)則自動(dòng)入庫的情況如表5所示。

表5 規(guī)則入庫結(jié)果

從表中可以看出規(guī)則的沖突所占的比例為6.6%，而這1 029條規(guī)則是人工挖掘后再集中入庫的，有的規(guī)則重復(fù)與規(guī)則矛盾人工很容易發(fā)現(xiàn)，為了測試系統(tǒng)對規(guī)則重復(fù)和矛盾的處理，在入庫時(shí)特意制造了一些規(guī)則的重復(fù)和矛盾規(guī)則進(jìn)行測試。規(guī)則沖突的比例很低的主要原因是由于漢語復(fù)句的復(fù)雜性以及約束條件的制定涉及到的類型之多而形成的，與“人工”制定規(guī)則也有關(guān)系，因此越是規(guī)則制定的詳細(xì)，規(guī)則的沖突就越少，處理的結(jié)果就越準(zhǔn)確。

在人工集中大量規(guī)則入庫時(shí)，除去人工加入的一些矛盾規(guī)則和重復(fù)規(guī)則的因素，規(guī)則沖突中規(guī)則包含的沖突所占的比例是很大的，主要是由于規(guī)則的約束條件的嚴(yán)格與寬松。若一個(gè)關(guān)系標(biāo)記序列有約束條件非常寬松的一條規(guī)則，那它接下來的入庫規(guī)則中與之產(chǎn)生沖突的可能性就越大。

從規(guī)則處理的情況來看，所有發(fā)現(xiàn)的沖突都得到了相應(yīng)的處理，規(guī)則的重復(fù)和規(guī)則的矛盾情況比較好判斷。而規(guī)則的包含情況，在所入庫的規(guī)則中遇到的23例包含約束都得到了檢測和相應(yīng)的處理。

6 結(jié)語

本文主要解決了規(guī)則自動(dòng)生成系統(tǒng)中規(guī)則的沖突檢測與處理的問題，它作為整個(gè)規(guī)則自動(dòng)生成系統(tǒng)的核心部分，利用規(guī)則的各個(gè)字段的值來進(jìn)行沖突檢測判斷，并將產(chǎn)生沖突的規(guī)則進(jìn)行分類處理，重復(fù)規(guī)則阻止入庫，矛盾規(guī)則提出警告并阻止入庫，若是包含關(guān)系的規(guī)則就利用有向無環(huán)圖的方式進(jìn)行邏輯的處理，然后入庫。

利用該檢測方法和有向無環(huán)圖的處理方式，入庫了1 029條規(guī)則。實(shí)驗(yàn)表明，利用本文的方法對規(guī)則檢測和處理正確率達(dá)到100%。這是一個(gè)非常理想的效果。這也說明，本文所研究的規(guī)則自動(dòng)生成系統(tǒng)沖突檢測與處理的方法和實(shí)現(xiàn)算法是比較有效的。

由于本系統(tǒng)中現(xiàn)有規(guī)則表中的規(guī)則是由人工整理并自動(dòng)入庫，其效率不高，因此應(yīng)深入研究規(guī)則的自動(dòng)挖掘技術(shù)，在此基礎(chǔ)上完成規(guī)則的自動(dòng)生成，使得整個(gè)系統(tǒng)更加自動(dòng)化。

[1] 劉遷,賈惠波. 中文信息處理中自動(dòng)分詞技術(shù)的研究與展望[J].計(jì)算機(jī)工程與應(yīng)用,2006,(03): 175-177.

[2] Sproat R， Emerson T. The First International Chinese Word Segmentation Bakeoff[C]//Proceedings of the Second SIGHAN Workshop on Chinese Language Processing.Sapporo, Japan: July 11-12,2003：133-143.

[3] 黃昌寧,趙海.中文分詞十年回顧[J].中文信息學(xué)報(bào),2007,21(3):8-18.

[4] 賈宗福,王知非.中文句子相似度計(jì)算的研究[J].科技信息,2009，(11)： 402-403.

[5] 昝紅英,左維松,張坤麗等.規(guī)則和統(tǒng)計(jì)相結(jié)合的情感分析研究[J]. 計(jì)算機(jī)工程與科學(xué),2011,(5):146-150.

[6] 尤昉,李涓子,王作英. 基于語義依存關(guān)系的漢語語料庫的構(gòu)建[J].中文信息學(xué)報(bào),2003，17(1):46-53.

[7] 邢福義.復(fù)句與關(guān)系詞[M].哈爾濱: 黑龍江人民出版社, 1985.

[8] 胡金柱，舒江波，等.面向中文信息處理的復(fù)句關(guān)系詞提取算法[J].計(jì)算機(jī)工程與科學(xué), 2009 (10).

[8] 周強(qiáng),黃昌寧.漢語句法規(guī)則的自動(dòng)構(gòu)造方法研究[J].中文信息學(xué)報(bào),1998,12(3):1-7.

[9] 李渝勤,孫麗華.基于規(guī)則的自動(dòng)分類在文本分類中的應(yīng)用[J],中文信息學(xué)報(bào),2004,18(4):9-14.

[10] 傅間蓮,陳群秀.基于規(guī)則和統(tǒng)計(jì)的中文自動(dòng)文摘系統(tǒng)[J],中文信息學(xué)報(bào),2006,20(5):10-16.

[11] 代翠,周俏麗,蔡東風(fēng),等.統(tǒng)計(jì)和規(guī)則相結(jié)合的漢語最長名詞短語自動(dòng)識別[J],中文信息學(xué)報(bào),2008,22(6):110-115.

[12] 于淼,呂雅娟,蘇勁松,等.規(guī)則和統(tǒng)計(jì)相結(jié)合的中文地址翻譯方法[J],中文信息學(xué)報(bào),2012,26(3):49-53.

[13] 胡金柱，陳江曼等.基于規(guī)則的連用關(guān)系標(biāo)記的自動(dòng)標(biāo)識研究[J].計(jì)算機(jī)科學(xué)，2012,(7):190-194.

Rule Conflict Resolution for Relation Word in Chinese Compound Sentences

YANG Jincai1, XIE Fang2, WANG Zhonghua1, HU Jinzhu1

(1. School of Computer Science of Huazhong Normal University， Wuhan, Hubei 430079, China；2. School of Computer Science of Hubei University of Technology， Wuhan, Hubei 430068, China)

Relation words are very important to the study of semantic relationships among clauses in compound sentences. Rule based relation word identification demands dynamic and constantly improved rules. This article investigates how to recognize the rule conflicts and solve them. Compound sentences have four kinds of rules: common rules, even words rules, common sentence pattern rules, and collocation patterns rule. This article gives a formal description of all the rules and the way of storing them, based on which we designed the flow of relation word detection, rule condition detection, result detection. A way of detecting the conflicts is given, include another two ways of solving the conflicts-priority mode and directed acyclic graph mode. With this proposed method, we have imported more than 1067 rules, with a correct rate of 100%.

relation words in compound sentences; rule conflicts; directed acyclic graph

楊進(jìn)才(1967-),博士,教授,主要研究領(lǐng)域?yàn)閿?shù)據(jù)庫和中文信息處理。E-mail:jcyang@mail.ccnu.edu.cn謝芳(1981-),博士研究生,講師,主要研究領(lǐng)域?yàn)橹形男畔⑻幚砗蛙浖こ?。E-mail:thanks_xf@hotmail.com胡金柱(1947-),教授,博士生導(dǎo)師,主要研究領(lǐng)域?yàn)橹形男畔⑻幚砗蛙浖こ?。E-mail:jzhu@mail.ccnu.edu.cn

1003-0077(2015)04-0008-08

2013-10-06 定稿日期： 2014-04-09

國家教育部人文社科基金(13YJAZH117),國家社科基金(11BYY052)

TP391

A