lzw实验报告

LZW编码算法

1．实验目的

1)通过实验进一步掌握LZW编码的原理；

2)用C/C++等高级程序设计语言实现LZW编码 。

2．实验设备

硬件：装有32M以上内存MPC；

软件：Windows 9X/NT/XP/2000操作系统、 TC 或C++等高级语言环境。

3．实验设计原理

LZW编码思想：

（1）在压缩过程中动态形成一个字符列表（字典）。

（2）每当压缩扫描图像发现一个词典中没有的字符序列，就把该字符序列存到字典中，并用字典的地址（编码）作为这个字符序列的代码，替换原图像中的字符序列，下次再碰到相同的字符序列，就用字典的地址代替字符序列。

 LZW编码算法的具体执行步骤如下：

步骤1：开始时的词典包含所有可能的根(Root)，而当前前缀P是空的；

步骤2：当前字符(C) ：=字符流中的下一个字符；

步骤3：判断缀-符串P+C是否在词典中

   (1)如果“是”：P ：= P+C // (用C扩展P) ；

   (2)如果“否”

      ①把代表当前前缀P的码字输出到码字流;

      ②把缀-符串P+C添加到词典;

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

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

   (1)如果“是”，就返回到步骤2；

   (2)如果“否”

     ①把代表当前前缀P的码字输出到码字流;

     ②结束。

4.程序框图

5.程序设计代码

#include

#include

using namespace std;

const int N=200;

class LZW{

private: string Dic[200];

       int code[N];

public: LZW(){

Dic[0]='a';

Dic[1]='b';

Dic[2]='c';

string *p=Dic;

}    

void Bianma(string cs[N]);

int IsDic(string e);

int codeDic(string f);

void display(int g);

};

void LZW::Bianma(string cs[N]){

string P,C,K;

P=cs[0];

int l=0;

for(int i=1;iC=cs[i];

K=P+C;

if(IsDic(K)) P=K;

else{

code[l]=codeDic(P);

Dic[3+l]=K;

P=C;

l++;

}

if(N-1==i)

 code[l]=codeDic(P);

}

display(l);

}

int LZW::IsDic(string e){

for(int b=0; b<200; b++)

{ if(e==Dic[b]) return 1; }

return 0;

}

int LZW::codeDic(string f){

int w=0;

for(int y=0;y<200;y++)

if(f==Dic[y]){

w=y+1;

break;

}

return w;

}

void LZW::display(int g){

cout<<"经过LZW编码后的码字如下："<for(int i=0;i<=g;i++)

cout<cout<cout<<"经LZW编码后的词典如下："<for(int r=0;rcout<}

int main(){

LZW t;

string CSstream[N];

int length;

cout<<"请输入所求码子序列的长度：";

cin>>length;

while(length>=N){

cout<<"该长度太长，请重新输入：";

cin>>length;

}

cout<<"请输入要进行LZW编码的字符序列："<for(int a=0;acin>>CSstream[a];

t.Bianma(CSstream);

return 0;

}

6.程序截图

7.心得体会

7.1 LZW算法的优缺点

LZW的优点是逻辑简单，实现速度快。缺点是字典的生成和查找是基于顺序插和检索模式，需要处理的数据量较大时会降低查找效率。

7.2实验中遇到的问题和自己的感想

对于我来说,这个实验还是比较难的,所以经过仔细的看书和网上查阅书籍,我渐渐明白了原理,也自己攻克了这个实验,考验了我们的思考能力和解决问题的能力.使我们在下次的实验中更加如鱼得水,成功完成。