南京理工大学电路实验报告超详细版

-叠加定理与戴维南定理

 

第二篇：南京理工大学多媒体实验报告

无损数据压缩实验报告

班    级： 

学    号：      

姓    名：         

20##年1月10日

LZW算法压缩编码技术

1.     设计思路：

　LZW就是通过建立一个字符串表,用较短的代码来表示较长的字符串来实现压缩. 字符串和编码的对应关系是在压缩过程中动态生成的,并且隐含在压缩数据中,解压的时候根据表来进行恢复,是一种无损压缩. .在本次实验中我们就进行了LZW编码以及译码简单算法的编写。

LZW编码又称字串表编码，是无损压缩技术改进后的压缩方法。它采用了一种先进的串表压缩，将每个第一次出现的串放在一个串表当中，用一个数字来表示串，压缩文件只进行数字的存贮，则不存贮串，从而使图像文件的压缩效率得到了较大的提高。

　 LZW压缩算法的基本原理：提取原始文本文件数据中的不同字符，基于这些字符创建一个编译表，然后用编译表中的字符的索引来替代原始文本文件数据中的相应字符，减少原始数据大小。应该注意到的是，这里的编译表不是事先创建好的，而是根据原始文件数据动态创建的，解码时还要从已编码的数据中还原出原来的编译表.对于字符串流，我们要进行分析，从词典中寻找最长匹配串，即字符串P在词典中，而字符串P+后一个字符C不在词典中。此时，输出P对应的码字，将P+C放入词典中。经过努力，我初步知道了对于一个字符串进行编码的过程。

2.步骤

(1)根据需要得建立一个初始化词典。这里字根分别为A B C。具体的初始化算法如下：

void init()//词典初始化

{

  dic[0]="A";

  dic[1]="B";

  dic[2]="C";//字根为A,B,C

  for(int i=3;i<30;i++)//其余为空

  {

      dic[i]="";

  }

}

(2)对于编码算法的建立，则需先建立一个查找函数，用于查找返回序号：

int find(string s)

{

    int temp=-1;

    for(int i=0;i<30;i++)

    {

       if(dic[i]==s) temp=i+1;

    }

    return temp;

}

(3) 编写编码算法:

void code(string str)

{

  int();//初始化

  char temp[2];

  temp[0]=str[0];//取第一个字符

  temp[1]='\0';

  string w=temp;

  int i=1;

  int j=3;//目前字典存储的最后一个位置

  cout<<"\n  编码为：";

  for(;;)

  {

     char t[2];

     t[0]=str[i];//取下一字符

     t[1]='\0';

     string k=t;

     if(k=="") //为空，字符串结束

     {

         cout<<" "<<find(w);

         break;//退出for循环,编码结束

     }

     if(find(w+k)>-1)

     {

         w=w+k;

         i++;

     }

     else

     {

         cout<<" "<<find(w);

         string wk=w+k;

         dic[j++]=wk;

         w=k;

         i++;

     }

  }

  cout<<endl;

  for(i=0;i<j;i++)

  {

     cout<<setw(45)<<i+1<<setw(12)<<dic[i]<<endl;

  }

  cout<<endl;

}

(4) 译码是编码的逆过程。在译码中根缀表仍为A,B,C。且定义如下变量

StringP :前一步码字流

pW : StringP的第一个字符

StringC :当前的码字流

cW : StringC的第一个字符

 结合老师给的前两步译码过程，得到译码算法如下：

 void decode(int c[])

{

  init();

  int pw,cw;

  cw=c[0];

  int j=2;

  cout<<"\n  译码为：";

  cout<<dic[cw-1];

  for(int i=0;i<n-1;i++)

  {

     pw=cw;

     cw=c[i+1];

     if(cw<=j+1)

     {

         cout<<dic[cw-1];

         char t[2];

         t[0]=dic[cw-1][0];

         t[1]='\0';

         string k=t;

         j++;

         dic[j]=dic[pw-1]+k;

     }

     else

     {

         char t[2];

         t[0]=dic[pw-1][0];

         t[1]='\0';

         string k=t;

         j++;

         dic[j]=dic[pw-1]+k;

         cout<<dic[cw-1];

     }

  }

  cout<<endl;

  for(i=0;i<j+1;i++)

  {

     cout<<setw(45)<<i+1<<setw(12)<<dic[i]<<endl;

  }

  cout<<endl;

}

(5) 最后的主函数用菜单的方式编写：a.编码   b.译码。

3.程序源代码：

#include<iostream>

#include<string>

#include<iomanip>

using namespace std;

string dic[30];

int n;

int find(string s)

{

  int temp=-1;

  for(int i=0;i<30;i++)

  {

      if(dic[i]==s) temp=i+1;

  }

  return temp;

}

void init()

{

  dic[0]="A";

  dic[1]="B";

  dic[2]="C";

  for(int i=3;i<30;i++)

  {

      dic[i]="";

  }

}

void code(string str)

{

  init();//初始化

  char temp[2];

  temp[0]=str[0];

  temp[1]='\0';

  string w=temp;

  int i=1;

  int j=3;

  cout<<"\n  编码为：";

  for(;;)

  {

      char t[2];

      t[0]=str[i];

      t[1]='\0';

      string k=t;

      if(k=="")

      {

          cout<<" "<<find(w);

          break;

      }

      if(find(w+k)>-1)

      {

          w=w+k;

          i++;

      }

      else

      {

          cout<<" "<<find(w);

          string wk=w+k;

          dic[j++]=wk;

          w=k;

          i++;

      }

  }

  cout<<endl;

  for(i=0;i<j;i++)

  {

      cout<<setw(45)<<i+1<<setw(12)<<dic[i]<<endl;

  }

  cout<<endl;

}

void decode(int c[])

{

  init();

  int pw,cw;

  cw=c[0];

  int j=2;

  cout<<"\n  译码为：";

  cout<<dic[cw-1];

  for(int i=0;i<n-1;i++)

  {

      pw=cw;

      cw=c[i+1];

      if(cw<=j+1)

      {

          cout<<dic[cw-1];

          char t[2];

          t[0]=dic[cw-1][0];

          t[1]='\0';

          string k=t;

          j++;

          dic[j]=dic[pw-1]+k;

      }

      else

      {

          char t[2];

          t[0]=dic[pw-1][0];

          t[1]='\0';

          string k=t;

          j++;

          dic[j]=dic[pw-1]+k;

          cout<<dic[cw-1];

      }

  }

  cout<<endl;

  for(i=0;i<j+1;i++)

  {

      cout<<setw(45)<<i+1<<setw(12)<<dic[i]<<endl;

  }

  cout<<endl;

}

void main()

{

  string str;

  while(1)

  {

      cout<<"\n\n\t1.编码\t2.译码\n\n";

      cout<<"请选择：";

      char cha;

      cin>>cha;

      if(cha=='1')

      {

          cout<<"\n输入要编码的字符串(由A、B、C组成)：";

          cin>>str;

          code(str);

      }

      else

      {

          int c[30];

          cout<<"\n消息序列长度是：";

          cin>>n;

          cout<<"\n消息码字依次是：";

          for(int i=0;i<n;i++)

          {

              cin>>c[i];

          }

          decode(c);

      }

  }

}

4.设计截图

5.心得体会：

     这次设计，刚开始的时候感觉无从下手，因为对LZW算法的不熟悉，总感觉压缩与解压是一个很深奥的东西。但是通过自己不懈的努力和同学的帮助，最终我还是完成了实验。

对于我来说，收获最大的是方法和能力；那些分析和解决问题的能力。在整个设计的过程中，我发现我们在经验方面十分缺乏，空有理论知识，没有理性的知识；可能只懂了算法，但是到具体的编程方面，却总显得有些无从下手，有些东西可能与实际脱节。总体来说，我觉得像这种设计对我们的帮助还是很大的，它需要我们将学过的相关知识系统地联系起来，从中暴露出我长期不编程后编程能力的下降，急待改进！