引言

　　当今各种信息系统数据量越来越大如何更快、更多、更好地传输和存储数据成为数据信息处理首要问题而数据压缩技术则是解决这问题重要思路方法事实上从压缩软件SoftwareWINRAR到熟知MP3数据压缩技术早已应用于各个领域

　　2 数据压缩技术概述

　　本质上压缩数据是数据自身具有冗余性数据压缩是利用各种算法将数据冗余压缩到最小并尽可能地减少失真从而提高传输效率和节约存储空间

　　数据压缩技术般分为有损压缩和无损压缩无损压缩是指重构压缩数据(还原解压缩)而重构数据和原来数据完全相同该思路方法用于那些要求重构信号和原始信号完全致场合如文本数据、和特殊应用场合图像数据(如指纹图像、医学图像等)压缩这类算法压缩率较低般为1／2~1／5典型无损压缩算法有:Shanno-Fano编码、Huffman(哈夫曼)编码、算术编码、游程编码、LZW编码等而有损压缩是重构使用压缩后数据其重构数据和原来数据有所区别但不影响原始资料表达信息而压缩率则要大得多有损压缩广泛应用于语音、图像和视频数据压缩常用有损压缩算法有 PCM(脉冲编码调制)、预测编码、变换编码(离散余弦变换、小波变换等)、插值和外推(空域亚采样、时域亚采样、自适应)等新代数据压缩算法大多采用有损压缩例如矢量量化、子带编码、基于模型压缩、分形压缩和小波压缩等

　　3 常用数据无损压缩算法

　　3．1 游程编码

　　这种数据压缩思想:如果数据项d在输入流中连续出现n次则以单个对nd来替换连续出现n次数据项这n个连续出现数据项叫游程n这种数据压缩思路方法称游程编码(RLE)其实现流程如图1所示RLE算法具有实现简单压缩还原速度快等优点只需扫描次原始数据即可完成数据压缩其缺点是呆板适应性差区别文件格式压缩率波动大平均压缩率低实战表明RLE能够压缩复杂度不高原始点阵图像



　　图片看不清楚？请点击这里查看原图(大图)

　　3．2 基于字典编码技术LZW算法

　　LZW 算法是LZ78流行变形由Terrv Welch在1984年开发LZW算法首先将字母表中所有化到字典常用8位在输入任何数据前优先占用字典前256项 (0～255)LZW编码原理:编码器逐个输入并累积个串I每输入个则串接在I后面然后在字典中查找I；只要找到I该过程继续执行搜索直到在某点添加下个x导致搜索失败这意味着串I在字典中而Ix(x串接在I后)却不在此时编码器输出指向串字典指针；并在下个可用字典词条中存储串Ix；把串I预置为x其压缩流程如图2所示



　　图片看不清楚？请点击这里查看原图(大图)

　　字典前256项被占用因此字典指针必须高于8位由于LZW算法字典中串每次仅增加个因此要获得长串则需较长时间这样才能较好地压缩．IZW编码能够适应输入数据

　　LZW算法和其他算法相比具有自适应特点即可以根据压缩内容区别来建立区别字典以减少冗余度提高压缩比；并且解压时这个字典无需和压缩代码同时传送而是在解压过程中逐步建立和压缩时完全相同字典从而完整、准确地恢复被压缩内容因此LZW算法是种解码速度和压缩性能较好压缩算法

　　实现LZW算法需要考虑以下几点:

　　(1)字典建立(数据结构和字典大小) LZW字典数据结构是棵多叉树字典越大代替子串越多但应用中字典容量则受定限制要权衡利弊选择合适字典

　　(2)字典维护和更新 字典指针由哈希生成正确选择哈希非常重要这将影响执行效率正确哈希所产生重复值极少这样检索串所需比较次数也较少从而可有效提高代码执行效率

　　当字典满时字典维护和更新对压缩率也是至关重要可重新从状态建立字典；也可监测压缩率当压缩率变坏时全部或部分清除字典

　　(3)压缩数据代码长度压缩时输入数据般是8位但压缩后输出是转化串代码其中0～255为8位码256为9位码25l～512为10位码l 024为11位码解压则相反需要位操作因此输出可以从9位码开始随着字典内容增加码字也逐渐增加这样可提高执行效率但在译码时需考虑不等长码识别可通过设置标志位来解决

　　3．3 基于哈夫曼编码原理压缩算法

　　哈夫曼算法过程为:统计原始数据中各出现频率；所有按频率降序排列；建立哈夫曼树:将哈夫曼树存入结果数据；重新编码原始数据到结果数据哈夫曼算法实现流程如图3所示



　　哈夫曼算法实质是针对统计结果对本身重新编码而不是对重复或重复子串编码实用中．符号出现频率不能预知需要统计和编码两次处理所以速度较慢无法实用而自适应(或动态)哈夫曼算法取消了统计可在压缩数据时动态调整哈夫曼树这样可提高速度因此哈夫曼编码效率高运算速度快实现方式灵活



　　采用哈夫曼编码时需注意问题:

　　(1)哈夫曼码无保护功能译码时码串若无错就能正确译码；若码串有错应考虑增加编码提高可靠性

　　(2)哈夫曼码是可变长度码因此很难随意查找或压缩文件中间内容然后再译码这就需要在存储代码的前加以考虑

　　(3)哈夫曼树实现和更新思路方法对设计非常关键

　　3．4 基于算术编码压缩算法

　　算术编码压缩也是种根据出现概率重新编码压缩方案该思想和哈夫曼编码有些相似但哈夫曼编码每个需用整数个位表示而算术编码思路方法则无这限制它是将输入流视为整体进行编码虽然算术编码压缩率高．但运算复杂速度慢

　　4 结语

　　游程编码和LZW编码属于基于字典模型压缩算法而哈夫曼编码和算术编码属于基于统计模型压缩算法前者和原始数据排列次序有关而和其出现频率无关后者则正好相反这两类压缩思路方法算法思想各有所长相互补充许多压缩软件Software结合了这两类算法例如WINRAR就采用了字典编码和哈夫曼编码算法这几种数据无损压缩算法应用广泛设计人员可以根据具体应用中数据流特点来改进算法从而开发适用软硬件压缩器