注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

yeye55的博客

编程就象品一杯清茶,清淡却又深厚。

 
 
 

日志

 
 
关于我

宅男一只,喜欢编程。没事的时候就喜欢抱着电脑看看电影、看看动漫、听听音乐、打打网游、逛逛论坛。清静的时候喜欢专研编程技术,但是发现自己至今仍然只是一只三脚猫。

网易考拉推荐

Delphi下实现数值变量压缩  

2011-11-05 12:06:13|  分类: 数据压缩算法 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

  本文最早于2009年6月19日在编程论坛(programbbs.com)上发表,页面地址:http://programbbs.com/bbs/view12-21325-1.htm 。

1 前言

  众所周知不同的数值变量类型根据其占用字节的大小可以表示不同范围的数值(注:本文只讨论无符号数值类型)。例如:Byte类型占用1个字节可以表示0至255范围的数;Cardinal类型占用4个字节可以表示0至4,294,967,295范围的数。有的时候需要在内存或文件中保存大量的数值数据。这些数值数据大部份都很小,用Byte或Word就可以表示,但有一小部份数值很大,需要用Cardinal表示。为了兼容性通常使用可能出现的最大数值所能容纳的数值类型进行保存,如果大部份数值都很小这种方法会浪费很多空间。于是有这么一种压缩算法:它可以根据数值的大小使用不同长度的字节来表示。例如:小于等于127时占用1个字节,大于127小于等于16,383时占用两个字节。下面来说说这种算法的实现。

2 实现

  一个数值可以用不同长度的二进制位来表示,该算法就是将这些二进制位每7位分割成一个块,然后用一个或多个字节来保存这些块。从数值最低位的块开始保存,从最高位开始向最低位全为0的块不保存。每个字节的低7位用来保存数据,最高位设为标志位。当标志位为1时表示这是最后一个块。现在让我们来看几个范例:假设n是Cardinal类型的变量那么它将占用4个字节(32位),当n等于25时二进制位分割成的块如下(注:左边为高位,右边为低位,下同):

0000 0000000 0000000 0000000 0011001

  最低位的块为“0011001”,高位的块都为0不保存。把最后一个块也是唯一的一个块标志位置1为“10011001”($99)。于是数值25压缩后占1个字节:$99。

  当n等于3541时二进制位分割成的块如下:

0000 0000000 0000000 0011011 1010101

  最低位的块为“1010101”,不是最后一个块标志位置0为“01010101”($55),第二个块“0011011”是最后一个块标志位置1为“10011011”($9B),其它高位的块都为0不保存。于是数值3541压缩后占2个字节:$55,$9B。

  解压缩的过程就是一个反向过程这里就不多说了。压缩和解压缩的代码如下:

//对一个Cardinal数值变量进行压缩并写入缓冲区,返回写入长度。
function PackCardinal(n : Cardinal; Buf :  PByteArray): Integer;
var
    i : Integer;
begin
    i:=-1;
    repeat
         Inc(i);
         Buf[i]:=n and $7F;
         n:=n shr 7;
    until n=0;
    Buf[i]:=Buf[i] or $80;
    result:=i+1;
end;
//从缓冲中读取一个已压缩的Cardinal数值变量进行解压缩,返回读取长度。
function UnpackCardinal(var n : Cardinal;  Buf : PByteArray): Integer;
var
    i,m : Cardinal;
begin
    i:=0; m:=0;
    n:=Buf[i];
    while (Buf[i] and  $80)=0 do
    begin
        Inc(i);  Inc(m,7);
         n:=n or (Buf[i] shl m);
    end;
    n:=n and (not ($80 shl  m));
    result:=i+1;
end;

  使用上述算法进行压缩时,当数值小于等于127($7F)时占一个字节,大于127小于等于16,383($3FFF)时占两个字节,大于16,383小于等于 2,097,151($1FFFFF)时占三个字节,大于2,097,151小于等于268,435,455($FFFFFFF)时占四个字节,大于268,435,455时占五个字节。

3 优缺点

  上述算法的优点是很明显的,它可以有效节约存储空间。假设有10,000个数值,只有10个数值在128至16,383之间,其它数值都小于128。用Cardinal类型进行保存时要占用40,000字节,用上述算法压缩保存后只占用10,010字节。另外它可以用来保存无穷大数,无论多大的数值只要存储空间够用都可以保存。它的缺点也很多:首先就是运算不方便,要进行数值运算时一般都要将数值解压缩出来。其次,如果不进行解压缩就无法知道数值到底占用多少长度的字节,这对于定位访问很不利。还有就是如果保存的数值都很大,那么该算法的压缩比就会很小甚至出现负压缩比,算法的优势将无法体现。

相关文件下载

  项目文件下载(点这里

  评论这张
 
阅读(804)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017