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

（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)鍵詞，費時費力。由于圖數(shù)據(jù)的激增，在有限的時間內(nèi)很難完成和應(yīng)用；人工標(biāo)注關(guān)鍵字具有一定的主觀性，對于一張圖片，不同的人可能對其內(nèi)容有不同的評價[2]。甚至同一個人在不同的時間、不同的角度對同一圖片會作出不同的評價，都會導(dǎo)致關(guān)鍵詞不一致或不存在，從而導(dǎo)致檢索失??；一個圖片的內(nèi)容是非常豐富的，很難用幾個關(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ù)庫是運用圖論原理對數(shù)據(jù)進行存儲、管理和檢索的非關(guān)系型數(shù)據(jù)庫，圖庫中的數(shù)據(jù)采用圖式結(jié)構(gòu)，即結(jié)點集和邊集相結(jié)合。每一個結(jié)點代表一個實體，每一個邊代表實體之間的關(guān)系[3]。結(jié)點和邊可以有多個屬性，每個都是描述實體或關(guān)聯(lián)關(guān)系的“鍵值”對[4-5]。圖庫系統(tǒng)為圖數(shù)據(jù)的大規(guī)模管理和檢索提供了一套行之有效的方法，因為代碼結(jié)構(gòu)可以很自然地用圖形數(shù)據(jù)結(jié)構(gòu)來描述，所以用圖形數(shù)據(jù)庫來管理軟件代碼是有效可行的，而且具有很高的檢索和運行效率[6-7]。

1.1 抽象語法樹描述方式

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

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

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

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

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

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

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

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

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

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

2.1 索引構(gòu)造

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

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

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

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

2.2 檢索結(jié)點過濾

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

圖2 改進后的結(jié)點結(jié)構(gòu)

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

2.3 檢索流程

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

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

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

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

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

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

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

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

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

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

3 實驗結(jié)果分析

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

3.1 實驗環(huán)境

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

3.2 實驗過程

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

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

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

3.3 實驗結(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è)計方法使用少量計算方式，在一定程度上加強了過濾，剔除了候選數(shù)據(jù)里的重復(fù)數(shù)據(jù)，通過該索引，在保留原始快速索引的優(yōu)勢下，減少了計算步驟，索引效果較好。

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ù)邏輯解析及檢索方法，索引效果較好，提供了一個完整的框架，以集成各種代碼結(jié)構(gòu)為基礎(chǔ)，使軟件開發(fā)人員能夠輕松檢索代碼結(jié)構(gòu)。

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

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