我寻求一种算法，它可以让我将输入的位序列表示为字母（'a' .. 'z'），以最小的方式使位流可以从字母中重新生成，而无需保存整个序列在记忆中。
也就是说，给定一个外部位源（每次读取都返回一个几乎随机的位），并且用户输入了一些位，我想打印出可以代表这些位的最少字符数。
理想情况下，应该有一个参数化 - 在需要一些浪费之前有多少内存与最大位。
效率目标 - 与位的 base-26 表示相同的字符数。
非解决方案：
如果存在足够的存储空间，则存储整个序列并使用大整数 MOD 26 运算。
将每 9 位转换为 2 个字符 - 这似乎不是最理想的，浪费了字母输出的 25% 的信息容量。
如果您为每个字母分配不同数量的位，您应该能够在允许的 26 个字母中精确编码位，而不会浪费任何位。（这很像霍夫曼代码，只是有一个预先构建的平衡树。）
要将位编码为字母： 累积位，直到您与查找表中的位代码完全匹配。输出那个字母，清除位缓冲区，然后继续。
将字母解码为位： 对于每个字母，输出表中的位序列。
在代码中实现留给读者作为练习。（或者对我来说，如果我以后觉得无聊的话。）
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 位 base 2 表示。最后1一位不是数据，而是标志着位流的结束。
霍夫曼编码会是您正在寻找的吗？这是一种压缩算法，它几乎可以用最少的浪费位表示任何信息。
零浪费是每个字母 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
您使用的任何解决方案都将是空间效率低下的，因为 26 不是 2 的幂。就算法而言，我宁愿使用查找表而不是对每个 9 位系列进行动态计算。您的查找表将包含 512 个条目。
如果您希望每个字母的二进制足迹具有相同的大小，则最佳解决方案将由Arithmetic Encoding给出。但是，它不会达到 4.5 位/字符的平均表示的目标。给定 26 个不同的字符（不包括空格等），如果不使用可变长度编码（例如 Huffman。请参阅 Jaegers 的答案）或其他压缩算法，4.7 将是最好的。
一个次优但更简单的解决方案可能是找到一个可行的字符数以适合一个大整数。例如，如果您从每 6 个字符块（可能为 26^6 < 2^32）中形成一个 32 位整数，则使用 5.33 位/字符。实际上，您甚至可以将 13 个字母放入 64 位整数（4.92 位/字符）中。这非常接近最佳解决方案，并且仍然很容易实现。由于缺少许多编程语言的本机支持，使用大于 64 位的整数可能会很棘手。
如果您想要更好的文本压缩率，您绝对还应该研究基于字典的压缩算法，例如 LZW 或 Deflate。