光传输与微数据

阅读：评论：作者：rybby 日期：2013-04-23 来源：rybby.com

何为光传输？如字面意义，光速的传输速度！

有人曾断言，在不久的将来，全世界只需要五台计算机，一台是Google的，一台是IBM的，一台是Yahoo的，一台是微软的，一台是Amazon的。由于云计算的流行，这个将来离我们越来越近了！到那时，我们只需要一台能连接互联网的终端设备，这个终端不需要CPU，不需要硬盘，只需要少量内存就能做我们现在用微机做的所有事情！我们的数据全部存在云端，随需随取，云端的计算机可达到几十亿次每秒的计算能力！计算机的发展历程大致是这样：大型计算机 > 微机 > 大型计算机。

这个美好的将来到底什么时候来？我不确定，但是，如果不能解决传输速度的问题，这个将来可能永远不会来！想想看，我们的程序都在云端，我们请求一个操作类型，比如一个画图操作，以云端计算机的能力可以瞬间完成，然后将数据结果返回给我们，但如果传输速度跟不上就会产生不连贯！可能比卡卡跑丁车还卡！所以我们首先要解决传输速度的问题，在不增加网络带宽的前提下能否提升传输速度？似乎真没有什么有效的办法呢，但是如果我们能把数据压缩到很小就可以！比如将1GB缩小到1MB甚至1KB，这样就能实现超快的传输速度！这就是光传输的概念（当然这不可能与光速相比，只是一种形容罢了），要实现光传输必须先实现微数据，说到底就是数据压缩嘛！

没错，就是压缩，实现了压缩就能模拟光或以接近光的速度进行传输！如果我们能把一部几GB的高清电影压缩到几百KB，只需要几秒钟就实现上传、下载～
锐多：“这摆明是不可能的嘛！”
以目前的技术确实不可能，但如果大家都开动脑筋去想的话说不定能想出有效可行的方法呢！看看我们目前都有哪些压缩技术，如果从这些技术上继续挖掘或触类旁通，或许能找到好方法。

常用的无损压缩算法：游程编码（RLE，run-length encoding）、哈夫曼（Huffman Coding）、LZ77、LZ78、LZW、Burrows–Wheeler变换(BWT，也称作块排序压缩)。

游程编码

原理：将多次连续出现的字符用某个字串代替以实现数据压缩。
aaabbccccdd0011110011 // 压缩前
3a2b4c2d20412021 // 压缩后

哈夫曼

原理：将出现频率高的用短字符表示，频率低的用长字符表示,然后以二进制存储。

abacfbddadffdffdf // 压缩前（17Byte）

a=3，b=2，c=1，d=5，f=6 // 字符出现次数

f > d > a > b > c // 频率排序

构建二叉树，从频率低的开始合并
c1=1
b2+1=3
a3+3=6
d5+6=11
f6+11=17

树形结构（很抱歉！这棵树长得好像有点丑）
锐多：“什么好像，明明就是很丑！”

      17
    0/｜1
f6+11 11
    0/｜1
d5+6  6
    0/｜1
a3+3  3
    0/｜1
b2+1 ｜
      c1

锐多：“咦！怎么看都不像一棵树的样子捏？”
锐牛：“笨呀！你，将显示器倒过来或者把自己的脚吊在天花上就看到树了。”
锐多：“呀～这么牛逼的方法都想得到，你以前一定这样做过！”

进入左边叶子的树枝用0表示，进入右边叶子的树枝用1表示，然后得到下面的码表
f=0，d=10，a=110，b=1110，c=1111 // 码表（用这个码表的0、1代替原数据的字符）

abacfbddadffdffdf // 压缩前（17Byte）
1101110110111101110101011010001000100 // 压缩后(以二进制存储，37bit，8bit=1Byte)

反压缩，根据码表从频率低的到高的进行替换

1101110110111101110101011010001000100 // 压缩后的数据
1101110110c01110101011010001000100
110b110c0b101011010001000100
abac0b1010a10001000100
abac0bddad00d00d0
abacfbddadffdffdf // 解压后的数据

对于有很多重复字符的字符串，哈夫曼确实可以压缩，不然效果可能不减反增。有一点我不明白，数据以二进制流存储确实比字符流存储更节省空间，但在网络传输好像是以字符流进行传输的吧，这样1字节的8位二进制流不是变成8个字符了？锐某只是个菜鸟！望高手不要见笑！

LZW

LZW（懒子王）是LZ77与LZ78的升级版，77与78版的就不说了，不了解的网友可以到各大维客阅读相关词条。LZW是各种压缩软件用得最多的压缩算法，它的优点是压缩后的数据不需要码表，上面的哈夫曼必须将码表存进压缩后的数据里，不然无法进行逆操作。而LZW的码表可以在解压时自动生成与压缩时一模一样的码表，真佩服那三位前辈，居然想出来如此精妙的方法！！！

原理：
将重复出现的字符用码表的索引代替，压缩后将码表丢弃，用说的是说不明白滴，直接上例子。

step1
读取第一个字符并作为前缀

step2
读取下一个字符与前缀组合

step3
查询码表是否已经有这个字符组合

step4
step4-1 存在，将字符组合对应的码表索引作为前缀，转到step2
step4-2 不存在，将这个字符组合加入码表，输出前缀，将当前读取的字符作为前缀，转到step2

step5
读完字符串后将最后一个前缀输出

按照上面的流程进行操作，过程如下：

abccbcabccdab // 压缩前的数据（13Byte）
基本数据a,b,c,d，对应码表的值0,1,2,3。

a > ab(不存在，加入码表，值为4；输出前缀a) > bc(不存在，加入码表，值为5；输出前缀b) > cc(不存在，加入码表，值为6；输出前缀c) > cb(不存在，加入码表，值为7；输出前缀c) > bc(存在，将值5作为前缀) > 5a >(不存在，加入码表，值为8；输出前缀5) ab(存在，将值4作为前缀) > 4c(不存在，加入码表，值为9；输出前缀4) > cc(存在，将值6作为前缀) > 6d(不存在，加入码表，值为10；输出前缀6) > da(不存在，加入码表，值为11；输出前缀d) > ab(存在，将值4作为前缀) > (已读完字符串，将前缀4输出)

最终输出的字符串：abcc546d4 // 压缩后（9Byte）
最终码表：a:0; b:1; c:2; d:3; ab:4; bc:5; cc:6; cb:7; 5a:8; 4c:9; 6d:10; da:11

反压缩，虽说与压缩原理相同，但要复杂太多了！毋须害怕，明知山有虎偏向虎山行这是我们应该具备的精神！

step1
读取第一个字符并作为前缀并输出

step2
读取下一个字符与前缀组合

step3
查询码表是否已经有这个字符组合

step4
step4-1 存在
step4-1-1
当前读取到的字符是基本数据还是码表索引（这里稍微有点复杂，如何判断这个字符是基本数据还是码表索引？有的网友通过基本数据的最大索引来判断，即基本数据有4个字符，那最大索引就是3，大于3的就是索引；但是呢，如果基本数据里有个“5”，码表的索引也有个“5”，那这个5到底是哪个5？有个办法，虽说不是太聪明，但还是可行的，就是加个分割符）
step4-1-1-1 基本数据
将它作为前缀，并输出当前字符，转到step2

step4-1-1-2 码表索引
将当前字符作为前缀，获取索引指向的数据，如果数据的前缀还是索引，先保存此数据的后缀，继续取索引的数据，直到它是基本数据为止，最后将基本数据加上遍历过程中保存的后缀，然后输出，转到step2
锐呆：“啊～我要晕了！！！”
锐牛：“不是很难的说，看看就明白了！”
锐呆：“看个鸟呀！人家可不像你有四只眼啊，老兄！”
哈！我好像说过会复杂的吧！不过也不是复了很多杂！稍微有点而已。

step4-2 不存在，将字符组合加入生词码表；将字符组合加入数据码表。（这里又稍微有点复杂了，为什么要设计两个码表？当码表很大的时候可能会冲突，我不确定，照理论上来说会这样，数据码表与生词码表不一样的，数据码表的后缀不能是索引，必须是基本数据，不然下面的遍历取基本数据就会出错！所以这个数据码表的后缀也必须遍历取到基本数据为止（如果是前后缀组成的数据就取前缀）。而生词码表只是用来判断是否有新的前后缀组合，如果用数据码表来判断的话可能会有无法及时添加生词而使得取基本数据出错吧！我说了我不太确定哦！要复杂地想这么多复杂的东西也真够复杂的说。）
锐呆：“我才刚醒过来又要晕了！神啊！救救我吧！”
锐牛：“要不我给副眼镜你带带看！”
锐呆：“那样我会晕得更快！你想害我是不是？”

step4-2-1 当前读取到的字符是基本数据还是码表索引
step4-2-1-1 基本数据
将它作为前缀，并输出当前字符，转到step2

step4-2-1-2 码表索引
将当前字符作为前缀，获取索引指向的数据，如果数据的前缀还是索引，先保存此数据的后缀，继续取索引的数据，直到它是基本数据为止，最后将基本数据加上遍历过程中保存的后缀，然后输出，转到step2

按照上面的解压流程进行操作，过程如下：

abccbcabccdab // 压缩前的数据
abcc546d4 // 解压前的数据
基本数据a,b,c,d，对应码表的值0,1,2,3。（解压时的基本数据要与压缩时的基本数据要一样哦）

a(读第一个字符，作为前缀并输出a) > ab(加入生词码表，索引是a,b，值是4，加入数据码表，索引是4，值是a,b，将后缀b作为前缀并输出b) > bc(加入生词码表，索引是b,c，值是5，加入数据码表，索引是5，值是b,c，将后缀c作为前缀并输出c) > cc(加入生词码表，索引是c,c，值是6，加入数据码表，索引是6，值是c,c，将后缀c作为前缀并输出c) > c5(加入生词码表，索引是c,5，值是7，加入数据码表，索引是7，值是c,b，将后缀5作为前缀并输出bc) > 54(加入生词码表，索引是5,4，值是8，加入数据码表，索引是8，值是5,a，将后缀4作为前缀并输出ab) > 46(加入生词码表，索引是4,6，值是9，加入数据码表，索引是9，值是4,c，将后缀6作为前缀并输出cc) > 6d(加入生词码表，索引是6,d，值是10，加入数据码表，索引是10，值是6,d，将后缀d作为前缀并输出d) > d4(加入生词码表，索引是d,4，值是11，加入数据码表，索引是11，值是d,a，将后缀4作为前缀并输出ab) > 终末

最终输出字符串：abccbcabccdab // 解压后的数据
最终生词码表：a:0; b:1; c:2; d:3; a,b:4; b,c:5; c,c:6; c,5:7; 5,4:8; 4,6:9; 6,d:10; d,4:11
最终数据码表：0:a; 1:b; 2:c; 3:d; 4:a,b; 5:b,c; 6:c,c; 7:c,b; 8:5,a; 9:4,c; 10:6,d; 11:d,a
压缩时的码表：a:0; b:1; c:2; d:3; ab:4; bc:5; cc:6; cb:7; 5a:8; 4c:9; 6d:10; da:11
可以看到，解压时生成的数据码表与压缩时生成的码表是一一对应的！只是将压缩时的码表的值作为键而已，这样做的好处是不用写个for去对比是否存在这个生词，直接写if(obj[key]!=''）就行了！或者这样写也行if(typeof(ofj[key]) != 'undefined')，但是，这样写是不行滴：if(obj[key])，数字0与字符串0是不一样的哦！数字0会返回false。

代码就不用我抛出来了吧！随便哪一种语言都能实现。毕竟原理最重要，掌握了原理就可用很多方法去实现，锐某的建议是：多走弯路！多犯错！这会为你积累非常宝贵的经验！不要老想走捷径去拷贝别人的代码，另外，我写的代码是写给机器看的，不是写给人看的，就是有些人有事没事都拿程序的可读性来说事，如果不是以团队合作进行开发，可读性，闪边去吧！

说一下压缩效果，如果一段字串是重重复复重重复复重复又重复地出现，当然用游程好！也可以用BWT来进行乾坤大挪移使字串出现这种重复又重复的结构，然后游它一程！哈夫曼就不用了吧，不但“鸭”不出什么效果来！还要往它肚皮里塞串字典，得不偿失！还是懒子好，二进制数据的话可以压到原数据的1/2左右吧！但是问题来了，如果将普通的字符串转成二进制，必须增大至少6倍，如果里面再啃些中文字符就更大了，用UTF8的话，一个中文字符就需要16位二进制表示，如果不用UTF8就只有用三进制或九进制将字符的二进制值或八进制值进行分隔，这样比UTF8还要更大！
锐多：“娜妮？还有九进制的说法！！！”
什么进制都有的吧！进制数越大，能表示的数值越多！2位2进制可以表示4种组合（2的2次方）；2位3进制可以表示9种组合（3的2次方）；2位4进制有16种组合；2位8进制有64种组合，16进制有256种组合...于是，就有人研究几千进制，几万进制，以期望用最少的数表示更多的数，这其中要用到很多中文字符。

让我们看看，到底用哪一种进制效果更好。如果将一串字符转成二进制，ASCII码范围内有的6位，有的7位，但遇到中文就是十几位，可见字符间的长短参差不齐，这给还原时拆解带来困难！一长串的二进制数字，你知道从哪里分开一个字符？可行的办法就是加个2或加个9使之变成三进制或从八进制转成九进制，以后还原时再以这个加进去的字符进行分隔，然后转成UNICODE再转成原字符。如果有三个英文字母与两个中文字符，通过UNICODE转换成二进制就是：010101020101011201010102010101010101010120101010101010101 = 3*7+16*2+4 = 57字节，然后用LZW压缩一半，变成28字节，这个比三个字母+两个中文=9字节还要大！如果压缩后的数据只有0与1的话就好办了，6位二进制有64种组合，我们完全可以用64个字符来分别代替每6位二进制，但是压缩后的数据都是0-9之间的数据，也就是十进制，如果将两位数字合并成一位的话需要100个字符来代替这100种组合，遗憾的是我们用完所有字母、标点符号、数字也不够用。那我们将它转成二进制看看，每位数字要用多少位二进制来表示呢？3位二进制有8种组合，不够表示10个数字，所以至少要用4位二进制表示一位数字。然后用上面压缩得到的28字节*4=112，112/6=18，比原来的9字节还要大一半。那我们不压了，直接转成base64看看。上面的57字节的三进制怎么转成base64，算算看，2位三进制是9种组合，3位是27，4位是81，再多一位就不够字母表示了，好吧，我们将它转成base81，81的话，字母加数字加标点还是够用的。57字节/4=14，14/9=150%我们不压缩直接转成base81还能省点。再来看看用base64能省多少？三进制是不能转成base64的（应该说不能直接转成，先转成3位的27个字符再转二进制还是可以的），我们只能从一开始就转成二进制，为了可以恢复回原来的字符，我们应该用UTF8编码，UTF8的好处就是它有一定的格式，每个字符都由数据头加数据身组成，这样我们可以很容易从一长串二进制数字中分开一个字符。

UTF-8编码有以下几种格式：

U-00000000 – U-0000007F: 0xxxxxxx
U-00000080 – U-000007FF: 110xxxxx 10xxxxxx
U-00000800 – U-0000FFFF: 1110xxxx 10xxxxxx 10xxxxxx
U-00010000 – U-001FFFFF: 11110xxx 10xxxxxx 10xxxxxx 10xxxxxx
U-00200000 – U-03FFFFFF: 111110xx 10xxxxxx 10xxxxxx 10xxxxxx 10xxxxxx
U-04000000 – U-7FFFFFFF: 1111110x 10xxxxxx 10xxxxxx 10xxxxxx 10xxxxxx 10xxxxxx

网络上有人说UTF8最长有4字节，也人说最长有6字节，真不知该听谁的！以上的数据从网络上拷贝来的，4字节还是6字节就不要追究了，可以看到，数据头有多少个1，就代表这个字符有多少字节。让我们将字符串按照这些模板生成二进制，三个字母都是7位，于是在最高位补0让它变成8位，这样每个字符的位数都是8的倍数，以后就很容易分开了，两个中文字可能是15位又可能是16位，那只能用3字节的UTF8模板了，用字符的0和1将模板里的x替换掉，如果不够位数用0补，也就是将最左边的x干掉啦！最后得到：3*8+2*24=72，72/6=12，12/9=130%，将字符串转成base64后大概占原大小的130%左右。看来上面的压缩技术只适合将数据压成二进制文件存储，不适合网络传输，不知这样说对不对，我对二进制文件不是很了解。

LZW唯一的不足就是还原时不确定读取多少位进行逆操作，如果能知道下一个索引是几位数的话我们真的能把GB级的数据压缩成KB级，只要反复进行压就行了，比如进行几百几千次压缩，解压时再进行同样次数的逆操作就行了，时间我们有的是。我试过同时压缩解压几百次，能实现无损逆操作，但压缩效果实在不行！因为要固定每次只读一位进行逆操作，所以压缩时必须将码表的索引控制在十以内，超过十就清空码表重新生成。LZW是靠重复出现的字符实现压缩的，靠这十个索引确实不可能压出效果来。每次读两位字符进行逆操作的我也试过了，就是小于十的索引在前面补0，大于100就清空码表，但是这样与在索引之间加分割符没两样，都是越压越大！用单个字符代替多位索引的方法也试过了（用几百个字符代替0-几百之间的索引，还原时再通过码表将单位字符映射为多位数的数字索引），也是不行！还试了很多其它方法：三进制、五进制、七进制、64进制、二合一法则、变身术、替身术、挪位术等，都不尽人意。希望通过此文能抛砖引玉，越多人投入这个领域钻研，我们就越快能获得受益！这里面有多大的市场呢？保守估计有10亿美元吧！这不是吹，古狗（Google）花了1亿美元收购VP6（一种视频压缩技术），曾拟定2亿美元收购Digg！人家古狗既不是疯子也不是呆子，估计很快又会推出3D社交网站吧。想想看，有多少领域迫切需要这样的压缩技术，多媒体网站（视频、音乐、图片等）、网盘存储、网页地图、网页游戏、下载类网站、不久将来的3D社交网站以及逐渐开始流行的云计算...