数据流环境下xml模式匹配算法研究

《数据流环境下xml模式匹配算法研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、中图分类号：TP311.13论文编号：102871616-S071学科分类号：081200硕士学位论文数据流环境下XML模式匹配算法研究研究生姓名陈冲学科、专业软件工程研究方向XML数据库指导教师蒋夏军讲师南京航空航天大学研究生院计算机科学与技术学院二О一六年一月NanjingUniversityofAeronauticsandAstronauticsTheGraduateSchoolCollegeofComputerScienceandTechnologyRearchonXMLPatternMatchingbasedonDataStreamEnvironmentAT

2、hesisinSoftwareEngineeringbyChenChongAdvisedbyLecturerJiangXiajunSubmittedinPartialFulfillmentoftheRequirementsfortheDegreeofMasterofEngineeringJanuary,2016承诺书本人声明所呈交的硕±学位论文是本人在导师指导下进行的研究工作及取得的研究成果。除了文中特别加臥标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得南京航空航天大学或其他教育机构的学位或证书而使用过的材料。本人

3、授权南京航空航天大学可１＾＾１将学位论文的全部或部分内容编入有关数据库进行检秦，可ｌ＾Ｊｌ采用影印、缩印或扫描等复制手段保存、汇编学位论文。。（保密的学位论文在解密后适用本承诺书，）■１作者辦：巧冲．日期：＂Ｉ．！．．．．．＇＇■■．．．．．？■？＊？．■？南京航空航天大学硕士学位论文摘要随着“互联网+”时代的到来，越来越多的数据开始以网络在线的方式进行发布、交换和集成，Web已经成为人类社会的主要信息源、媒体和商务的门户。作为Web上一种跨产品、跨界面、跨平台的互联网标准语言，XML已经显

4、现出其强大的应用前景。对XML文档的查询和检索效率反映了以XML文档作为数据核心的应用程序的处理效率和用户体验，现有算法能够支持普通小枝模式和部分复杂形式的查询要求，但随着XML数据容量和复杂度的快速增长，在内存消耗和时间效率上依然有提升的潜力。为此，基于数据流环境，论文对XML文档的相关匹配算法进行了深入研究。首先，提出了一种新的基于数据流环境下的小枝模式匹配算法——TwigInStream，该算法可在顺序解析XML文档的过程中得到元素的局部起止编码，仅需对编码有序列表进行操作即可得到匹配结果，无需其他数据结构。理论分析和实验结果验证了该算法具有良好的时空效率，且在

5、处理小枝模式中的P-C关系时体现出一定的优势。其次，针对现有算法在处理通配符匹配时效率低下、内存消耗大、无用中间结果过多等现状，提出了一种新的支持通配符查询的XML模式匹配算法——WTwigList，该算法采用局部的扩展Dewey编码，叶子节点过滤过程减少了参与最终匹配的单路径个数，设置新的数据结构表示通配符在查询模式中的层次信息，减少了参与匹配的通配符个数，限制了通配符匹配元素的范围，在有序的叶子节点编码列表中执行匹配操作得到结果。最后，在真实和合成数据集上做了大量实验，与现有经典算法在参与路径个数、时间效率、内存消耗等方面进行对比，实验结果表明WTwigList算

6、法具有更好的性能。关键词：XML，编码方案，小枝模式，数据流模型，通配符匹配，有序列表I数据流环境下XML模式匹配算法研究ABSTRACTWiththearrivalofthe“Internet+”era,moreandmoredataarestartingtobepublishedonline,exchangedandintegratedwiththenetwork.Webhasbecomethemaininformationsourceofthehumansocietyandtheportalofthemediaandbusiness.AsanInternetst

7、andardlanguageonWebwhichcrossproduct,interfaceandplatform,XMLhasshownitsstrongapplicationprospects.QueryandretrievalefficiencyofXMLdocumentreflectstheprocessingefficiencyanduser-expericnceoftheapplicationwhosedatacoreisXMLdocument.Existingalgorithmsareabletosupportthequeryrequi