詞典編碼是指用符號代替一串字元，在編碼中僅僅把字元串看成是一個號碼，而不去管它來表示什麼意義，1977年由兩位以色列教授發明，1985年美國Wekch對該算法進行了改進。
基本介紹
- 中文名：詞典編碼
- 發明時間：1977年
- 國籍：以色列
- 基本思想：用符號代替一串字元
- 改進時間：1985年
- 代碼位數：9位，10位，11位，12位
簡介,算法步驟,編碼步驟,解碼步驟,算法舉例,
簡介
詞典編碼 包括 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 : \n");
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 \n",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("\n Please input the codestream number:");
scanf("%d",&k);
printf("\n Please input the codestream number:");
for(i=0;i<k;i++)
scanf("%d",(code+i));
cW=code[0];
printf("\n output the wordstream:%s",word[cW].w);
pW=cW;
for(i=1;i<k;i++)
{
cW=code[i];
if(cW<j)
{
printf("\n 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("\n output the wordstream: %s",p);
j=j+1;
pW=cW;
}
}
for(i=1;i<j;i++)
printf("\n The dictionary is %s",word[i].w);
printf("\n this is over\n");
}
