C#压缩整数及其解压缩算法的实现

算法/数据结构频道 >

时间: 2008-08-21 22:24

压缩算法描述

当整数的大小在0x00000000 (00000000 0000000000000000 00000000B)到0x0000007F (00000000 00000000 0000000001111111B)之间时，采用1个字节存放整数值，该字节最高位为0。压缩后的值形如[0bbbbbbb]B。
当整数的大小在0x00000080 (00000000 00000000 00000000 10000000B)到0x00003FFF (0000000000000000 0011111111111111B)之间时，采用2个字节存放整数值，第一个字节的最高位为1，第二位为0。压缩后的值形如[10bbbbbb bbbbbbbb]B。
当整数的大小在0x00004000 (00000000 00000000 01000000 00000000B)到0x1FFFFFFF(00011111 11111111 1111111111111111B)之间时，采用4个字节存放整数值，第一个字节的最高位和第二位是1，第三位是0。压缩后的值形如[110bbbbbbbbbbbbb bbbbbbbb bbbbbbbb]B。
该压缩算法采用大尾数法，即第一个字节是原整数的最高一个字节。

图1更为直观地展示了区间的划分。
图1 - 整数压缩算法

解压缩算法描述

如果读到的第一个字节b0型如0bbbbbbb（与0x80进行按位与运算，结果为0x00），则采用1个字节存放整数值。原整数值=b0。
如果读到的第一个字节b0型如10bbbbbb（与0xC0进行按位与运算，结果为0x80），则采用2个字节存放整数值，需要再读取1个字节b1。原整数值=(b0 & 0x3F) << 8 | b1。
如果读到的第一个字节b0型如110bbbbb（与0xD0进行按位与运算，结果为0xC0），则采用4个字节存放整数值，需要再读取3个字节b1、b2、b3。原整数值=(b0 & 0x1F) << 24 | b1 << 16 | b2 << 8 | b3。

[复制到剪贴板]

CODE:

public static UInt32 Decompress(this Byte[] data)
{
if (data == null)
throw new ArgumentNullException("data");
if (data.Length == 0)
throw new InvalidCompressedIntegerException();
if ((data[0] & 0x80 /* (1000000B) */) == 0 // 使用一个字节存储大小（0bbbbbbb B)
&& data.Length == 1)
{
return (UInt32)data[0];
}
else if ((data[0] & 0xC0 /* (11000000B) */) == 0x80 /* (10000000B) */ // 使用两个字节存放大小（10bbbbbb bbbbbbbb B）
&& data.Length == 2)
{
return (UInt32)((data[0] & 0x3F /* (00111111B) */) << 8 | data[1]);
}
else if ((data[0] & 0xD0 /* (11100000B) */) == 0xC0 /* (11000000B) */ // 使用四个字节存放大小（110bbbbb bbbbbbbb bbbbbbbb bbbbbbbb B）
&& data.Length == 4)
{
return (UInt32)((data[0] & 0x1F /* (00011111B) */) << 24 | data[1] << 16 | data[2] << 8 | data[3]);
}
else
{
throw new InvalidCompressedIntegerException();
}
}

learnerkk 时间: 2008-08-22 08:36

呵呵，这些什么压缩整数和压缩数组之类的算法还是挺有意思的，不过现在貌似也不用那么节约空间了。

哎……现在编程的门槛越来越低了。

顺便赞一下管理员的头像，很有爱。

1 / 1 页

跳转页

作者
admin

添加至收藏夹