LZW算法详解

偏执的太偏执、 2023-06-27 05:47 2阅读 0赞

# 1. LZW算法简介 #

LZW算法又叫“串表压缩算法”就是通过建立一个字符串表，用较短的代码来表示较长的字符串来实现压缩，是一种无损压缩算法。  
LZW压缩有三个重要的对象：数据流（CharStream）、编码流（CodeStream）和编译表（String Table）。在编码时，数据流是输入对象（文本文件的据序列），编码流就是输出对象（经过压缩运算的编码数据）；在解码时，编码流则是输入对象，数据流是输出对象；而编译表是在编码和解码时都须要用借助的对象。  
其中在编码和解码时编译表（下面称为字典），是中间产物，在编码和解码后删除即可。

# 2. LZW编码算法手动模拟 #

现在我们先假设一个简单的场景以便我们理解，假设我们现在对 **ILOVEYOUILOVEYOU** 这一串只有 大写字母A-Z的序列进行压缩。  
因为这段序列中只有字母A-Z那么我们只需要下面这个字典就可以一定可以编码这个序列。

现在我们设想如果字典里有我们要编码的序列的子序列的话，例如字典中有（27，“YOU”）这一项，那么我们编码序列的长度与原来相比肯定更优，LZW就是基于这一思想，下面我们具体看看。

*  **Current** 表示当前编码的子序列。子序列选取的标准，**例如对“IL“进行编码，字典中有条目（1，”I“）和（2，”L“），（3，”IL“）这时，依据字典编码有两种编码方式一种是12，一种是3，我们选取的标准就是，从字典中选取最长的编码序列对子序列进行编码。**
 *  Next表示Current的后一个字符
 *  Code 是序列的编码。
 *  Insert（Code，Seq）是向字典中插入一条数据。

<table> 
 <thead> 
  <tr> 
   <th>Current</th> 
   <th>Next</th> 
   <th>Code</th> 
   <th>Insert(Code,Seq)</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>I</td> 
   <td>L</td> 
   <td>09</td> 
   <td>（27，IL）</td> 
  </tr> 
  <tr> 
   <td>L</td> 
   <td>O</td> 
   <td>12</td> 
   <td>（28，LO）</td> 
  </tr> 
  <tr> 
   <td>O</td> 
   <td>V</td> 
   <td>15</td> 
   <td>（29，OV）</td> 
  </tr> 
  <tr> 
   <td>V</td> 
   <td>E</td> 
   <td>22</td> 
   <td>（30，VE）</td> 
  </tr> 
  <tr> 
   <td>E</td> 
   <td>Y</td> 
   <td>05</td> 
   <td>（31，EY）</td> 
  </tr> 
  <tr> 
   <td>Y</td> 
   <td>O</td> 
   <td>25</td> 
   <td>（32，YO）</td> 
  </tr> 
  <tr> 
   <td>O</td> 
   <td>U</td> 
   <td>15</td> 
   <td>（33，OU）</td> 
  </tr> 
  <tr> 
   <td>U</td> 
   <td>I</td> 
   <td>21</td> 
   <td>（34，UI）</td> 
  </tr> 
  <tr> 
   <td><strong>IL</strong></td> 
   <td>O</td> 
   <td>27</td> 
   <td>（35，ILO）</td> 
  </tr> 
  <tr> 
   <td>OV</td> 
   <td>E</td> 
   <td>29</td> 
   <td>（36，OVE）</td> 
  </tr> 
  <tr> 
   <td>EY</td> 
   <td>O</td> 
   <td>31</td> 
   <td>（37，EYO）</td> 
  </tr> 
  <tr> 
   <td>OU</td> 
   <td>结束</td> 
   <td>33</td> 
   <td></td> 
  </tr> 
 </tbody> 
</table>

Code序列就是编码序列。不难看出，假设我们对每个字符用1B进行编码，那么**ILOVEYOUILOVEYOU**序列总共需要16B，若采用LZW压缩算法，那么只需要12B就可以进行编码，只不过压缩时需要维护一个字典，牺牲了空间，但是传输过程不需要传输字典，字典在解码过程中重新生成即可。

# 3. LZW解码过程手动模拟 #

只要大家看懂上面的编码过程以后，解码过程一目了然。

*  **Code**: 表示编码序列
 *  **Prev**: 表示当前解码出来的字符串的上一个字符串。
 *  **Text**: 表示解码的字符串。
 *  **Insert(Code, Seq)**: 表示向字典中插入一条数据，字典中初始数据是1至26对应‘A’-‘Z’。

<table> 
 <thead> 
  <tr> 
   <th>Code</th> 
   <th>Prev</th> 
   <th>Text</th> 
   <th>Insert(Code,Seq)</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>9</td> 
   <td>无</td> 
   <td>I</td> 
   <td>无</td> 
  </tr> 
  <tr> 
   <td>12</td> 
   <td>I</td> 
   <td>L</td> 
   <td>(27,“IL”)</td> 
  </tr> 
  <tr> 
   <td>15</td> 
   <td>L</td> 
   <td>O</td> 
   <td>(28,“LO”)</td> 
  </tr> 
  <tr> 
   <td>22</td> 
   <td>O</td> 
   <td>V</td> 
   <td>(29,“OV”)</td> 
  </tr> 
  <tr> 
   <td>5</td> 
   <td>V</td> 
   <td>E</td> 
   <td>(30,“VE”)</td> 
  </tr> 
  <tr> 
   <td>25</td> 
   <td>E</td> 
   <td>Y</td> 
   <td>(31,“EY”)</td> 
  </tr> 
  <tr> 
   <td>15</td> 
   <td>Y</td> 
   <td>O</td> 
   <td>(32,“YO”)</td> 
  </tr> 
  <tr> 
   <td>21</td> 
   <td>O</td> 
   <td>U</td> 
   <td>(33,“OU”)</td> 
  </tr> 
  <tr> 
   <td>27</td> 
   <td>U</td> 
   <td>IL</td> 
   <td>(34,“UI”)</td> 
  </tr> 
  <tr> 
   <td>29</td> 
   <td>IL</td> 
   <td>OV</td> 
   <td>(35,“ILO”)</td> 
  </tr> 
  <tr> 
   <td>31</td> 
   <td>OV</td> 
   <td>EY</td> 
   <td>(36,“OVE”)</td> 
  </tr> 
  <tr> 
   <td>33</td> 
   <td>EY</td> 
   <td>OU</td> 
   <td>(37,“EYO”)</td> 
  </tr> 
 </tbody> 
</table>

# 4. 简单实现LZW编码解码过程的C++代码 #

#include <iostream>
    #include <string>
    #include <cstring>
    
    #define NotExist -1
    #define MaxSize 1000
    
    using namespace std;
    
    typedef struct Dictionary{
        
    	char	**seq;		// 字符串集合
    	int		*code;		// 字符串编码的集合
    	int		size;		// 字典的大小
    	int		maxsize;	// 字典的最大长度
    }Dictionary, *PDictionary;
    
    // 向字典中插入一条数据
    void insert_seq(PDictionary dict, int code, char* seq)
    {
        
    	if (dict->size == dict->maxsize){
        
    		printf("字典已满，插入失败!");
    		return;
    	}
    	int i = dict->size;
    	dict->code[i] = code;
    	dict->seq[i] = (char*)malloc(sizeof(char) * strlen(seq) + 1);
    	strcpy(dict->seq[i], seq);
    	dict->size++;
    	return;
    }
    
    // 初始化字典
    void initDict(PDictionary dict, int maxsize)
    {
        
    	dict->maxsize = maxsize;
    	dict->size = 0;
    	dict->code = (int*)malloc(sizeof(int) * maxsize);
    	dict->seq = (char**)malloc(sizeof(char*) * maxsize + 1);
    
    	// 初始化时先放入‘A’~‘Z’
    	char seq[2] = "A";
    	for (int i = 0; i < 26; i++){
        
    		insert_seq(dict, i, seq);
    		seq[0]++;
    	}
    	return;
    }
    
    // 打印字典
    void print_dict(PDictionary dict)
    {
        
    	printf("===================\n");
    	printf("Code            Seq\n");
    	for (int i = 0; i < dict->size; i++)
    	{
        
    		printf("%4d%7s\n", dict->code[i], dict->seq[i]);
    	}
    	return;
    }
    
    // 查找字典中有无seq
    int is_exist_seq(PDictionary dict, char *seq)
    {
        
    	for (int i = 0; i < dict->size; i++)
    	{
        
    		if (strcmp(seq, dict->seq[i]) == 0){
        
    			return dict->code[i];
    		}
    	}
    	return NotExist;
    }
    
    // 根据编码查找Seq
    char* find_seq(PDictionary dict, int code)
    {
        
    	return dict->seq[code];
    }
    
    // LZW编码
    void lzw_encode(PDictionary dict, char* text)
    {
        
    	char cur[MaxSize];
    	char next;
    	int code;
    	char seq[MaxSize];
    	int i = 0;
    	int len = strlen(text);
    	while (i < len)
    	{
        
    		sprintf(cur, "%c", text[i]);
    		
    		while (is_exist_seq(dict, cur) != NotExist && i < len)
    		{
        
    			i++;
    			sprintf(cur, "%s%c", cur, text[i]);
    		}
    		
    		if (i < len) {
        
    			insert_seq(dict, dict->size, cur);
    			cur[strlen(cur) - 1] = '\0';
    		}
    		code = is_exist_seq(dict, cur);
    		printf("%d,", code, cur);
    	}
    	return;
    }
    
    // LZE解码
    void lzw_decode(PDictionary dict, int *code, int size)
    {
        
    	char *pre = NULL;
    	int i = 0;
    	char str[MaxSize];
    
    	while (i < size)
    	{
        
    		strcpy(str, find_seq(dict, code[i]));
    		printf("%s", str);
    		if (pre != NULL)
    		{
        
    			char tmp[MaxSize];
    			sprintf(tmp, "%s%c", pre, str[0]);
    			insert_seq(dict, dict->size, tmp);
    		}
    		pre = (char*)malloc(sizeof(char) * strlen(str) + 1);
    		strcpy(pre, str);
    		i++;
    	}
    	printf("\n");
    	return;
    }
    
    int main()
    {
        
    	Dictionary dict;
    	int code[] = {
         8, 11, 14, 21, 4, 24, 14, 20, 26, 28, 30, 32, 3, 14, 31, 20, 27, 29, 12, 4, 38, 40, 42, 4, 44 };
    	int size = 25;
    
    	initDict(&dict, MaxSize);
    	//lzw_encode(&dict, "ILOVEYOUILOVEYOUDOYOULOVEMEDOYOULOVEME");
    	lzw_decode(&dict, code, size);
    	//print_dict(&dict);
    	return 0;
    }