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

張 瑞，李躍新，洪宗祥

（1.商丘師范學(xué)院 計(jì)算機(jī)與信息技術(shù)學(xué)院，河南 商丘 476000；2.湖北大學(xué) 數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院，湖北 武漢 430062）

自1956年提出人工智能研究領(lǐng)域以來(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]。作者在文獻(xiàn)[1]中提出的關(guān)系模型的語(yǔ)義網(wǎng)知識(shí)表示基礎(chǔ)上，將其轉(zhuǎn)換成關(guān)系樹(shù)模型，對(duì)基于該模型提出一般直接知識(shí)的正向，逆向知識(shí)查詢算法以及隱含知識(shí)查詢算法。

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

自然語(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í)提取基本思想為：第1步：將知識(shí)庫(kù)中的知識(shí)用語(yǔ)義網(wǎng)絡(luò)表示，將語(yǔ)義網(wǎng)絡(luò)中有向邊的起始節(jié)點(diǎn)與終止節(jié)點(diǎn)的關(guān)系構(gòu)成關(guān)系模型，將關(guān)系模型順時(shí)針旋轉(zhuǎn)90度得到關(guān)系樹(shù)模型，第2步：在此關(guān)系樹(shù)模型上進(jìn)行查詢，調(diào)用查詢算法，返回查詢知識(shí)與當(dāng)前模板匹配，第3步：返回查詢結(jié)果。其中，第2步是論文研究核心。下面簡(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ò)程如如圖1～3所示。

圖1 語(yǔ)義網(wǎng)絡(luò)Fig.1 Emantic network

圖2 關(guān)系模型Fig.2 Relation model

圖3 關(guān)系樹(shù)Fig.3 Relation tree model

其中，Start_Node_Table和End_Node_Table定義如下：

Start_Node_Table（NodeID，NodeName，EndNodePointer）

End_Node_Table（NodeID，NodeName，NodeRelation）

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)名稱，Node Relation為起始節(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ǔ)義上分為2類：第1，求知性查詢，即用戶的目的是從知識(shí)庫(kù)系統(tǒng)中獲取未來(lái)知識(shí)，常用的句型如：“什么是人工智能？”，“網(wǎng)絡(luò)協(xié)議是什么”等，第2，求證性查詢，即用戶已具備某些相關(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]，查詢算法如下：

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 “學(xué)生”詞匯概念樹(shù)Fig.4 Concept-tree of“student”

如圖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)題，相關(guān)問(wèn)題的研究成果將在后續(xù)論文中發(fā)表。

[1]Dimitris N.Chorafas.Knowledge engineering[M].NewYork:Van Nostrand Reinhold，1990.

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

[3]熊冬明.漢語(yǔ)自動(dòng)分詞和中文人名識(shí)別技術(shù)研究 [D].杭州：浙江大學(xué)，2006.

[4]唐素勤，李波.基于句型模板的智能問(wèn)答系統(tǒng)[J].廣西師范大學(xué)學(xué)報(bào)，2007（6）：5－8.TANG Su-qin，LI Bo.Intelligent question answering system based on sentence template[J].Journal of Guangxi Normal University，2007（6）：5－8.

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

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