基于图数据库的数据逻辑解析及检索

牛佳乐，张 毅，郑 剑，刘 宁，王丹丹

（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 结束语

基于图数据库的数据逻辑解析及检索方法，索引效果较好，提供了一个完整的框架，以集成各种代码结构为基础，使软件开发人员能够轻松检索代码结构。

使用基于图数据库检索方法检索效率较高，一定程度上可以提高软件重用效率，使数据逻辑解析及检索简单化。这种索引结构在保持原算法独立维特征的同时，提高了过滤性能。

数据逻辑解析及检索还在不断发展和探索中，对于未来的研究工作，可以就缩短数据逻辑解析及检索时间进行更加深入的探讨。