近年来, 随着中国海洋战略走向深蓝, 我国深远海调查和科考任务越来越多, 使用的科考仪器设备也越来越多。浮标作为一种全天候式的海上观测平台, 能在深远海的海区中连续地、自动地、长期地观测所处海区的海洋气象水文乃至生物化学要素, 是我们了解深海大洋的一个重要设备手段。深远海观测浮标的使用过程中, 离不开数据的通信, 与近岸观测不同, 深远海观测设备保养和回收周期较长, 工作环境更为恶劣和复杂, 因此对浮标通信的可靠性和安全性提出了更高的要求。现阶段深远海海洋观测浮标数据需往往受限制于通信卫星带宽、自容式电池电量有限等问题影响, 发送数据量较小或者效率较低。因此对深远海观测浮标通信数据进行压缩, 对提升通信质量具有很大的必要性。

国内外对数据压缩应用到海洋浮标观测数据领域的研究较少。原因一可能是海洋浮标观测数据量本身较小, 压缩空间不大; 二可能是现阶段大部分海洋观测浮标是作为近海观测浮标应用, 带宽足够, 因此压缩意义不大。随着深远海观测浮标的应用越来越多, 数据量和卫星通信费用的考量越来越重要, 所以对海洋观测数据进行压缩具有必要性。由于海洋科学观测数据要求准确性和科学性, 所以需要对数据进行无损压缩, 能保真地还原原始观测数据, 故有损压缩不在本文讨论范围。无损压缩算法大致分为两类, 一种是基于统计, 一种是基于字典的, 本文分别选取两类中较为具有代表性的Huffman算法和LZW算法, 对海洋观测浮标通信数据进行压缩应用研究。

1 浮标通信数据压缩算法及实现 1.1 Huffman算法及实现

Huffman算法是一种基于统计的压缩方法, 并且是一种可变长编码(VLC), 它将数据本身字符的形式拆散, 形成一个以0、1位形式的新的数据串, 其本质是对一段数据中的字符进行重新编码, 出现频率越高的字符, 其对应的编码也越短, 从而达到压缩数据的目的。

对于海洋观测浮标数据来说, 观测数据是一串ASCII码数据, 每个ASCII码占用8个字节大小, 而且数据中的字符往往只使用到ASCII码中的数字和个别标点符号, 故而为Huffman算法提供了可利用的压缩空间。

对于本文Huffman编码来说, 大致需要4个步骤(如图 1所示): (1)对所要压缩的数据进行遍历; (2)对应字符串在数据中的权值(概率); (3)数据中的字符串建立Huffman树, 并建立相应的Huffman码表; (4)通过建立的Huffman树对所要压缩的数据进行重构, 形成压缩数据。

经过编码后的数据文件, 主要包含2个部分: Huffman码表部分和压缩后的数据内容部分。解压缩的时候, 先把Huffman码表取出来, 然后对压缩内容部分各个字符进行逐一解码, 形成原数据文件。

Huffman编码的核心在于Huffman树的建立并建立与之相应的Huffman码表, Huffman树的建立是通过最优二叉树节点实现, 将其定义为一个指针的结构体, 可以方便地实现节点的遍历和置换。其中部分代码如下:

typedef struct _tagHtNode
{
  _tagHtNode(unsigned char byData, unsigned long
  dwWeight): Val(byData, dwWeight), pLeft(0),
  pRight(0){}
  struct _tagDataWW
    {
      _tagDataWW(unsigned char Data, unsigned
      long Weight):byData(Data),
      dwWeight(Weight){}
      unsigned char byData;
      unsigned long dwWeight;
    }
  _tagHtNode *pLeft;
  _tagHtNode *pRight;
}

1.2 LZW算法及实现

LZW算法是一种基于字典模型的的压缩算法。最早由Lemple、Ziv、Welch三人共同提出并创造, 故而用他们的名字对算法进行命名。LZW算法的本质是要建立一个字典表, 通过使用较少的字符来表示较长的重复字符来实现对数据的压缩效果。通常对LZW算法来说, 数据是一个数据流的概念, 算法将数据流中每个第一次出现的字符建立一个字典串表(一般用数字表示相应字符), 不断地读取数据流中下一个字符, 如果没有字典中对应字符就在字典中添加新的对应关系串表, 如果在在字典中有对应字符, 就用已知的字典中的对应数字表示, 如此反复, 直到遇到结束标志位字符结束, 最后输出经过字典翻译之后的压缩数据。

对于海洋观测浮标数据来说, 通信数据中主要涉及位置信息、水文气象等数字信息, 大部分是数字信息和标点信息, 并且有大多数观测数据数据格式相同, 这就为LZW算法提供了压缩空间。在LZW算法中, 单字符可以使用ASCII码字典来表示(0至256), 大于等于2个字符的字符串, 可使用的数字范围是256至4 096(LZW算法中, 一般字典中使用12 bit来表示一个字符串), 对于单次通信的浮标观测数据来说已经足够。这样一来, 一个字符(8 bit)需要用12 bit来储存, 而大于等于2个字符的字符串(≥16 bit)也可以用12 bit来存储, 所以在总体上重复率够高的字符串越多, 起到压缩效果越好。经过以上分析, 我们可以使用LZW压缩算法来对海洋观测浮标数据进行压缩, 算法流程如图 2所示, 因为LZW算法在传输过程中不需要携带字典, 故而需要按顺序依次读取字符, 这样在解码时才能不依靠字典无损地解析出原始数据, 其中算法实现部分代码如下:

  for (i = 1; i < size; i++)
{
  char_type ch = in[i];
  string[str_len] = (unsigned char) ch;
  str_len++;
  if (dict_contains(dictionary, string, str_len))
    continue;
  else
  {
    str_len--;
    code = *dict_get_code(dictionary, string, str_len);
    code_len = code_length(code);
    if (code_len > cur_len)
      {
        write_data(INC_LENGTH, cur_len);
        cur_len++;
        cur_size = 1$ \ll $cur_len;
      }
      write_data(code, cur_len);
      if (!dictionary_full)
      {
      dict_insert(dictionary, string, str_len + 1);
      }
     *string = (char_type) in[i];
      str_len = 1;
      if (!dict_allow_insert(dictionary))
        dictionary_full = true;
    }
}

2 数据测试和分析

本文测试数据选取于“全球变化与海气相互作用”专项在西太平洋中南部水体综合调查冬季航次布放的一套深海观测浮标。此套深海观测浮标的单包数据长度是定长(926 bit), 包含信息有:时间、浮标位置(经纬度)、浮标状态标志位、风速风向、温度、湿度、浪高浪向、水流速(ADCP)。数据时间是从2016年1月至3月, 在此时间内随机选取观测浮标数据组(共50组)进行测试, 对每组数据分别使用Huffman和LZW算法测试数据压缩率, 测试结果如图 3所示。

通过两种算法的测试结果分析, 可以得出以下几个判断:

(1) Huffman算法对此组观测数据的压缩率大致在45%左右, LZW算法对此组观测数据的压缩率大致在55%。针对本文所使用的海洋观测浮标通信数据而言, 两种方法都能较好地对数据进行压缩。

(2) 从压缩率角度看, Huffman算法要优于LZW算法, 压缩率大致低10%左右。分析可能是因为此包数据的数据格式里面, 重复的字符较高, 而相对重复的长字符串相对较少的原因, 故而从算法来判断Huffman算法压缩率略优。

(3) LZW算法的压缩率浮动较大, 而且最大差值可达15%左右; 而Huffman算法的压缩率曲线浮动较小, 并且最大差值在5%左右。根据数据特点, 数据包中0到9的数字和相应的标点符号等字符出现的概率分布大致是相同的, 故而Huffman算法的稳定性较高一些, 而这些字符出现的排列组合形式可能有较大区别, 对以字符串形式压缩的LZW算法来说稳定就会稍差一些。

(4) 整体看Huffman和LZW算法在压缩率上具有一定的线性相关性。两种算法虽然一个是基于统计的压缩算法, 一个是基于字典的压缩算法, 但本质上都属于使用较少位数来表示数据中较长的位数, 实质上都是针对数据中大量的重复数据除去冗余, 故而存在一定程度上的相线性关性。

(5) 从两种算法复杂度上分析, LZW算法要优于Huffman算法。首先从时间复杂度上分析, Huffman算法至少要遍历两次数据流, 而LZW算法只需要一次遍历数据即可生成压缩数据, 故而在算法结构上LZW算法的时间复杂度要优于Huffman算法; 其次从空间复杂度上分析, 两者在数据压缩重构过程中都产生类似字典性质的数据存储空间, 根据海洋观测浮标数据特点, 两者所需空间复杂度大致相同, 但LZW算法在传输过程中不需要此字典, 而Huffman算法需要通过传输此字典来进行解码, 故LZW算法在空间复杂度要略优于Huffman算法, 因此总体上LZW算法复杂度要优于Huffman算法。

3 结语

本文主要通过两种主流无损压缩算法在海洋观测浮标数据压缩中的应用分析, 对两种压缩算法效果进行实验比测。实验结果, 从压缩率角度看, Huffman算法要略优于LZW算法, LZW算法复杂度要略优于Huffman算法。但是两者在压缩效果上, 相较于源数据都能压缩约45%甚至以上, 都基本能满足浮标远程通信需求。

在海洋观测浮标数据通信的实际应用中, 压缩算法的选用还要考虑到通信过程的编码效率的影响, 主要是运算速度、内存及编码时耗等因素的影响。在这些方面, LZW算法相对于Huffman算法有一定的优势, 遍历数据次数少, 需要内存空间也相对较小, 所以运算速度会稍快。所以在实际使用中, 两种算法可以兼顾考虑, 根据具体情况进行选择, 都能较好地达到数据压缩要求, 并提高数据的保密和安全性。