零、常用无损数据压缩算法

字典算法

游程编码

基于字典编码技术的LZW算法

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

基于算术编码的压缩算法

一、LZW算法介绍

LZW（Lempel-Ziv-Welch Encoding）算法又叫“串表压缩算法”就是通过建立一个字符串表，用较短的代码来表示较长的字符串来实现数据的无损压缩。

LZW压缩算法是Unisys的专利，有效期到2003年，所以现在对它的使用已经没有限制了。

二、算法介绍

1、LZＷ算法的基本概念

LZW有三个重要对象：数据流（CharStream）、编码流（String Table）和编译表（String Table）。

（1）编码时，数据流是输入对象（数据序列），编码流就是输出对象（经过压缩运算的编码数据）；

（2）解码时，编码流是输入对象，数据流是输出对象；而编译表是在编码和解码时都需要借助的对象。

2、LZW压缩的基本原理

提取原始文本文件数据中的不同字符，基于这些字符创建一个编译表，然后用编译表中的字符的索引来替代原始数据中的相应字符，减少原始数据大小。注意：此处的编译表是根据原始数据动态创建的，解码时需要从已编码的数据中还原出原来的编译表。

 1. 初始状态，字典里只有所有的默认项，例如0->a，1->b，2->c。此时P和C都是空的。2. 读入新的字符C，与P合并形成字符串P+C。3. 在字典里查找P+C，如果:- P+C在字典里，P=P+C。- P+C不在字典里，将P的记号输出；在字典中为P+C建立一个记号映射；更新P=C。4. 返回步骤2重复，直至读完原字符串中所有字符。

3、LZW算法流程

（1）步骤一：开始时词典包含所有可能的根，当前前缀字符串P 和当前字符均为空；

（2）步骤二：读入新的字符C，与P合并形成字符串P+C；

（3）步骤三：判断P+C是否在字典中

如果“是”：

P = P + C；

返回步骤二；

如果“否”：

输出P的映射；

P = P+C ；

把前缀字符串P添加到字典，建立映射;

令P = C //(现在的P仅包含一个字符C);

（4）步骤四：判断码字流中是否还有码字要译

如果“是”：

返回步骤二；

如果“否”：
　　把代表当前前缀P的码字输出到码字流;
　　结束。

例如：

待压缩字符串：

abccbaaabc

初始时字典中包含所有的根：

初始	映射
a	1
b	2
c	3

在数据压缩过程中形成的字典：

Step	P	C	P+C	if P+C	Action	Output
1	–	a	a	y	p = a	–
2	a	b	ab	n	4<–ab, p = b	1
3	b	c	bc	n	5<–bc, p = c	2
4	c	b	cb	n	6<–cb, p = b	3
5	b	a	ba	n	7<–ba, p = a	2
6	a	a	aa	n	8<–aa, p = a	1
7	a	a	aa	y	p = aa	–
8	aa	b	aab	n	9<–aab,p = b	8
9	b	c	bc	y	p = bc	–
10	bc	–	bc	y	p = –	5