压缩存储（精选4篇）
压缩存储 篇1
摘要：对于图的同构判定问题、Ramsey理论、计算Folkman数等图论的研究方向, 研究人员通常需要用计算机程序生成并处理大量的简单无向图。为了节省内存和外存空间、提高程序运行速度, 应该对图进行压缩存储。文中对目前研究中广泛采用的简单无向图graph6存储格式进行了介绍, 并给出了将图的邻接表存储格式转换为graph6存储格式的程序片段。
关键词：简单无向图,压缩存储,graph6,图存储格式的转换
0 引言
多年来, 计算机辅助计算和证明的研究方法一直受到图论研究学者的关注。目前, 在图的同构判定、图的自同构群计算等图论研究领域, 由Brendan D.Mc Kay在澳大利亚国立大学 (The Australian National University) 开发的nauty软件包因开发时间长、比较成熟而获得了广泛的应用, 软件包下载和完整手册参见文献[1]。nauty软件包被应用在图论研究的许多领域, 例如图的同构判定问题、Ramsey数以及Folkman数的计算等[2]。
用nauty软件包进行图论计算, 通常都需要生成和处理大量的图。如何减少这些图所占用的内外存空间、快速读写图数据、提高nauty的运算速度就成为研究中必须解决的问题。为了配合nauty的使用, Mc Kay专门开发了graph6和sparse6两种关于简单无向图的压缩存储格式。
简单无向图是指没有环和多重边的无向图。用G表示一个简单无向图, 用V (G) 和E (G) 分别表示图G的顶点集和边集。在本文剩余部分, 除非特殊指明, 否则图都是指简单无向图。本文中关于图论的术语和符号遵从文献[3]。
1 graph6的编码规则
用graph6格式存储图的文件是一个纯文本文件, 通常使用.g6作为文件的扩展名。*.g6文件既可以带文件头>>graph6<<, 也可以不带该文件头, 也就是说, 文件头是可选的。规定文件头后无行结束符, 在Windows操作系统中, 行结束符为rn;在类UNIX系统中, 行结束符为n。graph6存储格式用一行ASCII码串来表示一个图。在*.g6文件中, 除了文件头和行结束符, 每个字节作为一个无符号数都在范围63到126内。因此, 这些字节都是可打印的ASCII码字符。graph6格式的详细定义参见文献[1]。
1.1 函数R (x) 和N (n) 的定义
函数R (x) 的定义:
graph6格式要用到位向量的概念。一个长度为k的位向量x是一个由0和1组成二进制位串, 例如:x=1000101100011100, 此时k=16。对x进行如下三步变换:
(1) 在位向量的右边填充最少数目个0 (或者不填充, 如果k为6的倍数) 使得k为6的倍数, 接上例得到:x=100010110001110000, 此时k=18。
(2) 然后将该k=18的位矢量按每6个一组进行分组, 接上例得到:x=100010 110001 110000。
(3) 最后将每一组加上63, 并看成从高位到低位存储的无符号整数, 接上例得到一串无符号整数:97 112 111 (十进制表示) 。
这一串无符号整数全部落在63到126的范围内, 每个数都存入一个字节, 这样所需要的字节总数为ceiling (k/6) , 也就是k/6向上取整。函数R (x) 就表示经过上面三步变换得到的字节串。
函数N (n) 的定义:
n为一个0到68719476735 (2^36-1) 范围内的整数。
(1) 如果0≤n≤62, 定义N (n) 为单字节无符号整数n+63。
(2) 如果63≤n≤258047, 定义N (n) 为四个字节的无符号整数串:126R (x) , 这里x是n从高位到低位存储的18个位的二进制形式。
(3) 如果258048≤n≤68719476735, 定义N (n) 为八个字节的无符号整数串:N (n) =126 126 R (x) , 这里x是n从高位到低位存储的36个位的二进制形式。举例如下:
1.2 上三角阵的压缩编码
假设G有n个顶点, 顶点的标号从0到n-1。图的邻接矩阵是由n的平方个0和1组成的方阵, 该方阵的主对角线全为0且关于主对角线对称。因此, 只需存储不包括主对角线的上三角阵即可包含图的所有信息, 所需位矢量的长度为1+2+…+ (n-1) =n (n-1) /2。
graph6格式对上三角阵的压缩编码为先列后行, 列从小标号列到大标号列, 每列从小标号行到大标号行的顺序。图1展示了对4个顶点的图进行编码的顺序。第一行和第一列分别是邻接矩阵的列标号和行标号, 上三角阵 (不包括主对角线) 中的数字1到6表示了上三角阵中对应的0或1项的编码顺序。对于一般的n, 在顶点标号从0到n-1的约定下, 位向量x由上三角阵中对应位置 (0, 1) , (0, 2) , (1, 2) , (0, 3) , (1, 3) , (2, 3) , …, (n-2, n-1) 的0或1的项组成。得到上三角阵的位向量x后, 图的graph6格式编码就定义为N (n) R (x) 。
2 邻接表到graph6的格式转换
关于图的非压缩存储格式, 比较常用的有邻接矩阵和邻接表存储格式。邻接矩阵格式适合边数比较多的稠密图 (dense graph) , 而邻接表格式适合边数比较少的稀疏图 (sparse graph) , 但当图的顶点数较少时, 这两种格式占用空间的大小和对程序运行效率的影响差别不大[4]。
图的邻接表存储格式, 在外存中一般来说也是一个纯文本文件, 存储指定顶点数目的若干个图。每个图由三部分构成:图的序号占用一行;图的度序列占用一行;邻接表数据占用n行 (n为图的顶点数目) 。每行邻接表数据都以图的顶点标号开始, 后面是该标号顶点邻接的所有顶点, 按照一种指定的顺序排列。图2展示了一个简单无向图的邻接表存储格式的文本, 该图有5个顶点, 度序列采用相邻两个数值相减的方式给出。
2.1 程序片段
将邻接表转换为邻接矩阵并对上三角阵进行压缩编码:
2.2 解释说明
上面给出了从邻接表格式转换为graph6格式的C语言程序ALG6的程序片段1。该程序片段首先逐行解析邻接表数据填充邻接矩阵b Matrix的对应项, 然后对b Matrix的上三角阵按graph6格式进行编码, 最后将b Matrix的上三角阵按照graph6格式的编码顺序写入到p UT指向的字符数组中。
b Matrix是一个元素为布尔类型的二维数组, 两个维数都为图的顶点数目vn, 用来存储图的邻接矩阵。程序片段中的row和col表示邻接矩阵的行和列的索引, 字符指针p Line指向每行读取的文本, ar Ze、ar Get和sz Get都是用来解析邻接表数据的变量, 解析文本行的工作主要由C语言的库函数strtok () 完成, 将文本行中以空格或制表符作为分隔符的顶点标号数字提取出来。
上三角阵按照graph6格式的编码顺序写入到字符数组p UT, TRUE对应1, FALSE对应0。这个字符数组p UT就是上三角阵的位向量。对vn调用函数N (n) , 对p UT调用R (x) , 再将两个结果字符串拼接起来, 就得到了图的graph6字符串N (vn) R (p UT) 。
3 实验结果
编写了一个转换单个图的程序ALG6, 用于将图从邻接表格式转换为graph6格式。该程序可以很容易地修改为成批转换图的程序。ALG6是在Mac OS X 10.6.8操作系统下用C语言开发的, 用gcc 4.2.1编译。用ALG6程序进行了若干格式转换实验, 程序运行结果正确且运行稳定, 速度满足要求。
3.1 程序运行结果
对于程序的运行结果, 这里给出一个稍复杂的实例。考虑11个顶点的圈C11, 其补图为一个8-正则图。该图的邻接表格式文本如图3所示。
运行ALG6程序算得该图的graph6字符串为J~|x{~Nx~f_。先用nauty软件包中的geng程序生成C11, 命令行为geng-c-d2-D2 11 11:11C11.g6, 然后用complg程序求C11的补图, 命令行为complg C11.g6 C11_Complg.g6, complg的运算结果与ALG6的运算结果一致。C11的补图如图4所示。
3.2 空间占用比较
将ALG6程序的算法应用在计算不含C4圈的极图的程序Ex_C4中, 并用Ex_C4计算得到所有顶点数小于等于17的不含C4圈的极图。Ex_C4程序同时向外存输出邻接表和graph6两种存储格式的结果, 两种存储格式所表示的图是完全一样的, 以此来对外存空间占用的情况进行比较。
表1给出了顶点数大于等于13且小于等于17的所有不含C4圈的图的两种不同格式的空间占用情况的统计结果。表格中的n表示图的顶点个数, zn表示对应n个顶点的不含C4的极图的个数, al表示含zn个图的邻接表格式文件的大小, g6表示含zn个图的graph6格式文件的大小。文件大小指其在NTFS文件系统中, 单位为k B。
4 结束语
简单无向图的传统存储方式, 除了邻接表还有邻接矩阵。Mckay开发的图的压缩存储格式, 除了graph6还有sparse6。这样从工作的完备性来讲, 一共应该开发8个格式转换程序, 才能实现全部4对不同格式的双向转换。这是未来要完成的工作。
另外从表1可以看出, 邻接表格式的外存占用大小至少是graph6格式的10倍, 这显示出graph6压缩存储格式的巨大优势, 根据graph6格式的编码算法, 实际上可以对这个压缩比值进行理论上的估算。鉴于graph6和sparse6格式在节省存储空间方面的优势, 应该在图论的计算机算法中广泛地运用。
参考文献
[1]Brendan D McKay, Adolfo Piperno.nauty and Traces User’s Guide (Version 2.5) [EB/OL].Software and complete manual available at http://cs.anu.edu.au/~bdm/nauty.
[2]Radziszowski S.Small Ramsey Numbers, Electronic Journal of Combinatorics, Dynamic Survey DS1, revision#13 (2011) , 84 pages[EB/OL].http://www.combinatorics.org.
[3][美]ary Chartrand, Ping Zhang.图论导引[M].范益政, 汪毅, 龚世才, 等译.北京:人民邮电出版社, 2007.
[4]严蔚敏, 吴伟民.数据结构 (C语言版) [M].北京:清华大学出版社, 2010.
压缩存储 篇2
大数据是目前人们关注的热点。XML (Extensible Markup Language) 作为一种简单、开放、可扩充的描述语言, 丰富扩展标记完全可以描述不同类型的数据。XML应用到各种领域的数据存储和交换, 解决了数据格式差异的障碍, 统一了信息交换过程的数据格式。XML是一种拥有很好应用前景的数据存储方式, 伴随着XML技术应用领域的不断扩大, XML出现的问题也越来越引起人们的关注。
随着数据量的增加, XML标记冗余也增加, 以至体积都大于相同数据内容的其它类型文档。随着XML文档在Web上应用的扩展, 其大小也会随之增加, 这实质上增加了数据的存储量、交换量及大量冗余的产生, 尤其是海量数据XML文档资料, 影响网络传输效率、内存消耗大。因此XML文档的体积问题成为了阻碍XML的因素。如果能够在服务器端传输前进行有效压缩, 就可以节省传输占用带宽和时间。
目前, 压缩算法和软件很多, 如典型的gzip和zip算法、LZW、Huffman、winzip、LSDX等, 这些用于文本文档、图像、视频文件等压缩, 但针对XML文档比较少, 如XMill、XMLPPM。XML压缩对于许多应用非常重要, 但没有基于语法的XML压缩技术, 也没有公开的XML压缩器。对XML进行压缩、存储之后传输, 逐渐成为学术界、商业软件开发商关注的问题。
本文通过研究压缩原理和关键算法, 提出一种针对XML文件格式的压缩存储方法。
1 相关压缩算法现状
LSDX编码是一种针对XML的前缀编码, 采用数字表示XML标签节点的层次关系, 字母表示节点的位置。LSDX编码表示方式:XN.Y, X是字母, 表示节点父节点;N是数字, 表示节点的层次;Y是字母, 表示节点也是父节点的子节点。前缀编码是一种支持节点频繁插入、删除、更新的方式[1]。
LZW压缩算法是一种新颖的压缩方法, 采用了一种先进的串表压缩, 将每个第一次出现的串放在一个串表中, 用一个数字来表示串, 压缩文件只存储数字, 不存储串, 如果这个字符串再次出现时, 即用表示它的数字代替, 从而使文件的压缩效率得到较大的提高。不管是在压缩还是在解压缩的过程中都能正确地建立这个串表, 压缩或解压缩完成后, 这个串表被丢弃[2]。
XMill是第一个针对XML文件数据的压缩方法, 它的基本思路是:首先将结构信息与数据项分离, 并在利用GZip压缩工具进行数据压缩之前对文档进行预压缩。为了达到优化XML文档压缩的目的, 预压缩需要完成两个主要工作: (1) 从文档数据中分离出结构信息; (2) 将具有相关语义的数据项划分组别。
为了完成第一个预压缩步骤, XMill需采用字典编码方法将标签和属性名存储到一个字典中, 在文档中将这些标签和属性名用所在字典中的索引代替, 从而完成压缩文档的基本结构框架, 再将这一基本结构框架存入一个“结构容器”中;接着, 该算法会应用近似匹配的方法决定数据项所应归属的“数据容器”[3]。例如, 可以将文字类和数字类数据分开存储, 在压缩阶段, 应用GZip压缩工具对各容器进行分别压缩, 并在输出前将这些数据单元连接成一个输出文件。XMill算法具有很好的压缩性能, 但用户访问被压缩的XML文档前必须解压缩整个文档, 因此, 该算法没有得到广泛应用, 但其思想却影响了其后的一些XML压缩算法。XMLPPM算法是一种多层次建模方法, 可以解决人工干预的缺陷, 但是压缩速度较慢[4]。
2 压缩与存储算法原理
2.1 压缩算法
计算机数据存在两种形式的重复:短语形式的重复、单字节的重复。
(1) 短语形式重复。一个字节有256 (0-255) 种可能的取值, n个字节有255n种可能的情况, 以指数方式增长。各种类型的数据都有出现重复的可能, 但是, 只有一部分字符信息重复出现, 如:语法关键字会重复出现, 进行短语压缩后, 短语式重复的情况可以消除。
(2) 单字节重复。一个字节取值情况只有256种, 所以字节重复是必然存在的。其中一些字节出现比较频繁, 另一些可能很少用到, 其中字母和数字则使用较多。字母之间使用频率也是不一样的, 字母e的使用概率最高, 所以, 给256种字节取值重新编码, 使出现较多的字节使用较短的编码, 出现较少的字节使用较长的编码。通过这种方法, 文件的总长度减少, 从而达到压缩的效果。
Huffman原理包括树和编码。Huffman树又称最优二叉树, 是一种带权路径长度最短的二叉树。树的带权路径长度WPL, 是树中所有的叶结点的权值与其到根结点的路径长度的积, 根结点为0层, 叶结点到根结点的路径长度为叶结点的层数。树的带权路径长度总和为:
n个权值wi (i=1, 2, ...n) 构成一棵有n个叶子结点的二叉树, 相应的叶结点路径长度为li (i=1, 2, ...n) , 可以保证Huffman树的WPL是最小的。
Huffman编码是一种变长编码, 即前缀编码方式, 根据字符出现的概率来构造平均长度最短的编码。
本文基于Huffman原理, 结合XML文档的特点, 利用Huffman编码。在编码过程中, 编码长度严格按照标签名、属性名出现频率的大小逆序排列, Huffman编码后得到的编码, 字符串出现的频率不同, 对应编码长度也不同。这种变长的编码把XML的标签名、属性名等重复率高的转化为最短编码, 把结构冗余部分降到最低[5]。
2.2 存储算法
由于生成的Huffman编码都是0或1组成, 可以把编码按照二进制处理, 8位转化1个字节, 不够8位的编码补齐, 然后转换为对应的Ascii字符, 保存这个字符。所以, 可能原来8位的编码, 现在存储只占一个字符的空间。
假设编码之后:item:1001 country:1011
存储处理如图1所示。
如上所述, 这样就把编码按真正的二进制编码处理了, 把item或countruy字符串变为1个字符, 即表示二进制编码的字符。值得注意的是补位数不能丢掉, 这样才能解码还原, 所以必须再与补位码一起保存。这样存储方式, 可以大大减少存储空间。
3 编码实现与测试
本文采用C++语言实现算法实验平台, 部分核心代码如下:
实验测试过程:从各种常用软件 (酷我音乐、阅读软件、游戏客户端) 中获取XML文件做为测试数据, 通过实验平台进行测试, 如图2所示。以压缩率为指标, 压缩率
即压缩文件大小与原文件大小之比, 压缩率越小, 压缩效果越好。
本文经过对大量XML文件的实验测试和分析, 列出部分文件经过算法压缩之后与原文件的大小对比 (见表1) , 压缩率值的分布约在50%左右 (见图3) , 并且随着原文件大小的增加, 冗余增加, 压缩率越低, 压缩效果越好。
4 结语
本文以XML文档结构为研究对象, 结合Huffman树算法, 形成了一个针对XML不断重复的标签、属性进行字典编码压缩的方法, 成功实现了压缩和存储XML文件。通过编码实现和实验分析, 验证了XML压缩算法的可行性。如: (1) 本文利用字典编码思想, 针对标签值进行字符串操作, 进一步分解成单词操作, 提高了压缩效果; (2) 本文采用先读取压缩文件, 然后建立一棵中间树, 再构建对应XML文档树, 最后保存为新的XML文档的解压缩过程, 其中省略中间树的可行性有待研究, 如果能够减少这一步骤, 可以提高压缩时间。
摘要：XML (可扩展标记语言) 是一种广泛应用于网络的数据存储交换格式, 采用通用标记语言, 具有良好的数据存储和分析能力, 其缺点是XML文档存在结构冗余。伴随着XML在网络上应用的扩展, XML压缩成为目前关注的研究问题。从压缩、存储两方面研究了XML文件的压缩算法。根据重复出现权重, 基于Huffman树生成对应的编码 (0、1数字表示) , 减少XML文件结构重复导致的冗余。存储文件时, 把n位编码 (二进制) 转化为一个ASCII字符存储 (n不是8倍数即补位) , 节省了存储空间。大量实验证明:算法具有良好的可行性和研究价值。
关键词：XML,Huffman树,压缩算法,存储,编码
参考文献
[1]刘先锋.一种分数前缀XML编码方案[J].计算机工程, 2012, 38 (12) :29-31.
[2]王平.LZW无损压缩算法的实现与研究[J].上海交通大学学报, 2002, 28 (7) :98-100.
[3]仇睿恒.XTrim——一种基于XMLSchema和微型数据块优化的XML压缩方法[J].北京大学学报, 2010, 46 (5) :771-774.
[4]祝园园.XML数据压缩技术的研究[D].哈尔滨:哈尔滨工业大学, 2009.
压缩存储 篇3
基于上述需求,开发了一套基于双FPGA+ARM架构的独立式多分辨率VGA/GVI压缩和存储系统。该系统支持DVI/VGA接口输入,并支持SVGA、XGA、SXGA、UXGA、1080p等任意分辨率的图像压缩和存储,同时能做到音视频同步。另外,该系统采用了双FPGA+ARM架构,提高了系统的灵活性及平台可升级性,拓宽了其应用场合。
本文主要介绍独立式多分辨率VGA/DVI图像压缩存储系统的核心架构,并给出系统的性能。
1 系统架构与实现
该系统的整体架构如图1所示。系统采用了双FPGA+ARM的架构,主要包括四部分:图像前端接口电路、预处理模块、图像压缩模块和管理模块。它同时支持VGA和DVI图像源输入,图像源的缓存或部分运算的中间结果通过Flash和外部存储器实现。这里主要介绍该系统中涉及到前端预处理模块和图像压缩核心模块。
图1中左面一片FPGA主要完成前端预处理,如分辨率检测、色彩转换和图像分析等功能;右面一片FPGA主要用来实现图像实时压缩;ARM对系统进行管理,如压缩后码流管理、网络管理和音频录制等。
1.1 前端预处理模块
前端接口电路采用AD9888作为前端的视频模数转换器,TI公司推出的TFP403作为DVI接收芯片。前端预处理模块采用Xilinx公司的Virtex4[2]系列的FPGA(XC4VLX40),它主要完成的功能是分辨率的检测和色彩空间转换等,如图2所示。
1.1.1 分辨率检测
对于标准的VGA接口,不同分辨率下其HSYNC与VSYNC时序不同,系统设计时用一个单独的模块来检测输入端的分辨率。该模块可以通过检测两个相邻VSYNC上升沿间的HSYNC数目来识别VGA信号的分辨率,然后将检测到的分辨率参数送给后端的图像压缩模块,让系统根据对应参数来配置图像采集和图像压缩。
1.1.2 色彩转换
标准的VGA接口输出为RGB信号,在进行压缩之前,先对图像进行色彩空间转换,将RGB信号转换为YUV信号。色彩空间转换公式为:
系统实现时采用4:2:2采样模式,FPGA采用定点化处理后,将得到的Y和UV分量送给后端的编码模块进行编码。
1.2 图像压缩部分
在系统设计时,考虑到不同分辨率的图像压缩和后续功能扩展,需要采用硬件资源丰富的FPGA,后端模块采用Xilinx公司的Virtex4系列的FPGA(XC4VLX100)。图像压缩的核心架构如图3所示,它主要涉及图像缓存、图像压缩和码流缓存三部分。
1.2.1 图像缓存模块
为了提高系统的处理速度和数据吞吐效率,图像采集模块中采用图4所示的“乒乓操作”缓存图像,即把一帧图像的Y和UV分量缓存到片外的SDRAM1中,同时,系统会从SDRAM2读取另一帧已经缓存的图像到后端的图像压缩模块。这样图像缓存和压缩可以并行处理,提高系统的压缩效率。
系统设计时采用Micron公司16 MB的SDRAM[3],它包含了4个bank。其中,bank0与bank1用来缓存Y分量,bank2与bank3用来缓存UV分量,为了提高读写SDRAM的效率,采用burst读写数据方式,可以减少仲裁操作。
1.2.2 图像并行压缩模块
在系统算法设计时,图像变换采用了基于离散小波变换的空间推举算法(SCLA[4]),相对常见的离散小波变换(DWT),SCLA算法的行与列变换同时进行,乘法次数最少,且重建图像的PSNR值更高。编码算法采用改进的无链表零树编码算法(SLC),它融合了多层次零树编码算法(SPIHT[5])和无链表零树编码(LZC[6])的思想,在性能上逼近SPIHT,但更易于硬件实现。
系统在实现架构上采用了图3所示的双通道并行压缩架构,即Y和UV分量的小波变换和编码并行进行,极大地提高了系统的并行度和压缩效率。兼顾数据读取效率和内存考虑,本系统设计时采用了片外SDRAM和片内SRAM结合的方法来缓存小波系数,所以小波变换和编码模块主要由FPGA和2块片外SDRAM协同完成。SCLA算法采用9/7小波的五层分解,其中SDRAM3用来缓存Y通道分解过程中产生的部分小波系数,SDRAM4用来缓存UV通道分解过程中产生的部分小波系数,向SDRAM中读写数据时仍然采用burst方式。SLC算法以一棵小波树为基本单元,且压缩比可自由控制,完成一帧图像所有小波树的编码。
1.2.3 码流缓存模块
图3中Y通道和UV通道编码后的码流,需要合理的码流管理机制。在此,为了提高系统的吞吐效率,压缩后的码流缓存也采用2片SDRAM进行“乒乓操作”,即向SDRAM5写一帧码流时,从SDRAM6中读取前一帧压缩后的码流;同理,向SDRAM6写一帧码流时,同时从SDRAM5中读取前一帧缓存的码流,原理与图4类似。
2 实验结果与性能
该系统的电路板采用10层板制作工艺,电路板大小30.8 cm×16.7 cm。测试结果表明,当系统工作频率为100 MHz时,可以对分辨率1 280×1 024的图像进行实时压缩(约25帧/s),对分辨率1 600×1 200的图像压缩速率为17帧/s,同时也支持其他更高分辨率的压缩。
本系统对分辨率为1 600×1 200的计算机屏幕的PPT文档界面操作过程进行了测试,实验结果表明其压缩比约为25倍,重建PSNR值约为38 dB,
近年来,视频图像的压缩和存储在信息处理和安防监控等领域起着重要作用。鉴于市场上大多数图像压缩系统很难支持多种分辨率和高分辨率的实时压缩,本文设计了一款双FPGA+ARM架构的独立式多分辨率VGA/DVI图像压缩存储系统。该系统能接收VGA/DVI接口输入,支持SVGA、XGA、SXGA、UXGA、1080p等任意分辨率的连续压缩和存储,并能实现音视频同步。在正常工作频率100 MHz时,可以对SXGA(1 280×1 024的图像进行实时压缩(25帧/s),对UXGA(1 600×1 200)的图像压缩为17帧/s,且图像重建后的PSNR值要优于JPEG标准,压缩性能与JPEG2000标准近似。另外,该系统设计时采用双FPGA+ARM架构,提高了系统的灵活性和平台可升级性,具有广阔的应用前景。
摘要：一种独立式多分辨率VGA/DVI压缩存储系统,该系统支持VGA/DVI输入,同时支持SV-GA、XGA、SXGA、UXGA、1080p等任意分辨率图像的连续压缩和存储。在100 MHz时钟频率下,系统可以对图像SXGA和UXGA实时压缩为(25帧/s)和(17帧/s)。实验表明,在不同码率下,系统的单帧图像压缩性能与JPEG2000标准近似,PSNR值优于JPEG标准。
关键词：小波变换,多分辨率,FPGA,图像压缩
参考文献
[1]Analog Devices Corporation.JEPG2000 Video CodecADV212[EB/OL].[2010-02-26].http://www.analog.com/static/imported-files/data_sheets/ADV212.pdf.
[2]Xilinx,Inc.Virtex-4 Family Overview[EB/OL].[2010-02-26].http://www.xilinx.com/support/documentation/data_sheets/ds112.pdf.
[3]Micron Technology,Inc.Synchronous DRAM[EB/OL].[2009-02-24].http://www.micron.com/search/result?txtSearch=MT48LC4M32B2.
[4]LIU Leibo,CHEN Ning,MENG Honying.A VLSI architectureof JPEG2000 encoder.IEEE Journal of Solid-StateCircuits,2004,39(11):2032-2040.
[5]SAID A,PEARLMAN W A.A new fast and efficient imagecodec based on set partitioning in hierarchical trees.IEEETrans.CVST,1996,6(3):243-250.
压缩存储 篇4
关键词：历史数据,XML,LZW算法,XPath
1 引言
历史数据是数据库中非常重要的组成部分, 它提供了大量的过程数据供日后进行查看或者数据挖掘。人员定位监控系统是基于无线传感网技术的监控平台, 由硬件设备和软件系统组成:前者包括电子标签、读写器等;后者是Web管理系统;主要应用于监狱、精神病医院等场所, 实现特殊人群监控, 防止意外发生。系统实施后, 虽然监控人员的活动空间和时间有限, 但如果不做数据处理, 也会导致系统处理速度下降, 甚至系统崩溃。
数据压缩是历史数据问题中的关键课题, 根据压缩粒度可分为无损压缩和有损压缩。LZ算法是一种基本的无损压缩算法, 由一系列压缩算法组成:LZ77 (顺序压缩通用算法) 、LZ78 (可变比率编码的独立序列算法) 、LZW算法等等。
历史数据导出的文件存储格式有很多种, 其中包括XML文件。XML是一种自描述且可扩展的标记语言, 是一种独立于应用程序和供应商的描述及交换数据的方法。XML标签往往是重复的, 这虽然会造成冗余, 但却有利于进行数据压缩。虽然XML在数据量上并不具有优势, 但其在数据管理及开放性方面具有不可忽略的优势。XML有两种查询检索方式:XPath和XQuery。XPath是一种表达式语言, 提供定位和链接信息的通用语法和语义, 适合作为小型查询语言应用到实际项目中。
本文提出一种针对历史数据的数据库与XML文件相结合的解决方案, 包括XML数据结构设计、压缩算法应用、XML节点搜索方法、数据库与XML文件调度设计等。
2 方案设计
历史数据解决方案是人员定位系统的一部分, 但在处理逻辑上独立于软件平台。历史数据处理流程涉及到采集层、存储层和检索层, 按照这三个层次描述方案详细设计:
(1) 采集层实现采集数据的有损压缩。采集器通过定位算法计算出标签位置, 判断读写器信息是否变化、标签位置是否超出设定阈值, 确定数据是否入库。
(2) 数据存储层的设计思想。每天零点对数据库中将采集数据按照预定义的数据结构生成XML文件, 文档以前一天日期作为文件名;再通过LZW算法压缩生成lzw文件, 存储在服务器硬盘上并删除XML文件。XML文件数据结构按照数据库history表单结构设计, 如图1所示。
(3) 历史数据检索时, 当天数据通过数据库查询获得, 其他日期的数据首先确定本地是否存在已解压的XML文件, 存在则直接通过XPath路径查询节点信息, 不存在则先解压再从XML文件中查询所需数据, 返回给系统。解压生成的XML文件定期删除。
综上系统工作的具体流程如图2所示。
3 系统实现
系统通过SQL语句获取数据库history表数据集, 将数据与实体类History Dat和Record的属性相映射, 存放到List
XML文件生成使用dom4j API, 首先建立History Data根节点, 子节点循环递归实体并利用Method反射机制及invoke方法获得数值, 按设计定义为Element或Attribute或Text;最后XMLWriter按文件名地址规则输出XML文件。然后通过LZW压缩算法[6]压缩XML文件, 而在日后查询时则反向解压文件即可。
查询步骤包括两个部分:一是确定查询范围;二是XML文件内部查询。当天数据通过SQL语句访问数据库即可获得, 因此难点在于XML文件内部节点的XPath查询。以查询过去某天某标签为例可表明XML文件内部查询过程:
输入:待查询标签labelid, 起始时间s Time, 结束时间e Time
4 结束语
人员定位系统历史数据主要用于追溯发生异常事件时人员位置信息, 而异常情况并不是频繁发生, 因此本文解决方案在用户体验上与传统方法差距不大, 但在存储空间上有很大优势:数据库中1000多条数据占用的空间大小约300KB, 其中包含200KB的预留空间, 而压缩XML文件不到20KB。实验表明本文提出的历史数据解决方案能够解决存储压力问题。
参考文献
[1]文水英.实时数据库中历史数据压缩算法的研究[D].长沙:中南大学, 2008.
[2]孙克成.工业历史数据库数据压缩算法研究[D].西安:西安科技大学, 2011.
[3]汪陈应.XML数据编码与存储管理关键技术研究[D].天津:南开大学, 2010.
[4]阎红灿.面向Web的XML文档数据管理及分类检索技术研究[D].天津:天津大学, 2008.