DrV*_*DrV 5 compression embedded algorithm
我有一个带有图形用户界面的低资源嵌入式系统。该接口需要字体数据。为了节省只读内存（闪存），需要压缩字体数据。我正在为此目的寻找算法。
要压缩的数据的属性
对压缩算法的要求
结论和想法
问题
迄今为止最好的算法
只是为了提供一些背景信息，我能够找出的最有用的算法如下：
该数据解压速度很快，因为可以通过较小的（243 x 3 = 729 个八位字节）查找表将 base-3 值解码为 base-4 值。压缩率高度依赖于字体大小，但使用我的典型数据，我可以得到大约 1:2。由于这比 LZ 变体（大约为 1:3）要差得多，所以我想尝试静态字典方法。
当然，通常的 LZ 变体使用 Huffman 或算术编码，这自然使压缩数据更小。另一方面，我拥有所有可用数据，压缩速度不是问题。这应该可以找到更好的词典。
由于数据的性质，我可以使用有损算法，但在这种情况下，最有可能的有损算法将减少像素数据中的量化级别数。这不会改变潜在的压缩问题太多，我想避免由此产生的位对齐麻烦。
我确实承认这是一个很好回答我的问题的边缘情况，但由于我对这个问题进行了一些研究，这个答案既描述了我选择的方法，又提供了关于问题本质的更多信息（如果有人遇到这种情况）它。
\n\n“正确答案”又名最终算法
\n\n我最终得到的是我在问题中描述的内容的变体。首先，每个字形被分成 trit 0、1 和中间。然后使用 256 槽静态字典压缩该三元信息。字典（或查找表）中的每个项目都是二进制编码字符串（0=0、10=1、11=中间），并在最高有效端添加一个 1。
\n\n灰度数据（对于中间三色）散布在对查找表的引用之间。所以，数据基本上是这样的：
\n\n<LUT reference><gray value><gray value><LUT reference>...\n灰度值的数量自然取决于从静态字典中查找到的三元数据中的中间三元组的数量。
\n\n解压代码非常短，可以很容易地写成一个状态机，只有一个指针和一个给出状态的 32 位变量。像这样的东西：
\n\nstatic uint32_t trits_to_decode;\nstatic uint8_t *next_octet;\n\n/* This should be called when starting to decode a glyph\n data : pointer to the compressed glyph data */\nvoid start_glyph(uint8_t *data)\n{\n next_octet = data; // set the pointer to the beginning of the glyph\n trits_to_decode = 1; // this triggers reloading a new dictionary item\n}\n\n\n/* This function returns the next 8-bit pixel value */\nuint8_t next_pixel(void)\n{\n uint8_t return_value;\n\n // end sentinel only? if so, we are out of ternary data\n if (trits_to_decode == 1)\n // get the next ternary dictionary item\n trits_to_decode = dictionary[*next_octet++];\n\n // get the next pixel from the ternary word\n // check the LSB bit(s)\n if (trits_to_decode & 1)\n {\n trits_to_decode >>= 1;\n // either full value or gray value, check the next bit\n if (trits_to_decode & 1)\n {\n trits_to_decode >>= 1;\n // grayscale value; get next from the buffer\n return *next_octet++; \n }\n // if we are here, it is a full value\n trits_to_decode >>= 1;\n return 255;\n }\n\n // we have a zero, return it\n trits_to_decode >>= 1;\n return 0;\n}\n（该代码尚未完全按照这种形式进行测试，因此可能存在拼写错误或其他愚蠢的小错误。）
\n\n移位操作有很多重复。我不太担心，因为编译器应该能够清理它。（实际上，左移可能更好，因为这样可以在移位后使用进位位。但由于在 C 中没有直接的方法可以做到这一点，所以我不打扰。）
\n\n另一项优化与字典（查找表）的大小有关。可能有短项和长项，因此可以将其构建为支持 32 位、16 位或 8 位项。在这种情况下，必须对字典进行排序，以便小数值引用 32 位项目，中间值引用 16 位项目，大值引用 8 位项目，以避免对齐问题。那么查找代码如下所示：
\n\nstatic uint8_t dictionary_lookup(uint8_t octet)\n{\n if (octet < NUMBER_OF_32_BIT_ITEMS)\n return dictionary32[octet];\n if (octet < NUMBER_OF_32_BIT_ITEMS + NUMBER_OF_16_BIT_ITEMS)\n return dictionary16[octet - NUMBER_OF_32_BIT_ITEMS];\n return dictionary8[octet - NUMBER_OF_16_BIT_ITEMS - NUMBER_OF_32_BIT_ITEMS];\n}\n当然，如果每种字体都有自己的字典，则常量将成为从字体信息中查找的变量。任何半像样的编译器都会内联该函数，因为它只被调用一次。
\n\n如果减少量化级别的数量，也可以处理。最简单的情况是 4 位灰度级 (1..14)。这需要一个 8 位状态变量来保存灰度级。那么灰度分支将变为：
\n\n// new state value\nstatic uint8_t gray_value;\n...\n\n // new variable within the next_pixel() function\n uint8_t return_value;\n\n ...\n\n // there is no old gray value available?\n if (gray_value == 0)\n gray_value = *next_octet++;\n // extract the low nibble\n return_value = gray_value & 0x0f;\n // shift the high nibble into low nibble\n gray_value >>= 4;\n return return_value;\n这实际上允许使用 15 个中间灰度级（总共 17 个级别），这非常好地映射到线性 255 值系统。
\n\n三位或五位数据更容易打包成 16 位半字并将 MSB 始终设置为 1。然后可以使用与三元数据相同的技巧（移位直到得到 1）。
\n\n应该注意的是，压缩比在某个时刻开始恶化。三值数据的压缩量不取决于灰度级的数量。灰度级数据未压缩，八位位组的数量（几乎）与位数成线性关系。对于典型字体，8 位灰度级数据是总数的 1/2 .. 2/3，但这高度依赖于字体和大小。
\n\n因此，从 8 位减少到 4 位（在大多数情况下在视觉上是难以察觉的）通常会将压缩大小减少 1/4..1/3，而减少到 3 位所提供的进一步减少则要少得多。两位数据对于这种压缩算法没有意义。
\n\n如何建立词典？
\n\n如果解压缩算法非常简单且快速，那么真正的挑战在于字典的构建。很容易证明存在最佳字典（对于给定字体给出最少数量的压缩八位字节的字典），但是比我更聪明的人似乎已经证明找到这样的字典的问题是NP完全的。
\n\n由于我在该领域相当缺乏理论知识，我认为会有很好的工具提供相当好的近似值。可能有这样的工具，但我找不到，所以我推出了自己的米老鼠版本。编辑：早期的算法相当愚蠢；找到了更简单、更有效的方法
\n\n这仍然是一种非常简单的方法，并且可能会给出非常次优的结果。它唯一的优点是它有效。
\n\n效果如何？
\n\n一个答案已经足够好了，但为了详细说明这一点，这里有一些数字。这是一种具有 864 个字形的字体，典型字形大小为 14x11 像素，每像素 8 位。
\n\n与逐个八位位组熵的比较非常有启发性。中间值数据具有高熵，而三值数据可以被压缩。这也可以通过原始数据中大量的值 0 和 255 来解释（与任何中间值相比）。
\n\n我们没有做任何事情来压缩中间值，因为似乎没有任何有意义的模式。然而，我们用三元数据明显击败了熵，甚至数据总量低于熵极限。所以，我们可以做得更糟。
\n\n将量化级别数减少到 17 会将数据大小减少到大约 42920 个八位位组（压缩率超过 66%）。熵是 41717 个八位位组，因此算法会像预期的那样变得稍差。
\n\n实际上，较小的字体很难压缩。这应该不足为奇，因为大部分信息是灰度信息。使用此算法可以有效地压缩非常大的字体大小，但游程压缩是更好的候选者。
\n\n什么会更好？
\n\n如果我知道的话，我就会用它！但我仍然可以推测。
\n\nJubatian表明字体中会有很多重复。对于变音符号来说一定是这样，因为 a\xc3\xa0\xc3\xa4\xc3\xa1\xc3\xa2\xc3\xa5 在几乎所有字体中都有很多共同点。然而，对于大多数字体中的 p 和 b 等字母来说，情况似乎并非如此。虽然基本形状很接近，但还不够。（仔细的逐像素字体设计是另一回事。）
不幸的是，这种不可避免的重复在较小尺寸的字体中并不容易利用。我尝试创建所有可能的扫描线的字典，然后仅引用这些扫描线。不幸的是，不同扫描线的数量很多，因此引用增加的开销超过了好处。如果扫描线本身可以被压缩，情况会有所改变，但每个扫描线的八位字节数量较少，使得有效压缩变得困难。当然，这个问题取决于字体大小。
\n\n我的直觉告诉我，如果使用比完整扫描线更长和更短的运行，这仍然是正确的方法。仅当有一种方法可以创建最佳字典时，与使用 4 位像素相结合可能会给出非常好的结果\xe2\x80\x94。
\n\n这个方向的一个提示是xz完整字体数据（127101 个八位位组）的 LZMA2 压缩文件（最高压缩）只有 36720 个八位位组。当然，这种格式不满足任何其他要求（快速解压缩、可以逐个字形解压缩、低 RAM 要求），但它仍然表明数据中的冗余比我的廉价算法能够实现的要多。开发。
字典编码通常在字典步骤之后与霍夫曼或算术编码相结合。我们不能在这里这样做，但如果可以的话，将又节省 4000 个八位字节。
\n