LZW编解码实验报告（含程序和注释）.doc-资料库

huangchen1990-3313395-4744300845169440595.doc.pdf-第1页.png

第1页 / 共8页

huangchen1990-3313395-4744300845169440595.doc.pdf-第2页.png

第2页 / 共8页

huangchen1990-3313395-4744300845169440595.doc.pdf-第3页.png

第3页 / 共8页

huangchen1990-3313395-4744300845169440595.doc.pdf-第4页.png

第4页 / 共8页

huangchen1990-3313395-4744300845169440595.doc.pdf-第5页.png

第5页 / 共8页

huangchen1990-3313395-4744300845169440595.doc.pdf-第6页.png

第6页 / 共8页

huangchen1990-3313395-4744300845169440595.doc.pdf-第7页.png

第7页 / 共8页

huangchen1990-3313395-4744300845169440595.doc.pdf-第8页.png

第8页 / 共8页

一、实验名称 LZW 编码及译码二、实验目的 1、熟悉和巩固信息论课程中有关信源编码中 LZW 编码的原理、方法。 2、会用 VC 调试和验证 LZW 编码译码程序，提高分析程序的能力 3、将所学的理论知识进行上机实践。三、实验要求设计一个 LZW 编码/译码系统，掌握 LZW 编码的特点、存储方法和基本原理，培养利用 C++语言编写程序以及调试程序的能力，运用信息论知识解决实际问题的能力。用 C 语言实现 LZW 编/译码的相关函数的基本框架设计，如 LZW 树的构建，LZW 编码的实现，LZW 译码的实现等。四、实验原理由韦尔奇在 1984 年开发的 LZW 算法，是 LZ 系列码中应用最广泛、变形最多的。它是先建立初始字典，在分解输入流为短语词条，这个短语若不在初始字典中，就将其存入字典，这些新词条和初始字典共同构成编码器字典。而初始字典可由信源符号集构成，每一个符号是一个词条。 1、编码原理：LZW 编码器使用了一种很实用的分析(parsing)算法，称为贪婪分析算法(greedy parsing algorithm)。在贪婪分析算法中，每一次分析都要串行地检查来自字符流(Charstream)的字符串，从中分解出已经识别的最长的字符串，也就是已经在词典中出现的最长的前缀(Prefix)。用已知的前缀(Prefix)加上下一个输入字符 C 也就是当前字符(Current character)作为该前缀的扩展字符，形成新的扩展字符串——缀-符串(String)：Prefix.C。这个新的缀-符串(String)是否要加到词典中，还要看词典中是否存有和它相同的缀-符串 String。如果有，那么这个缀-符串(String)就变成前缀(Prefix)，继续输入新的字符，否则就把这个缀-符串(String)写到词典中生成一个新的前缀(Prefix)，并给一个代码。编码示例：被编码的字符串位置 1 2 3 4 5 6 7 8 9 字符 A B B A B A B A C LZW 的编码过程步骤位置词典 (1) A (2) B (3) C (4) A B (5) B B (6) B A 1 2 3 1 2 3 输出 (1) (2) (2)

4 5 6 4 6 -- (7) A B A (8) A B A C -- -- (4) (7) (3) 2、解码原理： LZW 译码算法中会用到另外两个术语：①当前码字(Current code word)：指当前正在处理的码字，用 cW 表示，用 string.cW 表示当前缀-符串；②先前码字(Previous code word)：指先于当前码字的码字，用 pW 表示，用 string.pW 表示先前缀-符串。LZW 译码算法开始时，译码词典与编码词典相同，它包含所有可能的前缀根(roots)。LZW 算法在译码过程中会记住先前码字(pW)，从码字流中读当前码字(cW)之后输出当前缀-符串 string.cW，然后把用 string.cW 的第一个字符扩展的先前缀-符串 string.pW 添加到词典中。五、实验内容步骤及方案本实验主要有四个函数： 1、编码函数：code( ) 2、译码函数：decode( ) 3、字典查找函数：find( ) 4、字典初始化函数：init( ) 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 的码字输出到码字流; ② 结束。 LZW 译码算法的具体执行步骤如下：步骤 1：在开始译码时词典包含所有可能的前缀根(Root)。步骤 2： cW ：=码字流中的第一个码字。步骤 3：输出当前缀-符串 string.cW 到码字流。步骤 4：先前码字 pW ：= 当前码字 cW。步骤 5：当前码字 cW ：= 码字流中的下一个码字。步骤 6：判断先前缀-符串 string.pW 是否在词典中 (1) 如果“是”，则：

① 把先前缀-符串 string.pW 输出到字符流。 ② 当前前缀 P ：=先前缀-符串 string.pW。 ③ 当前字符 C ：=当前前缀-符串 string.cW 的第一个字符。 ④ 把缀-符串 P+C 添加到词典。 (2) 如果“否”，则： ① 当前前缀 P ：=先前缀-符串 string.pW。 ② 当前字符 C ：=当前缀-符串 string.cW 的第一个字符。 ③ 输出缀-符串 P+C 到字符流，然后把它添加到词典中。步骤 7：判断码字流中是否还有码字要译 (1) 如果“是”，就返回到步骤 4。 (2) 如果“否”, 结束。字典初始化操作： void init() //字典初始化 dic[0]="a"; dic[1]="b"; dic[2]="c"; //为简单起见，将字典中的字根设置为 a,b,c ，即刚开始时字典中只有 a,b,c 三个码字 for(int i=3;i<30;i++) dic[i]=""; //其余码字为空 //在字典中寻找的函数（返回序号为 int 型）字典查找操作： int find(string s) int temp=-1; for(int i=0;i<30;i++) //设字典中最大存储字根数为 30 if(dic[i]==s) temp=i+1; return temp; //返回所查找字在字典中所对应的序号 { } } { { { } } 六、实验程序 #include #include #include 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() { //字典初始化 //字典中寻找的函数（返回序号为 int 型） //设字典中最大存储字根数为 30 //返回所查找字在字典中所对应的序号 dic[0]="a"; dic[1]="b"; dic[2]="c"; //为简单起见，将字典中的字根设置为 a,b,c ，即刚开始时字典中只有 a,b,c //其余码字为空三个码字 for(int i=3;i<30;i++) { dic[i]=""; } } void code(string str) { //编码函数 code //取第一个字符 //调用初始化函数 //让下一个为空字符 //将前两个字符赋给变量 w init(); char temp[2]; temp[0]=str[0]; temp[1]='\0'; string w=temp; int i=1; int j=3; //目前字典存储的最后一个位置，因为原有码字个数为 3，所以让 j=3 cout<<"\n 编码为："; for(;;) { //for 语句内为编码操作，并显示出来 //显示编码 char t[2]; t[0]=str[i]; t[1]='\0'; string k=t; if(k=="") //取下一字符 //再下一个字符为未知字符，设为空 //为空，说明字符串结束

cout<<" "<-1) { w=w+k; i++; cout<<" "<

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<>cha; if(cha=='a') { //若选择 a，则执行编码 cout<<"\n 输入要编码的字符串(由 a、b、c 组成)："; cin>>str; code(str); //调用编码函数 } else { //若选择 b，则执行译码 int c[30]; cout<<"\n 消息序列长度是："; cin>>n; //将译码结果显示出来 cout<

cout<<"\n 消息码字依次是："; for(int i=0;i>c[i]; } decode(c); //调用译码函数 } } } 七、实验结果及分析上述程序在 VC++环境中编译运行后，出现如下图所示的画面： 1、选择 a.编码，并输入字符串 ababcbabccc 码字词条 I 新词条输出码 1 2 3 =================================== a b c

. 4 5 6 7 8 9 10 a ab b ba a ab abc c cb b ba bab b bc c cc c cc,eof N Y N Y N N Y N Y N N Y N Y N Y N N 2、选择 b.译码 1 2 4 3 5 2 3 10,eof 译码结果与编码输入一致八、心得体会通过编写实验代码和调试运行，可以逐步积累调试 C 程序的经验并逐渐培养我们的编程能力、以及用计算机解决实际问题的能力。对于信息论编码课程来说，通过实际编码和译码的实践，使我更加巩固了 lzw 码这部分的相关知识，对 lzw 码有了更深的体会。

资料库

LZW编解码实验报告（含程序和注释）.doc

相关推荐

信息化

热门标签

最新资料