基于小波理论的大规模科学数据的约减与压缩.doc

第11A期吴国清等：基于小波理论的大规模科学数据的约减与压缩95基于小波理论的大规模科学数据的约减与压缩吴国清1，陈虹2（1. 中国工程物理研究院 研究生部，北京 100088；2. 北京应用物理与计算数学研究所，北京 100088）摘 要：针对大规模数值模拟产生的海量科学数据，提出了一种科学数据约减与压缩方案。方案首先对科学数据进行离散小波变换，然后通过目标函数优化选取小波系数阈值，对小波系数进行约减，然后进行量化和熵编码，最后利用信噪比和相对能量误差对数据精度损失进行评估。利用激光与等离子体数值模拟数据进行的测试实验获得了几十倍的压缩比。此方法是一种分析处理GB甚至TB数量级科学数据的有效手段。关键词：离散小波变换；数据约减；数据压缩；科学数据中图分类号：TP311 文献标识码：B 文章编号：1000-436X(2008)11A-0091-05Wavelet based data reduction and compression scheme for high volume scientific dataWU Guo-qing1, CHEN Hong2(1. Postgraduate Department of China Academic of Engineering Physics, Beijing 100088,China;2. Institute of Applied Physics and Computational Mathematics, Beijing 100088,China)Abstract: To handle high volume numerical data from simulations, a data reduction and compression scheme based on discrete wavelet transform was presented. By discrete wavelet transform, most energy of scientific data is concentrated into a smaller region. Wavelet coefficients can be selected by thresholded and still retain high percentage of energy of the original data. To optimize the threshold, objection function is constructed to balance model accuracy and data reduction. Reduced coefficients are then quantized and finally entropy encoded. Signal noise ratio and relative energy error are used to evaluate precision loss of data in the whole process. To show applicability of scheme, results obtained with plasma simulation data is presented. Extension of the work leads to efficient analysis and understanding of the GB or TB volume scientific data.Key words: discrete wavelet transform; data reduction; data compression; scientific data1 引言收稿日期：2008-08-20基金项目：中国工程物理研究院科学技术基金资助课题（20040658）Foundation Item: Foundation of China Academic of Engineering Physics(20040658)计算能力和计算资源的不断提高，促进了高性能计算程序问题求解和运算规模的不断扩大，反之，计算程序不断消耗着更多的计算资源和存储资源，也促使计算平台的扩容和升级，海量科学数据成为计算用户面临的问题之一。目前的大规模并行计算程序，其输出数据很容易突破GB级的规模，达到10GB甚至100GB级的规模，这对绝大多数高性能计算平台都是不小的压力。例如，强激光与等离子体相互作用三维数值模拟，目前可以模拟的规模达到108个网格和109亿个粒子，单时间步、单物理量的数据量就可达到24GB，而为了得到一个真实的三维模拟过程，往往需要上百个甚至上千个时间步的数据，整个数据量规模已达TB级，而现有的计算环境显然无法满足数据存储的要求1。对用户来说，分配给他的磁盘空间似乎永远不够。用户常常面临这样的困境：物理问题的求解和计算常常受制于存储资源。现在这种情况越来越频繁，除了增加更多的存储空间外，同时也只好采取降低输出结果精度、减少输出物理量、降低分辨率和输出的时间步、甚至降低数据的维度等措施。事实上，数据存储系统不断为系统替换和增加更多的硬件资源外，还可以在数据输出时进行约减和压缩。大规模科学数据约减的目的是在保留模拟结果大部分信息的同时不影响对物理变化过程理解的前提下，减少数据规模；而压缩的目的是针对约减后的数据，利用无损或有损压缩算法，进一步减少存储空间(如图1所示)。前者面向的是数据外在冗余度，后者面向的是数据内在冗余度。目前已经发表了多种数据约减方法，Lu等将这些方法总结为三类2：抽样方法、变换方法和分裂方法，但是，对于非平稳、数据相关性强、变化复杂的科学数据而言，这些方法仍有其局限性。Li等介绍了一种从大数据集中抽取与其具有类似概率分布的数据子集的方法3。它通过极小化函数来抽取与原数据集拟合的子集。该方法是一种计算密集性方法，不适用于海量和高维科学数据。利用专家知识，Jin等人利用一些“特征”来抽取具有特殊模式的数据4，从而达到数据约减的目的，它是一种基于专家知识进行约减的方法，没有普适性。Antonio介绍了基于边际效用概念的网络流量监测数据的约减方法5，并利用均值、方差等统计量评估数据约减效果。对于非平稳数据，该方法具有较大的局限性。小波理论可以实现对数据的多分辨逼近，具有很大的灵活性。通过选取阈值l，可以保留信号或者数据的大部分能量或者信息，从而实现数据约减过程。对于约减后的科学数据，仍然具有内在冗余度，进行压缩存储可以进一步提高存储效率。例如，基于整型数差分的科学数据压缩方法6，其主要思想是首先将浮点数通过内存拷贝转换成整型数，然后用高阶差分替换原数据，最后进行熵编码。Ibarria提出了基于Lorenzo外插预测的压缩方法7。单纯依赖数据压缩，压缩时间开销与压缩效率不能同时取得满意的效果。在精度容许范围内进行数据约减，可以大大提高压缩性能。本文基于文献9，对科学数据进行离散小波变换，通过平衡能量逼近误差与约减数据量间的关系，极小化目标函数来优化阈值参数，从而约减大规模科学数据，并对约减后的数据使用deflate压缩算法进行压缩存储。最后，使用等离子体物理数值模拟数据进行了测试。实验表明，本文所提方法大大提高了大规模科学数据的存储效率，对科学数据管理工作具有实际应用价值。图1 大规模科学数据的约减与压缩流程2 小波变换基本理论信号处理和近代数学、物理学的一个重要技术手段就是根据需要，把信号(或函数、场) 分解为某种函数系的线性叠加12，即(1)而小波变换则是在小波函数系下的分解9。称满足如下(2)的函数为小波函数。通过变化尺度因子s与平移因子u，可以得到一族小波函数系。尺度函数的定义类似，但是。通过分别选取尺度函数与小波函数，可以得到的函数逼近式(3)其中，刻画了的低频信息，刻画了的高频信息。考察信号的时间序列抽样 ，则y的离散小波变换定义为其中，W是的离散小波变换矩阵，由式（3），有，利用小波逆变换，可以重构原信号3 数据约减在信号或者数据处理过程中，线性数值逼近的表示形式为，对于小波变换来说，取小波基底。在数据约减过程中，根据容许误差界或者经验决定M的大小，对进行逼近，从而达到约减数据量的目的。下面，从能量的观点讨论基于小波变换的科学数据约减方法。定义1 信号的能量定义为，相应地，信号的抽样数据的能量定义为。下述定理给出了利用前M个较大小波系数重构原信号的逼近误差的上界。定理1 考察信号，约减后的信号的逼近误差的上界为的选取是约减数据量和数值逼近精度的关键，文献9给出了一个数据约减目标函数（式4），优化的选取。目标函数通过平衡相对能量误差与数据约减数据量之间的关系，确定小波系数选取的硬阈值。(4)其中，表示选取的小波系数的示性函数，即当时，；当时，。为选择的小波系数个数。为偏好因子，可以根据用户对约减数据量和数据精度之间的偏好设定，通常选取。通过搜索值来极小化目标函数。定理2 对于离散小波变换系数 ,当时，目标函数取极小值。得到小波系数阈值后，采用硬阈值法对小波系数进行约减，然后再进行压缩。硬阈值法4 数据压缩数据压缩算法的基本原理是通过某种算法把数据低效（长的）表达方式改为高效（短的）表达方式，把输入数据流（原始数据）转变为另一种较小的数据流（压缩数据）的过程，从而去除了数据中的冗余，有效地压缩了数据大小。压缩算法主要包括无损压缩和有损压缩。无损压缩也通常称为熵编码，它的理论基础是仙农创立的信息理论。有损压缩是指压缩和解压缩过程中会产生一定精度损失，但是相比无损压缩，有损压缩具有压缩效率高的优点。压缩算法的压缩比和压缩速度是评价压缩算法（及其函数库）最重要的标准。关于压缩算法性能的比较，已有很多人做过此类的工作，比较著名的有ACT (archive compression test)。在一些应用中，对数据的精度没有苛刻的要求，因此，可以用有损压缩替代无损压缩。本文中使用的科学数据压缩方法有损压缩，它包括量化和熵编码两个步骤。对小波系数量化即因子与小波系数乘积（其中n表示为小波系数分配的比特位数），然后将乘积取整的过程。以表示小波系数，表示量化值，量化过程可以由式（5）表示。(5)熵编码本文使用了deflate算法。5 结果评估对于数据约减过程与有损压缩对科学数据的影响，需要进行定性和定量的分析。定性分析包括将原始数据的可视化结果与约减和有损压缩后的结果进行比对，判断是否影响对物理变化过程的理解。定量分析主要从误差度量的角度进行分析。定量分析主要使用信噪比与相对能量误差概念。1) 信噪比(SNR)其中，。2) 相对能量误差(RE)其中，。6 测试实验以三维等离子体粒子模拟的计算数据(网格规模为8020080，2 000个时间步)为例给出实验结果，以它为例有较强的实际意义。本文选取4个时间步的数据测试约减小波系数比例与压缩比(CR)及误差度量之间的关系，见表1。表1 约减数据量、误差度量、压缩比之间的关系时间步能量SNRRE小波系数比例CR100122.70.00132619.6%33.2%65300175.60.00893121.1%.44.3%59600289.20.01563818.4%57.8%521 000361.50.01984715.2%79.4%48下面以第1 000个时间步的数据为例，定性地考察约减的小波系数比例和压缩比与可视化效果情况。图2(a)给出的是第1 000个时间步激光入射方向的一行原始数据。图2(b)给出的是由80小波系数重构得到的数据，图2(c)给出的是由50小波系数重构得到的数据，图2(d)给出的是由20小波系数重构得到的数据。(a) 原始数据(b) 80小波系数重构(c) 50小波系数重构(d) 20小波系数重构图2 不同比例小波系数重构效果图3(a)图3(d)分别给出的是由100、80、50、20的小波系数进行数据重构，然后进行可视化，得到等值线效果切片图。 (a) 原始数据 (b) 80%小波系数重构 (c) 50%小波系数重构 (d) 20%小波系数重构图3 等值线图可视化效果从可视化图可以看出，尽管在传输20数据量的小波系数的情况下，仍对我们感兴趣区域(即激光入射部分)的可视化效果影响不大。表2给出了小波系数约减数据量和压缩比之间的关系。表2 第1 000个时间步的约减数据量与压缩比之间的关系小波系数比例205080100压缩比615248437 结束语本文针对大规模科学数据的存储问题，借助于小波分析理论，实现了约减与压缩存储，减少了数据存储空间，同时进行了误差分析。本文工作给科研人员提供了对GB或者TB量级规模的数据场进行结果分析、评估和可视化的高效辅助手段。本文工作的适用对象是结构离散网格数据，下一步的工作可以扩展到非结构离散网格数据。参考文献：1陈虹,张侠,夏芳等. 三维等离子体粒子模拟程序的数据模型和I/O性能改进J. 计算机工程与应用. 2004,40(9):104-107.CHEN H,ZHANG X,XIA F, et al. A data model and I/O performance improvement for 3D plasma simulat- ions with particleJ.Computer Engineering and Applications, 2004,40(9):104-107.2LU J C. Data Mining for Design and Manufacturi- ng Methods and ApplicationsM. New York: Kluwer Academic Publishers,2001. 255-288.3LI X B. Data reduction via adaptive samplingJ. Communications in Information and Systems, 2002,2(1):53-68.4JIN J, SHI J. Feature preserving data compression of stamping tonnage information using waveletsJ.Technometrics,1999,41(4): 327-339.5ANTONIO P. Entropy based reduction of traffic dataJ.IEEE Communication Letters,2007,11- (2):191-193.6ENGELSON V, FRITZSON D. Lossless compression of high volume data from simulationA. Data Compression ConferenceC. Snowbird, Utah, 2000.754-765.7IBARRIA L,LINDSTROMY P,ROSSIGNAC J. Out of core compression and decompression of large n-dimensional scalar fieldsJ. Eurographics, 2003,22(3):256-262.8吴国清，陈虹，徐小文，基于最优内插预测的科学数据压缩方法J.计算机科学，2007,34(8):15-17.WU G Q，CHEN H,XU X W. Scientific data compress- ion method based on optimized interpolate predictionJ.Computer Science,2007, 34(8): 15-17.9MYONG K