一种快速的XML文档验证算法

来源：计算机技术与发展杂志2015年第08期北京时间：

作者：张苗;惠小强

摘要：在用XML( eXtensible Markup Language) Schema校验来判断XML文档合法性的过程中，目前LIBXML2所采用的逐层遍历校验法对3层及以下嵌套效率低下，对多于3层嵌套的校验法失效。针对这一问题，文中提出一种新算法，可有效避免逐层遍历法验证的缺陷。先计算XML文档中某待验证元素出现的次数，然后把该次数分解为XSD( XML Schema Def-inition)文档中所定义的该元素允许出现次数区间内整数的线性组合，计算出所有线性组合中系数和的最小值和最大值。若计算出的系数和范围与XSD文档定义的范围有交集，则验证通过，否则不通过。利用所提算法，对多嵌套和maxOccurs较大的XML文档，验证效率可提高两个数量级。

关键词：XML文档;复杂类型;LIBXML2;XML Schema校验