本文主要是介绍[原创]用哈希表优化的lz77压缩算法的实现，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
最近终于有空研究研究E*F的K*KYU2。
和预料到的一样仍然是广泛使用LZ77，而且是毫不改变地使用LZ77……但是，时代进步了，图片文件都是真彩色的了，大小变大了3倍，仍然使用LZ77的代价就是速度……大家都知道LZ77的特点就是解压超快，压缩巨慢（不然就不会有LZW这种不伦不类的算法出来了……）
在png的相关网站上查找了一下优化方案，自己写了一下优化代码，虽然目前速度仍然不能很让人满意（在双核的机器上压缩一个160多兆的文件用了60多秒），但是勉强可以用于实际应用了。贴出来和大家分享。如果要进一步优化，估计要玩一些trick，或是借助于指令级别的。
以下讨论是基于4096字节定长窗口的字典的LZ77，字节组织是每bit表示查表或是原数据；查表是2字节，前16位表示索引，后16位表示长度，因此最长的序列只能有15字节。优化的思路是哈希表。
由环境可以看出，低于3个字节的码序列是不需要查表保存的，因此码的最短长度是3个字节。使用一个哈希算法将之转化成1个字节的哈希码。这种哈希码共有256个。当在查表前，首先要计算出当前字节及后面两个字节组成的序列的哈希码，然后在哈希码表中查得第一条匹配记录。当然，即使哈希码匹配，3字节并不一定完全一样，这之后还是需要按字节比较。但这可以提前淘汰大部分的数据。匹配后，再查下一条记录。
优化的负担是额外增加了一个哈希码头指针表和一个链表。每一个字节在字典中的更新都会造成它本身及前面两个字节处共3个字节的哈希码变化，即表项删除和增加。为了使这种删除和增加更有效率，做成了双向链表的形式（实际测试下来比单向节省约一半时间）。当然这里的链表是以数组形式实现的，不需要动态分配空间，否则所带来的负担将是不可承受的。字典定义如下：
typedef struct _tagLz77Dict ... {
int hash_start[256]; int hash_next[4096]; int hash_prev[4096]; char dict[4096];
} lz77_dict, * p_lz77_dict;
其中，hash_start是256个哈希码的首码索引。hash_next是每个哈希码的下一个编码，hash_prev是每个哈希码的前一个编码。均以-1表示无效。
字典初始化函数如下：
void init_dict(p_lz77_dict pdic) ... { int i; memset(pdic->dict, 0, 4096); for (i = 0; i < 256; ++i) pdic->hash_start[i] = -1; pdic->hash_start[HASH(0, 0, 0)] = 4096-16;
for (i = 0; i < 4096; ++i) ...{ if (i < 4096-16) ...{ pdic->hash_next[i] = -1; pdic->hash_prev[i] = -1; } else ...{ pdic->hash_next[i] = (i+1); pdic->hash_prev[i] = (i-1);
} } pdic->hash_prev[0] = -1; pdic->hash_next[4095] = -1;} 初始值仅后面16个码可用。
删除和增加哈希码函数：
void remove_dict_pos(p_lz77_dict pdic, int pos) ... { char a, b, c; unsigned char hash;这篇关于[原创]用哈希表优化的lz77压缩算法的实现的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
