夏海峰,陳軍華
(上海師范大學(xué) 計(jì)算機(jī)系,上海200234)
在當(dāng)今信息時(shí)代,萬維網(wǎng)成了主要的資源。隨著萬維網(wǎng)的飛速發(fā)展,使得其在全球網(wǎng)絡(luò)中所占的比重越來越大,其內(nèi)部涵蓋的信息也越來越豐富。然而對(duì)于其內(nèi)部所包含的Deep Web,卻沒有被很好地開發(fā)和利用。根據(jù)Bright Planet對(duì) Deep Web統(tǒng)計(jì)而發(fā)布的白皮書[1],截止到2011年,共有600萬個(gè)中文萬維網(wǎng)數(shù)據(jù)庫,并且每天都以指數(shù)級(jí)的速度增長(zhǎng)。傳統(tǒng)意義上的萬維網(wǎng)數(shù)據(jù)搜索只能通過查詢接口(即HTML表單)被用戶訪問,用戶得到的反饋內(nèi)容也僅僅局限于查詢接口與后臺(tái)數(shù)據(jù)庫交互之后生成的查詢頁面內(nèi)容。
基于當(dāng)前中文Deep Web數(shù)據(jù)庫的研究現(xiàn)狀,本文提出了基于語義相似度計(jì)算的中文Deep Web數(shù)據(jù)查詢方法。該方法旨在通過基于計(jì)算關(guān)鍵詞和屬性詞典之間的語義相似度,將用戶查詢的關(guān)鍵詞映射到具體的領(lǐng)域,最大程度地縮減數(shù)據(jù)庫的查詢范圍,最終提高查詢的效率。對(duì)于Deep Web數(shù)據(jù)庫,本文采用數(shù)據(jù)集成技術(shù)[2],將同一領(lǐng)域的數(shù)據(jù)庫表結(jié)構(gòu)采用標(biāo)簽的形式,形成對(duì)應(yīng)的屬性詞典,從而實(shí)現(xiàn)前后臺(tái)的無縫連接。
知網(wǎng)(HowNet)是一個(gè)以漢語和英語的詞語所代表的概念為描述對(duì)象,以揭示概念與概念之間以及概念所具有的屬性之間的關(guān)系為基本內(nèi)容的常識(shí)知識(shí)庫。其體系架構(gòu)如圖1所示。知網(wǎng)體系包含豐富的語義知識(shí)和相關(guān)本體知識(shí)。在知網(wǎng)中,所有詞匯的概念都是基于以下兩個(gè)主要概念:
(1)概念。它是對(duì)詞匯語義的一種描述,每一個(gè)詞可以表達(dá)為幾個(gè)義項(xiàng)。義項(xiàng)是用一種知識(shí)表示語言來描述的,這種知識(shí)表示語言所用的詞匯叫做概念。
圖1 知網(wǎng)體系架構(gòu)
(2)義原。它是用于描述一個(gè)概念的最小意義單位,從所有詞匯中提煉出的可以用來描述其他詞匯的不可再分的基本元素。
在知網(wǎng)體系中,每個(gè)詞匯都由一個(gè)四元組W_C=詞語;E_C=詞語例子;G_C=詞語詞性;DEF=概念定義)表示而成,并且在知網(wǎng)體系中,它并不像同義詞詞林那樣將所有的概念歸結(jié)到一個(gè)樹狀的概念層次體系中,而是每一個(gè)概念都是由義原采用四元組的形式加以表示。圖2顯示的是關(guān)鍵詞“北京”基于知網(wǎng)的語義表示形式。
圖2 關(guān)鍵詞“北京”
在Deep Web數(shù)據(jù)庫中,本文引入了屬性詞典的概念[3]。事先在數(shù)據(jù)庫中創(chuàng)建一個(gè)屬性詞典(稱之為Attr-Dict表),該表的作用在于保存數(shù)據(jù)庫中每一張表結(jié)構(gòu)的字段和對(duì)于該字段的詳細(xì)解釋。該屬性詞典主要用于計(jì)算關(guān)鍵詞和后臺(tái)數(shù)據(jù)庫屬性列之間的語義相似度。
該AttrDict表的表結(jié)構(gòu)如下:
其中,字段columName為數(shù)據(jù)列名,字段tableName為對(duì)應(yīng)的表名,字段description為屬性對(duì)應(yīng)的描述。
在本文的數(shù)據(jù)源中,假定其中的兩張表如下:
則對(duì)應(yīng)的AttrDict表對(duì)應(yīng)的字段如表1所示。
表1 屬性詞典表結(jié)構(gòu)示例
圖3 基于語義相似度計(jì)算Deep Web數(shù)據(jù)庫查詢
本文在計(jì)算關(guān)鍵詞[4-5]的語義相似度時(shí),采用基于詞語相似度的計(jì)算方法,其流程如圖3所示。計(jì)算出當(dāng)前關(guān)鍵詞和屬性詞典每個(gè)屬性列的相關(guān)聯(lián)程度,設(shè)定一個(gè)起初的閾值,當(dāng)相似度計(jì)算所得結(jié)果大于該閾值時(shí),認(rèn)為當(dāng)前屬性列對(duì)應(yīng)的領(lǐng)域即是當(dāng)前關(guān)鍵詞對(duì)應(yīng)的領(lǐng)域R,這樣也就確定了關(guān)鍵詞K和屬性列之間的對(duì)應(yīng)關(guān)系,從而確定對(duì)應(yīng)的表結(jié)構(gòu)的字段集合C,最終根據(jù)生成的一個(gè)完成的SQL查詢語句,將查詢的結(jié)構(gòu)反饋給用戶。
基于HowNet的詞語相似度[6]充分利用了 HowNet對(duì)每個(gè)概念描述時(shí)的語義信息,但沒有考慮到在信息檢索過程中關(guān)鍵詞的相關(guān)詞的語義相似度,這樣可能減少實(shí)際上關(guān)鍵詞的相關(guān)詞的檢索范圍?;谝陨嫌^點(diǎn),本文提出了一種改進(jìn)的詞語相似度計(jì)算方法[7],主要工作如下:
(1)首先利用詞林(哈工大版)[8]獲得當(dāng)前關(guān)鍵詞的相關(guān)詞集合;
(2)基于HowNet獲得相關(guān)詞集合的每個(gè)相關(guān)詞的概念定義(DEF);
(3)利用知網(wǎng)計(jì)算相關(guān)概念詞集合詞語和屬性詞典的概念相似度。
定義1 利用詞林(哈工大版)尋找相關(guān)詞,形成相關(guān)詞集合,用下面一個(gè)4元組構(gòu)成:
定義2 關(guān)鍵詞概念定義(DEF)用下面一個(gè)5元組構(gòu)成:
其中,ID表示單標(biāo)識(shí)符,由系統(tǒng)自動(dòng)賦予并唯一表示;KEYWORD表示當(dāng)前檢索系統(tǒng)提交的關(guān)鍵詞;RELATE_WORD表示通過詞林獲得關(guān)鍵詞的相關(guān)詞;N為正整數(shù),表示提交表單中概念定義屬性的個(gè)數(shù);DEF_VALUE為概念定義屬性名/值對(duì)集合,用來表示當(dāng)前關(guān)鍵詞的概念定義的詳細(xì)信息,其個(gè)數(shù)為N。
(1)詞語相似度:
假設(shè)現(xiàn)有兩個(gè)詞語A1和A2,A1由m個(gè)概念組成,A2由n個(gè)概念組成,如下表示:
[6]認(rèn)為兩個(gè)詞語的相似度,也就是兩個(gè)詞語的概念的任意組合的相似度的最大值。其計(jì)算采用的是最大值匹配法,公式如下:
(2)概念相似度
參考文獻(xiàn)[6]把對(duì)義項(xiàng)的描述分為4類:第一基本義原描述、其他基本義原描述、關(guān)系義原描述和關(guān)系符號(hào)描述。假設(shè)義項(xiàng)C1有m個(gè)義原,C2有n個(gè)義原,如下式所示:
則對(duì)于義項(xiàng)C1、C2之間的相似度可以用義原的相似度加以描述:
Sim1(S1,S2)表 示 第 一 義 原 的 相 似 度 ,Sim2(S1,S2)表 示其他基本義原的相似度,Sim3(S1,S2)表示關(guān)系義原描述的相似度,Sim4(S1,S2)表示符號(hào)義原的相似度,并且 β1+β2+β3+β4=1。
(3)義原相似度
HowNet是一個(gè)具有網(wǎng)狀結(jié)構(gòu)的世界知識(shí)庫,義原相似度要利用義原間的上、下位關(guān)系來構(gòu)造一種樹狀結(jié)構(gòu)的義原層次體系,通過樹中各個(gè)義原節(jié)點(diǎn)之間的相互關(guān)系來計(jì)算。許多學(xué)者在這方面進(jìn)行了大量的研究,其中被廣泛認(rèn)可的是中科院劉群等人的公式:
定義 3 對(duì)于給定的閾值 E,如果 Sim(A,B)≥E(Sim為計(jì)算相似度的方法,詳見2.2節(jié)),則認(rèn)為關(guān)鍵詞相關(guān)詞A和數(shù)據(jù)庫列屬性概念描述B相匹配,Match(A,B)=1;否則 Math(A,B)=0,兩者不匹配。
為了規(guī)則化處理,假設(shè)A和B都存放在單鏈表中,A的表頭指針為 HeadA,B的表頭指針為 HeadB,下面是關(guān)鍵詞相關(guān)詞A和數(shù)據(jù)庫列屬性概念描述B的匹配算法過程:
/*Threshold表示設(shè)定的閾值;r、s分別表示A、B兩個(gè)單鏈表中要比較的節(jié)點(diǎn);Delete(node)表示將當(dāng)前節(jié)點(diǎn)從鏈表中刪除*/
刪除B中不滿足條件的節(jié)點(diǎn)之后,剩下的都是和關(guān)鍵詞滿足一定相似度的列,基于此,下面給出了集成方法。
Deep Web蘊(yùn)含了海量的數(shù)據(jù),受客觀條件限制不可能在整個(gè)深度萬維網(wǎng)上進(jìn)行實(shí)驗(yàn),并且中文實(shí)驗(yàn)數(shù)據(jù)樣本不多,為了簡(jiǎn)化起見,選擇了上海師范大學(xué)某學(xué)院信息管理系統(tǒng)2012~2013年的數(shù)據(jù)進(jìn)行測(cè)試,整個(gè)系統(tǒng)共包含20張表結(jié)構(gòu),數(shù)據(jù)量500 MB。實(shí)現(xiàn)的步驟主要分為以下3個(gè)部分:
(1)基于哈工大《同義詞詞林(擴(kuò)展版)》計(jì)算關(guān)鍵詞的相關(guān)詞,獲取過程如圖4所示。
圖4 基于同義詞詞林的相關(guān)詞獲取過程
輸入關(guān)鍵詞"北京"進(jìn)行查詢,獲取"北京"的代碼為"Di03A01=",根據(jù)參考文獻(xiàn)[8]中相似度計(jì)算公式,得到與當(dāng)前關(guān)鍵詞處于同一層的關(guān)鍵詞分別是:"Di03A01=:北 京","Di03A02=:都 城","Di03A03@:陪 都"。在同義詞詞林的定義中,“=”代表“相等”、“同義”,“@”代表當(dāng)前該詞語在同義詞詞典中既沒有同義詞也沒有相關(guān)詞,故本實(shí)驗(yàn)中,省去"Di03A03@:陪都"這一個(gè)基于同義詞詞林獲得相鄰的近義詞。
(2)基于 HowNet獲得關(guān)鍵詞集合的概念定義(DEF)如表2所示,其中根據(jù)集合的原理,取其共同擁有的部分,則關(guān)鍵詞集對(duì)應(yīng)的DEF={地方,國都}。
表2 關(guān)鍵詞集表
(3)基于本文提出的改進(jìn)的相似度的計(jì)算方法,計(jì)算出關(guān)鍵詞DEF集和屬性詞典對(duì)應(yīng)屬性列之間的語義相似度。
①創(chuàng)建后臺(tái)數(shù)據(jù)庫屬性詞典(AttrDict)
選取上海師范大學(xué)某學(xué)院信息管理系統(tǒng)后臺(tái)表2個(gè)月的數(shù)據(jù)進(jìn)行試驗(yàn)。根據(jù)要求,屬性詞典主要包含3個(gè)部分:表名、字段名和對(duì)應(yīng)的描述文字,如表3所示。為了簡(jiǎn)便起見,選取其中的一張表member作為展示部分。
②相似度計(jì)算方法
由 DEF={地方,國都},根據(jù)HowNet逐個(gè)計(jì)算DEF值和當(dāng)前AttrDict中每條記錄的相似度,如圖 5、圖 6所示。
表3 屬性詞典表
圖5 地方的相似度計(jì)算
圖6 國都的相似度計(jì)算
根據(jù)事先設(shè)定的閾值E=0.5,當(dāng)兩個(gè)詞語之間的相似度 表4 相似度計(jì)算結(jié)果表 ③限定對(duì)應(yīng)的查詢領(lǐng)域 由表4中相似度計(jì)算所得結(jié)果,證實(shí)“北京”這一詞語可能與后臺(tái)數(shù)據(jù)庫對(duì)應(yīng)的“備注”、“地址”的相關(guān)度很高,已無需查詢所有的表結(jié)構(gòu)了,只需要查詢“備注”和“地址”列對(duì)應(yīng)的數(shù)據(jù),根據(jù)這一結(jié)果,動(dòng)態(tài)生成相應(yīng)的SQL查詢語句,并將查詢的結(jié)果返回給前臺(tái)頁面。 本文采用基于語義相似度的查詢方法進(jìn)行Deep Web數(shù)據(jù)庫源的查詢,較早地探討了中文深網(wǎng)技術(shù),宏觀上提出了整體解決方案,并且通過實(shí)驗(yàn)過程驗(yàn)證了當(dāng)前方法的可用性。本文是對(duì)Deep Web數(shù)據(jù)庫相似度的一次初探,主要研究通過計(jì)算查詢關(guān)鍵詞和屬性詞典概念之間的相似度,從而降低全表掃描帶來的系統(tǒng)資源的損耗,提高數(shù)據(jù)庫整體查詢效率。但是本文方法依然存在一些問題,下一步不僅應(yīng)該深入研究相似度的改進(jìn)算法,還要研究對(duì)于系統(tǒng)未登錄詞的處理,并將致力于做出全自動(dòng)的屬性匹配原型系統(tǒng)。另外,針對(duì)中文深網(wǎng)一整套解決方案實(shí)現(xiàn)原型系統(tǒng)也是未來工作的重點(diǎn)。 參考文獻(xiàn) [1]NOOR U,RASHID Z,RAUL A.A survey of automatic Deep Web classification techniques[J].International Journal of Computer Application,2011,19(6):43-50. [2]劉偉,孟小峰,孟衛(wèi)一.Deep Web數(shù)據(jù)集成研究綜述[J].計(jì)算機(jī)學(xué)報(bào),2007,30(9):1475-1489. [3]馮磊,陳軍華.數(shù)據(jù)庫全文搜索方案的研究[J].上海師范大學(xué)學(xué)報(bào)(自然科學(xué)版),2010,39(2):153-155. [4]丁傳羽,陳軍華,夏海峰.基于關(guān)鍵詞的深度萬維網(wǎng)查詢[J].計(jì)算機(jī)與數(shù)字工程,2013,41(4):616-618. [5]范舉,周立柱.基于關(guān)鍵詞的深度萬維網(wǎng)數(shù)據(jù)庫選擇[J].計(jì)算機(jī)學(xué)報(bào),2011,34(10):1797-1804. [6]劉群,李素建.基于知網(wǎng)的詞匯語義相似度的計(jì)算[C].第三屆漢語詞匯語義學(xué)研討會(huì),臺(tái)北,2002:59-76. [7]王小林,王義.改進(jìn)的基于知網(wǎng)的詞語相似度算法[J].吉林大學(xué)學(xué)報(bào)(信息科學(xué)版),2011,31(11):3076-3079. [8]田久樂,趙蔚.基于同義詞詞林的詞語相似度計(jì)算方法[J].計(jì)算機(jī)應(yīng)用,2010,28(6):602-605.