lzw源代码

LZW压缩算法原理及其JAVA实现LZW（Lempel-Ziv-Welch）是一种无损压缩算法，用于将文件或数据压缩以减小其占用的存储空间。

它是一种字典压缩算法，通过建立和更新一个用于存储常见字符串/符号的字典，从而实现压缩。

LZW算法的原理1.初始化字典：将所有单个字符（如'a'，'b'等）作为初始字典的项，并为每个字符分配一个唯一的编码。

例如，a对应0，b对应1，c对应2，以此类推。

2.遍历待压缩的数据，从左到右逐个字符进行处理。

3.维护当前字符串：初始为空字符串。

4.当前字符加入当前字符串。

5.检查当前字符串是否已经存在于字典中。

-如果存在，继续将下一个字符加入当前字符串，并重复此步骤。

-如果不存在，将当前字符串的编码输出，并将当前字符串加入字典中，并为其分配一个新的编码。

6.输出当前字符串的编码。

7.返回第4步，继续处理下一个字符。

LZW算法的Java实现下面是一个简单的Java代码示例，演示如何实现LZW压缩算法：```javaimport java.util.*;Map<String, Integer> dictionary = new HashMap<>(; for (int i = 0; i < 256; i++)dictionary.put("" + (char)i, i);}String current = "";List<Integer> result = new ArrayList<>(;for (char ch : data.toCharArray()} elseresult.add(dictionary.get(current));current = "" + ch;}}if (!current.equals(""))result.add(dictionary.get(current));}return result;}Map<Integer, String> dictionary = new HashMap<>(;for (int i = 0; i < 256; i++)dictionary.put(i, "" + (char)i);}StringBuilder result = new StringBuilder(current);String entry;if (dictionary.containsKey(code))entry = dictionary.get(code);} else if (code == dictionary.size()entry = current + current.charAt(0);} else}result.append(entry);dictionary.put(dictionary.size(, current + entry.charAt(0)); current = entry;}return result.toString(;}public static void main(String[] args)}```LZW压缩算法是一种流行且有效的压缩算法，广泛应用于多种应用领域。

数据压缩算法LZLZ和LZW的原理与实现在计算机科学领域，数据压缩算法是一种用于减小数据文件大小的方法。

其中，LZLZ和LZW是两种常见的数据压缩算法。

本文将详细介绍这两种算法的原理和实现。

一、LZLZ算法LZLZ算法是一种基于字典的数据压缩算法。

该算法的原理是将连续出现的重复字符序列替换为较短的标记。

具体实现过程如下：1. 初始化字典，将所有可能的字符序列添加到字典中。

2. 从输入数据中读取字符序列，并查找字典中是否存在相同的序列。

3. 如果找到匹配的序列，则将其替换为字典中对应的标记，并将序列长度增加1。

4. 如果未找到匹配的序列，则将当前字符添加到字典中，并输出该字符。

5. 重复步骤2至4，直到处理完所有输入数据。

通过将重复的序列替换为较短的标记，LZLZ算法可以有效地减小数据文件的大小。

二、LZW算法LZW算法也是一种基于字典的数据压缩算法，与LZLZ算法类似，但存在一些差异。

下面是LZW算法的原理和实现过程：1. 初始化字典，将所有可能的单字符添加到字典中。

2. 从输入数据中读取字符序列，并根据当前已读的序列来搜索字典。

3. 如果找到匹配的序列，则将已读的序列继续扩展一个字符，并重复步骤2。

4. 如果未找到匹配的序列，则将字典中最长的已读序列对应的标记输出，并将已读的序列和下一个字符添加到字典中。

5. 重复步骤2至4，直到处理完所有输入数据。

LZW算法通过动态扩展字典，可以更好地利用数据的重复性。

相比于LZLZ算法，LZW算法通常能够达到更高的压缩率。

三、LZLZ和LZW的比较LZLZ算法和LZW算法在原理上有相似之处，都是通过字典来实现数据压缩。

然而，两者之间存在一些差异。

首先，LZLZ算法使用固定长度的标记，这使得算法相对简单，但可能导致压缩率较低。

与之相反，LZW算法可以根据需要动态扩展字典，以适应不同类型的数据，从而获得更高的压缩率。

其次，LZLZ算法的字典只包含单个字符和字串，而LZW算法的字典可以包含任意长度的序列。

标准的LZW压缩原理：~~~~~~~~~~~~~~~~~~先来解释一下几个基本概念：LZW压缩有三个重要的对象：数据流(CharStream)、编码流(CodeStream)和编译表(String Table)。

在编码时，数据流是输入对象（图象的光栅数据序列），编码流就是输出对象（经过压缩运算的编码数据）；在解码时，编码流则是输入对象，数据流是输出对象；而编译表是在编码和解码时都须要用借助的对象。

字符(Character)：最基础的数据元素，在文本文件中就是一个字节，在光栅数据中就是一个像素的颜色在指定的颜色列表中的索引值；字符串(String)：由几个连续的字符组成；前缀(Prefix)：也是一个字符串，不过通常用在另一个字符的前面，而且它的长度可以为0；根(Root)：单个长度的字符串；编码(Code)：一个数字，按照固定长度（编码长度）从编码流中取出，编译表的映射值；图案：一个字符串，按不定长度从数据流中读出,映射到编译表条目.LZW压缩的原理：提取原始图象数据中的不同图案，基于这些图案创建一个编译表，然后用编译表中的图案索引来替代原始光栅数据中的相应图案，减少原始数据大小。

看起来和调色板图象的实现原理差不多，但是应该注意到的是，我们这里的编译表不是事先创建好的，而是根据原始图象数据动态创建的，解码时还要从已编码的数据中还原出原来的编译表（GIF文件中是不携带编译表信息的），为了更好理解编解码原理，我们来看看具体的处理过程：编码器(Compressor)~~~~~~~~~~~~~~~~编码数据，第一步，初始化一个编译表，假设这个编译表的大小是12位的，也就是最多有4096个单位，另外假设我们有32个不同的字符（也可以认为图象的每个像素最多有32种颜色），表示为a，b，c，d，e...，初始化编译表：第0项为a，第1项为b，第2项为c...一直到第31项，我们把这32项就称为根。

开始编译，先定义一个前缀对象Current Prefix，记为[.c.]，现在它是空的，然后定义一个当前字符串Current String，标记为[.c.]k，[.c.]就为Current Prefix，k就为当前读取字符。

LZW（Lempel-Ziv-Welch）是一种无损数据压缩算法。

以下是一个简单的C语言实现的LZW编码和解码示例：```c#include <stdio.h>#include <stdlib.h>#include <string.h>#define MAX_CODE_SIZE 128typedef struct {int code;char ch;} Code;void init_codes(Code codes[]) {for (int i = 0; i < MAX_CODE_SIZE; i++) {codes[i].code = i;codes[i].ch = i;}}int next_code(Code codes[], char ch) {for (int i = 0; i < MAX_CODE_SIZE; i++) {if (codes[i].ch == ch) {return codes[i].code;}}return -1;}void compress(char *input, char *output) {Code codes[MAX_CODE_SIZE];init_codes(codes);int input_len = strlen(input);int output_index = 0;int current_code = 256;int current_len = 1;int max_len = 1;int next_index = 0;output[output_index++] = codes[current_code].ch;for (int i = 1; i < input_len; i++) {next_index = next_code(codes, input[i]);current_len++;if (next_index != -1) {current_code = next_index;} else {current_code = codes[current_code].code;codes[current_code].ch = input[i];current_code++;current_len = 1;}if (current_len > max_len) {max_len = current_len;}if (current_len == max_len && current_code < MAX_CODE_SIZE) { output[output_index++] = codes[current_code].ch;current_code++;current_len = 0;max_len = 1;}}output[output_index] = '\0';}void decompress(char *input, char *output) {Code codes[MAX_CODE_SIZE];init_codes(codes);int input_len = strlen(input);int output_index = 0;int current_code = 0;int current_len = 0;int max_len = 0;int next_index = 0;while (input[current_code] != '\0') {current_len++;next_index = next_code(codes, input[current_code]);if (next_index != -1) {current_code = next_index;} else {codes[current_code].ch = input[current_code];current_code++;current_len = 1;}if (current_len > max_len) {max_len = current_len;}if (current_len == max_len && current_code < MAX_CODE_SIZE) {output[output_index++] = codes[current_code].ch;current_code++;current_len = 0;max_len = 0;}}output[output_index] = '\0';}int main() {char input[] = "ABABABABA";char output[256];compress(input, output);printf("Compressed: %s", output);char decompressed[256];decompress(output, decompressed);printf("Decompressed: %s", decompressed);return 0;}```这个示例中，`init_codes`函数用于初始化编码表，`next_code`函数用于查找下一个编码，`compress`函数用于压缩输入字符串，`decompress`函数用于解压缩输出字符串。

lzw编码原理
LZW（Lempel-Ziv-Welch）编码是一种无损压缩算法，基于字典的压缩算法。

它的原理如下：
1. 初始化字典：创建一个初始字典，其中包含所有单个输入符号（字符）作为键，对应的编码为它们的ASCII码值。

2. 分割输入：将输入字符串分割为一个个输入符号的序列。

3. 初始化缓冲区：将第一个输入符号加入到缓冲区中。

4. 处理输入序列：从第二个输入符号开始，重复以下步骤直到处理完所有输入符号：
- 将当前输入符号与缓冲区中的符号连接，得到一个新的符号。

- 如果新的符号在字典中存在，则将其加入到缓冲区中，继续处理下一个输入符号。

- 如果新的符号不在字典中，则将缓冲区中的符号编码输出，将新的符号添加到字典中，并将新的符号作为下一个缓冲区。

5. 输出编码：当所有输入符号处理完后，将缓冲区中的符号（不包括最后一个输入符号）编码输出。

LZW编码的核心思想是使用字典记录出现过的符号及其编码，以减少编码的长度。

在处理输入序列时，如果新的符号在字典中存在，则将其添加到缓冲区，并继续处理下一个输入符号；如果新的符号不在字典中，则将缓冲区中的符号编码输出，并将新的符号添加到字典中。

由于LZW编码使用了字典记录已编码的符号，因此在解码时只需根据字典中的编码逆向查找对应的符号即可恢复原始输入序列。

LZW编码算法详解LZW(Lempel-Ziv & Welch)编码又称字串表编码，是Welch将Lemple和Ziv所提出来的无损压缩技术改进后的压缩方法。

GIF图像文件采用的是一种改良的LZW 压缩算法，通常称为GIF-LZW压缩算法。

下面简要介绍GIF-LZW的编码与解码方程解：例现有来源于二色系统的图像数据源（假设数据以字符串表示）：aabbbaabb，试对其进行LZW编码及解码。

1）根据图像中使用的颜色数初始化一个字串表（如表1），字串表中的每个颜色对应一个索引。

在初始字串表的LZW_CLEAR和LZW_EOI分别为字串表初始化标志和编码结束标志。

设置字符串变量S1、S2并初始化为空。

2）输出LZW_CLEAR在字串表中的索引3H(见表2第一行)。

3）从图像数据流中第一个字符开始，读取一个字符a，将其赋给字符串变量S2。

判断S1+S2=“a”在字符表中，则S1=S1+S2=“a”（见表2第二行）。

4）读取图像数据流中下一个字符a，将其赋给字符串变量S2。

判断S1+S2=“aa”不在字符串表中，输出S1=“a”在字串表中的索引0H，并在字串表末尾为S1+S2="aa"添加索引4H，且S1=S2=“a”（见表2第三行）。

5）读下一个字符b赋给S2。

判断S1+S2=“ab”不在字符串表中，输出S1=“a”在字串表中的索引0H，并在字串表末尾为S1+S2=“ab”添加索引5H，且S1=S2=“b”（见表2第四行）。

6）读下一个字符b赋给S2。

S1+S2=“bb”不在字串表中，输出S1=“b”在字串表中的索引1H，并在字串表末尾为S1+S2=“bb”添加索引6H，且S1=S2=“b”（见表2第五行）。

7）读字符b赋给S2。

S1+S2=“bb”在字串表中，则S1=S1+S2=“bb”（见表2第六行）。

8）读字符a赋给S2。

S1+S2=“bba”不在字串表中，输出S1=“bb”在字串表中的索引6H，并在字串表末尾为S1+S2=“bba”添加索引7H，且S1=S2=“a”（见表2第七行）。

LZW压缩算法C#源码using System;using System.IO;namespace ponents{public class LZWEncoder{private static readonly int EOF = -1;private int imgW, imgH;private byte[] pixAry;private int initCodeSize;private int remaining;private int curPixel;// GIFCOMPR.C - GIF Image compression routines//// Lempel-Ziv compression based on 'compress'. GIF modifications by// David Rowley (mgardi@)// General DEFINEsstatic readonly int BITS = 12;static readonly int HSIZE = 5003; // 80% occupancy// GIF Image compression - modified 'compress'//// Based on: compress.c - File compression ala IEEE Computer, June 1984.//// By Authors: Spencer W. Thomas (decvax!harpo!utah-cs!utah-gr!thomas)// Jim McKie (decvax!mcvax!jim)// Steve Davies (decvax!vax135!petsd!peora!srd)// Ken Turkowski (decvax!decwrl!turtlevax!ken)// James A. Woods (decvax!ihnp4!ames!jaw)// Joe Orost (decvax!vax135!petsd!joe)int n_bits; // number of bits/codeint maxbits = BITS; // user settable max # bits/codeint maxcode; // maximum code, given n_bitsint maxmaxcode = 1 << BITS; // should NEVER generate this codeint[] htab = new int[HSIZE];//这个是放hash的筒⼦,在这⾥⾯可以很快的找到1个keyint[] codetab = new int[HSIZE];int hsize = HSIZE; // for dynamic table sizingint free_ent = 0; // first unused entry// block compression parameters -- after all codes are used up,// and compression rate changes, start over.bool clear_flg = false;// Algorithm: use open addressing double hashing (no chaining) on the// prefix code / next character combination. We do a variant of Knuth's// algorithm D (vol. 3, sec. 6.4) along with G. Knott's relatively-prime// secondary probe. Here, the modular division first probe is gives way// to a faster exclusive-or manipulation. Also do block compression with// an adaptive reset, whereby the code table is cleared when the compression// ratio decreases, but after the table fills. The variable-length output// codes are re-sized at this point, and a special CLEAR code is generated// for the decompressor. Late addition: construct the table according to// file size for noticeable speed improvement on small files. Please direct// questions about this implementation to ames!jaw.int g_init_bits;int ClearCode;int EOFCode;// output//// Output the given code.// Inputs:// code: A n_bits-bit integer. If == -1, then EOF. This assumes// that n_bits =< wordsize - 1.// Outputs:// Outputs code to the file.// Assumptions:// Chars are 8 bits long.// Algorithm:// Maintain a BITS character long buffer (so that 8 codes will// fit in it exactly). Use the VAX insv instruction to insert each// code in turn. When the buffer fills up empty it and start over.int cur_accum = 0;int cur_bits = 0;int [] masks ={0x0000,0x0001,0x0003,0x0007,0x000F,0x001F,0x003F,0x007F,0x00FF,0x01FF,0x03FF,0x07FF,0x0FFF,0x1FFF,0x3FFF,0x7FFF,0xFFFF };// Number of characters so far in this 'packet'int a_count;// Define the storage for the packet accumulatorbyte[] accum = new byte[256];//----------------------------------------------------------------------------public LZWEncoder(int width, int height, byte[] pixels, int color_depth) {imgW = width;imgH = height;pixAry = pixels;initCodeSize = Math.Max(2, color_depth);}// Add a character to the end of the current packet, and if it is 254// characters, flush the packet to disk.void Add(byte c, Stream outs){accum[a_count++] = c;if (a_count >= 254)Flush(outs);}// Clear out the hash table// table clear for block compressvoid ClearTable(Stream outs){ResetCodeTable(hsize);free_ent = ClearCode + 2;clear_flg = true;Output(ClearCode, outs);}// reset code table// 全部初始化为-1void ResetCodeTable(int hsize){for (int i = 0; i < hsize; ++i)htab[i] = -1;}void Compress(int init_bits, Stream outs){int fcode;int i /* = 0 */;int c;int ent;int disp;int hsize_reg;int hshift;// Set up the globals: g_init_bits - initial number of bits//原始数据的字长,在gif⽂件中，原始数据的字长可以为1(单⾊图),4(16⾊)，和8(256⾊)//开始的时候先加上1//但是当原始数据长度为1的时候，开始为3//因此原始长度1->3,4->5,8->9//?为何原始数据字长为1的时候，开始长度为3呢？?//如果+1=2，只能表⽰四种状态，加上clearcode和endcode就⽤完了。

LZW编码的编程和实现一、实验目的编写源程序,实现LZW的编码和解码二、实验要求1.编码输入若干字母(如abbababac),输出相应的编码2.解码输入若干数字(如122473),输出相应的字母三、编程思想1.编码根缀表已知1 A2 B3 C编码分析字符串流，从词典中寻找最长匹配串，即字符串P在词典中，而字符串P+后一个字符C不在词典中此时，输出P对应的码字，将P+C放入词典中。

如第一步：输入A此时，A在表中，而AB不在表中，则输出A对应的码字1,同时将AB写入表中，此时表为1 A2 B3 C4 AB编码输出为1 (A已编码)第二步,输入B,B在词典中，而BB不在词典中，则输出2，将BB写入表中，此时表为1 A2 B3 C4 AB5 BB编码输出为12 (AB已经编码)....2.解码根缀表为1 A2 B3 C定义如下变量StringP :前一步码字流pW : StringP的第一个字符StringC :当前的码字流cW : StringC的第一个字符第一步输出StringC 并StringP = StringC如:1解码为A,则StringC = A那么输出A,并令StringP = A---------------------------------------------------------------------------第二步1.解码得到StringC,并输出StringC2.将StringP + cW放入词典(如果当前码字不在词典中,则将StringP + cP放入词典中)3.StringP = StringC如:第二步要解码为2,解码为B,则StringC=B,输出B (此时StringP = A)将StringP+cW放入表中,即将AB放入表中,此时表为1 A2 B3 C4 AB四、实验情况及分析编码解码错误提示附:源代码#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";//字根为a,b,cfor(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;//退出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;}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;}elsechar 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\ta.编码\tb.译码\n\n";cout<<"请选择：";char cha;cin>>cha;if(cha=='a'){cout<<"\n输入要编码的字符串(由a、b、c组成)："; cin>>str;code(str);}if(cha=='b'){int c[30];cout<<"\n消息序列长度是：";cin>>n;cout<<"\n消息码字依次是：";for(int i=0;i<n;i++){cin>>c[i];}decode(c);}else {cout<<"输入错误!"<<endl;} }。

实验二LZW编码算法的实现一、实验目的1、学习Matlab软件的使用和编程2、进一步深入理解LZW编码算法的原理二、实验内容阅读Matlab代码，画原理图。

三、实验原理LZW算法中，首先建立一个字符串表，把每一个第一次出现的字符串放入串表中，并用一个数字来表示，这个数字与此字符串在串表中的位置有关，并将这个数字存入压缩文件中，如果这个字符串再次出现时，即可用表示它的数字来代替，并将这个数字存入文件中。

压缩完成后将串表丢弃。

如"print"字符串，如果在压缩时用266表示，只要再次出现，均用266表示，并将"print"字符串存入串表中，在图象解码时遇到数字266，即可从串表中查出266所代表的字符串"print"，在解压缩时，串表可以根据压缩数据重新生成。

四、LZW编码的Matlab源程序及运行结果function lzw_test(binput)if(nargin<1)binput=false;elsebinput=true;end;if binputn=0;while(n==0)P=input('please input a string:','s')%提示输入界面n=length(P);end;else%Tests the special decoder caseP='Another problem on long files is that frequently the compression ratio begins...';end;lzwInput=uint8(P);[lzwOutput,lzwTable]=norm2lzw(lzwInput);[lzwOutput_decode,lzwTable_decode]=lzw2norm(lzwOutput);fprintf('\n');fprintf('Input:');%disp(P);%fprintf('%02x',lzwInput);fprintf('%s',num2str(lzwInput));fprintf('\n');fprintf('Output:');%fprintf('%02x',lzwOutput);fprintf('%s',num2str(lzwOutput));fprintf('\n');fprintf('Output_decode:');%fprintf('%02x',lzwOutput);fprintf('%s',num2str(lzwOutput_decode));fprintf('\n');fprintf('\n');for ii=257:length(lzwTable.codes)fprintf('Output_encode---Code:%s,LastCode%s+%s Length%3d\n',num2str(ii), num2str(lzwTable.codes(ii).lastCode),...num2str(lzwTable.codes(ii).c),lzwTable.codes(ii).codeLength)fprintf('Output_decode---Code:%s,LastCode%s+%s Length%3d\n',num2str(ii), num2str(lzwTable_decode.codes(ii).lastCode),...num2str(lzwTable_decode.codes(ii).c),lzwTable_decode.codes(ii).codeLength) end;function[output,table]=lzw2norm(vector,maxTableSize,restartTable)%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.%%maxTableSize can be used to set a maximum length of the table.Default%is4096entries,use Inf for ual sizes are12,14and16%bits.%%If restartTable is specified,then the table is flushed when it reaches%its maximum size and a new table is built.%%Input must be of uint16type,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-200414: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 uint8input vector and convert%to a rowif~isa(vector,'uint16'),error('input argument must be a uint16vector')Endvector=vector(:)';if(nargin<2)maxTableSize=4096;restartTable=0;end;if(nargin<3)restartTable=0;end;function code=findCode(lastCode,c)%Look up code value%if(isempty(lastCode))%fprintf('findCode:----+%02x=',c);%else%fprintf('findCode:%04x+%02x=',lastCode,c);%end;if(isempty(lastCode))code=c+1;%fprintf('%04x\n',code);return;Elseii=table.codes(lastCode).prefix;jj=find([table.codes(ii).c]==c);code=ii(jj);%if(isempty(code))%fprintf('----\n');%else%fprintf('%04x\n',code);%end;return;end;Endfunction[]=addCode(lastCode,c)%Add a new code to the tablee.c=c;%NB using variable in parent to avoid allocation coststCode=lastCode;e.prefix=[];e.codeLength=table.codes(lastCode).codeLength+1;table.codes(table.nextCode)=e;table.codes(lastCode).prefix=[table.codes(lastCode).prefix table.nextCode];table.nextCode=table.nextCode+1;%if(isempty(lastCode))%fprintf('addCode:----+%02x=%04x\n',c,table.nextCode-1);%else%fprintf('addCode:%04x+%02x=%04x\n',lastCode,c,table.nextCode-1);%end;Endfunction str=getCode(code)%Output the string for a codel=table.codes(code).codeLength;str=zeros(1,l);for ii=l:-1:1str(ii)=table.codes(code).c;code=table.codes(code).lastCode;end;Endfunction[]=newTable%Build the initial table consisting of all codes of length1.The strings%are stored as prefixCode+character,so that testing is very quick.To%speed up searching,we store a list of codes that each code is the prefix%for.e.c=0;stCode=-1;e.prefix=[];e.codeLength=1;table.nextCode=2;if(~isinf(maxTableSize))table.codes(1:maxTableSize)=e;%Pre-allocate for speedElsetable.codes(1:65536)=e;%Pre-allocate for speedend;for c=1:255e.c=c;stCode=-1;e.prefix=[];e.codeLength=1;table.codes(table.nextCode)=e;table.nextCode=table.nextCode+1;end;End%%Main loop%e.c=0;stCode=-1;e.prefix=[];e.codeLength=1;newTable;output=zeros(1,3*length(vector),'uint8');%assume compression of33%outputIndex=1;lastCode=vector(1);output(outputIndex)=table.codes(vector(1)).c;outputIndex=outputIndex+1;character= table.codes(vector(1)).c;、、tic;for vectorIndex=2:length(vector),%if mod(vectorIndex,1000)==0%fprintf('Index:%5d,Time%.1fs,Table Length%4d,Complete%.1f%%\n', outputIndex,toc,table.nextCode-1,vectorIndex/length(vector)*100);%*ceil(log2(size(table, 2)))/8);%tic;%end;element=vector(vectorIndex);if(element>=table.nextCode)%add codes not in table,a special case.str=[getCode(lastCode)character];else,str=getCode(element);Endoutput(outputIndex+(0:length(str)-1))=str;outputIndex=outputIndex+length(str);if((length(output)-outputIndex)<1.5*(length(vector)-vectorIndex))output=[output zeros(1,3*(length(vector)-vectorIndex),'uint8')];end;if(length(str)<1)keyboard;end;character=str(1);if(table.nextCode<=maxTableSize)addCode(lastCode,character);if(restartTable&&table.nextCode==maxTableSize+1)%fprintf('New table\n');newTable;end;end;lastCode=element;end;output=output(1:outputIndex-1);table.codes=table.codes(1:table.nextCode-1);Endfunction[output,table]=norm2lzw(vector,maxTableSize,restartTable)%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.%maxTableSize can be used to set a maximum length of the table.Default%is4096entries,use Inf for ual sizes are12,14and16%bits.%If restartTable is specified,then the table is flushed when it reaches%its maximum size and a new table is built.%Input must be of uint8type,while the output is a uint16.%Table is a cell array,each element containing 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-200414:16:08$%Revision:%Change the code table structure to improve the performance.%date:22-Apr-2007%by:Haiyong Xu%Rework the code table completely to get reasonable performance.%date:24-Jun-2007%by:Duncan Barclay%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 uint8input vector and convert%to a double row to make maths workif~isa(vector,'uint8'),error('input argument must be a uint8vector')Endvector=double(vector(:)');if(nargin<2)maxTableSize=4096;restartTable=0;end;if(nargin<3)restartTable=0;end;function code=findCode(lastCode,c)%Look up code value%if(isempty(lastCode))%fprintf('findCode:----+%02x=',c);%else%fprintf('findCode:%04x+%02x=',lastCode,c);%end;if(isempty(lastCode))code=c+1;%fprintf('%04x\n',code);return;Elseii=table.codes(lastCode).prefix;jj=find([table.codes(ii).c]==c);code=ii(jj);%if(isempty(code))%fprintf('----\n');%else%fprintf('%04x\n',code);%end;return;end;code=[];return;Endfunction[]=addCode(lastCode,c)%Add a new code to the tablee.c=c;%NB using variable in parent to avoid allocation coststCode=lastCode;e.prefix=[];e.codeLength=table.codes(lastCode).codeLength+1;table.codes(table.nextCode)=e;table.codes(lastCode).prefix=[table.codes(lastCode).prefix table.nextCode];table.nextCode=table.nextCode+1;%if(isempty(lastCode))%fprintf('addCode:----+%02x=%04x\n',c,table.nextCode-1);%else%fprintf('addCode:%04x+%02x=%04x\n',lastCode,c,table.nextCode-1);%end;Endfunction[]=newTable%Build the initial table consisting of all codes of length1.The strings%are stored as prefixCode+character,so that testing is very quick.To%speed up searching,we store a list of codes that each code is the prefix%for.e.c=0;stCode=-1;e.prefix=[];e.codeLength=1;table.nextCode=2;if(~isinf(maxTableSize))table.codes(1:maxTableSize)=e;%Pre-allocate for speedElsetable.codes(1:65536)=e;%Pre-allocate for speedend;for c=1:255e.c=c;stCode=-1;e.prefix=[];e.codeLength=1;table.codes(table.nextCode)=e;table.nextCode=table.nextCode+1;end;End%%Main loop%e.c=0;stCode=-1;e.prefix=[];e.codeLength=1;newTable;output=vector;outputIndex=1;lastCode=[];tic;for index=1:length(vector),%if mod(index,1000)==0%fprintf('Index:%5d,Time%.1fs,Table Length%4d,Ratio%.1f%%\n',index,toc, table.nextCode-1,outputIndex/index*100);%*ceil(log2(size(table,2)))/8);%tic;%end;code=findCode(lastCode,vector(index));if~isempty(code)lastCode=code;Elseoutput(outputIndex)=lastCode;outputIndex=outputIndex+1;%fprintf('output****:%04x\n',lastCode);if(table.nextCode<=maxTableSize)addCode(lastCode,vector(index));if(restartTable&&table.nextCode==maxTableSize+1)%fprintf('New table\n');newTable;end;end;lastCode=findCode([],vector(index));end;end;output(outputIndex)=lastCode;output((outputIndex+1):end)=[];output=uint16(output);table.codes=table.codes(1:table.nextCode-1);End五、运行结果1、请写下实验结果Input:111111111111111111111111111111111111111111111111111111111111111111111111111111 Output:?????????????????????????????Input:123123123123123123123123123123123123123123123123123123123123123123123 Output:?????????????????????????????2、请在实验代码中加入计算压缩比例的代码，并显示上述两种输入的不同压缩比。