基于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%
我审查了一下自己算法的实现，感觉还有许多改进的余地，打算周末仔细改造一下。
Comments
在网上看到有人用lzw压缩网络包申请专利，基本上就是把这篇文章的内容实现出来了而已。。。
http://www.google.com/patents/CN1964351A?cl=zh
Posted by: easy | (22) October 4, 2017 04:58 PM
如果协议也用的是ID协议号的形式来区分，那可以为每个不同的协议准备一个压缩器，这样应该有相当强的压缩率
Posted by: 凄临雨 | (21) January 14, 2015 11:59 AM
可以看看7zip使用的lzma 应该比lzw 强
基于流的压缩如果要求速度的话可以看
lzo
http://www.oberhumer.com/opensource/lzo/
Posted by: ironarmor | (20) March 7, 2007 04:19 PM
我能理解你的意思，但是我的实验经常是后面的数据会变大，可能是我的字典的问题，能不能给我看看你的源代码呢。在压缩这方面我是个初学者，只是参考下。谢谢我的邮箱zxzombie@msn.com
Posted by: zxzombie | (19) June 6, 2006 10:04 PM
变长的码从我自己的实现上看，没有慢的理由。在位操作的时候并没有额外的代码。
任何代码都需要对缓冲区做严格的判断和限制，防止溢出，这并不是 lzw 的问题。如果对性能有特别的要求，觉得这个校验带来的性能损失都是不可以原谅的，那么自然有别的方法优化。比如用操作系统提供的内存读写异常等。
Posted by: Cloud![[TypeKey Profile Page]](https://blog.codingnow.com/nav-commenters.gif)
| (18)
February 15, 2006 01:15 PM
我的窗口是指lzw字典的大小，固定的输出位是指定长的输出码。变长的输出码自然更好，但是处理起来速度就慢很多了。lzw的解码overflow的意思是说构造了一个数值序列使解压后的数据大得超过了你的输入缓冲，不就出错了么，这样就必须在输出的时候做上严格的判断和限制。
Posted by: 2002thinking | (17) February 14, 2006 10:36 PM
LZW解码overflow 会发生吗？算法的实现是自己写的，无论什么代码在编写的正确的时候，都不会 overflow。防止 overflow 是编码者的责任，而非选择算法。
lzw 是基于流压缩的，tcp 传输也是一个数据流。所以本来就没有包这个概念。另外，"缩小窗口",窗口是什么? 标准的 lzw 的输出位也是固定的，只有改进的 lzw 才是变长的，而变长的 lzw 算法往往效果更好，比如 gif 的压缩。
Posted by: Cloud![[TypeKey Profile Page]](https://blog.codingnow.com/nav-commenters.gif)
| (16)
February 13, 2006 01:28 PM
网络数据包的压缩是可行的，LZW算法也要做部分的妥协才行。比如说减小窗口，固定输出位等，另外压缩过程中还要加上智能判断，当发现压缩的输出达到了原始输入大小的一个临界比率后，需要立即停止压缩。最后给个建议，客户端向服务器一定不能使用LZW压缩，否则可能在解码黑客精心设计的错误数据包（符合CRC码)时，导致LZW解码overflow。
Posted by: 2002thinking | (15) February 11, 2006 08:52 PM
首先这种情况在网络包中不常见，其次你不一定用按 8bit 分节来压缩数据。最后，字典的context环境是保留的，第一次出现这种情况后，再次出现类似情况就会被压缩了。
独立的看一个信息，压缩后的长度有可能增加；但是对于特定的数据流，信息熵是一定的，所以都会有一定的压缩率。
Posted by: Cloud | (14) February 11, 2006 04:39 PM
比如：就256个各异的字符，这样创建的字典显然码字长就要超过8bit了，如果按照这样编码，每位的码长>8bit，由于没有重复，256个码字的总长度显然就大于原长度了。而且，不论怎么再编码，因为没有重复码字，也就没有重复子串，也就无法压缩。
Posted by: 清风雨 | (13) February 10, 2006 10:27 PM
回答这个问题，需要弄清楚为什么压缩后的数据更大，再从原因下手解决。
同样，为什么你会认为LZW的字典字段长度可能会导致压缩结果反而更大呢。
Posted by: Cloud![[TypeKey Profile Page]](https://blog.codingnow.com/nav-commenters.gif)
| (12)
February 10, 2006 02:29 PM
我想请问一下：
1. 虽然LZW是基于流的，但实际的压缩结果也是和真实数据相关的（就像haffman编码，可能导致结果比原文还长），也就是聚合的效果不明显时，得到的压缩效果也会很糟。
2. 另LZW的字典字段长度问题，如果选择不适合，可能压缩的反而更大，而字典是动态建立的，那么到底该选什么长度并不好预知。对于网络，这个压缩的效果就有所值得怀疑了。
Posted by: 清风雨 | (11) February 10, 2006 01:27 PM
cpu 的问题可以通过多核来解决。加密这种工作可以很方便的放去另外一个进程。
Posted by: Cloud![[TypeKey Profile Page]](https://blog.codingnow.com/nav-commenters.gif)
| (10)
January 22, 2006 10:05 PM
呵呵，我想追问云风一个问题：
－－－－－－－－－－－－－－－－
但是我们游戏碰到的另一个问题是，当搞活动时，机房的带宽成了问题，这个时候减少 20%~30% 的带宽也是有意义的。
－－－－－－－－－－－－－－－－
既然这样，那你认为在搞活动时，对CPU的需求就会低吗？:)
如果CPU也会相应地提高占用率，那由于活动带来的带宽方面的节省，是不是转价到了CPU上呢？
Posted by: wonna | (9) January 22, 2006 09:45 PM
哦，那确实有效，不错
Posted by: coder | (8) January 22, 2006 12:03 AM
聚合不会改变压缩率，因为lzw 是基于数据流的，跟你一次送多少字节进来，分多少次送进来无关。
Posted by: Cloud![[TypeKey Profile Page]](https://blog.codingnow.com/nav-commenters.gif)
| (7)
January 21, 2006 11:19 PM
这会是个很复杂并且很有趣的问题，在高峰期，聚合本身会带来原信息的多样化，实际上这就会降低压缩的效率。我想聚合无非两种方法，一种是定长聚合，一种是定期聚合。定长就是当要发送的包达到一定的长度发送，定期就是每过一段小的时间发送。定长是不合适的，低峰的时候会引发延迟。定时在低峰的时候不起聚合作用，在高峰的时候起到聚合作用。但这个时候聚合的包的信息将多样化，查字典这样的压缩方法将起不到多大作用。真要为解决高峰的带宽问题考虑，可能需要换压缩方法。
Posted by: coder | (6) January 21, 2006 09:10 PM
包的聚合和压缩必须同时做的，否则就没有什么效果。我们需要减少的也只是高峰的带宽，而高峰的时候包是很密集的，所以也没有什么延迟的问题。
Posted by: Cloud![[TypeKey Profile Page]](https://blog.codingnow.com/nav-commenters.gif)
| (5)
January 21, 2006 07:27 PM
去看了看卷1：
8 0 2 . 3标准定义的帧和以太网的帧都有最小长度要求。8 0 2 . 3规定数据部分必须至少为3 8字节，而对于以太网，则要求最少要有4 6字节。为了保证这一点，必须在不足的空间插入填充（p a d）字节。
我记得去年和人讨论过这个问题，得出的答案就是小包压缩没什么用处，当时他就是告诉我这些东西。
Posted by: coder | (4) January 21, 2006 02:00 PM
你的数据是统计的tcp流量还是ip包？如果你说的是ip包，我感觉你的统计有问题。ip包的包头就是20字节，按你的数字来看压缩后的平均是21.3个字节，就是说你从平均8.7的字节压到了1.3字节，这个效率很让人吃惊。不过如果只是反复的发同样的包，确实可以理解，但这个可能和现实环境又不一样了。如果要达到这样的效果，本身的协议设计就要更简单，比如移动的信息，设计成只表明移动方向而不涉及到坐标，这样重复的机率就大，但这个会加大服务端的工作量。
如果是tcp包，那么实际的比率应该都加20，41/48 = 0.85
不要忘记下面还有链路层，实际上真实的节约不会到10%。
我其实本身对下层协议并不太熟悉，你如果真想实际的了解是否真能起到作用，应该去找些网络很精通的人咨询下，我感觉小包的情况下压缩用处不大。
你说的包的聚合我觉得是关键问题，不过这里有个两难，你自己也说了，如何面对延迟？
Posted by: coder | (3) January 21, 2006 01:51 PM
上面我给出了一些数据, 平均算下来我们的包是 28 字节。加密跟压缩是同时做的，一般是先压缩再加密。
普通的找一个别人写好的压缩模块直接对包压缩没有什么意义。所以如果真的想做，就得自己把这些算法搞清楚，再想办法做一个合适的。
小的 tcp 包如果单独一个个发因为 ip 包头的关系，实际数据会比较大，只有 ppp 协议才会压缩包头，所以我们在 engine 应该适当的做一些包的聚合。
效率问题我的意思很清楚，这样做肯定会更浪费 CPU ，但是现在机器都是多核的，我们可以单独拿一个 CPU 来处理网络压缩和加密，所以不太所谓，只是编程变得复杂了。
根据实测的结果，压缩对减少带宽是有效果的。昨天跟同事讨论过，单台机器减少带宽意义不大，因为我们可以配备千M网卡和交换机。
但是我们游戏碰到的另一个问题是，当搞活动时，机房的带宽成了问题，这个时候减少 20%~30% 的带宽也是有意义的。
Posted by: Cloud![[TypeKey Profile Page]](https://blog.codingnow.com/nav-commenters.gif)
| (2)
January 20, 2006 11:44 PM
提三个问题：
1。你压缩的包平均长度有多大？据我看来网络游戏的包平均长度一般很小，大部分低于128字节，特别频繁的包，如走路攻击等，一般在32字节以内，大一点的包一般出现在游戏角色初始化上。而实际上tcp包的实际长度是要加上不少内容的，具体的我记不大清楚。我只知道我以前和人讨论过，网络游戏的包压缩是不是能节约带宽，但得出的结论是实际上从最后得到的物理上传输的信号来看，低于一定字节数的包压缩是节约不了什么带宽的。
2。效率问题，我没看大明白，你认为直接拷贝数据的效率要比编码低吗？或者说在流量小的情况下会低？我觉得应该是我的理解不到位，但我觉得直接拷贝数据肯定要比编码得数据的效率要高。
3。你的包采取动态加密吗？我认为最好还是要采取，虽然你可以把防外挂的重点放在检测外挂上，但我觉得对协议的保护也是很重要的。
我不知道我有没有理解你写这个的意思，但我觉得如果是讨论游戏包的压缩问题好像不是很实用，并且把问题复杂化了。好像你说了是纯娱乐，：）
Posted by: coder | (1) January 20, 2006 11:14 PM