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