什么是"LZW 压缩"？

首先是lzw的概念 LZW(Lempel Ziv Welch)压缩编码是一种先进的数据压缩技术,属于无损压缩编码,该编码主要用于图像数据的压缩。对于简单图像和平滑且噪声小的信号源具有较高的压缩比,并且有较高的压缩和解压缩速度。

一个较大的文件经压缩后，产生了另一个较小容量的文件。而这个较小容量的文件，我们就叫它是这些较大容量的（可能一个或一个以上的文件）的压缩文件。而压缩此文件的过程称为文件压缩。

网络上有两种常见的压缩格式：一种是Zip，另一种是EXE。其中Zip的压缩文件可以通过WinZip这套解压缩工具进行解压缩，而EXE则是属于自解压文件，只要用鼠标双击这类下载后的文件图标(若您的Windows98属于Web风格，则只需按一下)，便可以自动解压缩。

因为EXE文件内含解压缩程序，因此会比Zip略大一些。若想充分考虑到文件容量的大小，其实Zip是一个较佳的选择。

压缩技术可分为通用无损数据压缩与有损压缩两大类，但不管是采用何种技术模型，其本质内容都是一样的，即都是通过某种特殊的编码方式将数据信息中存在的重复度、冗余度有效地降低，从而达到数据压缩的目的。

LZW（Lempel Ziv Welch）压缩编码是一种先进的数据压缩技术，属于无损压缩编码，该编码主要用于图像数据的压缩。对于简单图像和平滑且噪声小的信号源具有较高的压缩比，并且有较高的压缩和解压缩速度。

1977年，两位以色列教授Lempel和Ziv提出了查找冗余字符和用较短的符号标记替代冗余字符的概念。1985年，由Welch加以充实而形成LZW，简称“LZW”技术。

1.LZW压缩基本原理

LZW压缩技术把数据流中复杂的数据用简单的代码来表示，并把代码和数据的对应关系建立一个转换表，又叫“字符串表”。

转换表是在压缩或解压缩过程中动态生成的表，该表只在进行压缩或解压缩过程中需要，一旦压缩和解压缩结束，该表将不再起任何作用。

2.LZW算法

LZW算法基于转换串表（字典）T，将输入字符串映射成定长（通常为12位）的码字。在12位4096种可能的代码中，256个代表单字符，剩下3840给出现的字符串。

LZW字典中的字符串具有前缀性，即 。

LZW算法流程：

1)初始化：将所有的单字符串放入串表

2)读第一个输入字符给前缀串ω

3)Step: 读下一个输入字符K

if 没有这样的K(输入已穷尽)：

码字(ω) 输出；结束。

If ωK 已存在于串表中：

ωK:=ω；repeat Step；

else ωK不在于串表中:

码字(ω) 输出；

ωK加进串表；

K:=ω；repeat Step.

例子：ababcbababaaaaaaa

LZW编码：a,b,c,ab,ba,abc,cb,bab,baba,aa,aaa,aaaa

3．LZW压缩的特点

LZW码能有效利用字符出现频率冗余度进行压缩，且字典是自适应生成的，但通常不能有效地利用位置冗余度。

具体特点如下：

l)LZW压缩技术对于可预测性不大的数据具有较好的处理效果，常用于GIF格式的图像压缩，其平均压缩比在2)1以上，最高压缩比可达到3：1。

2)对于数据流中连续重复出现的字节和字串，LZW压缩技术具有很高的压缩比。

3)除了用于图像数据处理以外，LZW压缩技术还被用于文本程序等数据压缩领域。

4)LZW压缩技术有很多变体，例如常见的ARC、RKARC、PKZIP高效压缩程序。

5)对于任意宽度和像素位长度的图像，都具有稳定的压缩过程。压缩和解压缩速度较快。

6)对机器硬件条件要求不高，在 Intel 80386的计算机上即可进行压缩和解压缩。

function [output,table] = lzw2norm(vector)

%LZW2NORM LZW Data Compression (decoder)

% For vectors, LZW2NORM(X) is the uncompressed vector of X using the LZW algorithm.

% [...,T] = LZW2NORM(X) returns also the table that the algorithm produces.

%

% For matrices, X(:) is used as input.

%

% Input must be of uint16 type, while the output is a uint8.

% Table is a cell array, each element containig the corresponding code.

%

% This is an implementation of the algorithm presented in the article

% http://www.dogma.net/markn/articles/lzw/lzw.htm

%

% See also NORM2LZW

% $Author: Giuseppe Ridino' $

% $Revision: 1.0 $ $Date: 10-May-2004 14:16:08 $

% How it decodes:

%

% Read OLD_CODE

% output OLD_CODE

% CHARACTER = OLD_CODE

% WHILE there are still input characters DO

% Read NEW_CODE

% IF NEW_CODE is not in the translation table THEN

% STRING = get translation of OLD_CODE

% STRING = STRING+CHARACTER

% ELSE

% STRING = get translation of NEW_CODE

% END of IF

% output STRING

% CHARACTER = first character in STRING

% add translation of OLD_CODE + CHARACTER to the translation table

% OLD_CODE = NEW_CODE

% END of WHILE

% ensure to handle uint8 input vector

if ~isa(vector,'uint16'),

error('input argument must be a uint16 vector')

end

% vector as a row

vector = vector(:)'

% initialize table (don't use cellstr because char(10) will be turned to empty!!!)

table = cell(1,256)

for index = 1:256,

table{index} = uint16(index-1)

end

% initialize output

output = uint8([])

code = vector(1)

output(end+1) = code

character = code

for index=2:length(vector),

element = vector(index)

if (double(element)+1)>length(table),

% add it to the table

string = table{double(code)+1}

string = [string character]

else,

string = table{double(element)+1}

end

output = [output string]

character = string(1)

[table,code] = addcode(table,[table{double(code)+1} character])

code = element

end

% ###############################################

function code = getcodefor(substr,table)

code = uint16([])

if length(substr)==1,

code = substr

else, % this is to skip the first 256 known positions

for index=257:length(table),

if isequal(substr,table{index}),

code = uint16(index-1) % start from 0

break

end

end

end

% ###############################################

function [table,code] = addcode(table,substr)

code = length(table)+1 % start from 1

table{code} = substr

code = uint16(code-1) % start from 0

文件2

%LZW DEMO 1

% $Author: Giuseppe Ridino' $

% $Revision: 1.0 $ $Date: 10-May-2004 14:16:08 $

% string to compress

str = '/WED/WE/WEE/WEB/WET'

% pack it

[packed,table]=norm2lzw(uint8(str))

% unpack it

[unpacked,table]=lzw2norm(packed)

% transfor it back to char array

unpacked = char(unpacked)

% test

isOK = strcmp(str,unpacked)

% show new table elements

strvcat(table{257:end})

文件3

function [output,table] = norm2lzw(vector)

%NORM2LZW LZW Data Compression (encoder)

% For vectors, NORM2LZW(X) is the compressed vector of X using the LZW algorithm.

% [...,T] = NORM2LZW(X) returns also the table that the algorithm produces.

%

% For matrices, X(:) is used as input.

%

% Input must be of uint8 type, while the output is a uint16.

% Table is a cell array, each element containig the corresponding code.

%

% This is an implementation of the algorithm presented in the article

% http://www.dogma.net/markn/articles/lzw/lzw.htm

%

% See also LZW2NORM

% $Author: Giuseppe Ridino' $

% $Revision: 1.0 $ $Date: 10-May-2004 14:16:08 $

% How it encodes:

%

% STRING = get input character

% WHILE there are still input characters DO

% CHARACTER = get input character

% IF STRING+CHARACTER is in the string table then

% STRING = STRING+character

% ELSE

% output the code for STRING

% add STRING+CHARACTER to the string table

% STRING = CHARACTER

% END of IF

% END of WHILE

% output the code for STRING

% ensure to handle uint8 input vector

if ~isa(vector,'uint8'),

error('input argument must be a uint8 vector')

end

% vector as uint16 row

vector = uint16(vector(:)')

% initialize table (don't use cellstr because char(10) will be turned to empty!!!)

table = cell(1,256)

for index = 1:256,

table{index} = uint16(index-1)

end

% initialize output

output = vector

% main loop

outputindex = 1

startindex = 1

for index=2:length(vector),

element = vector(index)

substr = vector(startindex:(index-1))

code = getcodefor([substr element],table)

if isempty(code),

% add it to the table

output(outputindex) = getcodefor(substr,table)

[table,code] = addcode(table,[substr element])

outputindex = outputindex+1

startindex = index

else,

% go on looping

end

end

substr = vector(startindex:index)

output(outputindex) = getcodefor(substr,table)

% remove not used positions

output((outputindex+1):end) = []

% ###############################################

function code = getcodefor(substr,table)

code = uint16([])

if length(substr)==1,

code = substr

else, % this is to skip the first 256 known positions

for index=257:length(table),

if isequal(substr,table{index}),

code = uint16(index-1) % start from 0

break

end

end

end

% ###############################################

function [table,code] = addcode(table,substr)

code = length(table)+1 % start from 1

table{code} = substr

code = uint16(code-1) % start from 0