lzw编码源代码（LZW编码例题）

今天给各位分享lzw编码源代码的知识，其中也会对LZW编码例题进行解释，如果能碰巧解决你现在面临的问题，别忘了关注本站，现在开始吧！

本文目录一览：

• 1、LZW是什么意思
• 2、用lz,lzw,kieffer-yang算法编码
• 3、跪求C语言进行哈夫曼编码、算术编码和LZW编码，要求源程序要有注释。
• 4、跪求LZW码编、解码的Matlab实现程序！
• 5、求一个c++的用lzw（字典）算法来压缩bmp图片的代码
• 6、急求lzw算法的英文文本压缩C语言源代码！

LZW是什么意思

LZW压缩编码

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的计算机上即可进行压缩和解压缩。

用lz,lzw,kieffer-yang算法编码

1，Lemple-Ziv算法（简称LZ）是编码时将一个位串分成词组，然后将数据流描述成一系列的对。每个对组成一个新的词组，它包含一个数字（前一个词组的标识）和一个位（被附加到前一个词组上）。这种编码方式很庞大，可是一旦应用到适合的字符串，它就是相当有效率的编码方式。压缩率最大达400%。

2，LZW（Lempel-Ziv Welch）算法能把大文件转变成更适合于网页使用的较小文件。实现方法是将一系列符号压缩成单个符号乘以该符号的出现次数。LZW压缩格式叫做“无陨”数据压缩格式，即尽管数据得到压缩，但解压后的图像看上去同原文件完全一样。lzw压缩率在200% 以上，最大可达到300%。

3，Kieffer-Yang是基于语法的普适信源压缩算法。压缩率300%。

跪求C语言进行哈夫曼编码、算术编码和LZW编码，要求源程序要有注释。

以下是哈夫曼编码

#includeiostream

#includemath.h

#includestring

#includeiomanip

using namespace std;

int n;

int isin(string str,char a)

{

int temp=0;

for(int i=0;istr.length();i++)

{

if(str[i]==a) temp=1;

}

return temp;

}

void bubble(double p[],string sign[])//排序

{

for(int i=0;in-1;i++)

{

for(int j=i+1;jn;j++)

{

if(p[i]p[j])

{

double temp=p[i];

p[i]=p[j];

p[j]=temp;

string m=sign[i];

sign[i]=sign[j];

sign[j]=m;

}

}

}

}

void huff(double tempp[],string tempstr[])

{

double p[20][20];

string sign[20][20];

sign[0][i]=tempstr[i]; //符号放在sign数组中

for(int i=0;in;i++)

{

p[0][i]=tempp[i]; //p数组放对应的概率(第1列中)

}

for(i=0;in-1;i++)

{

bubble(p[i],sign[i]); //第一次排序

for(int j=0;jn-2-i;j++)

{

p[i+1][j]=p[i][j]; //前n-2-i个概率重新放在p数组中(是数组的第2列中)

sign[i+1][j]=sign[i][j];

}

p[i+1][j]=p[i][j]+p[i][j+1];//第一次两个最小概率求和

sign[i+1][j]=sign[i][j]+sign[i][j+1];//符号跟随

for(j=n-1-i;jn;j++)

{

p[i+1][j]=0;

}

}

string final[20];

for(i=n-2;i=0;i--)

{

for(int k=0;kn;k++)

{

if(isin(sign[i][n-2-i],sign[0][k][0])) final[k]+="0";

if(isin(sign[i][n-1-i],sign[0][k][0])) final[k]+="1";

}

}

coutsetw(9)"哈弗曼编码如下:"endl;

for(i=0;in;i++)

{

coutsetw(7)sign[0][i]setw(7)p[0][i]setw(10)final[i]

setw(7)final[i].length()endl;

}

}

void main()

{

char a[50];

cout"该字符串符号为:";

cina;

string s=a;

n=s.length();

char b[20][2];

for(int i=0;in;i++)

{

b[i][0]=a[i];

b[i][1]='\0';

}

string str[20];

for(i=0;in;i++)

{

str[i]=b[i];

}

double tempp[20];

cout"字符概率依次为：";

for(i=0;in;i++)

{

cintempp[i];

}

huff(tempp,str);

}

跪求LZW码编、解码的Matlab实现程序！

文件1

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

%

%

% 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

%

%

% 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

求一个c++的用lzw（字典）算法来压缩bmp图片的代码

参见gif压缩算法源代码。

1.LZW的全称是什么?

Lempel-Ziv-Welch (LZW).

2. LZW的简介和压缩原理是什么？

LZW压缩算法是一种新颖的压缩方法，由Lemple-Ziv-Welch 三人共同创造，用他们的名字命名。它采用了一种先进的串表压缩，将每个第一次出现的串放在一个串表中，用一个数字来表示串，压缩文件只存贮数字，则不存贮串，从而使图象文件的压缩效率得到较大的提高。奇妙的是，不管是在压缩还是在解压缩的过程中都能正确的建立这个串表，压缩或解压缩完成后，这个串表又被丢弃。

LZW算法中，首先建立一个字符串表，把每一个第一次出现的字符串放入串表中，并用一个数字来表示，这个数字与此字符串在串表中的位置有关，并将这个数字存入压缩文件中，如果这个字符串再次出现时，即可用表示它的数字来代替，并将这个数字存入文件中。压缩完成后将串表丢弃。如"print" 字符串，如果在压缩时用266表示，只要再次出现，均用266表示，并将"print"字符串存入串表中，在图象解码时遇到数字266，即可从串表中查出266所代表的字符串"print"，在解压缩时，串表可以根据压缩数据重新生成。

3.在详细介绍算法之前，先列出一些与该算法相关的概念和词汇

1)'Character': 字符，一种基础数据元素，在普通文本文件中，它占用1个单独的byte，而在图像中，它却是 一种代表给定像素颜色的索引值。

2)'CharStream'：数据文件中的字符流。

3)'Prefix':前缀。如这个单词的含义一样，代表着在一个字符最直接的前一个字符。一个前缀字符长度可以为0,一个prefix和一个character可以组成一个字符串(string),

4)'Suffix': 后缀，是一个字符，一个字符串可以由(A,B)来组成，A是前缀,B是后缀,当A长度为0的时候，代表Root，根

5)'Code:码,用于代表一个字符串的位置编码

6)'Entry'，一个Code和它所代表的字符串(string)

4.压缩算法的简单示例，不是完全实现LZW算法，只是从最直观的角度看lzw算法的思想

对原始数据ABCCAABCDDAACCDB进行LZW压缩

原始数据中，只包括4个字符(Character),A,B,C,D,四个字符可以用一个2bit的数表示，0-A,1-B,2-C,3-D,从最直观的角度看，原始字符串存在重复字符：ABCCAABCDDAACCDB，用4代表AB,5代表CC，上面的字符串可以替代表示为:45A4CDDAA5DB,这样是不是就比原数据短了一些呢！

5.LZW算法的适用范围

为了区别代表串的值(Code)和原来的单个的数据值(String)，需要使它们的数值域不重合，上面用0-3来代表A-D,那么AB就必须用大于3的数值来代替，再举另外一个例子，原来的数值范围可以用8bit来表示，那么就认为原始的数的范围是0～255，压缩程序生成的标号的范围就不能为0～255（如果是0-255，就重复了）。只能从256开始，但是这样一来就超过了8位的表示范围了，所以必须要扩展数据的位数，至少扩展一位，但是这样不是增加了1个字符占用的空间了么？但是却可以用一个字符代表几个字符，比如原来255是8bit,但是现在用256来表示254，255两个数，还是划得来的。从这个原理可以看出LZW算法的适用范围是原始数据串最好是有大量的子串多次重复出现，重复的越多，压缩效果越好。反之则越差，可能真的不减反增了。

6.LZW算法中特殊标记

随着新的串(string)不断被发现，标号也会不断地增长，如果原数据过大，生成的标号集（string table)会越来越大，这时候操作这个集合就会产生效率问题。如何避免这个问题呢?Gif在采用lzw算法的做法是当标号集足够大的时候，就不能增大了，干脆从头开始再来，在这个位置要插入一个标号，就是清除标志CLEAR，表示从这里我重新开始构造字典，以前的所有标记作废，开始使用新的标记。

这时候又有一个问题出现，足够大是多大？这个标号集的大小为比较合适呢？理论上是标号集大小越大，则压缩比率就越高，但开销也越高。 一般根据处理速度和内存空间连个因素来选定。GIF规范规定的是12位，超过12位的表达范围就推倒重来，并且GIF为了提高压缩率，采用的是变长的字长。比如说原始数据是8位，那么一开始，先加上一位再说，开始的字长就成了9位，然后开始加标号，当标号加到512时，也就是超过9为所能表达的最大数据时，也就意味着后面的标号要用10位字长才能表示了，那么从这里开始，后面的字长就是10位了。依此类推，到了2^12也就是4096时，在这里插一个清除标志，从后面开始，从9位再来。

GIF规定的清除标志CLEAR的数值是原始数据字长表示的最大值加1，如果原始数据字长是8，那么清除标志就是256，如果原始数据字长为4那么就是16。另外GIF还规定了一个结束标志END，它的值是清除标志CLEAR再加1。由于GIF规定的位数有1位（单色图），4位（16色）和8位（256色），而1位的情况下如果只扩展1位，只能表示4种状态，那么加上一个清除标志和结束标志就用完了，所以1位的情况下就必须扩充到3位。其它两种情况初始的字长就为5位和9位。此处参照了

7.用lzw算法压缩原始数据的示例分析

输入流，也就是原始的数据为:255,24,54,255,24,255,255,24,5,123,45,255,24,5,24,54..................

这个正好可以看到是gif文件中像素数组的一部分，如何对它进行压缩

因为原始数据可以用8bit来表示，故清除标志Clear=255+1 =256,结束标志为End=256+1=257，目前标号集为

0 1 2 3 .................................................................................255 CLEAR END

第一步,读取第一个字符为255,在标记表里面查找，255已经存在，我们已经认识255了，不做处理

第二步,取第二个字符，此时前缀为A,形成当前的Entry为(255,24),在标记集合不存在，我们并不认识255,24好，这次你小子来了，我就记住你，把它在标记集合中标记为258,然后输出前缀A,保留后缀24，并作为下一次的前缀（后缀变前缀)

第三步，取第三个字符为54，当前Entry(24,54),不认识，记录(24,54)为标号259,并输出24,后缀变前缀

第四部：取第四个字符255,Entry=(54,255),不认识，记录(54,255)为标号260,输出54,后缀变前缀

第五步 取第5个字符24，entry=(255,24),啊，认识你，这不是老258么，于是把字符串规约为258，并作为前缀

第六步 取第六个字符255,entry=(258,255)，不认识，记录(258,255)为261,输出258,后缀变前缀

.......

一直处理到最后一个字符,

用一个表记录处理过程

CLEAR=256,END=257

第几步 前缀 后缀 Entry 认识(Y/N) 输出 标号

1 255 （，255）

2 255 24 (255,24) N 255 258

3 24 54 (24,54) N 24 259

4 54 255 (54,255) N 54 260

5 255 24 (255,24) Y

6 258 255 (258,255) N 258 261

7 255 255 (255,255) N 255 262

.....

上面这个示例有些不能完整体现，另外一个例子是

原输入数据为:A B A B A B A B B B A B A B A A C D A C D A D C A B A A A B A B .....

采用LZW算法对其进行压缩，压缩过程用一个表来表述为:

注意原数据中只包含4个character,A,B,C,D

用两bit即可表述，根据lzw算法，首先扩展一位变为3为,Clear=2的2次方+1=4; End=4+1=5;

初始标号集因该为

0 1 2 3 4 5

A B C D Clear End

而压缩过程为:

第几步 前缀 后缀 Entry 认识(Y/N) 输出 标号

1 A （，A）

2 A B (A,B) N A 6

3 B A (B,A) N B 7

4 A B (A,B) Y

5 6 A (6,A) N 6 8

6 A B (A,B) Y

7 6 A (6,A) Y

8 8 B (8,B) N 8 9

9 B B (B,B) N B 10

10 B B (B,B) Y

11 10 A (10,A) N 10 11

12 A B (A,B) Y

.....

当进行到第12步的时候，标号集应该为

0 1 2 3 4 5 6 7 8 9 10 11

A B C D Clear End AB BA 6A 8B BB 10A

8.LZW算法的伪代码实现

1STRING = get input character

2WHILE there are still input characters DO

3 CHARACTER = get input character

4 IF STRING+CHARACTER is in the string table then

5 STRING = STRING+character

6 ELSE

7 output the code for STRING

8 add STRING+CHARACTER to the string table

9 STRING = CHARACTER

10 END of IF

11END of WHILE

12output the code for STRING

13

急求lzw算法的英文文本压缩C语言源代码！

#includeiostream

#includecstdio

#includecstring

#includectime//用来计算压缩的时间

using namespace std;

//定义常数

const int MAX = 1000003;//最大code数，是一个素数，求模是速度比较快

const int ascii = 256; //ascii代码的数量

const int ByteSize = 8; //8个字节

struct Element//hash表中的元素

{

int key;

int code;

Element *next;

}*table[MAX];//hash表

int hashfunction(int key)//hash函数

{

return key%MAX;

}

void hashinit(void)//hash表初始化

{

memset(table,0,sizeof(table));

}

void hashinsert(Element element)//hash表的插入

{

int k = hashfunction(element.key);

if(table[k]!=NULL)

{

Element *e=table[k];

while(e-next!=NULL)

{

e=e-next;

}

e-next=new Element;

e=e-next;

e-key = element.key;

e-code = element.code;

e-next = NULL;

}

else

{

table[k]=new Element;

table[k]-key = element.key;

table[k]-code = element.code;

table[k]-next = NULL;

}

}

bool hashfind(int key,Element element)//hash表的查找

{

int k = hashfunction(key);

if(table[k]!=NULL)

{

Element *e=table[k];

while(e!=NULL)

{

if(e-key == key)

{

element.key = e-key;

element.code = e-code;

return true;

}

e=e-next;

}

return false;

}

else

{

return false;

}

}

void compress(void)//压缩程序

{

//打开一个流供写入

FILE *fp;

fp = fopen("result.dat", "wb");

Element element;

int used;

char c;

int pcode, k;

for(int i=0;iascii;i++)

{

element.key = i;

element.code = i;

hashinsert(element);

}

used = ascii;

c = getchar();

pcode = c;

while((c = getchar()) != EOF)

{

k = (pcode ByteSize) + c;

if(hashfind(k, element))

pcode = element.code;

else

{

//coutpcode' ';

fwrite(pcode, sizeof(pcode), 1, fp);

element.code = used++;

element.key = (pcode ByteSize) | c;

hashinsert(element);

pcode = c;

}

}

//coutpcodeendl;

fwrite(pcode, sizeof(pcode), 1, fp);

}

int main(void)

{

int t1,t2;

//欲压缩的文本文件

//freopen("input.txt","r",stdin);

freopen("book5.txt","r",stdin);

t1=time(NULL);

hashinit();

compress();

t2=time(NULL);

cout"Compress complete! See result.dat."endl;

coutendl"Total use "t2-t1" seconds."endl;

lzw编码源代码的介绍就聊到这里吧，感谢你花时间阅读本站内容，更多关于LZW编码例题、lzw编码源代码的信息别忘了在本站进行查找喔。