步骤五历史

算法步骤(编码步骤 译码步骤)

算法举例(C语言)

步骤五历史

词典编码 即 LZW编码 是1977年有两位以色列教授发明 Lempel-Ziv压缩技术。并在1985年有美国的Wekch将此技术实用化。

其基本思想是 用符号代替一串字符；这一串字符可以是有意义的，也可以是无意义的。在编码中仅仅把字符串看成是一个号码，而不去管它来表示什么意义。

此压缩技术是围绕词典的转换来完成，这个词典实际是8位ASCII字符集进行了扩充。扩充后的代码有，9位，10位，11位，12位，乃至更多。12位的代码可以有4096个不同的代码。

算法步骤

编码步骤

步骤一：开始的时候词典包含所有可能的单字符，而当前前缀P是空的。

步骤二：当前字符C：=字符流中的下一个字符。

步骤三：判断P+C是否在词典中。

如果是，则用C扩展P，即P=P+C

如果否，则

①输出代表当前前缀P的码字

②将前缀-字符串P+C添加到字典中

③令P：=C

步骤四：判断字符流中是否还有字符需要编码。

如果是，则返回到步骤二

如果不是，输出代表当前前缀P的码字，并结束

译码步骤

步骤一：在开始译码时词典包含所有可能的前缀根。

步骤二：cW：=码字流中的第一个码字。

步骤三：输出当前缀符串string.cW到字符流。

步骤四：先前码字pW：=当前码字cW.

步骤五：当前码字cW:=码字流中的下一个码字。

步骤六：判断先前缀符串是否在词典中。

如果“是”，则：1把当前缀符串string.cW输出到字符流；2当前前缀p:=先前缀符串pW;3当前前缀符串string.cW的第一个字符；4把缀符串P+C添加到词典中。

如果“否”，则：1当前前缀p:=先前缀符串pW;2当前字符C：=当前缀符串pW的第一个字符；3输出缀符串P+C到字符流，然后把它添加到词典中。

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

如果“是”，就返回到步骤4，如果“否”，结束。

算法举例

C语言

//编码

# include<stdio.h>

# include<string.h>

//拷贝字符串

void copy1(char *prefix,char *s,int i,int j)

{

int k;

for(k=0;k<20;k++)

prefix[k]='\\0';

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

prefix[k-i]=s[k];

}

void main ()

{

char s[30],prefix[30],dic[20][30]={"","A","B","C"};

int i,j,k,m,n;

i=0;j=1;k=4;m=0;

printf("please input string : \");

gets(s);

while(i<strlen(s))

{

copy1(prefix,s,i,j);

for(n=1;n<k;n++)

{

if(strcmp(prefix,dic[n])==0)

{

j=j+1;

m=n;

if((i+j)<=strlen(s))

copy1(prefix,s,i,j);

else

{

strcpy(prefix, " ");

}

}

}

printf("%d ",m);

if(strlen(prefix)!=0)

{

strcpy(dic[k],prefix);

printf("%s \",dic[k]);

}

k=k+1;

i=i+j-1;

j=1;

}

}

//译码

# include<stdio.h>

# include<string.h>

# define N 20 // The max string length

# define M 20 //The max codestream number in the dictionary

# define L 20

struct wordstream

{

char w[N];

}word[L];

void main()

{

int code[M];//存贮码字流

//int code[]={1,2,3,4,7,3};

int i,k,t;

int j;//词典中缀符串

int cW;//当前码字

int pW;//先前码字

unsigned char C;//当前字符

char p[20];//缀-符串

word[1].w[0]='A';//输入词典的初始化

word[2].w[0]='B';

word[3].w[0]='C';

j=4;

//输出需要译码的码字流

printf("\ Please input the codestream number:");

scanf("%d",&k);

printf("\ Please input the codestream number:");

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

scanf("%d",(code+i));

cW=code[0];

printf("\ output the wordstream:%s",word[cW].w);

pW=cW;

for(i=1;i<k;i++)

{

cW=code[i];

if(cW<j)

{

printf("\ output the wordstream:%s",word[cW].w);//输出到字符流

C=word[cW].w[0];

strcpy(p,(const char *)word[pW].w);

t=strlen((const char *)p);

p[t]=C;

p[t+1]='\\0';

strcpy(word[j].w,(const char*)p);

j=j+1;

pW=cW;

}

else

{

strcpy(p,(const char *)word[pW].w);

C=word[pW].w[0];

t=strlen((const char *)p);

p[t]=C;

p[t+1]='\\0';

strcpy(word[j].w,(const char *)p);

printf("\ output the wordstream: %s",p);

j=j+1;

pW=cW;

}

}

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

printf("\ The dictionary is %s",word[i].w);

printf("\ this is over\");

}