《一种基于硬件的 xml 解析方法的设计与实现》由会员分享,可在线阅读,更多相关《一种基于硬件的 xml 解析方法的设计与实现(80页珍藏版)》请在金锄头文库上搜索。
1、ffffffffffffffffffffffffffffffffffffffff 公开公开公开公开TP311.10TP311.10TP311.10TP311.10 代代号号 分类号分类号 学学号号 密密级级 107011070110701107010921421389092142138909214213890921421389 题题(中、英文中、英文中、英文中、英文)目目一种基于硬件的一种基于硬件的 XMLXMLXMLXML 解析方法的设计与实现解析方法的设计与实现 TheTheTheThe DesignDesignDesignDesignandandandand RealizationRea
2、lizationRealizationRealization ofofofofA A A AHardware-BasedHardware-BasedHardware-BasedHardware-Based XMLXMLXMLXMLParsingParsingParsingParsing MethodMethodMethodMethod 作作 者者 姓姓 名名黄宁黄宁指导教师姓名指导教师姓名、职务职务霍红卫霍红卫 教授教授 学学 科科 门门 类类工科工科 提交论文日期提交论文日期二二二二一二年一月一二年一月一二年一月一二年一月 学科、专业学科、专业计算机软件与理论计算机软件与理论 独创性(或创新
3、性)声明独创性(或创新性)声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究 成果。尽我所知,除了文中特别加以标注和致谢中所罗列的内容外,论文中不包 含其他人已经发表或撰写过的研究成果;也不包含为获得西安电子科技大学或其 它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的 任何贡献均已在论文中做了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处,本人承担一切相关责任。 本人签名:日期: 关于论文使用授权的说明关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定,即:研究 生在校攻读学位期间论文工作的知识产权单位属西安
4、电子科技大学。本人保证毕 业离校后,发表论文或使用论文工作成果时署名单位仍然为西安电子科技大学。 学校有权保留送交论文的复印件,允许查阅和借阅论文;学校可以公布论文的全 部或部分内容,可以允许采用影印、缩印或其它复制手段保存论文。 (保密的论文 在解密后遵守此规定) 本学位论文属于保密在_年解密后适用本授权书。 本人签名:日期: 导师签名:日期: 摘要 XML(Extensible Markup Language,可扩展标记语言)是一种使用标记标记 内容以传输信息的简单方法,由于它的可扩展性和跨平台特征,在 web 服务器和 数据库系统中得到了广泛的应用,已经成为了数据描述和交换的标准。然而,
5、相 对于现在企业级服务器 GB 级的数据吞吐量,基于软件的 XML 解析无法达到所 要求的吞吐量,对网络性能来说,这已成为一个严重的瓶颈。如今,开发一种能 够替代软件解析 XML 的方法已成为必须。 本文通过对 XML 解析的理论分析以及四种解析模型的对比,最后提出了一 种基于 DOM 解析模型的硬件解析 XML 的方法。它主要包括四个重要的模块: 词法分析模块、格式良好检查模块、DOM 树构建模块和 Schema 验证模块。词法 分析主要是对输入的 XML 字符做出相应的标记,从而识别出元素名、属性名以 及文本内容,通过使用一个 FSM 实现。格式良好检查主要是对 XML 文档进行语 法检查
6、,包括元素名检查和属性名检查,在元素名检查中,主要使用栈结构对元 素名字符进行匹配,而属性名检查主要是检查同一元素的属性名唯一性,本文使 用一种名为布隆过滤器的高效随机存储结构,可以快速的判断当前的元素是否已 经出现过。DOM 树构建模块独立于格式良好检查模块和 Schema 验证模块,它是 对整个 XML 文档的信息建立一棵树形结构,主要包括元素名节点、属性名节点、 元素内容节点和属性内容节点四种节点类型。Schema 验证是对 XML 文档中的元 素和属性与 Schema 文档中所定义的规则进行匹配来验证 XML 文档的合法性, 由 于 Schema 文档定义的规则比较固定,在解析之前,首
7、先对 Schema 文档进行预处 理,将它定义的规则制作成一个静态表存储在本地内存中,这样在进行解析的过 程中可以直接通过查询表寻找相应的规则。 最后通过大量的实验,验证了本文的硬件解析方法较软件解析方法拥有很高 的加速比,此系统的吞吐量可以达到 1.2Gbps。所有的实现都是在 FPGA 硬件环 境下测试与仿真的。 关键字:关键字:XMLXMLXMLXML 解析解析SchemaSchemaSchemaSchema 验证验证DOMDOMDOMDOM 树树布隆过滤器布隆过滤器 Abstract XML( ( ( (Extensible Markup Language)isa simple met
8、hod thatitmarks content with markers to transmission information.Due toitsextensibility and cross-platform features,XMLhasbeen widely used in web server and database system, andithas become a data description and exchange standard. However, relative to the present enterprise server GB data throughpu
9、t, software-based XML processing methodsfailto deliver the required throughput, posing a severe bottleneck to network performance. The need for exploring alternative solutions for parsing XML data has thus assumed prime importance today. Analyzing the theore of the XML parsing and contrasting the fo
10、ur parsing models, this paper proposes a DOM-based XML hardware parsing technique.Itincludes four mainmodules:LexicalAnalysismodule,Well-formedCheckingmodule,DOM Constructor module and SchemaVerification module .The input XML characters are marked to identifythe element name,the attribute name and t
11、ext content in theLexical Analysis .This module uses a FSM to implement. Well-formed checkingismainly to check syntaxofthe XML document, which including the element name checking and attribute name checking. A stackisused to match the element name characters, and an efficient random storage structur
12、e called bloom filterisused to check uniqueness of attribute name, which can rapidly judge whether the current attribute had appeared. DOM constructing moduleisindependent on the Well-formed Checking module and the SchemaVerification module,which uses four kinds of node-type to build a DOM tree of t
13、he input XML document,including the element name node ,the attribute name node, the element content node and the attribute content node. Schema Verificationis mainly to match the element and the attribute name with the rules definedinthe Schema file. Due to the relatively small volatility of schema
14、files, we first pre-compile the current schemafileinto a static table which be storaged in a custom local memory to lookup rules At last , comparedwithsoftware parsing method,through a large number of experiments, the hardware parsing XML method has a high speedup ratio,.the system throughput can be
15、 achieved 1.2Gbps.Realizations aretested and simulated.under the FPGA environment. KeywordKeywordKeywordKeyword: : : :XMLXMLXMLXMLParsingParsingParsingParsingSchemaSchemaSchemaSchema ValidationValidationValidationValidationDOMDOMDOMDOM treetreetreetreeBloomBloomBloomBloomFilterFilterFilterFilter 目录
16、第一章 绪论. 1 1.1 研究背景.1 1.2 研究现状.2 1.3 主要工作3 第二章 XMLXML和 XMLXML SchemaSchema.5 2.1 XML 简介.5 2.1.1 XML 的发展和作用5 2.1.2 XML 的定义和例子6 2.1.3 XML 的相关术语7 2.1.4 XML 的应用11 2.2 XML Schema 简介.13 2.2.1XML Schema 的定义和例子.13 2.2.2XML Schema 的重要性和优点15 2.3 本章小结.16 第三章 主要的解析模型.17 3.1 DOM 解析模型.17 3.2 SAX 解析模型.18 3.3 StAX 解析模型.20 3.4 VTD-XML 解析模型.21 3.5 四种解析模型的对比22 3.6 本章小结23 第四章 基于 DOMDOM解析的步骤分析.25 4.1 格式良好检查.25 4.2 Schema 验证.27 4.3 DOM 树构建.28 4.4 本章小结28 第五章 硬件体系结构设计.29 5.1 模块之间的连接方式.29 5.2 Schema 预处理技术.30 5.2