字典编码编程.docx

1. 词典编码主要利用数据本身包含许多重复的字符串的特性。例如：吃葡萄不吐葡萄皮，不吃葡萄倒吐葡萄皮。 我们如果用一些简单的代号代替这些字符串，就可以实现压缩，实际上就是利用了信源符号之间的相关性。字符串与代号的对应表就是词典。2. 实用的词典编码算法的核心就是如何动态地形成词典，以及如何选择输出格式以减小冗余。3. 字典压缩编码是一种无损的数据压缩技术。它只是对数据的冗余信息进行压缩。4. LZ78的编码思想是不断地从字符流中提取新的字符串(String)，通俗地理解为新“词条”，然后用“代号”也就是码字(Code word)表示这个“词条”。这样一来，对字符流的编码就变成了用码字(Code word)去替换字符流(Char stream)，生成码字流(Code stream)，从而达到压缩数据的目的。LZ78编码器的输出是码字-字符(W,C)对(当W为0时，表示在词典中找不到相应的码字，直接输出该字符，也正因为如此，词典的索引号要从1开始)，每次输出一对到码字流中，与码字W相对应的字符串(String)用字符C进行扩展生成新的字符串(String)，然后添加到词典中。程序实现：/压缩部分：/注：码字流将会输出到另外一个新建的文本里，该文本格式是：前面sizeof(unsigned short)个字节存放的是字典的大小值（以便解压时用来确定动态建立的字典的大小）。紧接下来就是所有的码字对。码字对格式（index,c）,其中，index表示字典的下标，其对应一个字符串，当index=0时，表示该码字只对应一个字符c。/本程序为LZ8字典压缩算法的C实现/适合压缩英文文章，即文章中只有英文字母、数字和其它键盘符号（包括标点符号），不适用于中文文本#include #include #include #include #define MAXINDEXES 65535#define MAXBUFFER_IN 256unsigned int bufin_count,in=0; /in is the pointer to input bufferstruct indexes_node /用于构建一级索引的结点unsigned short indexes8;indexes_node* next;void initNode()next=NULL;for(int i=0; i); scanf(%s,infilename); if(!(fp_in=fopen(infilename,r) printf(Cant not find the txtfile!n);elsebreak; while(1) printf(Please input the path for the outfile(including outfile name)-); scanf(%s,outfilename); if(!(fp_out=fopen(outfilename,wb) printf(Memory is not enough!n);elsebreak; fwrite(&sizeofdictionary,1,sizeof(unsigned short),fp_out); while(!feof(fp_in) bufin_count=fread(buffer_in,1,MAXBUFFER_IN,fp_in);in=0;while(inbufin_count)ch0=buffer_inin;in+;slen+=ch0; tmp_index=find_lemma(s); /the processor is much too time-consumingif(tmp_index!=0) /matching index=tmp_index;continue;/ tmp_index=0: no matchinginsert_dictionary(s);fwrite(&index,1,sizeof(unsigned short),fp_out); fwrite(ch,1,sizeof(char),fp_out); index=0;len=0; for(int k=0;k30;k+) sk=0;if(index) /表示能匹配下去但输入缓冲中已无字符了slen-1=0;index=find_lemma(s); fwrite(&index,1,sizeof(unsigned short),fp_out); fwrite(ch,1,sizeof(char),fp_out);rewind(fp_out);fwrite(&p,1,sizeof(unsigned short),fp_out);fclose(fp_out);fclose(fp_in);printf(The LZ78 algorithm has done the compression successfully!nn); scanf(%d,&len); /in order to let the outwindow pause! return 0;int insert_dictionary(char *lemma)unsigned short length=strlen(lemma);struct indexes_node *pnext; unsigned short i,j;if(pMAXINDEXES)if( !( dictionaryp=(char*)malloc(length+1) ) )printf(Allocation err!n);return 0;for(j=0;jlength+1;j+)dictionarypj=0;strcpy(dictionaryp,lemma);p+;else /字典已满而待压缩数据还没有结束的情况，此时直接输出码字而不插入字典return -1; /indicating the dictionary is full/TODO: update the index_level1,find the index i for c i=lemma0;if(i255)printf(Error!nsome Chinese words or marks in the following txt:n=n%sn,buffer_in);exit(0);if(index_level1i=NULL)index_level1i=(struct indexes_node *)malloc(sizeof(indexes_node);index_level1i-initNode(); index_level1i-indexes0=p-1;else pnext=index_level1i; while(pnext-next)pnext=pnext-next; j=0;while(jindexesj=0)break;j+; if(j=8) /the node is full pnext-next=(struct indexes_node *)malloc(sizeof(indexes_node); pnext-next-initNode();pnext-next-indexes0=p-1;elsepnext-indexesj=p-1; return 1; /insert successfullyunsigned short find_lemma(char * tmp_lemma)unsigned short length=strlen(tmp_lemma);struct indexes_node *pnext; unsigned short i,j;if(length0)i=tmp_lemma0;if(i255) printf(Error!nsome Chinese words or marks in the following txt:n=n%sn,buffer_in); exit(0); pnext=index