XML模式匹配算法的分析-计算机软件与理论专业论文.docx

摘要 XML 逐渐成为了网络中数据表示、数据分析和数据交换的标准。但由于 XML 数据描述的灵活性，以及 XML 文档数量和规模的日益增大，如何高效的管理大规 模 XML 数据以及集成大量的 XML 数据资源变得十分重要。因此用于识别 XML 模式之间的一致性元素的自动 XML 模式匹配技术成为许多领域亟待解决的问题。 本文在分析研究现有模式匹配方法的基础上，结合 XML 模式中元素的信息特 征，综合考虑匹配质量和匹配效率，提出了一种新的 XML 模式匹配算法。它主要 包括模式的预处理和匹配算法两个部分。首先，模式经过简化处理表示为一种序 列结构 CPS(Consolidated Prüfer Sequence)。然后用综合语言匹配和结构匹配的混合 匹配算法对模式进行匹配。语言匹配充分利用模式元素的特征信息，包括名称匹 配、数据类型匹配和基数约束匹配，其中名称匹配采用决策树的原理合并多种字 符串匹配算法。结构匹配算法中，首先用孩子元素、叶子元素、祖先元素和兄弟 元素的信息计算所有复杂元素对的结构相似值，得到匹配的复杂元素对。然后仅 把结构匹配算法应用到匹配复杂元素对下的原子元素，而不是计算所有原子元素 的结构相似值，这种结构匹配方法易于发现复杂匹配。 最后为了进一步改善效率本文设计了几种并行策略，提出了并行语言匹配算 法和并行非复杂节点的结构匹配算法。通过大量实验，验证了本文的模式匹配算 法具有高效性，并行改进的算法也具有可行性。 关键字：XML 模式 模式匹配 相似值 CPS 决策树 Abstract XML has emerged as a standard for data representation, data analysis and data exchange on the Web. However, due to the flexibility of data description and the increase in the number and the size of XML documents, how to efficiently manage large XML data and integrate lots of XML data sources have become vital. Therefore an automatic XML schema matching used to identify semantic correspondences among XML schemas is an urgent problem in many domains. Analyzing the existing methods of schema matching and combining with the information characters of element in XML schema, this paper proposes a new approach of XML schema matching which considers both matching quality and matching efficiency. It consists mainly of two parts-schema pre-processing and matching algorithm. First each simplified XML schema is represented as a sequence called CPS (Consolidated Prüfer Sequence). Then matching algorithm is applied on two schemas. It is a hybrid matcher combining linguistic matcher and structural matcher. Comprehensively exploiting the feature information of element, linguistic matcher consists of name matcher, data type matcher and constraint matcher. In addition, name matcher combines multiple string matching algorithms with the idea of decision tree. Structural matcher first computes the structural similarity of all complex el