基于圖數(shù)據(jù)庫的數(shù)據(jù)邏輯解析及檢索

牛佳樂，張 毅，鄭 劍，劉 寧，王丹丹

（1.國網(wǎng)天津市電力公司，天津 300010；2.天津三源電力信息技術(shù)股份有限公司，天津 300010）

隨著高速互聯(lián)網(wǎng)技術(shù)的發(fā)展與應(yīng)用，人們可以通過各種形式(圖像、文本、聲音、視頻等)獲取所需信息，數(shù)字圖像的需求也隨之增加[1]。圖數(shù)據(jù)的需求和圖數(shù)據(jù)的幾何增長使得圖數(shù)據(jù)檢索成為圖數(shù)據(jù)庫推廣應(yīng)用的關(guān)鍵。以前使用的關(guān)鍵詞檢索方法，每幅圖像都需要人工標(biāo)注關(guān)鍵詞，費(fèi)時(shí)費(fèi)力。由于圖數(shù)據(jù)的激增，在有限的時(shí)間內(nèi)很難完成和應(yīng)用；人工標(biāo)注關(guān)鍵字具有一定的主觀性，對于一張圖片，不同的人可能對其內(nèi)容有不同的評價(jià)[2]。甚至同一個(gè)人在不同的時(shí)間、不同的角度對同一圖片會作出不同的評價(jià)，都會導(dǎo)致關(guān)鍵詞不一致或不存在，從而導(dǎo)致檢索失敗；一個(gè)圖片的內(nèi)容是非常豐富的，很難用幾個(gè)關(guān)鍵字來描述?；谖谋镜年P(guān)鍵字檢索方法不適合當(dāng)前圖像數(shù)據(jù)庫的應(yīng)用。為此，提出了基于圖數(shù)據(jù)庫的數(shù)據(jù)邏輯解析及檢索方法，以圖形數(shù)據(jù)的形式反映數(shù)據(jù)與業(yè)務(wù)的對應(yīng)關(guān)系，支持?jǐn)?shù)據(jù)邏輯的快速引用與檢索。

1 基于圖數(shù)據(jù)庫的數(shù)據(jù)邏輯解析

圖數(shù)據(jù)庫是運(yùn)用圖論原理對數(shù)據(jù)進(jìn)行存儲、管理和檢索的非關(guān)系型數(shù)據(jù)庫，圖庫中的數(shù)據(jù)采用圖式結(jié)構(gòu)，即結(jié)點(diǎn)集和邊集相結(jié)合。每一個(gè)結(jié)點(diǎn)代表一個(gè)實(shí)體，每一個(gè)邊代表實(shí)體之間的關(guān)系[3]。結(jié)點(diǎn)和邊可以有多個(gè)屬性，每個(gè)都是描述實(shí)體或關(guān)聯(lián)關(guān)系的“鍵值”對[4-5]。圖庫系統(tǒng)為圖數(shù)據(jù)的大規(guī)模管理和檢索提供了一套行之有效的方法，因?yàn)榇a結(jié)構(gòu)可以很自然地用圖形數(shù)據(jù)結(jié)構(gòu)來描述，所以用圖形數(shù)據(jù)庫來管理軟件代碼是有效可行的，而且具有很高的檢索和運(yùn)行效率[6-7]。

1.1 抽象語法樹描述方式

通過細(xì)化、過濾和組織相應(yīng)的抽象語法樹，可以將軟件代碼結(jié)構(gòu)解析成一個(gè)有向圖結(jié)構(gòu)[8-9]。圖數(shù)據(jù)庫操作碼是邏輯解析結(jié)果層的字節(jié)碼，是腳本解析后的中間語言。PHP 腳本讀取腳本字符串后，通過詞法分析器將其轉(zhuǎn)換為語言片段標(biāo)記，然后再轉(zhuǎn)換為重點(diǎn)片段標(biāo)記。最后，虛擬機(jī)執(zhí)行每個(gè)操作碼以獲得運(yùn)行結(jié)果。腳本對應(yīng)的操作碼文本可以通過PHP 的VLD 擴(kuò)展程序直接獲得[10]。

兩個(gè)相鄰的操作碼被分成一個(gè)短語，計(jì)算每個(gè)樣本中短語的頻率矩陣，得到基于操作碼序列的詞頻矩陣作為特征向量。

利用前面部分的特征提取方法，結(jié)合代碼文本層和編譯結(jié)果層，得到特征集。但是，特征集的維數(shù)可能很高，這將給后續(xù)的誤譯語句自動識別帶來巨大的計(jì)算壓力[11]。在數(shù)據(jù)預(yù)處理階段采用抽象語法樹描述方式，能夠有效降低特征維數(shù)和后期模型訓(xùn)練的復(fù)雜性。

1.2 圖數(shù)據(jù)庫結(jié)點(diǎn)屬性和邊生成規(guī)則

為了提高圖數(shù)據(jù)庫的數(shù)據(jù)邏輯解析及檢索精度，利用二維信息熵理論定義了編輯距離除以兩個(gè)字符串的平均長度來識別不同類型的數(shù)據(jù)信息，區(qū)分具有高度相似性的差異特征，并生成誤譯信息和正確信息之間的最大識別結(jié)構(gòu)[12-13]。具體步驟如下：

式（1）中，djip表示誤譯語句標(biāo)簽節(jié)點(diǎn)。

2 基于圖數(shù)據(jù)庫的多維檢索

在基于圖數(shù)據(jù)庫的數(shù)據(jù)邏輯解析的支持下，設(shè)計(jì)多維檢索流程，如圖1 所示。

圖1 基于圖數(shù)據(jù)庫的多維檢索流程

由圖1 可知，這種搜索機(jī)制是從軟件開發(fā)人員輸入的搜索語句等自然語言開始的，它在代碼結(jié)構(gòu)分析生成的圖形數(shù)據(jù)庫中提供了一個(gè)子圖作為搜索結(jié)果。該檢索過程可分為3 個(gè)階段：1）利用自然語言處理技術(shù)對檢索到的語句進(jìn)行語義分析，確定檢索到的語句的檢索目的；2）在此基礎(chǔ)上，選擇合適的代碼結(jié)構(gòu)模式匹配算法，從圖庫中生成搜索結(jié)果；3）根據(jù)開發(fā)人員的實(shí)際需求，預(yù)先定義搜索目標(biāo)的決策規(guī)則，并提出一種代碼結(jié)構(gòu)模式匹配算法，其優(yōu)點(diǎn)之一是預(yù)定義的結(jié)果具有一定的輕量級性，且具有高度可擴(kuò)展性[16]。

2.1 索引構(gòu)造

圖數(shù)據(jù)庫多維檢索流程：

首先計(jì)算多維矢量(p1,p2,…,pn)歐式距離：

由式（3）完成多維矢量歐式距離計(jì)算后，通過該距離將N維空間映射到一維空間，在該空間上，利用B+樹構(gòu)造索引。

由于歐式距離矢量較多，增加了輸入-輸出操作步驟，為此引入新的New-NB-Tree 索引結(jié)構(gòu)，該結(jié)構(gòu)過濾能力強(qiáng)，訪問對象數(shù)量少，能夠有效減少輸入-輸出操作步驟，提高檢索效率。

2.2 檢索結(jié)點(diǎn)過濾

在NB-Tree 葉子結(jié)點(diǎn)上加入偏移角，設(shè)計(jì)了一種新的索引結(jié)構(gòu)New-NB-Tree。改進(jìn)后的結(jié)點(diǎn)結(jié)構(gòu)如圖2 所示。

圖2 改進(jìn)后的結(jié)點(diǎn)結(jié)構(gòu)

由圖2 可知，用簡單計(jì)算方法，突出結(jié)點(diǎn)結(jié)構(gòu)信息，剔除數(shù)據(jù)庫中的重復(fù)數(shù)據(jù)，保留原始快速索引優(yōu)勢，減少了計(jì)算步驟，由此完成檢索結(jié)點(diǎn)過濾。

2.3 檢索流程

檢索流程是基于圖數(shù)據(jù)庫的數(shù)據(jù)邏輯解析及檢索的核心，檢索流程如圖3 所示。

圖3 New-NB-Tree范圍檢索流程

New-NB-Tree范圍檢索流程具體步驟如下所示：

步驟一：初始化檢索向量信息，對數(shù)據(jù)進(jìn)行預(yù)處理，確定相關(guān)參量；

步驟二：確定結(jié)點(diǎn)指針指向索引樹根；

步驟三：如果檢索半徑歐氏距離大于結(jié)點(diǎn)指針歐氏距離，則無檢索結(jié)果輸出，檢索過程結(jié)束；

步驟四：如果前一個(gè)結(jié)點(diǎn)的指針歐氏距離小于檢索半徑，則檢索出結(jié)果；

步驟五：將上述檢索的結(jié)果記錄到內(nèi)存中；

步驟六：如果內(nèi)存歐氏距離大于檢索半徑歐氏距離，檢索過程結(jié)束；

步驟七：如果檢索半徑歐氏距離最大值小于等于內(nèi)存歐氏距離時(shí)，需從內(nèi)存相應(yīng)位置隨機(jī)讀取記錄，同時(shí)求得相鄰檢索對象之間的距離以及檢索需要的時(shí)間，最后記錄數(shù)據(jù)邏輯解析及檢索結(jié)果。

3 實(shí)驗(yàn)結(jié)果分析

為了驗(yàn)證基于圖數(shù)據(jù)庫的數(shù)據(jù)邏輯解析及檢索的合理性，進(jìn)行實(shí)驗(yàn)驗(yàn)證分析。實(shí)驗(yàn)具體分析如下。

3.1 實(shí)驗(yàn)環(huán)境

實(shí)驗(yàn)環(huán)境為CPU(Intel celeron2.6GHz)+RAM(1GB)+Window2000+GNU Common Lisp-2.6.1，開發(fā)軟件為Matlab Version7.3.0.267。實(shí)驗(yàn)中所采集的數(shù)據(jù)庫來自不同場景，不同的數(shù)據(jù)分別從圖數(shù)據(jù)庫中隨機(jī)選取數(shù)據(jù)信息。

3.2 實(shí)驗(yàn)過程

數(shù)據(jù)邏輯解析及檢索需要選擇轉(zhuǎn)換，通常使用圖數(shù)據(jù)庫來達(dá)到解析及檢索的目的。該圖數(shù)據(jù)庫能夠提供大量的圖數(shù)據(jù)，提取16 維紋理特征、32 維顏色特征以及64 維圖表特征集，滿足圖數(shù)據(jù)庫數(shù)據(jù)邏輯分析及檢索需求，其中圖數(shù)據(jù)庫局部結(jié)構(gòu)如圖4所示。

圖4 圖數(shù)據(jù)庫局部結(jié)構(gòu)圖

在每一個(gè)圖數(shù)據(jù)庫局部結(jié)構(gòu)上，隨機(jī)選取10 個(gè)不相鄰的數(shù)據(jù)進(jìn)行檢索，當(dāng)不同檢索位置對應(yīng)的信息不同時(shí)，記錄相應(yīng)信息，實(shí)時(shí)分析含有代表性的信息進(jìn)行檢索。

3.3 實(shí)驗(yàn)結(jié)果與分析

3.3.1 檢索半徑對比

分別使用關(guān)鍵字檢索方法M1和基于圖數(shù)據(jù)庫檢索方法M2對比分析檢索半徑，對比結(jié)果如表1所示。

表1 兩種方法檢索半徑對比

由表1 可知，使用關(guān)鍵字檢索方法的索引次數(shù)較多，最多索引次數(shù)為4 130 次；使用基于圖數(shù)據(jù)庫檢索方法的索引次數(shù)少，最多索引次數(shù)為130 次，由此可知，使用基于圖數(shù)據(jù)庫檢索方法索引效果好。其原因是所設(shè)計(jì)方法使用少量計(jì)算方式，在一定程度上加強(qiáng)了過濾，剔除了候選數(shù)據(jù)里的重復(fù)數(shù)據(jù)，通過該索引，在保留原始快速索引的優(yōu)勢下，減少了計(jì)算步驟，索引效果較好。

3.3.2 檢索效率對比

分別使用關(guān)鍵字檢索方法和基于圖數(shù)據(jù)庫檢索方法對比檢索效率，結(jié)果如圖5 所示。

由圖5 可知，使用關(guān)鍵字檢索方法檢索效率最高為60%，最低為40%；使用基于圖數(shù)據(jù)庫檢索方法檢索效率最高為97%，最低為93%。由此可知，使用基于圖數(shù)據(jù)庫檢索方法檢索效率較高。

圖5 兩種方法檢索效率對比

4 結(jié)束語

基于圖數(shù)據(jù)庫的數(shù)據(jù)邏輯解析及檢索方法，索引效果較好，提供了一個(gè)完整的框架，以集成各種代碼結(jié)構(gòu)為基礎(chǔ)，使軟件開發(fā)人員能夠輕松檢索代碼結(jié)構(gòu)。

使用基于圖數(shù)據(jù)庫檢索方法檢索效率較高，一定程度上可以提高軟件重用效率，使數(shù)據(jù)邏輯解析及檢索簡單化。這種索引結(jié)構(gòu)在保持原算法獨(dú)立維特征的同時(shí)，提高了過濾性能。

數(shù)據(jù)邏輯解析及檢索還在不斷發(fā)展和探索中，對于未來的研究工作，可以就縮短數(shù)據(jù)邏輯解析及檢索時(shí)間進(jìn)行更加深入的探討。