印桂生，沈洁，谢晓芹

(哈尔滨工程大学 计算机科学与技术学院，黑龙江 哈尔滨 150001)

可扩展标记语言 (extensible markup language，XML)自1998年出现以来，目前已经成为国际互联网数据交换的标准格式，对XML数据流的过滤检索也是当前的研究热点.近年来，在XML过滤技术领域，运用有限自动机来对XML数据流进行过滤已有了一些研究［1-5］，并取得了一些成果.已有的研究主要分为两大类:第1类是基于非确定有限自动机(nondeterministic finite automaton，NFA)，其主要的思想是定义了XPath与NFA的相互转换，优点是构造简单，空间开销较小，这种技术的典型代表是XFilter和 YFilter系统;第2类是基于确定有限自动机(deterministic finite automaton，DFA)，它定义了XPath与DFA的相互转换，优点是状态转移目标明确，执行效率较NFA有明显的提高，其典型代表是Lazy DFA.

本文研究XML数据过滤过程中存在的缓存失效，缓存失效的发生会导致过滤的效率降低，因此研究基于确定有限自动机的XML数据过滤过程中如何减少缓存失效对于改进过滤的性能具有重要意义.本文的主要工作就是在DFA过滤机制研究的基础上加入缓存失效控制机制，最大限度地提高过滤的时间性能和空间使用性.

1 Lazy DFA基本思想

Lazy DFA的基本思想［5］是所有的查询表达式被转换到单一的DFA中，其步骤是:

1)将所有的查询转换为一个单一的NFA.

2)根据NFA再转换为相应的DFA.为了记录DFA状态转移的触发条件，每个DFA状态都维护一个状态转移哈希表.

3)需要记录在该DFA状态下，有哪些查询表达式是和当前过滤的XML文档相匹配的，用于在过滤过程中进行结果收集.

对于已经构……