張 瑞，李躍新，洪宗祥

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

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

1 自然語言查詢問題描述

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

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

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

則轉(zhuǎn)換過程如如圖1～3所示。

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

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

圖3 關(guān)系樹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描述了語義網(wǎng)絡(luò)中有向邊的起始節(jié)點，其屬性分別為NodeID節(jié)點 ID，NodeName節(jié)點名稱，EndNodePointer為指向 End_Node_Table的指針；End_Node_Table描述了語義網(wǎng)中有向邊的終止節(jié)點，其屬性分別為NodeID有向邊終止節(jié)點 ID，NodeName節(jié)點名稱，Node Relation為起始節(jié)點和終止節(jié)點之間的聯(lián)系 （包括is a，member of，live in 等）。

2 查詢算法描述

2.1 句型模板匹配算法

論文將知識庫知識節(jié)點構(gòu)建詞典，詞典中按照詞性分類建表如名詞表，疑問詞表等，列舉常見句型構(gòu)成句型模板表。用戶的查詢從語義上分為2類：第1，求知性查詢，即用戶的目的是從知識庫系統(tǒng)中獲取未來知識，常用的句型如：“什么是人工智能？”，“網(wǎng)絡(luò)協(xié)議是什么”等，第2，求證性查詢，即用戶已具備某些相關(guān)領(lǐng)域的知識，其目的是通過知識庫系統(tǒng)對這些知識進行求證或補充，常用的句型是：“計算機系統(tǒng)是由硬件系統(tǒng)和軟件系統(tǒng)組成的嗎？”等[4]。句型模板的采集采用概念－屬性模型：概念用C表示，如有多個概念用C1，C2，C3…表示，屬性用A表示，多個屬性用A1，A2，A3…表示，用 A.V表示屬性A的內(nèi)容，用點記號表示屬性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利用模糊集方法為每一個詞組i設(shè)定一個相似度閾值 T；

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

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

2.2 一般直接知識查詢算法

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

2.3 隱含知識查詢算法

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

圖4 “學(xué)生”詞匯概念樹Fig.4 Concept-tree of“student”

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

Step1將自然語言分詞后查詢是否有隱含詞匯，若有轉(zhuǎn)Step2，若沒有，采用直接知識查詢算法查詢；

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

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

2.4 算法分析

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

3 結(jié) 論

論文在關(guān)系模型的基礎(chǔ)上提出了關(guān)系樹模型，并基于關(guān)系樹提出了正向，逆向直接知識查詢算法以及隱含知識查詢算法，該算法有效的解決了基于知識庫中知識查詢問題。因論文的篇幅有限，論文中存在如只列舉出少量常用句型模板，句型模板匹配算法及隱含查詢算法用偽代碼表示，關(guān)系樹模型本身的一些缺陷以及查詢算法為多項式級等問題，為知識查詢提出更加強大的優(yōu)化算法將是論文今后研究的重點，作者已考慮將并行計算的思想引入進來解決相關(guān)問題，相關(guān)問題的研究成果將在后續(xù)論文中發(fā)表。

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

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

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

[4]唐素勤，李波.基于句型模板的智能問答系統(tǒng)[J].廣西師范大學(xué)學(xué)報，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]劉軍.基于短消息的知識查詢系統(tǒng)[D].長江：中南大學(xué)：2006.

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