对于n个待压缩的数据{p₁，p₂，…p_n}，其中0≤p_x≤255，将其分割成m个连续段s₁，s₂，…，s_m.其中第i个象素段s_i(1≤i≤m)中有l[i]个象素，且该段中每个象素都只用b[i]bit表示；设t[i]表示前i个连续段中p_i的个数，则t[i]=$ \sum\nolimits_{k = 1}^{i - 1} {\left[ k \right]} $.第i个象素段s_i的元素位置表示为t[i]+1至t[i]+l[i]，则第i个像素段s_i的最大数据所占二进制空间为h_i=|log(max_{t[i]+1≤k≤t[i]+l[i]}p_k+1)|，h_i≤b[i]≤8，因此只需要3 bit表示b[i]，如果限制1≤l[i]≤255，则只需要8 bit表示l[i]，因此，第i个象素段所需的存储空间为l[i]×b[i]+11 bit.按此格式存储象素序列{p₁，p₂，…p_n}，需要$\sum\nolimits_{i = 1}^m {l\left[ i \right]} \times b\left[ i \right] + 11m{\kern 1pt} {\kern 1pt} {\kern 1pt} {\rm{bit}}$的存储空间，压缩问题转变成求解不同分组下的最小片段和.

采用动态规划算法解决如下：

设l[i]，b[i]是{p₁，p₂，…p_n}的最优分段.显而易见，l[1]，b[1]是{p₁，…，p_l[1]}的最优分段，且l[i]，b[i]是{p_l[1]+1…p_n}的最优分段，即图像压缩问题满足最优子结构性质.

设s[i]，1≤i≤n，是象素序列{p₁，p₂，…p_n}的最优分段所需的存储位数，由最优子结构性质易知：

其中

以此编写的压缩算法所需的计算时间为O(n)^[15].

通过上述分析，可以看出该算法具有如下特征：

1) 算法适用于片段数据间差距较小的情况；

2) bmax(i，j)越小越好；

3) 算法重点是尽可能多地去除多余的0 bit，保留有效的1 bit；

4) k个数据序列的算法压缩效果取决于bmax(i-k+1，i)，当k个数据序列的最大值大于128时，bmax(i-k+1，i)=8，该片段的压缩效果基本无变化.

改进的动态规划算法如下：

1) 读取待压缩序列{p₁…p_j}，j＜255；

2) 定义算法存储片段长度为tmpsl=Interger.Max；//Interger.Max代表机器表示的最大整数

3) 定义当前位置为i=1，Reverse=0，片段断点位置为tmpk=i；

4) 定义断点位置k(0≤k≤i)，初始化k=i，初始化tmpbmax=8；

5) 寻找序列片段{p_k…p_i}最小值minx=min(p_k…p_i)；

序列最大值maxx=max(p_k…p_i)；//{p_k…p_i}表示从k到i的待压缩序列；

6) 求解序列片段{p_k…p_i}最大值maxx所需的二进制位bmax=binary(maxx)，反转后的最大值所需二进制为bmax =binary(255-minx)；

7) 求解当前序列所需存储空间长度tmps[i]=min{s[i-k]+k×bmax，s[i-k]+k×bmax }；tmpbmax=min{bmax，bmax }；

8) if tmps[i]==s[i-k]+k×bmax then Reverse=1；

//当tmps[i]来源于s[i-k]+k×bmax，tmpbmax=bmax，否则tmpbmax=bmax，代表需要反转；

9) if tmps[i]＜tmpsl then tmpsl=tmps[i]；tmpk=k；T[i]=Reverse；

10) if k=0 then序列的第一次断点位置为tmpk，s[i]=tmp；s[i]片段的断点l[i]为tmpk；

else

k- -；转到5)；

11) if i＜j then

i++；转到4)；

else

return s，l，T//s的第i个元素s[i]代表从{p₁…p_i}的最小存储空间，l的第i个元素l[i]代表片段s[i]的最优断开位置，T的第i个元素T[i]代表是否需要反转，为1则反转，否则不反转；

12) 根据返回的s[i]，l[i]，T[i]执行压缩.

其中

binary(maxx)算法逻辑如下：

1) len=1//定义maxx的初始化长度；

2) int tmp=maxx/2//开始二进制变换；

3) while tmp＞0//当tmp不为0，表示二进制转化并未完成；

tmp=(int)(tmp/2)//继续对tmp进行二进制变换迭代；

len=len+1//maxx的对应长度加1；

end while//循环结束；

4) return len.

以500 Byte数据量为一个测试数据片段，设计小数值整数不同出现概率下的压缩实验(以压缩一次为例)，实验以0.02为概率密度步长(0.02表示小数值整数出现概率为0.02，0.04表示小数值整数出现概率为0.04)，生成随机序列，对每个步长片段应用改进算法和原算法执行50次测试，以50次测试的压缩值均值为衡量数据.对比测试结果如表 1所示.

表 1中，V₁代表小数值整数的出现概率，V₂代表反转数据压缩算法的压缩结果长度值(单位为Byte)，V₃代表非反转数据压缩算法的压缩结果长度值(单位为Byte)，其压缩对比序列见图 1.如图 1所示，变位反转压缩算法整体效率优于原压缩算法.

由于每个压缩片段的最大值不超过255，所以两种算法的时间复杂度均为O(n)，空间复杂度均为O(1).算法比较简单，仅通过变位与反转的方法减少了算法的复杂性，使用性广；算法具有无损压缩性，算法的使用过程信息具有可逆性，可通过12位的信息位直接进行还原；算法压缩所需要的时间较少，算法支持流式压缩，在使用中可以根据需要利用多线程直接对前一个压缩片段结果进行压缩，在网络传输过程中可以根据需要边压缩、边传递、边使用，这对流式数据应用是很有益处的.

将基于变位与反转变换的动态规划压缩算法与基于统计的编码算法进行对比(选取huffman算法).以500 Byte数据量为一个测试数据片段，设计在不同数据分布场景下的实验.以$\left\lceil {{\rm{255/20}}} \right\rceil $为步长，以$\left\lceil {{\rm{255/20}}} \right\rceil $×i为小数据区块和大数据区块出现频率，对序列进行压缩，其中i代表循环次数，同时也对数据随机均匀分布的情况进行实验.实验结果对比图分别如图 2-4所示.

如图 2，3所示，在小数据块和大数据块两种情况下基于标志的反转变位压缩算法明显优于基于统计的huffman算法，只有在数据随机均匀分布的情况下huffman算法才稍优于基于变位与反转的压缩算法，但这种情况下，两种算法的压缩效率都不高.

综上，基于变位与反转的压缩算法比原移位压缩算法效果更好，在存在数据区块特征的数据序列中明显优于基于统计的huffman算法，在随机均匀分布的数据序列中稍逊于huffman编码.

通过对图像压缩算法的分析，提出一种基于标识的变位与反转变换的动态规划无损压缩算法，算法改进了原图像压缩算法的最优子结构存储和表示方法，以变位和反转变化方法构造新的动态规划最优子结构.经过试验对比，新的图像数据压缩算法总体上优于原算法，在极大值出现较频繁的压缩片段，压缩效率明显优于原图像数据压缩算法.算法压缩一次的时间复杂度为O(n)，空间复杂度为O(1)，适合大规模数据的压缩.算法具有分段压缩和流式拼接特征，适合网络环境下数据的分段压缩和快速片段解压拼接的流媒体应用.算法的压缩率动态可调，适合网速受限条件下的大规模流媒体传输和磁盘存储.