月度归档:2012年07月

整数的可变字节编码压缩算法

在各个平台中整数占用的字节数一直比较固定,通常是4个字节。它的表示的整数范围是-2147483648~2147483647。然而对于一些数值较小的整数,因为有大量的位数是前导0,这些比特在数值的表示中是没有意义的,仍旧花费4个字节去存储则显得有些浪费。这里的一篇文章『Variable byte codesd』,讲述正整数的可变字节编码的压缩,它可以在需要存储大量正整数的情况下有着较为实际的应用。

正整数可变字节编码压缩算法的思路是:
将每个字节分为2个部分:低7位为负载位(payload),用于存储数值,最高位为标志位(continuation bit),取值0或者1,用于标识当前字节是否是该整数在可变字节编码中的最后一个字节。

例如正整数130,它的二进制表示(4字节,共32位)为:00000000 00000000 00000000 10000010。经过可变字节编码压缩之后,130可压缩为2个字节:
Byte0: 0 0000010
Byte1: 1 0000001
Byte0的最高位为0,表示该字节并不是最后一个字节,低7位存储原比特流中的低7位。Byte1的最高位为1,表示该字节已经是最后一个字节,低7为存储原比特流中的第8位-第14位。舍弃原比特流中的所有前导0。

整数可变字节编码压缩算法的Java实现如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
/**
 * 对正整数列表进行可变字节编码,返回压缩后的字节数组。
 * @param intList
 * @return
 */
private static List<Byte> intToByte(List<Integer> intList) {
    List<Byte> list = new ArrayList<Byte>();
    if (intList == null) {
        return null;
    }
    for (int n : intList) {
        //遍历列表中的每个正整数。
        while (n > 0) {
            int byteOf = n % 128; //得到正整数的低7位。
            if (n < 128) {
                //如果n值已经能由7位表示,则该字节是最后一个字节。
                byteOf += 128; //将该字节的最高位置为1。
                list.add((byte) byteOf);
                break; //当前整数的可变字节编码结束。
            } else {
                list.add((byte) byteOf);
            }
            n /= 128;
        }
    }
    return list;
}
 
/**
 * 将可变字节编码形式存储的字节数组还原为正整数列表。
 * @param byteList
 * @return
 */
private static List<Integer> byteToInt(List<Byte> byteList) {
    List<Integer> list = new ArrayList<Integer>();
    int n = 0;
    int byteStartPerInt = 0;
    for (int i = 0; i < byteList.size(); i++) {
        //依次读取字节数组。
        if (byteList.get(i) >= 0) {
            //如果当前字节的值大于0,则表示最高位是0,该字节不是最后的字节。
            n += byteList.get(i) * Math.pow(128, i - byteStartPerInt);
        } else {
            //如果当前字节的值小于0,则表示最高位是1,该字节是最后的字节。
            n += (byteList.get(i) + 128) * Math.pow(128, i - byteStartPerInt);
            list.add(n);
            n = 0;
            byteStartPerInt = i + 1;
        }
    }
    return list;
}

经过简单的测试,随机生成1w个值为1-105之间的正整数,上述算法的压缩比约为0.29。也就是说,本来需要4w个字节存储的整数现在只需要2.8w左右的存储空间。随着测试数据的值越大,压缩率会变小,而当测试数据的值越小,压缩率会变大。极端情况下,上述算法的压缩率最大能达到75%。

由于可变字节编码压缩算法是建立在标识位的基础上的,因此,当待编码的正整数大于1284时(针对4个字节表示整数的情况),算法会失去作用,非但不能压缩,反而会引起数据膨胀,这也是该算法的最大缺陷。另外,如果对待编码正整数的顺序没有要求的话,可以先对整数列表排序,然后存储相邻两个正整数之间的差值,通过这样的操作之后,待编码的整数就以“差值”的形式变小了,从而提高压缩率。

--EOF--

Base64编码算法

严格意义上,Base64编码不算是一种加解密算法,它的主要作用是能用可打印字符表示二进制数据,因此在mime email和xml中都较通用。虽然经Base64编码后的字符串看似无规则,实际上只要知道了算法就能轻易解码/解密。

Base64编码是将源字符串以3个字节为单位,将这24bit分成4组,每组6bit。再在每组6bit数据左侧补2bit的0,凑足8bit,即1个字节。经过这样的变换,原先3个字节(24bit)的数据就被编码成了4个字节(32bit)的数据。然后以这4个字节的值为索引,分别去字符对照表中取出相应的字符即完成编码。编码后每个字节的值不会大于63,字符对照表索引0-25为大写英文字母,26-51为小写英文字母,52-61为数字0-9,62为'+',63为'/'。由此可见, Base64的编码算法是完全可逆的,一个编码后的字符串依次进行上述过程的逆操作就能实现解码。

对于源字符串不足3个字节的情况,Base64编码要经过两个步骤的补位操作,第一步是当目前bit数模6不等于0时,则在其右端补0,直到模6等于0为止。第二种是在第一步基础上,如果经过补0后的bit数除6小于4,那么小几个就补几个等号('=')。根据这个规则,一个Base64编码后的字符串最多只会在其末尾包含2个等号。因为最坏情况下,当源字符串只包含1个字节(8bit)时,首先会在其右端补4bit的0,凑足12bit(达到6的倍数),12除以6等于2,故需要填充4-2=2个等号。最好情况下,当源字符串的字节数正好是3个倍数时,Base64编码的冗余率为33%,其余情况下,冗余率会稍稍大于这个数字。

此外,RFC2045还规定,编码后的字符串每76个字符就要换行,换行是指每76个字符就要加回车换行符(\r\n)。最后一行即使未满76个字符也要加回车换行符。

下面以一个简单的例子说明:
字符串"AB"的ASCII码值为65和66,换成二进制是0100,0001和0100,0010。共16bit,不满足模6等于0,故需要在其右侧补2个0。
经右侧补0后的bit流如下:010000010100001000。
现以6个bit为一组分成3组,如下:010000,010100,001000。再在每个分组左侧补0凑足8bit,经左侧补0后形成的3个字节的值分别为16,20和8,对应着字符对照表中的Q,U和I。因此,"AB"经Base64编码后的字符串为QUI=,外加一个回车换行符\r\n。

对于非ASCII字符来说,一个字符可能是由2-4个字节构成,例如UTF-8或者GBK编码下的中文。要计算它们的Base64编码,只需获取该编码方式下字符的字节数组,然后按字节对其进行Base64编码。

Java中可调用org.apache.commons.codec.binary.Base64类的encode和decode方法来对字符串进行编码和解码操作。

--EOF--

『春天责备』

周云蓬,九岁失明,在黑暗中正式开始人生,写过诗,当过流浪歌手,出过专辑出过书,做过公益,懂得旅行的意义,每一样都还做得不错的,活得蛮精彩。写诗和唱歌之于周云蓬的意义,用他自己的话诠释最为准确:“我把我黑暗的日子拧啊拧,拧出窗台上的一张专辑和一本书,为那些虚度的光阴命名,还有一些流失的、不可命名的日子和人,为她们曾默默地微笑过存在过做见证。”

我只听过他之前的一张专辑『清炒苦瓜』,说句实话,我不大懂得欣赏“新民谣”,歌词现实味浓重在曲调上却又故作清新,为什么不干脆再猛烈一点直奔摇滚而去呢?周云蓬的给人的形象就不用多说了,像『弯刀』中的男主角丹尼·特乔(wiki),然而野兽的外表之下有颗文艺的心。我不喜欢他的歌,但我欣赏他写的歌词他的诗他的才情。

例举一二:


    春天,责备没有灵魂的人。


    无数平凡的昼夜
    排成黯淡的岁月
    是怎样的嘴
    吞噬了异乡的孩子
    把他们消化成喧哗与霓虹
    又呕出失败者


    如果我是尸体
    就该投入明亮的白昼焚烧
    在阳光下请你喝一瓶啤酒
    谈谈春天,然后,告诉你我有多想你


    我们活在租来的房子里
    我们活在公共汽车里
    我们活在蒙着灰尘的书里
    我们活在电视的荧光屏里
    一旦有一天看见了蓝天
    我们就成了失业者


    暗
    物质
    万有引力
    能量转化及守恒定律
    无限
    永不复归的时间
    我们咀嚼能咬碎的一切
    其余的
    再也没有可能


    在春天
    有人悲伤
    有人无钱掩埋他们的亲人


    心中寂寞
    互相怨恨又疼痛
    像拔掉了一颗牙
    说话
    或是沉默
    都带着血腥
    想不起某人的姓名了
    那种向后掏的滋味
    让人彻夜难眠


    今天轻如鸿毛
    落进雨地
    自己踩一脚
    别人踩几脚
    大喊一声
    吓自己一跳
    像蚂蚁打喷嚏

--EOF--