-
詞典編碼
鎖定
詞典編碼是指用符號代替一串字符,在編碼中僅僅把字符串看成是一個號碼,而不去管它來表示什麼意義,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"); }