XML文档过滤引擎有限自动机的构造

吴绍根

（广东轻工职业技术学院，广州 510300）

0 引言

XML即可扩展标记语言，自1998年出现以来，已经成为系统间进行数据交换的标准。访问XML文档的方式有两种：XML文档检索和XML文档过滤。XML文档检索是指依据一定的检索条件对所存储的XML文档进行查询，并将满足条件的XML文档或片段返回给检索者，是主动式的访问；XML文档过滤则是指将XML文档与所存储的条件规则进行匹配，并将满足条件规则的XML文档或片段返回给条件规则的制定者，是典型的订阅/发布式的访问。

近年来，针对这两种XML访问形式的研究和应用均有较大的发展[1-4]，特别是随着Internet网上数据量的剧增，基于XML文档过滤形式的访问更是得到了长足发展。在XML过滤系统中，用户只需制定相应的条件向系统订阅，随着XML文档到达过滤系统，即可将满足条件的XML文档推送/发布给相关感兴趣的用户，从而极大地提高了信息的时效性。XML文档过滤是XML相关技术领域的一个研究热点[4]。

在与XML文档过滤相关的研究成果中，出现了一些较为成熟的过滤系统，其中基于有限自动机的过滤系统比较突出，同时也得到了广泛的应用，包括首次将有限自动机应用于XML文档过滤的XFilter[5]系统和后续的 YFilter[6]系统、QFilter[7]系统等。在基于有限自动机的XML过滤系统中，核心组件是过滤引擎，而过滤引擎的核心是过滤有限自动机。过滤有限自动机的效率将直接决定过滤系统的效率。本文将介绍一种高效构造过滤有限自动机的方法，并给出了对过滤有限自动机进行动态在线更新的方法。

1 有限自动机和XM L过滤系统

在介绍过滤有限自动机的构造算法之前，首先对有限自动机和XML过滤系统进行简单的介绍。

1.1 有限自动机

有限自动机是一个五元组 M=（Q，Σ，δ，q0，F），其中，（1）Q 是一个有穷集合，称为状态集；（2）Σ是一个有穷集合，称为字母表；（3）δ是A→Q是转移函数，其中 A⊆Q×Σ，对于任何 b∉A，δ（b）=q0；（4）q0∈Q是起始状态；（5）F⊆Q是接受状态集。为了直观，在实际应用中，经常使用状态迁移图来表示特定的有限自动机。

1.2 XM L过滤系统

XML过滤系统也称为SDI[5]系统，即Selective Dissemination of Information，它基于用户的需求（User Profiles）对XML文档进行过滤并将满足条件的文档或文档片段分发到相应的用户，其体系结构如图1所示。

XML过滤系统有两个输入：XML文档和用户需求。其中XML文档是来源于任何数据源的已格式化为XML格式的数据；用户需求则是用户所订阅的匹配条件，存储在XML过滤系统中。

图1 XML过滤系统结构

XPath表达式已经成为查询XML文档的标准语言，在XML过滤系统中，存储于过滤系统中的用户需求是用XPath表示的。由于XPath表达式上下层路径所固有的内在关联性，可以使用有限自动机进行一致的表达。例如，对于如下四个XPath表达式：

（1）Q1：/a/b

（2）Q2：/a/*/c

暴怒中的赵仙童，企图找什么硬件殴打砖子，砖子慌了，撒腿逃出家门，心里苦苦地叫着：生活实验又开始了，老天爷啊，我快崩溃啦！

（3）Q3：/a//c

（4）Q4：b/c

可以转换为与之对应的有限自动机，如图2所示。

图2 XPath表达式的有限自动机表示

XML过滤有限自动机的构造就是将从XPath表示的条件创建与之等价的有限自动机，并实现对过滤有限自动机的维护。

2 过滤有限自动机的生成及维护算法

2.1 过滤自动机核心数据结构

为了将用XPath表示的过滤需求转换为有限自动机的形式，需要首先定义有限自动机的节点数据结构。为此，定义如下的数据结构（数据结构及算法均用伪C表示）来表示过滤有限自动机的状态节点。

struct StateNode{

unsigned int state; //节点状态

XML的元素标识

unsigned int shared; //当该节点被多个订阅需求共享时，记录共享的次数

struct StateNode*next; //指向可以由该节点迁移到的所有的后继节点的节点数组

unsigned int count; //该节点的后继节点的数目

unsigned int flag; //是否为接受状态，若是则为1，否则为0

struct User*users; //若为接受节点，则指向订阅用户的数组，否则为null

}

在过滤过程中，当XML文档满足某个订阅用户的需求时，需要将该XML文档或文档片段分发给订阅用户，为了表示用户的个体信息，定义如下的数据结构。

2.2 生成过滤有限自动机

生成过滤自动机的基本思路如下：首先判断过滤自动机是否存在，若不存在，则创建一个只有起始节点的有限自动机，然后分解XPath参数路径中的各个元素，并从过滤自动机的起始节点开始在过滤自动机中搜索，若搜索到对应的element，则相应节点的shared域加1，否则，新增一个节点。算法描述如下：

StateNode* AddNewXPath （StateNode *machine，string XPath，User*user）

2.3 从过滤有限自动机中删除一个XPath

随着时间的推移，用户所订阅的需求会发生变化，为此，需要从过滤有限自动机中将部分无用的需求删除。

分解XPath参数路径中的各个元素，并从过滤自动机的起始节点开始，在过滤自动机中进行搜索，若搜索到对应的element，则相应节点的shared域减1，如果减1后该节点的shared域的值为0，则从过滤有限自动机中删除该状态节点及该节点的所有后继节点。算法描述如下：

StateNode* DeleteAXPath （StateNode *machine，string XPath）

2.4 更新过滤有限自动机中的XPath

更新过滤有限自动机中的XPath，其含义是用一个新的XPath替换一个旧的XPath。更新的基本思想是：从过滤有限自动机中删除旧的XPath，并将新的XPath添加到过滤有限自动机中。算法描述如下：

3 过滤引擎有限自动机的动态更新

XML用户可能随时会对过滤需求进行变更，因而需要对过滤引擎有限自动机进行动态在线更新。

参照计算机CPU的中断工作机制可以实现对过滤引擎有限自动机的动态在线更新。在一个离线的系统中完成对过滤引擎有限自动机的更新并将自动机保存到一个介质上，然后向正在工作的过滤系统发送一个更新消息（相当于计算机CPU的中断管脚置位），当正在工作的过滤系统完成当前任务处理后，检测到该更新消息，从介质上加载并更新到新的自动机上。

4 结语

本文介绍了基于有限自动机的XML过滤引擎有限自动机的构造，详细描述了过滤有限自动机的生成算法、XPath的删除算法和XPath的更新算法，并借鉴CPU对中断的处理技术，介绍了如何实现过滤有限自动机的动态在线更新。为了实现更加精细的过滤，在过滤有限自动机中实现XPath的谓词功能和对XPath全集的支持是基于有限自动机的XML文档过滤的一个重要研究方向并将继续予以关注。

［1］周军锋，孟小峰．XML关键字查询处理研究［J］．计算机学报，2012（12）：2459-2478．

［2］刘宝龙，刘念，陈桦．基于XPath分解XML文档的完整性检查［J］．西安工业大学学报，2012（8）：17-21．

［3］刘丹，陆伟，张宓．XML 结构化检索研究及实现［J］．现代图书情报技术，2009（3）：52-56．

［4］覃泳睿，孙未未，张卓瑶，等．基于有限自动机的XML过滤技术研究综述［J］．计算机科学，2008（12）：19-24．

［5］Altinel M，Franklin M．Efficient filtering of XML documents for selective dissemination of information［C］．VLDB，2000．

［6］Diao Y，Fischer P，Franklin N M．YFilter：Efficient and Scalable Filtering of XMLDocuments［C］．ICDE，2002．

［7］Luo B，Lee D G．QFilter：Finegrained runtime XML access control via NFA-based query rewriting．CIKM 2004［C］．Washington D C：Conference on Information and Knowledge Management，2004．