您当前的位置:首页 > 计算机论文>智能科技论文

数据快速压缩算法的研究以及C语言实现

2015-07-08 09:31 来源:学术参考网 作者:未知

数据快速压缩算法的研究以及c语言实现

引言
  现有的压缩算法有很多种,但是都存在一定的局限性,比如:lzw[1]。主要是针对数据量较大的图像之类的进行压缩,不适合对简单报文的压缩。比如说,传输中有长度限制的数据,而实际传输的数据大于限制传输的数据长度,总体数据长度在100字节左右,此时使用一些流行算法反而达不到压缩的目的,甚至增大数据的长度。本文假设该批数据为纯数字数据,实现压缩并解压缩算法。
  1 数据压缩概念 本文由论文联盟http://收集整理
  数据压缩是指在不丢失信息的前提下,缩减数据量以减少存储空间,提高其传输、存储和处理效率的一种技术方法。或按照一定的算法对数据进行重新组织,减少数据的冗余和存储的空间。常用的压缩方式[2,3]有统计编码、预测编码、变换编码和混合编码等。统计编码包含哈夫曼编码、算术编码、游程编码、字典编码等。
  2 常见几种压缩算法的比较
  2.1 霍夫曼编码压缩[4]:也是一种常用的压缩方法。其基本原理是频繁使用的数据用较短的代码代替,很少使用的数据用较长的代码代替,每个数据的代码各不相同。这些代码都是二进制码,且码的长度是可变的。
  2.2 lzw压缩方法[5,6]:lzw压缩技术比其它大多数压缩技术都复杂, 压缩效率也较高。其基本原理是把每一个第一次出现的字符串用一个数值来编码,在还原程序中再将这个数值还成原来的字符串,如用数值0x100代替字符串ccddeee"这样每当出现该字符串时,都用0x100代替,起到了压缩的作用。WWw.133229.Com
  3 简单报文数据压缩算法及实现
  3.1 算法的基本思想 数字0-9在内存中占用的位最大为4bit,而一个字节有8个bit,显然一个字节至少可以保存两个数字,而一个字符型的数字在内存中是占用一个字节的,那么就可以实现2:1的压缩,压缩算法有几种,比如,一个自己的高四位保存一个数字,低四位保存另外一个数字,或者,一组数字字符可以转换为一个n字节的数值。n为c语言某种数值类型的所占的字节长度,本文讨论后一种算法的实现。
  3.2 算法步骤
  ①确定一种c语言的数值类型。
  #define long short #define num 2 union un /* 用来保存数据 */
  ②确定该数据类型最大保存的数字长度。
  比如:short是2字节,即 2的15次方,推算出,最大可以保存字符99999可以推算出#define max_len 5,最多可以对5个数字字符进行换算成short。
  ③编写基本函数。
  字符转换为数值,数值转换为字符 ,单元压缩 ,单元解压缩函数。
  ④实现数字字符串压缩解压缩。
  对任意长度的数字字符串进行从左到右每五个进行分组,然后再采用单元压缩。
  /* 数字字符串压缩 */char* compress(char *cnum2, char* cret)
  /* 数字字符串解压缩 */ char* uncompress(char *cret, char* cnum2)
  3.3 算法的优化
  ①前置数字字符0,比如012345 解压缩的时候 0就会丢掉,解决的办法就是在每一组之前加固定的数字字符,我们加固定的1,如static char* addfixednum(char *cnum, char*cnumfixed),/*解压缩时去掉*/ static char* delfixednum(char *cnumfixed, char *cnum)。
  ②不同操作系统的大端(big endian)小端(little endian)问题,比如:windows是小端规则,unix是大端规则。通过定义宏#define l_endian,来解决该问题。

  ③对于字符转换为数字后,十六进制数字中间字节含0x00的情况处理,如下:1011000012120000123915150101 转换成十六进制0xab 0x00 0xcc 0x00 0x12 0x39 0xff 0x11,考虑到数据类型short是2位且有符号位的,而我们需要压缩的数子字符不存在正负的情况,则可利用该符号位,对含有0x00的压缩片段打上一个标记。
  3.4 关键代码
  ①单元压缩
  static char *compress_unit(char *cnum, char* cret)
  {long l = atolong(cnum);
  return getchar(&l, cret);}
  ②单元解压缩
  static char *uncompress_unit(char *cret, char* cnum){
  int i = 0; unsigned char c; union un u;
  for(i = 0; i < num; i++) {
  ……
  c = c >> 7;
  if( c > 0 ) { u.c[1] &= 0x7f; u.c[0] = 0x00; }
  return longtoa(u.l, cnum); }
  ③数字字符串压缩
  char* compress(char *cnum2, char* cret){
  count = strlen(cnum)/max_len + ((strlen(cnum)%max_len) == 0 ? 0 : 1);
  for(; i < count; i++){
  memset(cnum_unit,0x00,sizeof(cnum_unit));
  ……
  len += num; }
  return cret; }
  ④数字字符串解压缩
  char* uncompress(char *cret, char* cnum2){
  memset(cnum, 0x00, sizeof(cnum));
  count = strlen(cret)/num + ((strlen(cret)%num) == 0 ? 0 : 1);
  for(; i < count; i++){
  ……}
  return delfixednum(cnum, cnum2); }
  3.5 算法的实现
  以s1为需要进行压缩的数字字符, s2 为压缩后的字符, s3为解压缩后的字符进行验证,验证函数如下。
  void main(){
  ……
  char s1[] = "0123456789012345678901234567890123 456";
  char s2[buf_len+1], s3[buf_len+1];
  memset(s2,0x00,sizeof(s2)); memset(s3,0x00,sizeof(s3));
  printf("s1 = [%s] len = [%d]\n",s1,strlen(s1));
  compress(s1,s2);
  uncompress(s2,s3);
  printf("s3 = [%s],len = [%d]\n", s3, strlen(s3)); }
  ①输入简单的数字字符,运行结果如图1。
  ② 输入连续连0的数字字符,运行结果如图2。
  从上面可以看出,不管输入任何字符,都可以按照原来的字符进行解压缩出来。
  4 结束语
  本文根据企业的实际需要,研究并实现了对简单报文数据的压缩及解压缩算法,目前已经应用于企业的项目开发中。
相关文章
学术参考网 · 手机版
https://m.lw881.com/
首页