12bit LZW压缩算法的实现问题

john_he

自己根据Wikipedia上的算法框架东拼西凑，外加参考了某些游戏引擎写了个实现，勉强能运行不过速度实在是!@$#%……请问有没有现成的实现可以参考？或者能对我的算法给点意见吗？

压缩算法：

2. int *build_next_table(const unsigned char *s, int n, int *t)
3. {
4.     int i = 2;
5.     int j = 0;
7.     t[0] = -1;
8.     t[1] = 0;
10.     while (i < n)
11.     {
12.         if (s[i-1] == s[j])
13.             t[i++] = ++j;
14.         else if (j > 0)
15.             j = t[j];
16.         else
17.             t[i++] = 0;
18.     }
20.     return t;
21. }
24. int kmp_match_mask(const unsigned char *s, int ls, int *t, const unsigned char *dic, int dic_start, int dic_pos, size_t dic_mask, int *match_len)
25. {
26.     int m = dic_start;
27.     int i = 0;
28.     int max_l = 0;
29.     int max_ptr = -1;
31.     build_next_table(s, ls, t);
33.     do
34.     {
35.         if (s[i] == dic[(m+i) & dic_mask] && ((m+i) & dic_mask) != dic_pos)
36.         {
37.             i++;
38.             if (i > max_l)
39.             {
40.                 max_l = i;
41.                 max_ptr = m;
42.                 if (max_l == ls)
43.                     break;
44.             }
45.         }
46.         else
47.         {
48.             m = (m + i - t[i]) & dic_mask;
49.             if (i>0) i = t[i];
50.         }
51.     } while (((m+i) & dic_mask) != dic_start);
53.     *match_len = max_l;
54.     return max_ptr;
55. }
58. size_t LZW_Compress(const unsigned char *src, unsigned char *dest, size_t size)
59. {
60.     size_t src_off = 0;
61.     size_t dest_off = 0;
62.     size_t dic_pos = 0xFEE;
63.     int dic_size = 18;
64.     unsigned char dic[0x1000];
65.     unsigned char *out_buf;
66.     int out_pos, s_len;
67.     int i,j;
68.     int next_table[18];
69.     int match_len, dic_ref;
71.     memset(dic, 0, 0x1000);
73.     while (src_off < size)
74.     {
75.         out_buf = dest+dest_off;
76.         out_buf[0] = 0;
77.         out_pos = 1;
79.         for (i=0; i<8; i++)
80.         {
81.             s_len = size-src_off;
82.             if (s_len <= 0) break;
83.             if (s_len > 18) s_len = 18;
85.             dic_ref = kmp_match_mask(src+src_off, s_len, next_table, dic, 0xFED, dic_pos, 0xFFF, &match_len);
86.             
87.             if (match_len < 3)
88.             {
89.                 out_buf[0] |= (1 << i);
90.                 out_buf[out_pos++] = dic[dic_pos++] = src[src_off++];
91.                 dic_pos &= 0xFFF;
92.                 if (dic_size < 0x1000) dic_size++;
93.             }
94.             else
95.             {
96.                 out_buf[out_pos++] = dic_ref & 0xFF;
97.                 out_buf[out_pos++] = ((dic_ref & 0xF00) >> 4) | ((match_len - 3) & 0xF);
98.                 for (j=0; j<match_len; j++)
99.                 {
100.                     dic[dic_pos++] = src[src_off++];
101.                     dic_pos &= 0xFFF;
102.                     if (dic_size < 0x1000) dic_size++;
103.                 }
104.             }   
105.         }
106.         dest_off += out_pos;
107.     }
109.     return dest_off;
110. }

复制代码

以上算法是根据Wikipedia上面的框架自己写的，字符串匹配算法用了KMP。


解压算法：

2. size_t LZW_Decompress(const unsigned char *src, unsigned char *dest, size_t src_size, size_t dest_size)
3. {
4.     size_t src_off = 0;
5.     size_t dest_off = 0;
6.     size_t dic_pos = 0xFEE;
7.     unsigned char dic[0x1000];
8.     size_t var_1010 = 0;
9.     size_t var_1008;
10.    
11.     memset(dic, 0, 0x1000);
12.    
13.     while (src_off < src_size)
14.     {
15.         var_1010 >>=1;
16.         if ((var_1010 & 0x0100) == 0)
17.         {
18.             var_1010 = src[src_off++] | 0xFF00;
19.         }
21.         if ((var_1010 & 0x0001) != 0)
22.         {
23.             if (dest_off >= dest_size) return dest_off;
24.             dest[dest_off++] = dic[dic_pos++] = src[src_off++];
25.             dic_pos &= 0xFFF;
26.         }
27.         else
28.         {
29.             size_t eax;
30.             size_t i;
32.             eax = src[src_off] | ((src[src_off+1] & 0xF0) << 4);
33.             src_off++;
34.             var_1008 = (src[src_off++] & 0x0F) + 2;
36.             for (i=0; i<=var_1008; i++)
37.             {
38.                 if (dest_off >= dest_size) return dest_size;
39.                 dest[dest_off++] = dic[dic_pos++] = dic[(eax+i)&0xFFF];
40.                 dic_pos &= 0xFFF;
41.             }
42.         }
43.     }
45.     return dest_off;
46. }

复制代码

以上是参考（可以算是抄了）某引擎的，这个应该没啥问题……

rednaxela

好神奇...参考LZW的框架实现了LZSS?
不行,还是觉得好神奇.LZ77/LZSS与LZ78/LZW唯一的相似点就是它们都是字典系的压缩算法,除此之外它们对在滑动窗口(字典)里保存什么和如何构造字典的方式上都很不同...

真正的12bit LZW是Welch的论文里提到的一种.用12位的代码(code word)来指向字典中的项,每项一个字节(8位).字典也就相应的有4096项(2^12).字典中的前256项依次被初始化为0-255,后面的3840项用来记录新的前缀.

而囧大这里碰到的是LZSS.使用16位的代码来指定一个长度为4096的滑动窗口(字典)中的字串.这个16位代码的构成是12位的指向字典的指针+4位的要复制的长度.编码后,每8个单元数据前都会有1字节的标志,用于记录后面的单元到底是一个8位的原数据(raw byte)还是一个16位的代码.字典一般以0x00填充作为初始化,也有用别的更常见的数据初始化的可能(但字典里每个字节的初始值都一样)

静态观察数据时,我一般是靠0xFF标记来辨认LZSS的,因为如果有连续的8字节都是原数据的话,前面就会有一个0xFF的标志,相当好辨认.如果是分析程序代码,我一般会找找0xFEE,如果是用了4096长度的字典LZSS的话,这0xFEE基本上少不了.

LZSS的代码发在CK那帖里,这边不重复发了

lw

究竟怎样是压缩的，偶只知道用HUFFMAN建树，然后保留到各个复现概率高的高度值－以上

shawind

lzss也应该是比较快的吧？

ps: john原来可以谐音成囧 [s:25]

rednaxela

LZSS里的滑动窗口（字典）被视为一个循环数组。它的任务就是把最近出现过的在最小匹配长度以上，最大匹配长度以下的所有字串给记录下来（就像是在输入流上的“滑动窗口”一般）。在经典的LZSS里，使用16位的代码来记录到底要从字典的什么位置（12位指针）复制多大长度（4位数字）的内容到输出流，这样最小的匹配长度就是>2，而最大匹配长度是（2^4+2=18）。因为指针有12位，所以字典里有4096（=2^12）项，每项一个字节。

具体的算法随便找找都有，这里就不多说了。代码我发在了CK那帖：
http://bbs.sumisora.com/read.php?tid=10875708
没注册的可能得先注册登录才进得去 OTL

shawind

可以直接看到，虽然N年在那注册过，现在连注册名是什么都想不起来了。
果然贴的那个很经典的C源文件。89年的...

lzss，lzw虽然是无失真＆高速，可也有个压缩率不是很高的问题。
一般来说，还有什么比较简单且高速的算法来配合一下？（无损的）

现在我的作法是把BMP的文件头改造了一下，后面的具体数据只是简单的用了下zlib。
[s:5]

john_he

好神奇...参考LZW的框架实现了LZSS?
不行,还是觉得好神奇.LZ77/LZSS与LZ78/LZW唯一的相似点就是它们都是字典系的压缩算法,除此之外它们对在滑动窗口(字典)里保存什么和如何构造字典的方式上都很不同...

好丢人……因为我是算法小白……

我这个解压算法是跟着DK4跟出来的，然后看雪上有位仁兄说破过ELF的花与蛇，说这是LZW，我看过代码也差不多，就认为是LZW了= =|||（诅咒那家伙~~~~）

而压缩算法是看了Wikipedia LZW那页之后写的，说实在Wikipedia上那页根本就没详细说明，于是剩下的就靠在下脑内YY，根据压缩算法简单逆推过来。在最关键的查字典上面是用KMP的，我想这个就是慢的原因，因为实在没有研究到用树……

至于算法辨认，连算法都不认识就不要说辨认了……俺分析程序唯一能说出名字就是SAYA的算法，不过不是看算法，是看到了调用zlib的初始化函数（逃~~~~）

不知道对于压缩算法方面有什么资料可以参考？俺觉得是时候补习补习了|||OTL……

再次感谢FX大人~~~~~

john_he

引用第5楼shawind于2007-12-31 14:56发表的  :
可以直接看到，虽然N年在那注册过，现在连注册名是什么都想不起来了。
果然贴的那个很经典的C源文件。89年的...

lzss，lzw虽然是无失真＆高速，可也有个压缩率不是很高的问题。
一般来说，还有什么比较简单且高速的算法来配合一下？（无损的）
.......

我觉得以现在机器的速度，用Deflate是没有问题的，NScripter甚至用了bzip2（具体情况不清楚，貌似比Deflate更费时）感觉上都没有什么延迟。其实我觉得只要引擎设计得好，尽量把资源加载集中在LOADING时，数据压缩并不是影响速度的主要因素（一般解压缩都是很快的）。

rednaxela

引用第5楼shawind于2007-12-31 14:56发表的  :
lzss，lzw虽然是无失真＆高速，可也有个压缩率不是很高的问题。
一般来说，还有什么比较简单且高速的算法来配合一下？（无损的）

现在我的作法是把BMP的文件头改造了一下，后面的具体数据只是简单的用了下zlib。

LZSS的压缩率还是相当不错的啦，特别是结合它的解压速度和复杂度来看的话能达到这个水平就相当不错了。
不过一般在字典压缩之后（注意一定是先字典压缩）接一个算术编码或者Huffman之类的熵减算法会是个不错的选择。其实zlib的deflate算法也是LZ77改进型+Huffman而已……并不复杂。

压缩图像用无损压缩能得到的收效始终还是太小。BMP的话要是在做deflate之前先做一次差分的话能得到更好的压缩率，也不会带来太多overhead（图不大的话嗯）。呵呵不过再多弄几步就变成PNG了。

引用第6楼john_he于2007-12-31 15:26发表的  :

不知道对于压缩算法方面有什么资料可以参考？俺觉得是时候补习补习了|||OTL……

LZSS编码算法的具体执行步骤如下：

1、把编码位置置于输入数据流的开始位置。
2、在前向缓冲存储器中查找与窗口中最长的匹配串
① Pointer ：=匹配串指针。
② Length ：=匹配串长度。
3、判断匹配串长度Length是否大于等于最小匹配串长度(Length ³ MIN_LENGTH) ，
如果“是”：输出指针，然后把编码位置向前移动Length个字符。
如果“否”：输出前向缓冲存储器中的第1个字符，然后把编码位置向前移动一个字符。
4、如果前向缓冲存储器不是空的，就返回到步骤2。

我有本书专门讲多媒体应用中的各种压缩算法……so繁复 T T
话说之前我在翻译的一个逆向工程相关的文章里也有讲压缩算法。可惜压缩算法那部分我坑了一年一直没翻完。主要是中间做了大概65%的时候那翻译稿突然在U盘里浮云了，让我没想法了……

lw

哈，等到要用的时候偶就找一个来自己写试试XD～
YY最高啊，偶也想先编写再说