基于TCP数据流的压缩

 收藏

这两天研究了一下 lzw 压缩算法,据说它专利已经过期了,那么应该可以随便用了吧。

这种基于字典的压缩算法,一个很大的优势就是,如果数据流中经常出现同一个词,那么会被极大的压缩掉。重复性的信息在网络游戏中经常碰到,不过是基于包和包之间的,而不是同一个包之内的。游戏又跟别的应用不太一样,我们往往希望更快的把数据交到对方,减少网络的延迟,所以大多数情况下,我们不会积攒很多数据一起发送。所以,不能简单的以每个数据包为单位调用压缩器。

其实最简单的方案是,压缩器的上下文被保留起来,也就是说每次压缩完毕后不重置字典,这样,重复的信息会被压缩的越来越短。我花了一晚上时间实现了个 lzw 算法做实验,因为lzw要求双方有相同的初始化字典,一般是所有可能出现的字符集。如果以 byte 为单位压缩,这个字符集就是 256 个。而压缩后的码长至少就是 9bit 起。为了方便,我在字符集中加了一个包结束符。这样,分包的时候就不需要再保存包的长度,而以这个结束符结尾就可以了。这样在解码处理时就非常方便,碰到结束符就知道一个包结束了。

为了优化,我们也大可不按 8bit 为单位压缩,比如可以用 4bit 分段,编码的码长就可以从 5 bit 开始。实际测试的效果也比较好。

写好程序后,我用 "Hello World" 这个字符串做了测试。
字符串一共是 11 字节,加上结束符信息大约需要 12 ~13字节的信息方能描述。
重复压缩 25 次结果如下:

04 99 62 58 35 4f 80 72 f0 11 2e 02 02
d1 74 59 d9 d6 3d 5f 08 01
23 65 99 1a e7 81 96 08
6d 89 c5 e9 5a 43
f6 8b a3 66 2c
bd cb 49 a6 a2 19 44
42 18 d0 c8 02
c9 5f 71 87 84 00
4d a2 ee 28 02
d2 5c 90 07
d6 25 54 04
d9 67 15 02
5c 2a 0b
5f 6c 14
61 26 0f
e3 2d 04
65 2f
67 16
68 1e
e9 28
6a 11
6b 08
6c
6c
6c

我们可以见到,第一次进入压缩器后,输出是 13 字节,比原有的数据稍长一点,但是随着次数的增加,越来越短。最后只用一个字节就可以表示这个串了

这次这个程序,每个编码器需要占用一块固定大小的内存,可以调整。如果按 32k 计的话,每个连接需要 64k 内存。那么 1000 个连接就是 64M ,算是一个不小的开销。我不知道在千M网上还有没有意义,因为网络流量增大后,如果网卡承受的起的话,给 CPU 的负担无非是每次发送从用户态向内核态拷贝数据的时间,这个速度非常的快,远远小于编码器的开销。

除了 lzw , 我还考虑了动态 huffman 算法,熵编码其实也不错,不过动态 huffman 树调整算法很复杂,时间开销更大,相比较还是 lzw 更具有实时操作的可行性了。

不过引擎提供这么一个特性还是满好玩的,纯属娱乐吧。

ps. 晚上拿大话西游的包测试了一下,2504 秒内,client 共收到 32903 个包。总共收到 943888 字节,压缩后 700508 字节。大约压缩到原始数据的 74.2%

我审查了一下自己算法的实现,感觉还有许多改进的余地,打算周末仔细改造一下。

回复