面对互联网上海量的信息,个性化的定制服务逐渐成为人们获取信息的一个重要手段。其核心技术是如何对大量的用XML格式表示的数据进行快速而有效地处理。针对XML数据流,普遍采用的是XPath表达式进行查询。因此,如何在XML数据流上对大量的XPath表示的查询进行快速处理是XML文档过滤的核心问题。对于基于小枝模式的XML文档过滤的研究,目前主要分为两个方向。一个是采用分解的思想,核心是如何高效地对节点间位置关系进行匹配。该类算法有一个通病,即在某些情况下需要多次重复扫描后代节点列表,这导致大量中间结果产生,严重影响了算法执行效率。并且,对于含较多相对路径表达式以及含通配符的表达式查询支持有限。另一个方向是采用整体匹配的思想,即在匹配过程中,将路径表达式中节点间的位置信息考虑在内,作为一个整体进行一次匹配。其主流做法是将XML文档和查询树均以某种编码进行转化,使之成为字符串,然后按照某种遍历策略对字符串进行匹配验证。该思想流行算法很多,但大都不支持逻辑谓词处理。本文在对当前主流XML文档过滤模型进行分析的基础上提出一种新型过滤模型-——FST (Filtering by Sequencing Twigs)。该模型采用整体匹配的思想,将XML文档树的结构信息存储在一种新型数据结构中,采用普吕弗序列生成算法将XML文档及小枝模式查询语句转化为字符串,于是XML文档过滤问题被成功的转化为普吕弗序列的匹配问题。匹配过程中利用一个全局运行栈的数据结构,保证了匹配的有序性,同时,利用全局运行栈从顺序索引的生成及子序列匹配范围的限制两个方面对算法进行了优化,保证了所有的过滤通过一次XML文档遍历便可完成,大大提高了程序的执行效率。针对值谓词以及逻辑谓词,本文提出了一种基于小枝模式的改进策略及预处理方法,使过滤模型可以有效支持等值谓词、非等值谓词以及逻辑谓词。多组实验数据表明,本文的基于有序小枝模式的XML文档过滤模型在效率上较以往过滤模型有较大提高。