字节对编码

字节对编码 是一种简单的数据压缩形式,这种方法用数据中不存的一个字节表示最常出现的连续字节数据。这样的替换需要重建全部原始数据。

字节对编码实例

假设我们要编码如下数据

aaabdaaabac

字节对“aa”出现次数最多,所以我们用数据中没有出现的字节“Z”替换“aa”得到替换表

Z <- aa

数据转变为

ZabdZabac

在这个数据中,字节对“Za”出现的次数最多,我们用另外一个字节“Y”来替换它(这种情况下由于所有的“Z”都将被替换,所以也可以用“Z”来替换“Za”),得到替换表以及数据

Z <- aa
Y <- Za
YbdYbac

我们再次替换最常出现的字节对得到:

Z <- aa
Y <- Za
X <- Yb
XdXac

由于不再有重复出现的字节对,所以这个数据不能再被进一步压缩。

解压的时候,就是按照相反的顺序执行替换过程。