基于關系樹的知識查詢算法研究

洪宗祥,李躍新

(湖北大學數學與計算機科學學院,湖北 武漢 430062)

自1956年提出人工智能以來,廣大的科研工作者對其進行了廣泛而深入的研究,同時也取得了一定的成果,直到20世紀70年代“知識工程”概念的提出,可謂是人工智能領域發展的里程碑.隨著專家系統的出現并且逐步商業化,知識工程的技術和理論也日益更新.到21世紀,知識自動獲取,知識庫系統的理論與技術和分布式知識庫系統成為研究的主要內容[1],有關知識庫中知識的表示存儲以及推理查詢成為國內外科研工作者研究的熱點.自然語言查詢問題更是其中重要組成部分.自然語言查詢就是研究如何使計算機理解并生成人們日常所使用的語言,并對人給計算機提出的問題用自然語言進行反饋[2].本文中提出的在關系模型的語義網知識表示基礎上,將其轉換成關系樹模型,對基于該模型提出一般直接知識的正向、逆向知識查詢算法以及隱含知識查詢算法.

1 自然語言查詢問題描述

圖1 語義網絡

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

假設一段知識的事實描述如下.

小明和小麗是x小學6年級學生,他倆是y小區的鄰居.

則轉換過程如下：

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

Start _Node _Table(NodeID, NodeName, EndNodePointer)

End_ Node_ Table(NodeID, NodeName, NodeRelation)

圖2 關系模型

圖3 關系樹模型

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

2 查詢算法描述

2.1句型模板匹配算法論文將知識庫知識節點構建詞典,詞典中按照詞性分類建表如名詞表,疑問詞表等,列舉常見句型構成句型模板表.用戶的查詢從語義上分為兩類：第一,求知性查詢,即用戶的目的是從知識庫系統中獲取未來知識,常用的句型如：“什么是人工智能？”,“網絡協議是什么”等,第二,求證性查詢,即用戶已具備某些相關領域的知識,其目的是通過知識庫系統對這些知識進行求證或補充,常用的句型是“計算機系統是由硬件系統和軟件系統組成的嗎？”等[4].句型模板的采集采用概念-屬性模型：概念用C表示,如有多個概念用C1,C2,C3…表示,屬性用A表示,多個屬性用A1,A2,A3…表示,用A.V表示屬性A的內容,用點記號表示屬性A的隸屬度,如概念C的屬性A為C.A,其內容為C.A.V,因此查詢最終歸結為概念查詢,概念關系查詢以及概念間關聯查詢等,部分模板如下[5]：

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

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

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

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

SM算法如下：

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

Step2:從自然語言句首進行最大匹配分詞,根據詞典結構,在當前漢字開頭的字串進行查找,測算當前匹配字串的相似度Ti,分詞閾值為Tmi,若Tmi≤Tm且Ti≥T,則分詞匹配成功；否則,調用多級相似詞庫,在最佳近似匹配條件下得出認為匹配的字串；

Step3:將句型的結構信息轉化成查詢的語義信息,利用模糊集方法與模板進行匹配,若Md≧Ts,則認定當前句型與匹配模板匹配成功,否則轉向Step2.

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

typedef struct Arcnode

{int Id; //節點ID號

char Name; //節點名稱 IofoType *p,*root; //終止節點指針,根指針

}Arcnode;

void ForwardDKQ(kT &G)

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

int ID[Nodenum];//定義節點Id號數組

cin>>Id>>Nodenum; //輸入待查詢節點Id及節點數

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

cin>>ID[i];//輸入所有節點Id號

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++; }//查詢關系表

cout<

<

}//正向直接知識查詢算法

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]; //輸入所有節點Id號

cin>>Id>>Nodenum; //輸入待查詢節點Id

p[0]=root;

while(j<=Nodenum)

{j++;

if(p[j]=null) cout<

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

{++k; ++q; count1++;}//查詢關系表

count2++；

}//查詢鄰接表

Cout<

<

}//逆向直接知識查詢算法

圖4 “學生”詞匯概念樹

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

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

Step1：將自然語言分詞后查詢是否有隱含詞匯,若有轉Step2;若沒有,采用直接知識查詢算法查詢；

Step2：查詢隱含知識的概念圖,表示出具體詞匯以及之間的關系,查看文法規則庫；

Step3：輸出查詢結果,與當前模板匹配,將結果反饋給用戶.

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

3 結論

在關系模型的基礎上提出了關系樹模型,并基于關系樹提出了正向、逆向直接知識查詢算法以及隱含知識查詢算法,該算法有效地解決了基于知識庫中知識查詢問題.由于篇幅有限,論文中存在如只列舉出少量常用句型模板,句型模板匹配算法及隱含查詢算法用偽代碼表示,關系樹模型本身的一些缺陷以及查詢算法為多項式級等問題,為知識查詢提出更加強大的優化算法將是今后研究的重點,并已考慮將并行計算的思想引入進來解決相關問題.

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

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

[3] 熊冬明.漢語自動分詞和中文人名識別技術研究[D].合肥：合肥工業大學,2006.

[4] 唐素勤,李波,許永敏.基于句型模板的智能問答系統[J].廣西師范大學學報.2007,25(2):5-8.

[5] 劉軍.基于短消息的知識查詢系統[D].長沙：中南大學,2006.

[6] 嚴蔚敏,陳文博.數據結構及應用算法教程[M].北京：清華大學出版社,2008.