CN1790918A - 基于虚拟信源和神经网络的无损数据压缩方法 - Google Patents

Abstract

本发明属于计算机技术领域，本发明提供一种基于虚拟信源和神经网络的无损数据压缩方法。其步骤如下：a.BP压缩：(1)把所有要处理的数据视为由虚拟信源产生的字符串；(2)建立虚拟信源的BP神经网络模型；(3)用BP模型参数去编码由虚拟信源产生的字符串；b.BP解压缩：(1)恢复BP模型参数；(2)恢复虚拟信源的模型；(3)虚拟信源的模型结合取整变换构建字符串的恢复映射；(4)完全恢复虚拟信源产生的字符串。本发明可用于计算机系统文件、医疗、保密通讯等。

Description

基于虚拟信源和神经网络的无损数据压缩方法

技术领域

本发明属于计算机技术领域，本发明提供一种基于虚拟信源和神经网络的无损数据压缩方法。

背景技术

我们注意到，随着光纤网和光盘设备等宽带信道和大客量存储介质的采用，信道带宽及存储量变越来越大，但数据量的增加远远快于带宽和存储量的增长。因此高效的数据压缩仍是不可缺少的。特别是在计算机系统文件、医疗、保密通讯等对数据质量要求苛刻的场合中，高效的无损压缩技术仍十分必要。

迄今没有高效的无损压缩方法。目前尽管有哈夫曼编码、算术编码、字典编码、游程编码、预测编码等众多无损压缩方法，但它们有三个公共缺陷：

1.这些无损数据压缩方法的压缩思想都只是尽量消除数据中统计冗余，数据中的其它冗余一点也弃除不掉。事实上，一大堆数据很可能有很大的非统计冗余，如平面上的一斜直线段上点的集合是由某个形如y＝kx+y₀，x∈(a，b)的“虚拟信源”给出的。显然这里斜直线段上点的集合几乎没有“统计”冗余，而我们可用{k，y₀，a，b}去编码它，从而成百成千倍压缩它，也说明该集合有很高的非统计冗余。

2.它们的压缩比小。对一般图象、文本的压缩比只有2∶1左右，显然一些被压缩过的图象、文本仍有很高的冗余度。

3.对已用熵编码压缩过的数据无法再压缩。由于所有熵编码，如哈夫曼编码、算术编码、字典编码、游程编码、预测编码，都是基于‘消除数据中统计冗余’思想来构建的，因此已用熵编码压缩过的数据几乎没有统计冗余了，从而也就不能再用哈夫曼编码、算术编码、字典编码、游程编码、预测编码等压缩了。

人们已尝试用高容错工具，如神经网络，来构造无损数据压缩方法，但没有获得成功。现有用神经网络构造的数据压缩方法都是有损的。

基于对传统的无损数据压缩的上述认识，本发明提出一种基于虚拟信源和神经网络的无损数据压缩方法，该方法不走‘仅消除数据中统计冗余’的过去无损数据压缩方法的唯一老路，独辟蹊径提出‘基于虚拟信源和神经网络’的建模压缩新思想，提高了无损数据压缩率。

发明内容

本发明提出一种基于虚拟信源和神经网络的无损数据压缩方法，从根本思想上提出不同于‘仅消除统计冗余方法’的基于虚拟信源和神经网络的建模压缩方法，提高了数据无损压缩比率，而且该压缩方法可压缩已用熵编码压缩过的数据(已弃除部分统计冗余数据)，从而用该压缩方法与已有熵编码结合可以获得具有更高压缩比的无损数据压缩方法。基于虚拟信源和神经网络的无损数据压缩方法的实现技术是人工神经网络，是国际国内首次应用神经网络实现无损数据压缩方案。

本发明首先提出了虚拟信源概念及基于虚拟信源和人工神经网络构建数据压缩方法的思想，设立了0与1的字符长串的通用虚拟信源Y，然后用神经网络建立了虚拟信源Y的模型，又用该模型和一个取整函数构造出了基于虚拟信源和神经网络的无损数据压缩方法。实验表明，一般情况下此压缩法的压缩比为3∶1。其步骤如下：

a.BP压缩

1.把所有要处理的数据视为由虚拟信源产生的字符串；

2.建立虚拟信源的BP神经网络模型；

3.用BP模型参数(数据量少于原始字符串的数据量)去编码由虚拟信源产生的字符串；

b.BP解压缩

1.恢复BP模型参数；

2.恢复虚拟信源的模型；

3.虚拟信源的模型结合取整变换构建字符串的恢复映射；

4.完全恢复虚拟信源产生的字符串。

附图说明

图1是本发明的压缩原理与解压缩原理流程图。

具体实施方式

本发明提供一种基于虚拟信源和神经网络的无损数据压缩方法，其流程图如图1所示。本发明实施步骤如下：

1.建立要处理的原始数据的虚拟信源。设有待压缩的长串γ＝c₁…c₄₉₁₅₂，c_j＝0 or 1，其中γ的长度为49152。下面定义12维单位超立方体顶点和中心的集合为原像集，像落在12维单位超立方体表面和中心的映射Y。称Y为γ＝c₁…c₄₉₁₅₂，c_j＝0 or 1的虚拟信源。

映射Y:设A＝{(x₁，…，x_i，…，x₁₂)|x_i＝0，1}把(x₁，…，x_i，…，x₁₂)按二进制数x₁x₂…x_i…x₁₂的大小倒序排列，即排为有序点a₁＝(1，1，…，1)，a₂＝(1，…，1，0)，a₃＝(1，…，1，0，1)，…，a₄₀₉₅＝(0，…，0，1)，a₄₀₉₆＝(0，…，0，0)。假定待压缩的0与1的字符串γ＝c₁…c₄₉₁₅₂，c_j＝0 or 1，其中γ的长度为49152，记B＝{b_j|b_j＝(c_12x(j-1)+1，…，c_12×j)，1≤j≤4096}，注：b_j中的c_i要转换为0与1数的形式，定义Y为A到B的映射

                         Y:A→B

              Y:a_i→b_i，i＝1，…，4096，a_i∈A，b_i∈B

即b_i＝Y(a_i)，i＝1，…，4096。

2.建立虚拟信源的神经网络模型。由于虚拟信源Y是有限点集A到有限点集B的有界映射，它一定可以扩充为球 A＝{(x₁，…，x_i，…，x₁₂)|0≤|x_i|≤1，i＝1，…，12}上的有界连续映射 Y。由有关结果可知，存在3层BP网络充分逼近 Y，自然该网络充分逼近Y。

我们根据实践经验，考虑到有4096个样本要处理，选用3层的有960+64＝1024个自由度的BP模型来逼近Y。选定神经网络某一满足条件的状态作为虚拟信源Y的模型，取模型参数编码字符串γ＝c₁…c₄₉₁₅₂，c_j＝0 or 1，以便压缩字符长串γ。本发明用3层64个神经元(输入、输出层各12个，隐含层40个)和隐含层输出函数为Sigmoid函数的BP模型来作为特定映射Y的逼近映射。其中960个接权值为w_ij ⁽¹⁾，i＝1，…，12，j＝1，…，40；w_ij ⁽²⁾，i＝1，…，40，j＝1，…，12和64个阈值为w_j ^(k)，j＝1，…，12，k＝1，2，3，w_j ⁽²⁾，j＝29，…，40。

3.BP压缩：如前设定待压缩的长串γ＝c₁…c₄₉₁₅₂，c_j＝0 or 1，其中γ的长度为49152，a_k，b_k，k＝1，…，4096及映射Y。(i)用顺序样本(a_k，b_k)训练所选BP网络，k＝1，…，4096，训练时设置变量|w_ij ^(k)|，|w_j ^(k)|的上界为128，所有权值w_ij ^(k)和阈值w_j ^(k)都精确到小数点后2位，(ii)选定BP网络的一状态(称为稳态)：该状态下输出b_k′与期望输出b_k的分量差的绝对值小于0.49，即|b_ki′-b_ki|＜0.49，i＝1，…，12，(iii)在稳态时，顺序取960个神经元联接权值w_ij ⁽¹⁾，i＝1，…，12，j＝1，…，40；w_ij ⁽²⁾，i＝1，…，40，j＝1，…，12和64个阈值w_j ^(k)＝1，…，12，k＝1，2，3，w_i ⁽²⁾ j＝29，…，40，作为字符长串γ的编码，(iv)顺序把960个神经元联接权值和64个阈值依次2进制编码，方案是用2个字节16位为每个w_ij ^(k)，w_j ^(k)编码，其中1位是符号位，1位是小数点记号位，7位用于小数点后2位编码，7位用于小数点前2位编码(此编码可确保当 $\left|w_{\mathrm{ij}}^{\left(k\right)}\right|<128+1,\left|w_j^{\left(k\right)}\right|<128+1,$ w_ij ^(k)，w_j ^(k)精确到小数点后2位时，编码正确有效，尽管压缩时编码有偏差，但是经下面解压缩方法解压缩之后可完全恢复γ。

由上述原理可知，若(i)，(ii)能顺利进行，则该压缩方法的压缩比为

$\frac{6\&times;1024\&times;8}{960\&times;13\&times;64\&times;16}=\frac{3}{1}$

4.BP取整函数解压缩：BP取整函数解压缩模型是由所选BP网络构成的映射复合(或外套)取整函数而成。(i)恢复稳态时的w_ij ⁽¹⁾，i＝1，…，12，j＝1，…，40，k＝1，2；w_ij ⁽²⁾，i＝1，…，40，j＝1，…，12，值和稳态时的阈值w_j ^(k)，j＝1，…，12，k＝1，2，3，w_j ⁽²⁾，j＝29，…，40，，恢复BP模型稳定状态，(ii)把恢复的网络视为一固定映射Y¹，这时Y¹是Y的似近映射，且逼近度量值小于0.49(注：与理论逼近度至多相差0.01，见附页的数学严格证明)，(iii)把Y¹与取整函数[y_i+0.5]，i＝1，…，10，复合得[y_i(X)+0.5]，i＝1，…，12，X＝(x₁，…，x_i，…，x₁₂)，(iv)把a_k，k＝1，…，4096顺序输入复合函数[y_i(X)+0.5]，i＝1，…，12中，顺序获得b_k，k＝1，…，4096，(v)由b_k，k＝1，…，4096完全恢复长串γ＝c₁…c₄₉₁₅₂。

实施例：

任取待压缩的长串γ＝c₁…c₄₉₁₅₂，c_j＝0 or 1，其中γ的长度为49152(长串长度超过49152，则分成若干段长度为49152的子段，若长度不够49152，则在串后面补若干个0使其长度变为49152)。

1.建立γ＝c₁…c₄₉₁₅₂，c_j＝0 or 1的虚拟信源Y。映射Y：设A＝{(x₁，…，x_i，…，x₁₂)|x_i＝0，1}把(x₁，…，x_i，…，x₁₂)按二进制数x₁x₂…x_j…x₁₂的大小倒序排列，即排为有序点a₁＝(1，1，…，1)，a₂＝(1，…，1，0)，a₃＝(1，…，1，0，1)，…，a₄₀₉₅＝(0，…，0，1)，a₄₀₉₆＝(0，…，0，0)。假定待压缩的0与1的字符串γ＝c₁…c₄₉₁₅₂，c_j＝0 or 1，其中γ的长度为49152，记B＝{b_j|b_j＝(c_12x(j-1)+1，…，c_{12 ×j})，1≤j ≤4096}。注：b_j中的c_i要转换为0与1数的形式。定义Y为A到B的映射

                             Y:A→B

              Y:a_i→b_i，i＝1，…，4096，a_i∈A，b_i∈B

即b_i＝Y(a_i)，i＝1，…，4096。

2.建立虚拟信源Y的神经网络模型。具体用神经网络3层64个神经元(输入、输出层各12个，隐含层40个)和隐含层输出函数为Sigmoid函数的BP模型来作为特定映射Y的逼近映射。其中960个接权值为w_ij ⁽¹⁾，i＝1，…，12，j＝1，…，40；w_ij ⁽²⁾，i＝1，…，40，j＝1，…，12和64个阈值为w_j ^(k)，i＝1，…，12，k＝1，2，3，w_j ⁽²⁾，j＝29，…，40。

3.γ的BP压缩：如前设定待压缩的长串γ＝c₁…c₄₉₁₅₂，c_j＝0 or 1，其中γ的长度为49152，a_k，b_k，k＝1，…，4096及映射Y。(i)用顺序样本(a_k，b_k)训练所选BP网络，k＝1，…，4096，训练时设置变量|w_ij ^(k)|，|w_j ^(k)|的上界为128，所有权值w_ij ^(k)和阈值w_j ^(k)都精确到小数点后2位，(ii)选定BP网络的一状态(称为稳态)：该状态下输出b_k′与期望输出b_k的分量差的绝对值小于0.49，即|b_ki′-b_ki|＜0.49，i＝1，…，12，(iii)在稳态时，顺序取960个神经元联接权值w_ij ⁽¹⁾，i＝1，…，12，j＝1，…，40；w_ij ⁽²⁾，i＝1，…，40，j＝1，…，12和64个阈值w_j ^(k)，j＝1，…，12，k＝1，2，3，w_j ⁽²⁾，j＝29，…，40，作为字符长串γ的编码，(iv)顺序把960个神经元联接权值和64个阈值依次2进制编码，方案是用2个字节16位为每个w_ij ^(k)，w_j ^(k)编码，其中1位是符号位，1位是小数点记号位，7位用于小数点后2位编码，7位用于小数点前2位编码。

4.γ的BP取整函数解压缩：BP取整函数解压缩模型是由所选BP网络构成的映射复合(或外套)取整函数而成。(i)恢复稳态时的w_ij ⁽¹⁾，i＝1，…，12，j＝1，…，40，k＝1，2；w_ij ⁽²⁾，i＝1，…，40，j＝1，…，12，值和稳态时的阈值w_j ^(k)，j＝1，…，12，k＝1，2，3，w_j ⁽²⁾，j＝29，…，40，，恢复BP模型稳定状态，(ii)把恢复的网络视为一固定映射Y¹，这时Y¹是Y的似近映射，且逼近度量值小于0.49，(iii)把Y¹与取整函数[y_i+0.5]，i＝1，…，10，复合得[y_i(X)+0.5]，i＝1，…，12，X＝(x₁，…，x_i，…，x₁₂)，(iv)把a_k，k＝1，…，4096顺序输入复合函数[y_i(X)+0.5]，i＝1，…，12中，顺序获得b_k，k＝1，…，4096，(v)由b_k，k＝1，…，4096完全恢复长串γ＝c₁…c₄₉₁₅₂。

Claims (4)

1.基于虚拟信源和神经网络的无损数据压缩方法，其特征在于，其步骤如下：

a.BP压缩

(1).把所有要处理的数据视为由虚拟信源产生的字符串；

(2).建立虚拟信源的BP神经网络模型；

(3).用BP模型参数去编码由虚拟信源产生的字符串；

b.BP解压缩

(1).恢复BP模型参数；

(2).恢复虚拟信源的模型；

(3).虚拟信源的模型结合取整变换构建字符串的恢复映射；

(4).完全恢复虚拟信源产生的字符串。

2.根据权利要求1所述的基于虚拟信源和神经网络的无损数据压缩方法，其特征在于，数据的虚拟信源是一映射：

映射Y：设A＝{(x₁，…，x_i，…，x₁₂)|x_i＝0，1}把(x₁，…，x_i，…，x₁₂)按二进制数x₁x₂…x_i…x₁₂的大小倒序排列，即排为有序点a₁＝(1，1，…，1)，a₂＝(1，…，1，0)，a₃＝(1，…，1，0，1)，…，a₄₀₉₅＝(0，…，0，1)，a₄₀₉₆＝(0，…，0，0)，假定待压缩的0与1的字符串γ＝c₁…c₄₉₁₅₂，c_j＝0 or 1，其中γ的长度为49152，记B＝{b_j|b_j＝(c_12x(j-1)+1，…，c_12×j)，1≤j≤4096}，注：b_j中的c_i要转换为0与1数的形式，定义Y为A到B的映射

                      Y：A→B

        Y：a_i→b_i，i＝1，…，4096，a_i∈A，b_i∈B

即b_i＝Y(a_i)，i＝1，…，4096。

3.根据权利要求1所述的基于虚拟信源和神经网络的无损数据压缩方法，其特征在于，BP神经网络模型是3层64个神经元和隐含层输出函数为Sigmoid函数的BP模型。

4.根据权利要求1所述的基于虚拟信源和神经网络的无损数据压缩方法，其特征在于，数据恢复映射是BP模型复合取整函数[y_i(X)+0.5]。