基于關(guān)系樹(shù)的知識(shí)查詢算法研究

洪宗祥,李躍新

(湖北大學(xué)數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院,湖北 武漢 430062)

自1956年提出人工智能以來(lái),廣大的科研工作者對(duì)其進(jìn)行了廣泛而深入的研究,同時(shí)也取得了一定的成果,直到20世紀(jì)70年代“知識(shí)工程”概念的提出,可謂是人工智能領(lǐng)域發(fā)展的里程碑.隨著專家系統(tǒng)的出現(xiàn)并且逐步商業(yè)化,知識(shí)工程的技術(shù)和理論也日益更新.到21世紀(jì),知識(shí)自動(dòng)獲取,知識(shí)庫(kù)系統(tǒng)的理論與技術(shù)和分布式知識(shí)庫(kù)系統(tǒng)成為研究的主要內(nèi)容[1],有關(guān)知識(shí)庫(kù)中知識(shí)的表示存儲(chǔ)以及推理查詢成為國(guó)內(nèi)外科研工作者研究的熱點(diǎn).自然語(yǔ)言查詢問(wèn)題更是其中重要組成部分.自然語(yǔ)言查詢就是研究如何使計(jì)算機(jī)理解并生成人們?nèi)粘Ｋ褂玫恼Z(yǔ)言,并對(duì)人給計(jì)算機(jī)提出的問(wèn)題用自然語(yǔ)言進(jìn)行反饋[2].本文中提出的在關(guān)系模型的語(yǔ)義網(wǎng)知識(shí)表示基礎(chǔ)上,將其轉(zhuǎn)換成關(guān)系樹(shù)模型,對(duì)基于該模型提出一般直接知識(shí)的正向、逆向知識(shí)查詢算法以及隱含知識(shí)查詢算法.

1 自然語(yǔ)言查詢問(wèn)題描述

圖1 語(yǔ)義網(wǎng)絡(luò)

自然語(yǔ)言查詢問(wèn)題最初在搜索引擎方面比較突出,現(xiàn)階段由于知識(shí)工程概念的推出,使得基于知識(shí)庫(kù)系統(tǒng)的自然語(yǔ)言查詢顯得尤為重要.通常是用戶在系統(tǒng)查詢界面上輸入自然語(yǔ)言,而系統(tǒng)在后臺(tái)執(zhí)行處理操作,進(jìn)而把查詢結(jié)果返回給用戶的過(guò)程.后臺(tái)處理的基本思想是：先對(duì)自然語(yǔ)言進(jìn)行分詞,預(yù)處理,然后進(jìn)行語(yǔ)義分析,知識(shí)提取,模板匹配以及反饋結(jié)果等[3].其中,分詞也是提取關(guān)鍵詞的過(guò)程,因此大多數(shù)自然語(yǔ)言查詢本質(zhì)是關(guān)鍵詞查詢.本文中主要是對(duì)知識(shí)提取模塊中知識(shí)查詢算法進(jìn)行研究.知識(shí)提取基本思想為：第一步：將知識(shí)庫(kù)中的知識(shí)用語(yǔ)義網(wǎng)絡(luò)表示(如圖1),將語(yǔ)義網(wǎng)絡(luò)中有向邊的起始節(jié)點(diǎn)與終止節(jié)點(diǎn)的關(guān)系構(gòu)成關(guān)系模型(如圖2),將關(guān)系模型順時(shí)針旋轉(zhuǎn)90°得到關(guān)系樹(shù)模型(如圖3).第二步：在此關(guān)系樹(shù)模型上進(jìn)行查詢,調(diào)用查詢算法,返回查詢知識(shí)與當(dāng)前模板匹配.第三步：返回查詢結(jié)果.其中,第二步是論文研究核心.下面簡(jiǎn)單說(shuō)明上文中從語(yǔ)義網(wǎng)絡(luò)到關(guān)系模型以及關(guān)系樹(shù)的轉(zhuǎn)換過(guò)程.

假設(shè)一段知識(shí)的事實(shí)描述如下.

小明和小麗是x小學(xué)6年級(jí)學(xué)生,他倆是y小區(qū)的鄰居.

則轉(zhuǎn)換過(guò)程如下：

其中,Start _Node_ Table 和End _Node _Table 定義如下：

Start _Node _Table(NodeID, NodeName, EndNodePointer)

End_ Node_ Table(NodeID, NodeName, NodeRelation)

圖2 關(guān)系模型

圖3 關(guān)系樹(shù)模型

Start_Node_Table描述了語(yǔ)義網(wǎng)絡(luò)中有向邊的起始節(jié)點(diǎn),其屬性分別為NodeID節(jié)點(diǎn)ID, NodeName節(jié)點(diǎn)名稱,EndNodePointer為指向End_ Node_ Table的指針；End_Node_Table描述了語(yǔ)義網(wǎng)中有向邊的終止節(jié)點(diǎn),其屬性分別為NodeID有向邊終止節(jié)點(diǎn)ID, NodeName節(jié)點(diǎn)名稱,NodeRelation為起始節(jié)點(diǎn)和終止節(jié)點(diǎn)之間的聯(lián)系(包括is a, member of,live in 等).

2 查詢算法描述

2.1句型模板匹配算法論文將知識(shí)庫(kù)知識(shí)節(jié)點(diǎn)構(gòu)建詞典,詞典中按照詞性分類建表如名詞表,疑問(wèn)詞表等,列舉常見(jiàn)句型構(gòu)成句型模板表.用戶的查詢從語(yǔ)義上分為兩類：第一,求知性查詢,即用戶的目的是從知識(shí)庫(kù)系統(tǒng)中獲取未來(lái)知識(shí),常用的句型如：“什么是人工智能？”,“網(wǎng)絡(luò)協(xié)議是什么”等,第二,求證性查詢,即用戶已具備某些相關(guān)領(lǐng)域的知識(shí),其目的是通過(guò)知識(shí)庫(kù)系統(tǒng)對(duì)這些知識(shí)進(jìn)行求證或補(bǔ)充,常用的句型是“計(jì)算機(jī)系統(tǒng)是由硬件系統(tǒng)和軟件系統(tǒng)組成的嗎？”等[4].句型模板的采集采用概念-屬性模型：概念用C表示,如有多個(gè)概念用C1,C2,C3…表示,屬性用A表示,多個(gè)屬性用A1,A2,A3…表示,用A.V表示屬性A的內(nèi)容,用點(diǎn)記號(hào)表示屬性A的隸屬度,如概念C的屬性A為C.A,其內(nèi)容為C.A.V,因此查詢最終歸結(jié)為概念查詢,概念關(guān)系查詢以及概念間關(guān)聯(lián)查詢等,部分模板如下[5]：

<句型1>：：C1,C2的屬性A1,A2是什么？(查詢概念的屬性)

<句型2>：：C的描述是什么？(查詢概念的描述)

<句型3>：：C和C1的關(guān)系？(查詢概念間關(guān)聯(lián))

為方便論述,設(shè)Tm為最大分詞閾值,T為相似度閾值,Ts為匹配成功的閾值,Wd為匹配程度,句型模板匹配算法(SM)偽代碼如下：

SM算法如下：

Step1:利用模糊集方法為每一個(gè)詞組i設(shè)定一個(gè)相似度閾值T；

Step2:從自然語(yǔ)言句首進(jìn)行最大匹配分詞,根據(jù)詞典結(jié)構(gòu),在當(dāng)前漢字開(kāi)頭的字串進(jìn)行查找,測(cè)算當(dāng)前匹配字串的相似度Ti,分詞閾值為Tmi,若Tmi≤Tm且Ti≥T,則分詞匹配成功；否則,調(diào)用多級(jí)相似詞庫(kù),在最佳近似匹配條件下得出認(rèn)為匹配的字串；

Step3:將句型的結(jié)構(gòu)信息轉(zhuǎn)化成查詢的語(yǔ)義信息,利用模糊集方法與模板進(jìn)行匹配,若Md≧Ts,則認(rèn)定當(dāng)前句型與匹配模板匹配成功,否則轉(zhuǎn)向Step2.

2.2一般直接知識(shí)查詢算法關(guān)系樹(shù)并非樹(shù),而是結(jié)合鄰接表和關(guān)系表兩種存儲(chǔ)結(jié)構(gòu),其上查詢必將具有兩種存儲(chǔ)結(jié)構(gòu)且兼容樹(shù)型結(jié)構(gòu)特點(diǎn).上層為鄰接表結(jié)構(gòu),下層為關(guān)系表.假設(shè)語(yǔ)義網(wǎng)絡(luò)中有N個(gè)節(jié)點(diǎn),每個(gè)節(jié)點(diǎn)建立索引號(hào)ID.一般直接知識(shí)就是能在關(guān)系樹(shù)模型中查詢到相應(yīng)關(guān)鍵字的事實(shí)描述的知識(shí),基于此查詢分為兩種：正向知識(shí)查詢和逆向知識(shí)查詢,正向即從上到下依次可查詢且從自然語(yǔ)言提煉的關(guān)鍵詞有終止節(jié)點(diǎn),如查詢過(guò)程中關(guān)鍵詞無(wú)終止節(jié)點(diǎn)且需要回溯稱為逆向查詢,算法選取語(yǔ)言為C++[6],查詢算法如下：

typedef struct Arcnode

{int Id; //節(jié)點(diǎn)ID號(hào)

char Name; //節(jié)點(diǎn)名稱 IofoType *p,*root; //終止節(jié)點(diǎn)指針,根指針

}Arcnode;

void ForwardDKQ(kT &G)

{ inti,j,k,Nodenum,count1=1,count2=1,*b;

int ID[Nodenum];//定義節(jié)點(diǎn)Id號(hào)數(shù)組

cin>>Id>>Nodenum; //輸入待查詢節(jié)點(diǎn)Id及節(jié)點(diǎn)數(shù)

for(i=1;i<=G.Nodenum;++i)

cin>>ID[i];//輸入所有節(jié)點(diǎn)Id號(hào)

while(Id!=ID[j]&&j<=Nodenum)

{++j; ++p;count1++;}//查詢鄰接表

if(j>=Nodenum) return false;

else cin>>Id;b=p;

while(Id! =ID[k]&&k<=Nodenum)

{++k;++b;count2++; }//查詢關(guān)系表

cout<

<

}//正向直接知識(shí)查詢算法

void BackwardDKQ(KT &G)

{inti,j,ID[Nodenum],j=0,count=0;

int *p[],*q;

for(i=1;i<=G.Nodenum;i++)

cin>>ID[i]; //輸入所有節(jié)點(diǎn)Id號(hào)

cin>>Id>>Nodenum; //輸入待查詢節(jié)點(diǎn)Id

p[0]=root;

while(j<=Nodenum)

{j++;

if(p[j]=null) cout<

while(Id!= (p[j].Id)&&k<=Nodenum)

{++k; ++q; count1++;}//查詢關(guān)系表

count2++；

}//查詢鄰接表

Cout<

<

}//逆向直接知識(shí)查詢算法

圖4 “學(xué)生”詞匯概念樹(shù)

2.3隱含知識(shí)查詢算法知識(shí)庫(kù)中直接知識(shí)可以通過(guò)上述算法查詢,但有的知識(shí)是隱含的不能直接查詢可得,這樣的知識(shí)稱為隱含知識(shí).知識(shí)庫(kù)中隱含知識(shí)大致可分為兩類：一類是知識(shí)庫(kù)特值詞匯知識(shí),例如：“學(xué)生”一詞,通常在數(shù)據(jù)庫(kù)中沒(méi)有“學(xué)生”這個(gè)抽象詞匯,取而代之的是“小學(xué)生”,“中學(xué)生”,“大學(xué)生”等具體的詞匯.另一類是知識(shí)庫(kù)相關(guān)操作詞匯知識(shí),是由知識(shí)之間相關(guān)性引起的.例如：“實(shí)收入”一詞,是收入減去成本所得,但在知識(shí)庫(kù)中通常不會(huì)有這樣的詞匯(易產(chǎn)生數(shù)據(jù)冗余).因此,隱含知識(shí)的共性就是“抽象性”,具體解決方法為抽象化具體,即將隱含知識(shí)轉(zhuǎn)化為直接知識(shí).針對(duì)隱含知識(shí)的特殊性,采用概念樹(shù)表示隱含知識(shí)(如圖4).

如圖4所示,將學(xué)生具體為小學(xué)生,中學(xué)生,大學(xué)生等具體詞匯,因此隱含知識(shí)查詢算法前步操作是轉(zhuǎn)換,后步操作是直接知識(shí)查詢,算法如下：

Step1：將自然語(yǔ)言分詞后查詢是否有隱含詞匯,若有轉(zhuǎn)Step2;若沒(méi)有,采用直接知識(shí)查詢算法查詢；

Step2：查詢隱含知識(shí)的概念圖,表示出具體詞匯以及之間的關(guān)系,查看文法規(guī)則庫(kù)；

Step3：輸出查詢結(jié)果,與當(dāng)前模板匹配,將結(jié)果反饋給用戶.

2.4算法分析在此主要針對(duì)正向直接知識(shí)查詢算法進(jìn)行分析.正向直接知識(shí)查詢算法,大致思想為：通過(guò)層次遍歷查詢方式從上到下進(jìn)行查詢,返回關(guān)鍵詞以及之間的聯(lián)系.如：用戶提問(wèn)小明的地址是y小區(qū)嗎？結(jié)果返回：小明live in y小區(qū),后續(xù)步驟就是模板匹配,反饋給用戶查詢結(jié)果,該算法有效地解決了直接知識(shí)的查詢.算法的復(fù)雜度為O(n2),是多項(xiàng)式級(jí)的,當(dāng)n較大時(shí),查詢時(shí)間較長(zhǎng),因此在算法優(yōu)化方面是今后研究的重點(diǎn).

3 結(jié)論

在關(guān)系模型的基礎(chǔ)上提出了關(guān)系樹(shù)模型,并基于關(guān)系樹(shù)提出了正向、逆向直接知識(shí)查詢算法以及隱含知識(shí)查詢算法,該算法有效地解決了基于知識(shí)庫(kù)中知識(shí)查詢問(wèn)題.由于篇幅有限,論文中存在如只列舉出少量常用句型模板,句型模板匹配算法及隱含查詢算法用偽代碼表示,關(guān)系樹(shù)模型本身的一些缺陷以及查詢算法為多項(xiàng)式級(jí)等問(wèn)題,為知識(shí)查詢提出更加強(qiáng)大的優(yōu)化算法將是今后研究的重點(diǎn),并已考慮將并行計(jì)算的思想引入進(jìn)來(lái)解決相關(guān)問(wèn)題.

[1] Dimitris N,Chorafas.Knowledge engineering[M].NewYork：Van Nostrand Reinhold, 1990.

[2] 金聰,戴上平,郭京蕾,等.人工智能教程[M].北京：清華大學(xué)出版社,2007.

[3] 熊冬明.漢語(yǔ)自動(dòng)分詞和中文人名識(shí)別技術(shù)研究[D].合肥：合肥工業(yè)大學(xué),2006.

[4] 唐素勤,李波,許永敏.基于句型模板的智能問(wèn)答系統(tǒng)[J].廣西師范大學(xué)學(xué)報(bào).2007,25(2):5-8.

[5] 劉軍.基于短消息的知識(shí)查詢系統(tǒng)[D].長(zhǎng)沙：中南大學(xué),2006.

[6] 嚴(yán)蔚敏,陳文博.數(shù)據(jù)結(jié)構(gòu)及應(yīng)用算法教程[M].北京：清華大學(xué)出版社,2008.