从位序列解码字母('a'..'z')不会浪费
我寻求一种算法，可以让我以最小的方式将传入的位序列表示为字母('a'..'z')，这样就可以从字母中重新生成位流，而不必保存整个序列在记忆中。
也就是说，给定一个外部位源(每次读取都返回一个几乎随机的位)，并且用户输入了许多位，我想打印出可以表示这些位的最少字符数。
理想情况下，应该进行参数化，以便在需要一些浪费之前先将多少内存与最大位数进行比较。
效率目标与以26为基数的位表示形式相同的字符数。
非解决方案：
- 如果存在足够的存储空间，则存储整个序列并使用大整数MOD 26操作。
- 将每9位转换为2个字符-这似乎不是最佳选择，浪费了字母输出的25％的信息容量。
解决方案
霍夫曼编码会是我们想要的吗？这是一种压缩算法，几乎可以用最少的浪费比特来表示任何信息。
我们使用的任何解决方案都将导致空间效率低下，因为26不是2的幂。就算法而言，我宁愿使用查找表，而不是对每个9位序列进行即时计算。查询表将有512个条目。
如果为每个字母分配不同数量的位，则应该能够在不浪费任何位的情况下以允许的二十六个字母准确地编码位。 (这很像霍夫曼代码，只带有一个预先构建的平衡树。)
要将位编码为字母，请执行以下操作：累积位，直到与查找表中的位代码之一完全匹配为止。输出该字母，清除位缓冲区，然后继续。
将字母解码为位：对于每个字母，输出表中的位序列。
编写代码留给读者练习。 (或者对我来说，如果我以后觉得无聊。)
a 0000 b 0001 c 0010 d 0011 e 0100 f 0101 g 01100 h 01101 i 01110 j 01111 k 10000 l 10001 m 10010 n 10011 o 10100 p 10101 q 10110 r 10111 s 11000 t 11001 u 11010 v 11011 w 11100 x 11101 y 11110 z 11111
将每个47位的块转换为10位的26位基数。这样可以为我们提供超过99.99％的效率。
此方法以及其他类似Huffman的方法都需要填充机制来支持可变长度输入。这引入了一些效率低下的问题，对于较长的输入来说效率低下。
在位流的末尾，添加一个额外的" 1"位。即使在位流的长度是47的倍数的情况下，也必须在所有情况下执行此操作。可以在最后一个编码输出块中跳过"零"值的任何高位字母。
解码字母时，可以用"零"字母填充截断的最后一个块，并将其转换为47位以2为基的表示形式。最后的" 1"位不是数据，而是标记位流的结尾。
如果我们希望每个字母的二进制足迹具有相同的大小，则最佳解决方案将由算术编码给出。但是，它无法达到平均表示4.5位/字符的目标。给定26个不同的字符(不包括空格等)，则4.7将是我们不使用可变长度编码(例如，霍夫曼(Huffman)。请参阅Jaegers的答案)或者其他压缩算法而获得的最佳效果。
次优(虽然更简单)的解决方案可能是找到可行数量的字符以适合大整数。例如，如果我们在每6个字符块中形成一个32位整数(可能为26 ^ 6 <2 ^ 32)，则使用5.33位/字符。实际上，我们甚至可以将13个字母放入64位整数(4.92位/字符)中。这与最佳解决方案非常接近，并且仍然易于实现。由于缺少许多编程语言的本机支持，因此使用大于64位的整数可能会很棘手。
如果我们想要更好的文本压缩率，则绝对应该考虑使用基于字典的压缩算法，例如LZW或者Deflate。
零浪费是每个字母log_2(26)位。如前所述，通过读取47位并将其转换为10个字母可以达到4.7. 但是，可以通过将每14位转换为3个字符来达到4.67. 这样做的好处是，它适合整数。如果我们有存储空间，并且运行时间很重要，则可以创建一个具有17,576个条目的查找表，将可能的14位映射为3个字母。否则，我们可以执行mod和div操作来计算3个字母。
number of letters number of bits bits/letter 1 4 4 2 9 4.5 3 14 4.67 4 18 4.5 5 23 4.6 6 28 4.67 7 32 4.57 8 37 4.63 9 42 4.67 10 47 4.7
