基于流量分析的XML嵌套数据流无损压缩算法.pdf

信息技术 年第 期基于流量分析的 嵌套数据流无损压缩算法徐 晨 顾曦华 盛银波 金 军(.嘉兴恒创电力集团有限公司华创信息科技分公司 浙江 嘉兴.国网浙江嘉兴供电公司 浙江 嘉兴)摘 要:为避免基体的反复压缩操作提出一种基于流量分析的 嵌套数据流无损压缩算法 利用 算法对高相似度的 嵌套数据流进行聚类分析并表述成“簇中心(基体)个体差异量”形式分解数据流完成一次基体压缩仅对差异量进行压缩极大减少对基体的反复压缩操作利用改进 算法实现 嵌套数据流无损压缩 实验结果表明压缩后不仅数据完整性得到了保证数据量也大幅减少数据冗余度降低与压缩前数据相比压缩后数据未出现变化说明压缩算法性能较好关键词:流量聚类 可扩展标记语言 嵌套数据流 无损压缩 串表压缩算法中图分类号:文献标识码:文章编号:():./.作者简介:徐晨()男本科工程师研究方向为电力信息化运维、智能化通信及信息设备监控等 (.):.“()”.:引 言在数据信息传输过程中(可扩展标记语言)是信息交换与数据处理的通用格式目前基于流量分析的 嵌套数据流无损压缩算法 徐晨 等很多数据信息都会选择以 的形式进行存储和交换 自身数据重复率较高会占用大量的存储资源降低了数据传输效率 为此很多专家和学者从压缩入手研究降低 嵌套数据流冗余目前压缩算法主要分为有损压缩和无损压缩 前者压缩后的数据较小但容易造成数据丢失后者能在保证数据完整性的同时消除冗余信息但是对数据精度要求较高压缩运算量大压缩时间较长 赵雅倩等人提出一种实现无损数据压缩算法的专用硬件电路采用多字典并行查找的方式提高重复数据的查找速率采用开放计算语言()实现了所提出的专用硬件电路在取得适当压缩率的同时显著地提高了数据的压缩速率压缩速率可达/本文以无损压缩的方式对 嵌套数据流进行研究 在保障数据完整性的同时降低压缩比基于流量分析的 嵌套数据流无损压缩算法 嵌套数据流是当下数据传输与储存的主要模式 这种模式由于其自身的优势能够承载更多的数据量且连续性较好但是这种模式同时也会造成数据冗余较大 无损压缩算法既能保证数据不缺失也同时可减少冗余的数据.基于聚类的 嵌套数据流分析无论是无损压缩还是有损压缩都是通过特殊编码的方式降低数据信息重复以及冗余度完成数据压缩 然而当数据流之间相似度较高时传统的无损压缩方法要保证数据的完整性所以压缩之后的数据量仍然很大因此为降低无损压缩的压缩比提高后续压缩效率在正式压缩之前针对相似性进行基于聚类的 嵌套数据流分析结合主动规则在数据流查询处理过程中构建主动服务系统按照统一机制完成主动性需求 框架模型主要包括用六个执行模块如图 所示类关系型操作会产生较多空值浪费数据存图 数据流框架储空间存储效率较低 将 文档以文件的形式存储在数据库中建立文档索引可提高数据库管理效率基本思路是通过聚类将 嵌套数据流划分为以 个簇为中心的形式即簇中心(基体)个体差异量这样可降低数据流之间的整体冗余量数据流与传统数据是不同的主要体现在如下两个方面:数据流是动态无限、连续变化的而传统数据是静止的数据流往往包含大量的属性因此维数较高针对数据流传统聚类算法都是在扩展数据集的聚类算法的基础上发展而来 表 给出几种典型的数据流聚类算法特点通过表 可以看出任何一种数据流聚类算法都存在缺点因此在本文选择一种混合算法进行 嵌套数据流分析即混合 算法和 算法生成一种 算法 算法 算法是一种基于密度的聚类算法基本思想如下:由密度可达关系导出最大密度相连的样本集合即为最终聚类的一个类别或者说一个簇 该算法具体过程如下:步骤:从数据流集合当中任意选取一个还未处理过的数据作为对象基于流量分析的 嵌套数据流无损压缩算法 徐晨 等表 典型的数据流聚类算法特点数据流聚类算法 算法 算法 算法 算法 算法 算法核心思想分治思想批处理分级思想分治思想两阶段处理框架投影思想衰减簇结构密度思想两阶段处理框架网格结构聚类质量一般一般好较好好一般可伸缩性差好好好一般好聚类形状球状球状球状任意任意任意输入敏感性是是不是不是不是不是噪声处理能力差好好好好好 步骤:判断该数据是否核心对象 若不是则需要回到步骤 重新进行选取否则以该点为核心以领域距离 为半径划分出所有直接密度可达点并都加入到类簇中步骤:重复步骤 直到所有数据点都判断完毕步骤:此一个聚类完成 重复步骤 到步骤 直到一个数据流集合中的所有数据都归到自己所属类别中 算法 算法是一种基于网格的聚类算法该算法分为联机和脱机两部分 前者将数据流元素按照定义映射或者说定位到某个网格中后者计算这些网格的密度也就是每个单元网格中数据流元素在整个数据流集合中的比例 最后基于密度计算结果将符合阈值(由用户自主给定)的网格单元聚成类簇 算法 算 法 是 算 法 和 算法的互补性结合 该算法在聚类框架基础上沿袭了 算法的特点是在线、离线双层数据流聚类结构 在在线层主要完成对输入的 嵌套数据流进行映射根据其具备的属性将其定位到相应的网格单元当中在离线层根据密度自适应地调整聚类和更新网格单元的特征向量最终完成簇的聚类 具体过程如下:步骤:输入一段 嵌套数据流 构建初始网格单元步骤:获取 嵌套数据流中的新数据对象步骤:映射新数据并更新网格单元的特征向量 特征向量表示形式如下:()为密度 为归属的类标志为存放地址 为新数据最近一次的流入时间步骤:判断(数据流流入时刻)是否与(时间间隔)相等 若相等则开始初始聚类否则回到步骤 步骤:判断?若相等则检查并去除噪声点否则回到步骤 步骤:网格单元进行类别调整输出最后的聚类结果 嵌套数据流聚类分析完成后用“簇中心(基体)个体差异量”形式表示方便后续压缩 上述提取出来的聚类中心作为基体个体差异量为围绕聚类中心的其他数据量这个数据量虽然都所属一类但是具体表示上会存在差别这个差别就是个体差异量 简单地说就是将数据流分解在压缩的时候即完成一次基体压缩然后仅对差异量进行压缩即可极大减少对基体的反复压缩操作 嵌套数据流聚类过程如图 所示.嵌套数据流无损压缩实现无损压缩算法有很多但大体分为两类即基于统计压缩算法和基于字典的压缩算法综合表 中几种无损算法的特点选择基于字典压缩算法中的串表压缩算法(算法)进行无损压缩由于 算法也存在缺点需对其进行相应的改进基于流量分析的 嵌套数据流无损压缩算法 徐晨 等图 数据流聚类过程 算法是用字典中词条的编码来代替复杂的字符串以减少数据冗余度 算法基本表 几种常用的无损压缩算法特征对比项目基于统计基于字典行程编码算术编码压缩比很好较好很好较好较好复杂度中等简单复杂中等中等实时性较差一般一般较好较好存储空间较大须预存数据较小较小窗口的面积几 字典面积一般几 适用场合任何数据二值图像任何数据任何数据尤其局部相关性好的数据任何数据尤其是全局或局部相关性好的数据流程如图 所示图 算法基本流程基于流量分析的 嵌套数据流无损压缩算法 徐晨 等 在 算法中字典起到了关键作用字典的容量一旦被填满或者受到计算机内存限制压缩效率和压缩质量都会受到限制 为解决这一问题删除字典中多余的词条为字典容量和计算机内存提供更大的空间 首先在动态构建的字典中加入一个清除的标志 当字典容量达到极限时判断压缩比是否小于设定的阈值小于时统计每一个码字的使用情况然后按照从大到小的顺序排列删除末尾的若干项 具体过程如下:步骤:输入 嵌套数据流步骤:构建字典步骤:初始化字典并记录大小使词典包含所有可能的根()当前前缀 置空步骤:当前字符 等于字符流中的下一个字符步骤:判断字符串 是否存在于字典中:判断为“是”则 并把代表当前前缀 的码字输出到码字流判断为“否”将 添加到字典中步骤:令 步骤:判断字典的容量是否达到极限 若字典的容量未满则回到步骤 否则统计输出字典中单字符的使用概率步骤:判断压缩比是否小于指定阈值若小于则清除使用概率最小的字符解决字典被填满和计算机内存不足的问题否则回到步骤 步骤:输入压缩结果 实验与结果分析为了验证本文所提压缩算法的性能从坎特伯雷语料库中选取了三个较大的不同类型的 嵌套数据流文件作为实验样本分别使用本文算法、一般 算法、改进 算法以及有损压缩算法进行压缩试验算法的实验环境如下:系统()()处理器 内存硬盘大小为 主频为 使用 编写算法代码.嵌套数据流样本表 嵌套数据流样本具体情况文件名 文件大小(字节)文件内容描述中央情报局档案圣经细菌的完整基因组.字典划分字典的划分方式会影响字典压缩编码的压缩率因此根据选取的 嵌套数据流大小采用 的划分方式.评价指标均方误差百分比:()()()()式中 为 嵌套数据流总数()表示原始 嵌套数据流()表示压缩后的 嵌套数据流()越小说明与原始 嵌套数据流的误差越小数据压缩后保存的数据越完整压缩比:()其中 为输出流的大小为输入流的大小压缩消除率:()()()()压缩消除率越大表示压缩后数据量越少所消除的数据量越多压缩结果越好压缩速率:()()()()式中 为压缩时间 压缩速率越大表示单位时间内的压缩消除率越高平均压缩效果越好.解压缩方法压缩后为查看 嵌套数据流的完整性还需要进行解压处理流程如图 所示.结果分析从表 中可以看出本文算法与一般 算基于流量分析的 嵌套数据流无损压缩算法 徐晨 等图 解压处理流程表 嵌套数据流压缩结果项目本文方法一般 算法改进 算法文献无损数据压缩算法均方误差百分比 压缩比 压缩消除率 压缩速率 法、改进 算法和有损压缩算法相比压缩速率并不高这是因为本文算法多了一个基于聚类的 嵌套数据流分析环节所以要花费的时间较多但是通过均方误差百分比这一指标本文算法压缩后数据的完整性得到了极大保证 此外通过对比压缩比和压缩消除率本文方法压缩后 嵌套数据流规模虽然大于文献无损数据压缩算法但是相差并不大说明本文算法基本解决了无损压缩后数据量过大问题提高了压缩质量利用 解压后与源文件分析比较图 压缩前后及解压后数据波形由图 可以看出解压后数据与压缩前数据完全一样无损压缩的本质也可以理解为使信源趋于等概率分布降低信源的冗余度 压缩后的数据从概率分布特性来看概率分布较压缩前数据更均匀概率分布图更为平稳由图 可以看出压缩后的概率分布曲线明显比压缩前的平缓直观上可以看出压缩后数据冗余度的降低与理论分析吻合 结束语为有效减少数据冗余降低数据占用率本文提出一种基于流量分析的 嵌套数据流无损压缩算法 该算法通过仿真分析基本实现了压缩量和数据完整性双重目标 然而本文仍有一些问题需要进一步探讨即在仿真实验结果中均方误差百分比仍然存在而无损压缩的宗旨是没有任何数据丢失因此针对数据丢失的原因需要进一步研究分析基于流量分析的 嵌套数据流无损压缩算法 徐晨 等图 数据压缩前后信源符号概率分布参 考 文 献:何志学廖湖声.基于森林自动机处理 流数据方法.计算机工程与设计():.杨敏珠邹曜璞韩昌佩.基于单帧干涉图的无损压缩的研究.现代电子技术():.赵雅倩李龙郭跃超等.基于 的 数据压缩算法.计算机应用():.胡斌李忠强刘婷婷等.与 算法在海洋观测浮标通信数据压缩中的应用研究.海洋科学():.赵延龙滑楠.基于数据集压缩的聚类算法性能优化研究 .计 算 机 应 用 研 究 ():.徐金甫刘露李伟等.一种基于阵列配置加速比模型的无损压缩算法.电子与信息学报():.梁耀鞠晓东李传伟等.基于帧间差分的随钻测井数据压缩算法.数据采集与处理():.李政廉吉立新黄瑞阳等.面向强连接网络图的无损压缩算法.计算机辅助设计与图形学学报():.杨敏珠邹曜璞韩昌佩.基于矢量量化与线性预测的干涉图分段无损压缩.红外技术():.罗瑜张珍珍.一种快速的纹理预测和混合哥伦布的无损压缩算法.电子与信息学报():.李欣然钟俊.基于 改进的 算法在报文压缩中的应用.现代电子技术():.刘晨李玉峰陈好.基于 无损数据压缩技术的改进与实现.电子设计工程():.孟卫东龙美彪.曲线数据压缩算法的研究及应用.计算机系统应用():.伍卫国王超辉王今雨等.基于混合编码的 系统配置文件压缩算法.计算机研究与发展():.高邈史国友李伟峰.改进的 在线船舶 轨迹数据压缩算法.交通运输工程学报():.(责任编辑:丁晓清)(上接第 页).计算机图形学:版.胡事民等译.北京:清华大学出版社:.龚立民.基于 的地球/地图三维模拟软件设计.信息技术():.朱国涛胡文婷.基于 和 的电子地图绘制技术研究.计算机科学与应用():.倪冰洁.天地图电子地图配图中 智能标注方法研究.江苏科技信息():.魏伟.数据采集及动态显示系统的研究与实现.青岛远洋船员学院学报():.张帅帅崔红霞.数据的采集提取和显示.科技创新导报():.(责任编辑:丁玥)