文档介绍：模式匹配查询算法研究
摘要:本文针对XML文档树设计了模式匹配查询算法,该算法包括XML文档树转换成为三层子树和利用各种操作进行结构匹配。在转换成为三层子树的时候,涉及到了三种形态的子树:单叉树、过度子树、一般子树。并且将XML树的节点分为两类:内部节点和值节点。在模式匹配的时候,用更新操作、删除操作、插入操作完成了模式匹配。
关键词:三层子树;更新操作;删除操作;插入操作
中图分类号: 文献标识码: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最早使用编辑距离计算了两棵树(图)之间的相似度,其基本思想是将两棵树间的距离定义为利用编辑操作将一棵树转化为另一棵树所耗费的最小代价。
在“内容十结构