基于圖數據庫的數據邏輯解析及檢索

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

（1.國網天津市電力公司，天津 300010；2.天津三源電力信息技術股份有限公司，天津 300010）

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

1 基于圖數據庫的數據邏輯解析

圖數據庫是運用圖論原理對數據進行存儲、管理和檢索的非關系型數據庫，圖庫中的數據采用圖式結構，即結點集和邊集相結合。每一個結點代表一個實體，每一個邊代表實體之間的關系[3]。結點和邊可以有多個屬性，每個都是描述實體或關聯關系的“鍵值”對[4-5]。圖庫系統為圖數據的大規模管理和檢索提供了一套行之有效的方法，因為代碼結構可以很自然地用圖形數據結構來描述，所以用圖形數據庫來管理軟件代碼是有效可行的，而且具有很高的檢索和運行效率[6-7]。

1.1 抽象語法樹描述方式

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

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

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

1.2 圖數據庫結點屬性和邊生成規則

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

式（1）中，djip表示誤譯語句標簽節點。

2 基于圖數據庫的多維檢索

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

圖1 基于圖數據庫的多維檢索流程

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

2.1 索引構造

圖數據庫多維檢索流程：

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

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

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

2.2 檢索結點過濾

在NB-Tree 葉子結點上加入偏移角，設計了一種新的索引結構New-NB-Tree。改進后的結點結構如圖2 所示。

圖2 改進后的結點結構

由圖2 可知，用簡單計算方法，突出結點結構信息，剔除數據庫中的重復數據，保留原始快速索引優勢，減少了計算步驟，由此完成檢索結點過濾。

2.3 檢索流程

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

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

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

步驟一：初始化檢索向量信息，對數據進行預處理，確定相關參量；

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

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

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

步驟五：將上述檢索的結果記錄到內存中；

步驟六：如果內存歐氏距離大于檢索半徑歐氏距離，檢索過程結束；

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

3 實驗結果分析

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

3.1 實驗環境

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

3.2 實驗過程

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

圖4 圖數據庫局部結構圖

在每一個圖數據庫局部結構上，隨機選取10 個不相鄰的數據進行檢索，當不同檢索位置對應的信息不同時，記錄相應信息，實時分析含有代表性的信息進行檢索。

3.3 實驗結果與分析

3.3.1 檢索半徑對比

分別使用關鍵字檢索方法M1和基于圖數據庫檢索方法M2對比分析檢索半徑，對比結果如表1所示。

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

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

3.3.2 檢索效率對比

分別使用關鍵字檢索方法和基于圖數據庫檢索方法對比檢索效率，結果如圖5 所示。

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

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

4 結束語

基于圖數據庫的數據邏輯解析及檢索方法，索引效果較好，提供了一個完整的框架，以集成各種代碼結構為基礎，使軟件開發人員能夠輕松檢索代碼結構。

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

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