|
注册会员
- 帖子
- 161
- 积分
- 67
- 技术分
- 28
- 在线时间
- 142 小时
- 注册时间
- 2004-9-23
|
1#
大 中
小 发表于 2006-12-20 20:55 只看该作者
关于涂鸦板数据压缩的思考（含涂鸦板源文件）
★这两天利用晚自习做了一个非常简易的 涂鸦板，就是能画线条能保存重放的那种，其实这是我专门为“火山之家”开发的“签名板”。由于功能非常简单，代码我也写的很清楚，基本没什么好讲的，只有数据压缩部分让我比较困惑，始终找不到满意的方案。下面是我的做法，只能无损压缩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，这使我萌生一个想法，在每段数据中，仅记录第一个坐标值，其它的依次求差，这样除了第一个值可能是三位外，其它坐标值一般都是一位。这样以来，如果坐标值都是三位的话，我们一下就能压缩掉三分之二。解压时，只需要对压缩过程进行逆过程就行了。
→压缩实现算法： 复制内容到剪贴板 代码:function yaSuo() {
//先去掉横坐标最后一项“#”号项
hengZuoBiao_array.pop();
//利用循环依次求差
for (var i = hengZuoBiao_array.length-1; i>0; i--) {
if (hengZuoBiao_array[i-1] != "#") {
hengZuoBiao_array[i] -= hengZuoBiao_array[i-1];
} else {
i--;
}
}
}这个压缩函数中，我用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。最后这组精简的数据将被记录入数据库。
→解压算法： 复制内容到剪贴板 代码:function jieYa() {
for (var i = 0; i<hengZuoBiao_array.length-1; i++) {
if (hengZuoBiao_array[i+1] != "#") {
hengZuoBiao_array[i+1] += hengZuoBiao_array[i];
} else {
i++;
}
}
}解压算法和压缩算法正好是互逆的，大家可以对比起来理解，我就不多说了，上面压缩过的数据 经过解压后，变成下面的样子： 引用: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 编辑 ]
寂寞火山个人门户V3：http://www.huoshan.org
|
