模式匹配查询算法研究

摘 要：本文针对XML文档树设计了模式匹配查询算法，该算法包括XML文档树转换成为三层子树和利用各种操作进行结构匹配。在转换成为三层子树的时候，涉及到了三种形态的子树：单叉树、过度子树、一般子树。并且将XML树的节点分为两类：内部节点和值节点。在模式匹配的时候，用更新操作、删除操作、插入操作完成了模式匹配。

关键词：三层子树；更新操作；删除操作；插入操作

中图分类号：TP301.6 文献标识码：A 文章编号：1674-7712 （2014） 04-0000-01

一、问题的描述

XML文档数据的重要特点之一就是具有结构性数据，在结构匹配的研究中，主要是信息检索中TF*IDF技术的方法。

TF-IDF是一种用于资讯检索与文本挖掘的方法。如果某个词或短语在一篇文章中出现的频率TF高，并且在其他文章中很少出现，则认为此词或者短语具有很好的类别区分能力。

TF-IDF实际上是TF * IDF，TF词频（Term Frequency），IDF逆向文件频率（Inverse Document Frequency）。TF表示词条在文档d中出现的频率。它的主要思想是：如果包含词条t的文档越少，也就是n越小，IDF越大，则说明词条t具有很好的类别区分能力。例如：如果某一类文档C中包含词条t的文档数为m，而其它类包含t的文档总数为k，显然所有包含t的文档数n=m+k，当m大的时候，n也大，按照IDF公式得到的IDF的值会小，就说明该词条t类别区分能力不强。但是实际上，如果一个词条在一个类的文档中频繁出现，则说明该词条能够很好代表这个类的文本的特征，这样的词条应该给它们赋予较高的权重，并选来作为该类文本的特征词以区别与其它类文档。这就是IDF的不足之处.

本文在这样的背景下提出模式匹配查询算法，该算法是以如何提高其数据信息的查询效率为目的，描述的一种既能够在保证查全率的同时又对其查准率有所提高的结构查询优化算法。

二、算法的设计

（一）三层子树

定义1（三层子树）：如果一个XML子树以一层节点为根，并且除了根节点以外，只包含二层节点和值节点，则称此XML子树成为三层子树。

在模式匹配查询过程中，XML树的节点分为两类：内部节点和值节点。值节点指的是XML树中的叶子节点。内部节点包括三类：一层节点、二层节点、过度节点。根据XML树的DTD定义三类节点如下：

（1）一层节点

一层节点在对应的DTD中是指的根节点，能够重复出现在父节点中，并且可以拥有二层节点和值节点。

（2）二层节点

二层节点的定义：至少有一个值节点（叶子节点）做它的子孙节点。

（3）过度节点

既不属于一层节点，也不属于二层节点的节点称之为过度节点。一个过度节点仅仅能够包含一层节点的子节点。

在进行结构查询的过程中，首先应该把XML树转换为三层子树。

（二）结构模式匹配

在XML树转换成三层子树后，就可以进行结构模式匹配。结构模式匹配的核心是计算编辑距离。编辑距离是指两个字符串通过插入、删除、改写字符等编辑操作而变为相同字符串所需要的最小操作数，而Tai最早使用编辑距离计算了两棵树（图）之间的相似度，其基本思想是将两棵树间的距离定义为利用编辑操作将一棵树转化为另一棵树所耗费的最小代价。

在“内容十结构”的算法查询模式（先进行内容查询再进行结构模式匹配查询）中，我们应该以内容信息为主，结构信息为辅。所以，在查询的过程中，结构信息必须与内容信息紧密相关，并且能够进一步对内容信息进行结构上的限定。也就是说，在进行内容查询之后，结构模式匹配查询的关键就是合理地计算编辑操作所需要的最小代价。

充分考虑了编辑节点时的不同代价，，本文定义了三种编辑操作代价的计算模型：（1）更新操作：就是改变一个节点的标签，把相关文档中的某个关键词节点的标签更新为用户查询中的某个查询关键词节点的标签。（2）删除操作：把相关文档中与用户查询不相匹配的节点q删除。其中，删除平衡因子（实验验证一般取值0.5为最佳），用来调整具体环境所决定的权重与删除代价间变换的差异。（3）插入操作：该操作与删除操作是相反操作。另外，插入平衡因子（实验验证一般取值0.5为最佳），用来调整具体环境所决定的权重与插入代价变换的相似度。

三、算法实现

在实现该算法时，设计了一个系统，该系统包括四个模块：输入输出模块、转换模块，结构查询模块，数据库存储模块。

输入输出模块：主要负责XML文档的输入、输出工作；

转换模块：输入的XML文档树转换成为三层子树，以便为以后的结构查询做准备。该模块是过度模块，是结构查询模块的跳板；

结构查询模块：经过转换模块后进入的第三个模块，该模块计算在模式匹配过程中所花费的代价之和；

数据库存储模块：用来存储XML数据，采用内联法来将XML映射到关系数据库中。数据库模块主要是关系表的设计。在关系表的设计过程中，主要利用Dewey码来表示节点。

四、结束语

本文提出了结构模式匹配查询算法， 该算法包括两部分，第一部分是将XML文档树转换成为三层子树。第二部分是利用各种操作进行结构模式匹配。

首先，本文中提出了三层子树的概念，在XML文档树转换成为三层子树的过程中，涉及到了三种形态的子树：单叉树、过度子树、一般子树。并且将XML树的节点分为两类：内部节点和值节点。值节点指的是XML树中的叶子节点。内部节点包括三类：一层节点、二层节点、过度节点。

在结构模式匹配中，涉及到了更新操作、删除操作和插入操作。在更新操作中引入迁移频度；在删除操作中引入删除平衡因子；在插入操作代价中引入插入平衡因子。迁移频度主要是体现更新时的等价度；删除平衡因子主要是用来调整具体环境所决定的权重与删除代价间变换的差异；插入平衡因子主要是用来调整具体环境所决定的权重与插入代价变换间的相似度。

参考文献：

[1]Stefano Ceri et al.XML-GL：A Graphical Language for Querying and Restructuring XML Documents，SEBD，1999：151-165.

[2]孟小峰.XML数据管理[M].北京：清华大学出版社，2009.