algorithm - 嵌入式轻量级(解压)算法

Question

我有一个带有图形用户界面的低资源嵌入式系统。该界面需要字体数据。为了节省只读存储器(闪存)，需要压缩字体数据。我正在为此目的寻找一种算法。

要压缩的数据的属性

每像素8位的矩形像素图的

透明度数据

字体(通常以一定大小采样的字体)中通常有大约200..300个字形

每个字形的大小通常为6x9至15x20像素

有很多零(“无墨水”)，而有少得多的255(“完全上墨”)，否则由于抗混叠

的性质，八位字节的分布相当均匀

压缩算法的要求

解压缩算法的重要指标是数据大小加上算法大小(因为它们将驻留在相同的有限内存中)。

几乎没有可用的RAM用于解压缩。可以将单个字形的数据解压缩到RAM中，但不能再压缩更多。

为了使事情变得更困难，该算法必须在32位微 Controller (ARM Cortex-M内核)上非常快，因为在将字形绘制到显示器上时需要对其进行解压缩。每个八位位组十或二十个机器周期是可以的，一百个周期肯定太多了。

为了使事情变得容易，先验的是完整的数据语料库，在压缩阶段有很多处理能力和可用的内存。

的结论和想法

由于熵相对较高，仅通过某种可变长度编码来打包每个八位位组的简单方法无法获得良好的结果。

任何利用较早解压缩的数据的算法似乎都是毫无疑问的，因为不可能存储其他字形的解压缩数据。这使得LZ算法效率较低，因为它们只能引用少量数据。

处理能力的限制似乎排除了大多数按位操作，即解压缩应该逐个字节地处理数据。这使得霍夫曼编码变得困难而算术编码变得不可能。

这个问题似乎是静态字典编码的一个很好的候选者，因为所有数据都是事先已知的，并且数据本质上是重复的(不同的字形共享相同的形状)。

问题

如何构造好的字典？我知道找到某些数据的最佳字典是一个np完全问题，但是是否有任何合理的近似值？我已经尝试过使用zstandard的字典构建器，但是结果不是很好。

我的结论中有什么地方我弄错了吗？ (我是在错误的轨道上并且省略了一些明显的东西吗？)

迄今为止最好的算法

仅提供一些背景信息，我能够找出的最佳有用算法如下:

将单个字形的字体数据中的所有样本连接(展平)为一维数组(向量，表格)。

每个样本都具有三种可能的状态:0、255和“其他”。

此信息一次将五个连续的样本打包成一个5位数的三进制数字(0..3 ^ 5)。

由于一个八位位组中有一些额外的值(2 ^ 8 = 256、3 ^ 5 = 243)，它们用于表示较长的0和255字符串。

对于每个“其他”值，实际值(1..254)存储在单独的向量中。

该数据可以快速解压缩，因为可以通过较小的(243 x 3 = 729个八位位组)查找表将base-3值解码为base-4值。压缩率高度依赖于字体大小，但是使用我的典型数据，我可以得到大约1:2的比例。由于这比LZ变体(大约1:3的变体)差得多，我想尝试一下静态字典方法。

当然，通常的LZ变体使用霍夫曼编码或算术编码，这自然会使压缩数据变小。另一方面，我拥有所有可用数据，并且压缩速度不是问题。这样应该可以找到更好的字典。

由于数据的性质，我可以使用有损算法，但是在那种情况下，最可能的有损算法将减少像素数据中的量化级别数。那不会改变太多的底层压缩问题，我想避免由此产生的位对齐麻烦。

Answer 1

您可以考虑使用已经针对类似您的场景开发的内容

https://github.com/atomicobject/heatshrink

https://spin.atomicobject.com/2013/03/14/heatshrink-embedded-data-compression/