字典编码编程

《字典编码编程》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、1.         词典编码主要利用数据本身包含许多重复的字符串的特性。例如：吃葡萄不吐葡萄皮，不吃葡萄倒吐葡萄皮。我们如果用一些简单的代号代替这些字符串，就可以实现压缩，实际上就是利用了信源符号之间的相关性。字符串与代号的对应表就是词典。2.         实用的词典编码算法的核心就是如何动态地形成词典，以及如何选择输出格式以减小冗余。3.      字典压缩编码是一种无损的数据压缩技术。它只是对数据的冗余信息进行压缩。4.      LZ78的编码思想是不断地从字符流中提取新的字符串(String)，通俗地理解为新“

2、词条”，然后用“代号”也就是码字(Codeword)表示这个“词条”。这样一来，对字符流的编码就变成了用码字(Codeword)去替换字符流(Charstream)，生成码字流(Codestream)，从而达到压缩数据的目的。LZ78编码器的输出是码字-字符(W,C)对(当W为0时，表示在词典中找不到相应的码字，直接输出该字符，也正因为如此，词典的索引号要从1开始)，每次输出一对到码字流中，与码字W相对应的字符串(String)用字符C进行扩展生成新的字符串(String)，然后添加到词典中。     程序实现：//////

3、/////////////////////////////压缩部分：///////////////////////////////////////////////////////注：码字流将会输出到另外一个新建的文本里，该文本格式是：前面sizeof(unsignedshort)个字节存放的是字典的大小值（以便解压时用来确定动态建立的字典的大小）。紧接下来就是所有的码字对。码字对格式（index,c）,其中，index表示字典的下标，其对应一个字符串，当index=0时，表示该码字只对应一个字符 c。////////////

4、////////////////////////////////////////////////////本程序为LZ8字典压缩算法的C实现//适合压缩英文文章，即文章中只有英文字母、数字和其它键盘符号（包括标点符号），不适用于中文文本#include#include#include#include#define MAXINDEXES65535  #define MAXBUFFER_IN 256unsignedintbufin_count,in=0;/

5、/inisthepointertoinputbufferstructindexes_node{ ////用于构建一级索引的结点 unsignedshortindexes[8]; indexes_node*next; voidinitNode(){  next=NULL;  for(inti=0;i<8;i++)   indexes[i]=0; }};structindexes_node*index_level1[256]={NULL};//storingallASCII //97typesofcharsinacommontx

6、tfile(ASCII:32~126++t)index_level1[]为一级索引，以提高查找速度char*dictionary[MAXINDEXES]={NULL}; //dictionarystructureunsignedshortp=1;//pointingtoanelementwhichisuptobeusednexttimeindictionary[]arraycharbuffer_in[MAXBUFFER_IN]; //inputbufferblockcharch[2]={''},s[30]={'

7、'};//workingmemory ch[]storesthecurrentcharintheinputbufferands[]storesthecurrentlemmaunsignedshorttmp_index,index=0;//tmp_indexindicatesthelocationofs[]inthedictionary,indexisthelocationofpre-s[]inthedictionaryunsignedshortfind_lemma(char*);//ifitfindsamatchedstri

8、ng,thenitreturnstheindexofthestringinthearrayelsereturns0intinsert_dictionary(char *);//insertanewlemmaintothedictionaryandupdatetheindex_level1[