无损数据压缩研究.ppt

LZW编码举例 见书本P60的示例 统计编码四 LZW编码的特点 LZW码能有效利用字符出现频率冗余度进行压缩，且字典是自适应生成的。 LZW压缩技术对于可预测性不大的数据具有较好的处理效果，常用于GIF格式的图像压缩，其平均压缩比在2:1以上，最高压缩比可达到3:1。 对于数据流中连续重复出现的字节和字串，LZW压缩技术具有很高的压缩比。 除了用于图像数据处理以外，LZW压缩技术还被用于文本程序等数据压缩领域。 LZW压缩技术有很多变体，例如常见的ARC、RKARC、PKZIP高效压缩程序。 对于任意宽度和像素位长度的图像，都具有稳定的压缩过程。压缩和解压缩速度较快。 对机器硬件条件要求不高，在 Intel 80386的计算机上即可进行压缩和解压缩。 统计编码四 练习 假设对信源: X: X1 X2 X3 X4 X5 X6 0.25 0.25 0.2 0.15 0.1 0.05 进行Huffman 编码，写出码字，码长及平均码长。 无损压缩编码实验 时间： 截止 2015.3.20 地点： kangqiju@ 实验内容： 任选一种无损编码方式，通过C++编程实现。 要求：1) 字符串的输入是手工输入的； 2) 在屏幕上显示编码结果； 3) 以学号+姓名 作为文件夹的名称，其中包括实验报告和源程序，打包压缩发送。 lb = log2 * * * * 房间里的两个人在聊天，在这个聊天的过程中，背景（房间和家具）一直是相同的，同时也没有移动，而且是同样的两个人在聊天，只有动作和位置的变化。 * * * * * * * * * * * LZW压缩算法是Unisys的专利,有效期到2003年 在1984年由Terry Welch作为Abraham Lempel与Jacob Ziv在1978年发表的LZ78的改进版本而发表的 蓝波-立夫-卫曲编码法（Lempel-Ziv-Welch，缩写LZW），是亚伯拉罕·蓝波、杰可布·立夫与泰瑞·卫曲共同提出的一种无损数据压缩算法。 它在1984年由泰瑞·卫曲改良亚伯拉罕·蓝与杰可布·立夫在1978年发表的LZ78的版本而来（主要是基于蓝波、立夫的压缩概念，设计出一套具有可逆推的逻辑程序）。 与霍夫曼编码相比，蓝波-立夫-卫曲编码法被视作将不同长度字串以固定长的码编辑（霍夫曼编码将固定长度字符用不同长度的码编辑）。其优点在于此方法只需储存一个相当小的表格，即可储存资料还原时相对应的值，所以所需成本相对地低；然而，这种算法的设计着重在实现的速度，由于它并没有对数据做任何分析，所以并不一定是最好的算法 是指使用压缩后的数据进行重构，重构后的数据与原来的数据有所不同，但不影响人对原始资料表达的信息造成误解。 典型的算法有： 混合编码的JPEG标准，预测编码，变换编码等。 特点：压缩比高，为几十到几百倍 一般用于图像，声音，视频压缩。 2.3数据冗余的类型与压缩方法分类 ● 有损压缩 数据压缩的方法 统计编码 预测编码 变换编码 混合编码 分析合成编码 2.4常用数据压缩方法的基本原理 根据消息出现概率的分布特性而进行的压缩编码。 Huffman编码 算术编码 行程编码 词典编码 2.4常用数据压缩方法的基本原理 ● 统计编码 Huffman编码 统计独立信源，能达到最小平均码长的编码方法。编码效率高。 霍夫曼(D.A. Huffman)在1952年提出和描述的“从下到上”的熵编码方法。 根据给定数据集中各元素所出现的频率来压缩数据的一种统计压缩编码方法。这些元素(如字母)出现的次数越多，其编码的位数就越少。 广泛用在JPEG, MPEG, H.26X等各种信息编码标准中。 统计编码一 Huffman编码 编码步骤：　　(1) 初始化，根据符号概率的大小按由大到小顺序对符号进行排序。　　(2) 把概率最小的两个符号组成一个节点。　　(3) 重复步骤（2）。　　(4) 从根节点开始到相应于每个符号的“树叶”，从上到下标上“0”(上枝)或者“1”(下枝)，至于哪个为“1”哪个为“0”则无关紧要，最后的结果仅仅是分配的代码不同，而代码的平均长度是相同的。　　(5) 从根节点开始顺着树枝到每个叶子分别写出每个符号的代码。 统计编码一 霍夫曼编码举例 现有一个由5个不同符号组成的30个符号的字符串：BABACACADADABBCBABEBEDDABEEEBB 计算 (1) 该字符串的霍夫曼码 (2) 该字符