论文部分内容阅读
XML (eXtensible Markup Language,可扩展标记语言)自1998年出现以来,已经成为互联网数据交换格式的标准。大量与之相关的应用,如消息通知系统、个人个性化信息等都需要对信息进行过滤。如何对XML的数据进行高效的过滤,已经成为近年来XML的热点研究问题之一。近些年,人们在对XML过滤的研究中,已经取得了一系列成果。其中,许多理论模型和上具,都已经很成熟。例如,XPath、自动机等有关理论已经形成了各种各样的应用机制。以XFilter的出现为代表,YFilter、lazy DFA等一系列与自动机有关的理论,被广泛应用到XML的过滤中,而各种自动机的有关模型也不断的被研究出来,这也是当前XML过滤应用所广泛使用的技术。存XML的过滤中,要考虑的是如何减少过滤时的开销,提高过滤的效率,从而追求效益的最大化,这其中,如何减少无效元素的处理,减少文档的解析量,便成为一个重要途径,本文相关的研究上作也由此而展开。减少无效元素的处理,包括两个方面,一是如何快速断定某些元素是无效元素,二是如何对这些无效元素进行处理。本文通过引入哈希表,来对无效元素进行判断,通过引入流索引,来对无效元素进行跳过,从而提高过滤的效率。哈希表存储了元素的位置信息,可以快速判断文档中任意两个元素的层次关系,以便判断元素是否为无效元素。过滤时,祖先后代关系“//”的处理往往需要消耗大量时间,因为如果有元素可以匹配该关系,那么无论该元素存文档的何种深度,都满足过滤条件,而对该元素判断的过程中,需要大量的压入堆栈操作,所耗用的时间和空间太大。存本文中,通过引入哈希表,存遇到祖先后代关系“//”,可以不必先将其压入堆栈,而是通过查找哈希表,看需要过滤的元素是否满足过滤条件,如果是,压入堆栈进行操作,如果否,则结合流索引进行跳过。流索引标记了元素的开始位置和结束位置,当遇到无效元素时,可以通过结束标记,对无效元素及其子孙元素进行直接跳过,从而避免无效元素的处理,从而提高解析效率。实验表明,当输入的文档深度较大和文档中的祖先后代关系较多时,本文中的方法要优于传统XML过滤方法的效率。