c - 字体压缩！RLE 或 Huffman 还是什么都没有？

Question

我正在开发一个嵌入式项目（ARM7）。在我的应用程序中，我必须存储大量中文字符，这会浪费大约 300k 的闪存。当前的字体编码是 Unicode，每个字符包含 22 个字节，因为每个字形都是 12*12 加上左侧和底部的一个行空间，这使其成为 169 像素（22 个字节）（参见示例）。例如，这个汉字的 Unicode

如下： /* unicode5939*/ 0x40, 0x44, 0x4c, 0x54, 0x64, 0xff, 0xff, 0x44, 0x54, 0x4c, 0x44, 0x40, 0x0, 0x8, 0x11, 0x11, 0x0, 0x8, 0x82, 0x , 0x0。

当前的 Unicode 是这样的：字形的前 8 行正好等于 Unicode 的前 13 个字节（基于列而不是基于行，从右上方开始）。剩下的 9 个字节代表字形的底部 5 行（从左侧看右侧，逐列将 0 和 1 放入一个字节中，直到字节变满，依此类推）。

如果我们对这个 Unicode（按位）进行 RLE 压缩，结果需要超过 22 个字节来存储每次运行的重复数（据我手工完成）。所以我想做另一种类型的压缩。有什么线索吗？

Answer 1

通过不在每个字形中存储空行，您将获得近 20% 的改进。

12x12 而不是 13x13 = 18 字节而不是 22。

Answer 2

（不是一个实际的答案，但我需要比评论更多的空间）

好吧，至少 13*13 适合 22 个字节（它是 169 位，因此是 21 1/8 个字节）。当布局为字节时，它看起来像这样：

01000000   01000    00010
01000100   01000    00010
01001100   00100    00100
01010100   00010    01000
01100100   00001    10000
11111111   00000    00000 Reordered by groups of five bits,
11111111   00000 <- 00000 <--------------------------+
01000100   00001    10000 flipped again             |
01010100   00010    01000                           |
01001100   00100    00100                           |
01000100   01000    00010                           |
01000000   01000    00010                           |
00000000   00000    00000                           |
00001000 -> 00010000 <- Bottom 9 bytes reversed: \  |
00010001 -> 10001000                             |  |
00010001 -> 10001000                             |  |
00000000 -> 00000000                             |  |
00001000 -> 00010000                             +--+
10000010 -> 01000001                             |
00100000 -> 00000100                             |
00000100 -> 00100000                             |
00000000 -> 0        (only one useful bit)       /

至少前 13 个字节绝对看起来像字符的前 8 行（右侧的上侧）。对于底部的 9 个字节，一旦反转，它们可以按 5 位为一组进行布局，看起来像底部。

或者更具可读性，它的编码方式如下：

现在要回答实际问题，我敢肯定尝试单独压缩字形会导致灾难。由于缺少存储未压缩数据的空间，也无法在一个块中压缩所有内容。因此，需要在 X 字形块中进行压缩，并使用用于解压缩块的缓存系统。

Answer 3

甚至可以使用例如具有 4 位邻域的算术编码来处理基于每个字形的字体压缩：

[ 4 ] [ 3 ] [ 2 ]
[ 1 ] ( x )

每个像素邻域 p1,p2,p3,p4 编码 x==0 与 x==1 的概率，在处理完位 'x' 后更新；与霍夫曼编码器不同，算术编码器能够以比单个比特更小的单元压缩符号，这是香农信息论给出的限制。

Context,    count               bits per symbol  
Zeros[ 0] = 45   Ones[ 0] = 4   19.987
Zeros[ 1] = 7    Ones[ 1] = 4   10.402
Zeros[ 2] = 6    Ones[ 2] = 0   0.000
Zeros[ 3] = 2    Ones[ 3] = 2   4.000
Zeros[ 4] = 6    Ones[ 4] = 5   10.934
Zeros[ 5] = 0    Ones[ 5] = 1   0.000
Zeros[ 6] = 2    Ones[ 6] = 0   0.000
Zeros[ 7] = 9    Ones[ 7] = 4   11.576
Zeros[ 8] = 5    Ones[ 8] = 13  15.343
Zeros[ 9] = 1    Ones[ 9] = 3   3.245
Zeros[10] = 4    Ones[10] = 0   0.000
Zeros[11] = 1    Ones[11] = 3   3.245
Zeros[12] = 2    Ones[12] = 2   4.000
Zeros[13] = 1    Ones[13] = 0   0.000
Zeros[14] = 1    Ones[14] = 5   3.900
Zeros[15] = 3    Ones[15] = 3   6.000
Total 92.634 bits = 12 bytes
vs. no context, 
Zeros = 95           Ones = 49      133.212 bits = 17 bytes

显而易见的问题是如何初始化数组：

1) 使用固定的，即频率的静态模型
2) 使用完全自适应模型，假设开始时有 50:50 的机会
3) 使用一组 (2-256?) 固定模型，最能表征字形
4) 开始使用预先计算的集合中的一些模型并更新

一个完整的模型需要 32 个字节来编码 0..169 的值，因此除非非常强烈（并且巧妙地）压缩，否则不能与字符一起传递。

编辑 如果使用单个（或很少使用全局静态表），也可以将表扩大到 5,6,7 像素邻域，或将像素位置信息嵌入到表中（此方法无法编码条件 'x位于底线'）：

[ B ] [ C ] [ D ],          where A,B,C,D = 00 for 'white'
[ A ]  (x)                                  11 for 'black'
                                            01/10 for pixel outside canvas 

or
[ 1 ] [ 3 ] [ 4 ] [ 5 ] [ 6 ]       + [ x is next to border? ]
[ 0 ] [ 2 ]  (x)

进一步阅读：
-传真压缩/ JBIG
-算术编码