视频查询语言SVQL语法分析模型

卢成浪, 尤卫军, 吴宗大

(1.西北工业大学 航海学院, 陕西 西安 710072; 2.浙江机电职业技术学院 现代信息技术学院, 浙江 杭州 310000;3.浙江省自然科学基金委办公室, 浙江 杭州 310000; 4.绍兴文理学院 计算机系, 浙江 绍兴 312000)

数据查询语言可以帮助用户有效描述查询需求，用户界面友好是实现数据检索的有效工具。尽管传统数据查询语言(如结构化查询语言SQL、面向XML数据查询语言XQuery等[1])已取得巨大成功，但它们无法直接应用于视频检索，这是因为视频数据包含的各类语义信息(如视频实体之间的时空关系)对视频查询语言的描述能力提出了许多新需求。虽然学者已提出了多种多媒体数据查询语言[2-3]，但它们的语法形式通常较为复杂，难以被普通用户掌握，并且其视频查询表达能力相对较弱，难以满足多样化的视频查询需求。为此，在前期工作中，提出了一种基于结构化声明的通用视频查询语言SVQL(structured video query language)[4-6]，它不仅拥有简洁语法形式，而且拥有良好可扩展性，能适应复杂的基于内容的视频查询需求，是实现有效视频检索的重要工具。

然而，由于SVQL语法的特殊性，其语法分析难以用其他结构化数据查询语言(如SQL等)的语法分析器[7-10]来完成。为此，本文研究SVQL语言语法分析模型的设计与实现。首先，以巴克斯范式、逻辑代数等工具形式化描述SVQL的文法规则和语义规则，研究构建了多层次SVQL语法分析模型。然后，基于语法分析模型，结合编译原理理论知识，设计了实现SVQL语法分析工具，从而为SVQL视频查询的后续优化奠定了重要前期基础。另外，本文工作对于其他结构化查询语言的语法分析模型构建同样具有重要的参考借鉴作用。

1 语法分析模型

1.1 视频查询语言SVQL

SVQL是一种基于结构化声明的通用视频查询语言，能有效支持多种形式视频查询，其一般化的语法形式可表述为：

FIND VIDEO(〈视频对象声明列表〉〈视频事件声明列表〉〈视频关系声明列表〉)；

可看出，一个SVQL查询由视频对象列表、视频事件列表和视频关系列表3个部分组成，其中：①〈视频对象列表〉负责描述视频所包含的视频对象及其属性应满足的基本条件；②〈视频事件列表〉负责描述视频包含的视频事件及其属性应满足的基本条件；③〈视频关系列表〉负责描述视频对象之间、视频事件之间、视频对象与视频事件之间应满足的各种关系。以下通过一个简单的例子来说明SVQL查询的语法形式。

例1.查询2004年，在北京体育馆，刘国梁和孔令辉发生同台竞技事件的所有视频。

FIND VIDEO(/*FIND VIDEO为关键字*/

/* 1、视频对象声明列表*/

OBJECT刘国梁(/*OBJECT为对象声明关键字，后面跟着对象名*/类型=运动员;)OBJECT孔令辉(类型=运动员;/*“类别”是对象的属性*/ )

/* 2、视频事件声明列表*/

EVENT比赛事件( /* EVENT为事件声明关键字，后面跟着事件名*/

开始时间>‘2004-01-01 00∶00∶00’;发生地点=北京体育馆，/*“时间”和“地点”均为属性*/ )

/* 3、视频关系声明列表*/

刘国梁AgentOf比赛事件;孔令辉AgentOf比赛事件; /*AgentOf为关键字*/)

1.2 语法分析模型

SVQL层次化语法分析模型如图1所示。可看出，SVQL语法规则分为：词法规则、文法规则和语义规则。其中：词法规则定义查询单词；文法规则定义形式语法；语义规则定义语义逻辑上的语法。

图1 层次化SVQL语法分析模型

1) 词法规则：词法规则负责定义SVQL查询单词。SVQL单词可分为关键字、固定符号(标点、运算符等)、符号(变量、属性等)、常量(布尔值、数字、日期、字符串等)等类型。其中，关键字和固定符号可直接枚举。以下仅给出符号(以变量、属性为代表)和常量(以数字、字符串为代表)的正则表达式描述。

<符号>::=[a-zA-Z0-9-u4e00-u9fa5]+

<数字>::=[0-9]+([E][+-]?[0-9]+)?|[0-9]+"."[0-9]*([E][+-]?[0-9]+)?

<字符串>::=′[^′ ]*′

基于词法规则，词法分析部件可以从SVQL查询文本中识别出所有实义单词，并过滤无实义词(空白、注释等)。据此形成的单词流是文法分析部件的输入。

2) 文法规则：负责定义SVQL形式语法，并不考虑视频对象变量和视频事件变量的具体语义问题。以下分别给出SVQL查询各个子句文法约束的巴克斯范式描述。

(1) 视频对象声明列表的文法规则

<视频对象声明列表>::=<视频对象声明>[{;<视频对象声明>}];

<视频对象声明>::=OBJECT<视频对象变量>(<属性条件项>[{;<属性条件项>}]);

<属性条件项>::=<视频对象变量>.<属性项><比较算符><比较值>;

<视频对象变量>::=<符号>;<属性项>::=<符号>;

<比较值>::=<布尔值>|<数字>|<日期>|<字符串>;

<比较算符>::= =|<>|>|>=|<|<=;

视频对象列表用于描述视频包含的视频对象以及视频对象应满足的属性条件。该规则要求：视频对象声明列表由若干个视频对象声明构成(各个声明用分号隔开)。

(2) 视频事件声明列表的文法规则

<视频事件声明列表>::=<视频事件声明>[{;<视频事件声明>}];

<视频事件声明>::=EVENT<视频事件变量>(<属性条件项>[{;<属性条件项>}]);

<属性条件项>::=<视频事件变量>.<属性项><比较算符><比较值>;

<视频事件变量>::=<符号>;<属性项>::=<符号>;

<比较值>::=<布尔值>|<数字>|<日期>|<字符串>;

<比较算符>::==|<>|>|>=|<|<=;

视频事件列表用于描述视频包含的视频事件以及视频事件应满足的属性条件。

(3) 视频关系声明列表的文法规则

<视频关系声明列表>::=<视频关系声明>[{;<视频关系声明>}];

<视频关系声明>::=<视频对象关系声明>|<视频事件关系声明>|<事件对象关系声明>;

<事件对象关系声明>::=

<视频对象变量>AgentOf<视频事件变量>[{;<事件对象关系声明>}];

<视频对象关系声明>::=

<视频对象变量><关系算符>[X|Y|Z|T]<视频对象变量>[{;<视频对象关系声明>}];

<视频事件关系声明>::=

<视频事件变量><关系算符>[X|Y|Z|T]<视频事件变量>[{;<视频事件关系声明>}];

<关系算符>::=BEFORE|MEETS|OVERLAPS|DURING|STARTS|FINISHES|EQUALS;

视频关系声明列表用于描述视频对象之间、视频事件之间、视频对象与事件之间以及其他实体之间的语义关系。

3) 语义规则：负责定义SVQL语义逻辑上的语法，它考虑各个视频变量具体含义。语义分析需要用到视频实体及其属性等模式信息，因而，定义视频实体数据模式如下：SVQL查询基于视频对象表VOS和视频事件表VES。其中，视频对象表模式可抽象表示为：VOS={|attrName为视频对象属性名，attrType为视频对象属性类型}。类似地，可定义视频事件表模式VES。据此，以下给出SVQL语义约束的逻辑代数描述。

(1) 视频对象声明语义：视频对象变量跟随的各个属性条件项须合法，即视频对象应确实包含相应属性项，并且属性项与比较值相匹配。记VOD为<视频对象声明列表>各个属性条件项所关联单词的集合，即VOD={|attrName和attrValue分别对应<属性条件项>中的<属性项>和<比较值>}，则视频对象声明的语义规则可表述如下：

∀e(e∈VOD→∃u(u∈VOS∧u.attrName=e.attrName∧isType(e.atrrValue,u.attrType))

(2) 视频事件声明语义：视频事件变量跟随的各个属性条件项须合法。记VED为<视频对象声明列表>各个属性条件项所关联文法单词的集合，即VED={|attrName和attrValue分别对应<属性条件项>中的<属性项>和<比较值>}，则视频事件声明的语义规则可表述如下：

∀e(e∈VED→∃u(u∈VES∧u.attrName=e.attrName∧isType(e.atrrValue,u.attrType))

(3) 视频关系声明语义：视频关系声明中出现变量须被视频对象声明过或被视频事件声明过。记VOV为视频对象声明出现的所有视频对象变量集合，记VOP为<视频对象关系声明>关联的视频对象变量集合，即VOP={| videoObj1和videoObj2为同1个<关系算符>所关联的2个<视频对象变量>}，则视频对象关系声明的语义规则可表述如下：

∀e(e∈VOP→∃u∃v(u∈VOV∧v∈VOV∧u=e.videoObj1∧=e.videoObj2))

记VEV为视频事件声明出现过的所有视频事件变量集合，记VEP为<视频事件关系声明>关联的视频事件变量集合，即VEP={|videoEve1和videoEve2为同一个<关系算符>所关联的2个<视频事件变量>}，则视频事件关系声明的语义规则可表述如下：

∀e(e∈VEP→∃u∃v(u∈VEV∧v∈VEV∧u=e.videoEve1∧v=e.videoEve2))

记VOE为<事件对象关系声明>关联的视频变量集合，即VOE={|videoObj和videoEve分别为同一个AgentOf关系算符所关联的<视频对象变量>和<视频事件变量>}，则视频事件对象关系声明的语义规则可表述如下：

∀e(e∈VOE→∃u∃v(u∈VOV∧v∈VOV∧u=e.videoObj∧v=e.videoEve))

为了支持多种形式的视频内容查询，SVQL语法规则比较繁杂，本节仅给出部分主要语法规则描述，其余细节语法规则不再赘述。

2 语法分析工具

基于前文构建的语法分析模型，以下设计实现SVQL语法分析工具，其实现框架如图2所示。

图2 SVQL语法分析工具框架

其中：①词法分析器负责将SVQL查询转换为记号集；②语法分析器负责根据文法规则，将记号集转化为语法树和符号表；③语义分析器由一系列数据结构及其处理函数组成，负责对语法树进行语义检查，生成中间结构(即初步查询计划)。

1) 词法分析器：利用正则表达式所描述的词法规则，识别出SVQL查询中的单词。此外，还要剔除无意义词(如空白字符等)，并检查词法(给出错误信息)。SVQL词法分析器借助LEX[11]实现，其输入是以正则表达式所描述的词法规则。词法分析器核心是getToken函数，不断调用它即可获取SVQL查询包含的所有单词。

2) 文法分析器：从词法分析器持续获取记号，并依据文法规则进行分析处理，以生成语法树和相应语义信息表。SVQL文法分析器借助YACC[12]实现，其输入是前文语法分析模型利用巴克斯范式所描述的文法规则。若SVQL查询存在文法错误，文法分析器会给出有指导性的文法错误描述，否则将输出语义信息表。据此，文法分析器可进一步生成语法树结构，它将是后续语义分析器的输入。

3) 语义分析器：语法分析模型利用逻辑代数形式化描述了语义约束规则集，据此，语义分析器负责构建算法，并对基于语法树结构和语义信息表所生成的各个语义项进行语义检查。其中语义项主要包括：VOD语义项、VED语义项、VOP语义项、VEP语义项、VOE语义项等，分别对应：视频对象声明、视频事件声明、视频对象关系声明、视频事件关系声明、事件对象关系声明等。限于篇幅，以下仅讨论VOP语义项和VOE语义项的语义分析检查算法(其他语义项的检查算法与之类似)。

(1) VOP语义检查：VOP数据结构存储了<视频对象关系声明>所关联的所有视频对象变量。VOP语义项的一个基本元素关联了2个视频对象变量，因而，VOP语义检查主要是检查各元素所关联的2个视频对象变量之间的语义合法性，伪码描述如算法1所示。

(2) VOE语义检查：VOE数据结构存储了<时间对象关系声明>所关联的所有视频对象变量和事件变量，其各元素关联了一个视频对象变量和一个视频事件变量。因而，本文主要检查各VOE元素所关联的2个视频变量之间的语义合法性，伪码描述如算法2所示。

算法1VOP语义检查

算法描述：

VOV为视频对象声明出现的视频对象变量集合

for (eachEin VOP) {

for (index1=0 to VOV.length) {

if (VOV[index1].name ==E.videoObj1) break;}

for (index2=0 to VOV.length) {

if (VOV[index2].name ==E.videoObj2) break;}

if (index1 == VOV.length) 报告错误并返回;

if (index2 == VOV.length) 报告错误并返回;

if (index1 == index2) 报告错误并返回;

}

算法2VOE语义检查

算法描述：

VOV为视频对象声明出现的视频对象变量集合

VEV为视频事件声明出现的视频事件变量集合

for (eachEin VOE) {

for (index1=0 to VOV.length) {

if (VOV[index1].name ==E.videoObj) break;}

for (index2 = 0 to VEV.length) {

if (VEV[index2].name ==E.videoEve) break;}

if (index1 == VOV.length) 报告错误并返回;

if (index2 == VEV.length) 报告错误并返回;

}

3 有效性测试

图3a)给出了SVQL语法分析工具的用户界面：①左上部分为查询输入框；②右上部分为内部结构信息，给出由词法分析、文法分析、语义分析所产生的词法分析表、语法树、符号集等内部结构信息；③下半部分为结果输出框，给出SVQL查询处理结果(或错误提示文本)。限于篇幅，以下简要给出语法分析工具的功能测试结果和性能测试结果。

1) 功能测试：图3a)给出了来自例1的视频查询(即查询刘国梁和孔令辉在北京体育馆同台竞技的所有视频)的语法分析测试结果。可看出，分析工具右上部分的输出框，给出了基于该查询所产生的词法分析表、语法树、符号集等内部数据结构，这些是后续查询处理优化的重要输入；下半部分的结果输出框，给出了查询的处理结果信息(即该查询无词法错误、无文法错误、无语义错误等)。图3b)～3d)给出了3个视频查询的语法分析测试结果(这3个视频查询分别存在词法错误、文法错误和语义错误)。可看出，对于存在文法、词法错误的视频查询语句，分析工具不仅能给出具有指导作用的错误文本，还能给出相应的修改建议。综上，基于SVQL层次化语法分析模型所构建的语法分析工具能较好地完成对SVQL查询的词法、文法和语义检查，生成内部数据结构和相关提示信息。

图3 SVQL语法分析器用户界面和功能测试结果

2) 性能测试：选取多组不同长度的视频查询语句对语法分析工具进行性能测试，评估结果如表1所示(10次运行的平均值)。

表1 性能测试结果

可看出，对于短查询语句(语句少于50行)，语法分析器的执行效率非常高(约为10 ms)，但对于长查询语句，语法分析器的执行效率有所下降。可看出，每行语句的平均解析速度为0.26 ms，因而分析工具的解析速度处在可接受水平(相比于其他一般性的数据查询语言解析器)；并且随着查询语句规模的增长，每行语句的平均解析速度会有所增加。

4 结 论

研究了SVQL(一种基于结构化声明的视频查询语言)的语言分析模型，并据此讨论实现了其语法分析工具。结果表明，研究构建的语法分析工具能有效地检测出SVQL查询中的词法错误、文法错误或语义错误，并给出有指导性的修正建议，为SVQL的后续优化奠定了前期基础。根据查询分析模型的输出，可以有效构建视频查询的内部被查询计划，因此后续的查询优化和查询处理问题将是下一步的重点研究内容。