关于涂鸦板数据压缩的思考（含涂鸦板源文件）

寂寞火山

★这两天利用晚自习做了一个非常简易的涂鸦板，就是能画线条能保存重放的那种，其实这是我专门为“火山之家”开发的“签名板”。由于功能非常简单，代码我也写的很清楚，基本没什么好讲的，只有数据压缩部分让我比较困惑，始终找不到满意的方案。下面是我的做法，只能无损压缩20%-50%。希望高手多多指教，给出更好的压缩或者数据利用方法。

→首先讲一下我的涂鸦板原理：在onMouseMove的时候，记录横纵坐标点，并记入数组，回放的时候再利用setInterval不停的lineTo这些点。

→下面是我储存数据的格式：如果仅仅是画一条线，非常简单，但如果画多条线，就必须在每次点击鼠标的时候记录这个点，不然回放时，所有的数据就会连成一条线，这个间断点我用“#”标记，也就说，每当我按下并松开鼠标的时候，我就会在记录坐标的数组中添加一个“#”号。下面给出的图示是我画的三条线，画线范围限制在凹陷深色长方形部分，其左上角为（0，0）点，即画板MC的注册点。

这时trace横坐标数组（hengZuoBiao_array），就会得到下面的输出结果：

3,4,4,5,6,6,6,7,7,8,8,9,9,10,10,11,11,12,13,14,15,16,16,17,17,18,19,19,20,20,21,22,23,23,24,25,26,27,28,30,31,32 ,#,122,123,124,125,127,129,132,134,136,138,139,140,141,142,143,144,145,146,147,147,148,149,151,153,155,156,157,1 58,159,160,160,161,162,#,264,265,265,266,266,267,268,270,271,272,273,273,274,275,276,277,278,279,280,281,282,283,284,285,286,287,288,289,290,291,292,293,294,294,295,296,297,298,299,300,301,302,303,304,#

大家看到，一共有三个#号，把所有的横坐标分成三部分，这三部分依次对应图示中的三条线。当然，最后一个#号多余了，随后我将把它从数组中删除掉。

→下面讲一下我的压缩原理：在画线速度不是超快的情况下，我发现相临两个坐标值的差一般都小于10，这使我萌生一个想法，在每段数据中，仅记录第一个坐标值，其它的依次求差，这样除了第一个值可能是三位外，其它坐标值一般都是一位。这样以来，如果坐标值都是三位的话，我们一下就能压缩掉三分之二。解压时，只需要对压缩过程进行逆过程就行了。

→压缩实现算法：

1. function yaSuo() {
   
2.         //先去掉横坐标最后一项“#”号项
   
3.         hengZuoBiao_array.pop();
   
4.         //利用循环依次求差
   
5.         for (var i = hengZuoBiao_array.length-1; i>0; i--) {
   
6.                 if (hengZuoBiao_array[i-1] != "#") {
   
7.                         hengZuoBiao_array[i] -= hengZuoBiao_array[i-1];
   
8.                 } else {
   
9.                         i--;
   
10.                 }
    
11.         }
    
12. }

复制代码

这个压缩函数中，我用if在倒序的循环压缩过程中进行判断，如果当前项的前一项是#号，本项停止压缩，并通过i--跳过#号继续进行压缩。压缩后的坐标数据变成下面的形式：

3,1,0,1,1,0,0,1,0,1,0,1,0,1,0,1,0,1,1,1,1,1,0,1,0,1,1,0,1,0,1,1,1,0,1,1,1,1,1,2,1,1,#,122,1,1,1,2,2,3,2,2,2,1,1,1,1,1,1,1,1,1,0,1,1,2,2,2,1,1,1,1,1,0,1,1,#,264,1,0,1,0,1,1,2,1,1,1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1,1

估计大家的第一感觉就是比第一段数据精简多了。另外我们再注意观察，会发现现在是通过两个#号把所有的坐标数据分成了三段，每段的第一个坐标值与第一段数据相同，但其后的所有值都变的非常小，而且都是一位。再跟第一段数据仔细对比，不难发现，第一组数据中的坐标值是第二组数据中对应坐标值跟其前面所有值的和。比如第一组数据中第五项的值是：6，那么这个值正好是第二组数据中的前五项的和，即：1+1+0+1+3=6。最后这组精简的数据将被记录入数据库。

→解压算法：

1. function jieYa() {
   
2.         for (var i = 0; i<hengZuoBiao_array.length-1; i++) {
   
3.                 if (hengZuoBiao_array[i+1] != "#") {
   
4.                         hengZuoBiao_array[i+1] += hengZuoBiao_array[i];
   
5.                 } else {
   
6.                         i++;
   
7.                 }
   
8.         }
   
9. }

复制代码

解压算法和压缩算法正好是互逆的，大家可以对比起来理解，我就不多说了，上面压缩过的数据经过解压后，变成下面的样子：

3,4,4,5,6,6,6,7,7,8,8,9,9,10,10,11,11,12,13,14,15,16,16,17,17,18,19,19,20,20,21,22,23,23,24,25,26,27,28,30,31,32 ,#,122,123,124,125,127,129,132,134,136,138,139,140,141,142,143,144,145,146,147,147,148,149,151,153,155,156,157,1 58,159,160,160,161,162,#,264,265,265,266,266,267,268,270,271,272,273,273,274,275,276,277,278,279,280,281,282,283,284,285,286,287,288,289,290,291,292,293,294,294,295,296,297,298,299,300,301,302,303,304

对比第一组数据，我们看到，除了最后一个#号没有了以外，其它的完全一样，而那个#号又正好多余，删除了更好。最后再根据解压后的数据进行回放。

★我在星期一最初的构思很理想化，我非常武断的认为通过onMouseMove记录的相临两点的差一定会小于10，这样我就可以在数据库中储存类似下面的数据：

3/10110010101010101111101011010111011111211#122/11122322211111111101122211111011#264/1010112111011111111111111111111101111111111

上面应该是一种最理想，最简化的状态，除了用于记录鼠标按下的“#”和用于分割每段坐标第一项的“/”，没添加太多冗余信息。可今天完工后自己测试时才发现，当画线速度非常快的时候，即便我把帧频调成50，相临两点间的最大差值也可达到50左右，别说50了，就算是10，只要是两位，就会给我的解压造成混乱，当然我在压缩的时候可以通过if进行判断，如果两项的差值大于9，就在数据中添加一个分割符，而解压的时候，再根据这个分割符进行特殊处理。但不知道这样做的效率如何，目前我还在测试中。而现在我采用的则是一种非常笨的方法：我对每项数据都用“,”进行分割，也就说，在把数组提交到数据之前，对数组进行join(",")，数据库中最终储存的数据格式如下：

3,1,0,1,1,0,0,1,0,1,0,1,0,1,0,1,0,1,1,1,1,1,0,1,0,1,1,0,1,0,1,1,1,0,1,1,1,1,1,2,1,1,#,122,1,1,1,2,2,3,2,2,2,1,1,1,1,1,1,1,1,1,0,1,1,2,2,2,1,1,1,1,1,0,1,1,#,264,1,0,1,0,1,1,2,1,1,1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1,1

这样平白无故的多了那么多“,”，好不容易压缩了百分之五六十，这样一下又多了百分之一二十，实在让人痛心。不知道现在几个比较强的涂鸦板是怎么压缩数据的，真希望能有高人来小提示一下：）

★涂鸦板终于完工了，其实我只是做了一个模型，透视一下涂鸦板的基本原理，还有很多不完善的地方，这里先开放源文件给大家一起玩吧。为了更好的理解我的源文件和源代码，请参阅《火山开发习惯2006》。

→观看演示
→源文件下载

[ 本帖最后由 寂寞火山 于 2006-12-22 11:57 编辑 ]

寂寞火山

涂鸦板源文件已经开放了，测试和下载地址在一楼最后。
欢迎大家测试，多提意见。

ybzjllj

好，不错。

ybzjllj

关于压缩算法，提两个思路：
1、自创一种进制，不是十进制，十六进制，可以把26个字母和10个数字全用上（尽可能）。比如32进制。
2、把“距离大于9的”值进行分割，如25可分成9+9+7，即把一条直线分成几段来画。相当于中间插值法，这样就不用哪些“，”号了。

ybzjllj

另，能不能直接用PHP等调用“RAR”程序来压缩和解压？

寂寞火山

TO：ybzjllj
你的第一种方案比较好，可惜的是，快速画线的时候，我发现两点的差有可能超过100，这是就算32进制，也会出现双位数，造成跟现在一样的困难。
第二种差值法别人也跟我提过，我试了一下，有点麻烦，而且很多情况下，会产生负数，负号会加大数据量，这样得不偿失了。
最后“调用RAR”的方案，非常有想象力，但我不知道怎么实现啊？

ybzjllj

1、高进位制的办法：画线的矩形最大尽寸小于进位制的数，就不会超出。以最快的速度移动鼠标，极限情况，从左到右（从上到下），不会超过“舞台”尺寸。在制作时，舞台设小些，放入网页后可以重新设置swf大小，不影响swf内部计算。
2、是麻烦一点，但能解决问题。就是一个已知直线两端点求中间某些点的问题。
3、调用“RAR”应该能实现，当然要服务器支持。当然这就与Flash没关系了，Flash只是提交数据。

ybzjllj

如果用二进制文件，一个字节可以表示：255的大小，用第一种方案，应该足够了。

寂寞火山

好象到FLASH9才支持二进制编程的！

net虫

火山想法很好啊，使用的算法有点象JPEG等图象压缩算法了，但使用16进制将使用2个字节，不太理想，如使用ybzjllj 所提到的32进制是一个相当好的办法，也可以用36进制0-9，A-Z，然后在超出该进制1位能表示的位置的地方（比如距离为100的时候）使用2个特殊符号，如：$100$来表示（$必须成对出现），这样可以将超出1位表示的数据单独列出来，从而省去“，”；呵呵，估计又能少个15%吧

ybzjllj

好办法，比插值算法简单。

xionghuan

这是我画的一条线段:

xionghuan

这是该线段的坐标点,一共有36个坐标点:

	0	1	2	3	4	5	6	7	8	9
x	241	242	243	244	247	251	254	260	265	270
y	159	159	159	159	159	159	159	160	160	160

	10	11	12	13	14	15	16	17	18	19
x	275	280	283	284	284	284	282	279	275	271
y	161	161	161	161	162	163	164	167	169	171

	20	21	22	23	24	25	26	27	28	29
x	267	265	263	262	261	261	261	260	259	259
y	173	174	175	173	171	169	168	166	163	161

	30	31	32	33	34	35	36	37	38	39
x	259	259	258	258	258	258	END	---	---	---
y	158	154	150	147	144	142	END	---	---	---

[ 本帖最后由 xionghuan 于 2006-12-24 18:53 编辑 ]

xionghuan

将各个坐标点求差后的结果,(x y) 表示坐标点, (dx dy) 表示差值:

[ 本帖最后由 xionghuan 于 2006-12-24 18:44 编辑 ]

xionghuan

其中带有颜色的值表示相邻线段具有相同的斜率,
因此将他们合并,合并后共有26组数:
根据画线的方向不同, (dx dy) 是有+ - 符号的,其范围被限定在 -126 到 127 之间 , 这是熵编码的要求,对于超过此范围的可以将一组 (dx dy) 拆成两组并使它们的值符合要求

[ 本帖最后由 xionghuan 于 2006-12-24 18:50 编辑 ]

xionghuan

(x y) 的取值范围和涂鸦板大小有关,使用定长码,例如:
我的涂鸦板尺寸为 800 * 600 ,
2^9 = 512 < 600 < 800 < 2^10 = 1024
所以 x y 都使用 10 位 BIN (2进制) 表示.

(dx dy) 的大小同鼠标移动的速度相关,移动得慢 |dx dy| (绝对值) 就小,移动得快 |dx dy| 就大,但大部分的值都集中在 0 附近, 大于几百的情况也存在,不过出现的概率非常低.
所以 (dx dy) 采用 3 位 BIN 至 10 位 BIN 变长的熵编码.
前 3 位 BIN 为 BIN 000 至  BIN 111 ,其十进制的值为 DEC 0 至 DEC 7 ,它的含义表示紧接着的 变长 BIN 的长度.将他们组合起来构成一个完整的熵码
例如:
BIN 001001011011011... 解释如下
先取前 3 位 BIN 001 表示后面跟有 1 位 BIN ,组合起来为 BIN 0010 , DEC 为 1
接下来的 3 位 BIN 010 表示后面跟有 2 位 BIN ,组合起来为 BIN 01011 , DEC 为 -3
再接下来的 3 位 BIN 011 表示后面跟有 3 位 BIN ,组合起来为 BIN 011011 , DEC 为 7
...

这是正整数的熵编码表:

熵码	数值
000	0
001 0	1
010 00	2
010 01	3
011 000	4
011 001	5
011 010	6
011 011	7
100 0000	8
100 0001	9
100 0010	10
100 0011	11
100 0100	12
100 0101	13
100 0110	14
100 0111	15
101 00000	16
101 00001	17
101 00010	18
101 00011	19
101 00100	20
101 00101	21
101 00110	22
101 00111	23
101 01000	24
101 01001	25
101 01010	26
...	...
111 0111111	127

这是负整数的熵编码表:

熵码	数值
001 1	-1
010 10	-2
010 11	-3
011 100	-4
011 101	-5
011 110	-6
011 111	-7
100 1000	-8
100 1001	-9
100 1010	-10
100 1011	-11
100 1100	-12
100 1101	-13
100 1110	-14
100 1111	-15
101 10000	-16
101 10001	-17
101 10010	-18
101 10011	-19
101 10100	-20
101 10101	-21
101 10110	-22
101 10111	-23
101 11000	-24
101 11001	-25
...	...
111 1111110	-126
111 1111111	END

其中  111 1111111 用于表示熵编码结束标志END

[ 本帖最后由 xionghuan 于 2006-12-24 21:49 编辑 ]

xionghuan

整理 #15  楼的数据:

	x	y
0	241	159

	dx	dy
1	6	0
2	4	0
3	3	0
4	6	1
5	10	0
6	5	1
7	5	0
8	6	0
9	1	0
10	0	2
11	-2	1
12	-3	3
13	-8	4
14	-8	4
15	-2	-4
16	0	-2
17	0	-1
18	-1	-2
19	-1	-3
20	0	-2
21	0	-3
22	0	-4
23	-1	-4
24	0	-6
25	0	-2
26	END	END
27	---	---
28	---	---
29	---	---

晚上再写....

[ 本帖最后由 xionghuan 于 2006-12-24 18:52 编辑 ]

ybzjllj

楼上也不错，
另，比值相同，斜率就相同，可以合并。

xionghuan

对 (x y) 进行定长的 10 位 BIN 编码,不足 10 位的补 0

	x	y
0	0011110001	0010011111

对 (dx dy) 进行 3 位 BIN 至 10 位 BIN 变长的熵编码,可查找 #16 楼的熵编码表

	dx	dy
1	011 010	000
2	011 000	000
3	010 01	000
4	011 010	001 0
5	100 0010	000
6	011 001	001 0
7	011 001	000
8	011 010	000
9	001 0	000
10	000	010 00
11	010 10	001 0
12	010 11	010 01
13	100 1000	011 000
14	100 1000	011 000
15	010 10	011 100
16	000	010 10
17	000	001 1
18	001 1	010 10
19	001 1	010 11
20	000	010 10
21	000	010 11
22	000	011 100
23	001 1	011 100
24	000	011 110
25	000	010 10
26	111 1111111	111 1111111
27	---	---
28	---	---
29	---	---

[ 本帖最后由 xionghuan 于 2006-12-24 21:13 编辑 ]

寂寞火山

xionghuan朋友的方法非常好，关注中，等xionghuan写完后，建议斑竹打分鼓励！

xionghuan

将所有的 BIN 按如下的格式连接起来:
(x0 y0) (dx1 dy1) (dx2 dy2) (dx3 dy3) ... ... (dx25 dy25) (dx26 dy26) ( END )

得到一组 BIN 流:
0011110001 0010011111 011010 000 011000 000 01001 000 011010 0010 000010 000 011001 0010 011001 000 011010 000 0010 000 000 01000 01010 0010 01011 01001 1001000 011000 1001000 011000 01010 011100 000 01010 000 0011 0011 01010 0011 01011 000 01010 000 01011 000 011100 0011 011100 000 011110 000 01010 1111111111
空格只是方便阅读,实际是不存在地,结束标志 END 也只需要一个:

0011110001001001111101101000001100000001001000011010001000001000001100100100110010000110100000010000000010000101000100101101001100100001100010010000110000101001110000001010000001100110101000110101100001010000010110000111000011011100000011110000010101111111111
一共花费了 259 位 BIN,到此为止我们已经完成了对 36 组坐标值得压缩.

可是 SWF 是不能发送 BIN 的,所以我们还要对这 259 位 BIN 进行 BASE64 编码,以得到一组字符串,方便 SWF 发送.
BASE64 会使上面的数据增加 1.3 倍,那也是没有办法的事!!
BASE64 编码很简单,它使用 “ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnop qrstuvwxyz0123456789+/” 这 64 个字符来表示 6 位 BIN ,
既从 BIN 000000 到  BIN 111111 共 64 个状态.

因此, BASE64 编码要求 BIN 的位数必须为 6 的整数倍, 将上面 259 位 BIN 尾部补 5 个 0,得到 264 位 BIN:
001111 000100 100111 110110 100000
110000 000100 100001 101000 100000
100000 110010 010011 001000 011010
000001 000000 001000 010100 010010
110100 110010 000110 001001 000011
000010 100111 000000 101000 000110
011010 100011 010110 000101 000001
011000 011100 001101 110000 001111
000001 010111 111111 100000

最后得到的 BASE64 码为:
PEn2gwEhoggyTIaBAIUS0yGJDCnAoGajWFBYcNWPBx/g
共 44 个字符

xionghuan

这 44 个字符仍然有很多的冗余,那是因为我设定的 (dx dy) 的范围为 -126 到 127 , 而本例只使用了 -8 到 10 的几个值.
在实际绘画中,绘制线条的速度范围是很宽的,在极端测试下 |dx dy| max 曾超过 300 ,在这种情况下应将 (dx dy) 拆分为多个值进行处理.

使用这个方法压缩数据的压缩率是多少,我也不晓用什么标准计算,但是通过本例可以得到一个结论,将 36 对坐标值变换为 44 个字符,
平均 每对坐标值 仅使用 1.22 个字符,因为使用的是变长编码,在不同的情况下这个比值会有很大的差别.

细心的朋友可能已经发现,整个压缩的方法就是在查表,一张是熵码表,一张是 BASE64 码表,所以实现起来是非常简单的事,而且效率也会很高

解压的方法就是压缩的逆过程,我就不在多说了.

我发现可以去写部教程来,呵呵 ^_^
好了,就写到这了.

ybzjllj

很不错的，再顶你一下。

寂寞火山

谢谢xionghuan的热心指教！
感觉有点深啊，我得好好研究一下再发表评论。

另外，并非所有的压缩算法都是可逆的，我在按自己的思路进行进阶压缩的时候，发现不可逆。这让我想到.rar文件的压缩和解压，它用的应该就是不可逆的压缩算法，它的压缩过程比解压过程要缓慢的多！

54558284

chenlangeer

疑虑：
1.as2做熵压缩是要付出代价的，咋看起来，是简单的查表运算，可别忘了，是二进制诸位查表（还是用字符模拟的），这样的执行效率是非常低的
2.目前的数据源类型还非常简单，只涉及到数字的排列组合，一旦出现字符，情况就更加复杂，熵值表的长度会大幅度增加，从而导致压缩/解压缩的时间成几何级增长。

我的观点：
数据的压缩和执行效率是一个此消彼长的东西，用as2写东西，更要时时提防。
绝大部分时间，更应该关注的是执行效率，因为这是和用户体验紧密相关的，数据压缩，是要以不影响体验做前提。

如果你和我一样，是个完美主义者，恭喜你，有得你头疼了，呵呵。
想两者兼得，基本思路很简单－－充分榨取CPU的剩余价值。用户每画一笔，就压一笔，化整为零，把压缩的时间插在用户思索该如何画下一笔的那一刹那里。从理论上讲，分块压缩率肯定没有整快压缩的效率高，也没后者来得痛快，也开销了额外得内存，可这些和收获比起来算得了什么，你可以很NB的告诉你的老板，告诉你的用户，－－你看，用我的程序，不管是绘画体验，还是数据压缩率\传输速度，都是十分完美的。

寂寞火山

chenlangeer前辈也来指教了，真是不胜荣幸，我还说再研究一下就专门去请教你呢

xionghuan的方法压缩程度很大，最重要的是，让我学到了新的知识和思路，非常感谢。不过对于数据合并那块儿，我有点疑问：正如xionghuan朋友自己在16楼提到的，画线速度的快慢反映在坐标值上就是差值的大小，差值越大，速度越快。如果我们把相同差值进行合并，那么势必要改变绘画者原先的画线速度，这样就会造成回放与原画节奏不同！

另外，.net虫朋友在10楼的方法正是我所采用的进阶压缩法，压缩部分我已经实现，效率不错，但可惜的是，我发现我的压缩算法竟然不可逆，解压的时候会非常麻烦，效率很低，最后还是放弃了

ybzjllj

向你学习！

chenlangeer

今天逛坛子发现好几处地方都讨论得很热烈，闪吧又开始人丁兴旺了哈，好现象。

xionghuan

chenlangeer  还真是多虑了啊.

其实 " 表驱动法 " 比你想像的更简单,举个例子:
假设你需要计算每个月的天数 ( 不考虑闰年 ) . 笨的做法是写一个大的 if 语句 :
if ( month == 1 ) {
    days = 31 ; }
else if ( month == 2 ) {
    days = 28 ; }
else if ( month == 3 ) {
    days = 31 ; }
else if ( month == 4 ) {
    days = 30 ; }
... ...
一种更简单的方法是把这些数据存到一张表里面 , 首先你需要创建出这张表:
var daysPerMonth = [ 31 , 28 , 31 , 30 , 31 , 30 , 31 , 31 , 30 , 31 , 30 , 31 ]
现在只需要一条简单的数组访问语句就可以得出每个月的天数了 :
days = daysPerMonth [ month - 1 ]

其实 , 熵编码表是很有规律的 , 用一个简单的公式就可以表达 ,
至于是使用 "逻辑表达式" ,  " 表驱动法 " 还是 " 公式法 " , 则在乎个人喜好.

数据压缩的方法有9999个 , 没有一个可以称作完美 , 我的法案是前辈们在50年前就用过的.
我只是在这里引用一下罢了.