版权所有:内蒙古大学图书馆 技术提供:维普资讯• 智图
内蒙古自治区呼和浩特市赛罕区大学西街235号 邮编: 010021
作者机构:复旦大学上海市智能信息处理重点实验室上海200433 华东师范大学上海市高可信计算重点实验室上海200062
出 版 物:《软件学报》 (Journal of Software)
年 卷 期:2010年第21卷第4期
页 面:672-679页
核心收录:
学科分类:08[工学] 0835[工学-软件工程] 081202[工学-计算机软件与理论] 0812[工学-计算机科学与技术(可授工学、理学学位)]
基 金:国家高技术研究发展计划(863)No.2007AA01Z189 上海重点学科建设项目资助No.B412
主 题:算法设计 数据流 Hamming范数 稳态分布 XML(extensible markup language)
摘 要:在数据库理论中,如何在较小的空间条件下快速地比较不同的XML(extensible markup language)流的差异性是一个基本问题.在这一问题的研究中,人们提出了树编辑距离等测度来描述XML文本的差异性.提出了一种基于Hamming范数的l0测度——即XML树的不同子树的个数,并以此来刻画XML文本的相关性.在数据流模型下,给出了基于空间有界伪随机数发生器、稳态分布于哈希函数的l0测度的概率算法.理论上的时空复杂性分析、正确性证明与实验模拟结果表明,这一概率算法对问题的输入提供了一个理想的近似.