嵌入式轻量级(de)压缩算法

Question

null

• 解压缩算法的重要指标是数据的大小加上算法的大小（因为它们将驻留在相同的有限内存中）。
• 可用于解压的RAM很少；可以将单个字形的数据解压缩到RAM中，但不能更多。
• 为了使事情变得更加困难，算法必须在32位微控制器（ARM Cortex-M core）上非常快，因为字形在被绘制到显示器上时需要解压缩。每八位元组十个或二十个机器循环是可以的，一百个肯定太多了。
• 为了使事情变得更容易，完整的数据语料库是先验已知的，并且在压缩阶段有大量的处理能力和可用内存。

结论和思考

• 由于熵相对较高，仅仅通过某种变长编码对每个八位字节进行打包的幼稚方法不会产生好的结果。
• 任何利用先前解压缩的数据的算法似乎都是不可能的，因为它不可能存储其他字形的解压缩数据。这使得LZ算法的效率较低，因为它们只能引用少量数据。
• 对处理能力的限制似乎排除了大多数按位操作，即解压缩应该逐个字节地处理数据。这使得哈夫曼编码变得困难，算术编码变得不可能。
• 这个问题似乎是静态字典编码的一个很好的候选问题，因为所有数据都是预先知道的，而且数据本质上有些重复（不同的字形共享相同的形状）。

null

为了给出一些背景信息，我已经能够计算出的最好的有用算法如下：

• 单个字形字体数据中的所有示例都串联（扁平化）到一维数组（向量、表）中。
• 每个示例有三种可能的状态:0、255和“其他”。
• 此信息被一次将五个连续的样本打包成一个5位数的基数为3的数字(0..3^5)。
• 由于在八位元组(2^8=256,3^5=243)中有一些额外的值可用，所以它们用来表示0和255的较长字符串。
• 对于每个“其他”值，实际值（1..254）存储在一个单独的向量中。

该数据解压缩速度很快，因为可以通过一个较小的(243×3=729个八位字节）查找表将基-3值解码为基-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/