从比特序列中解码字母('a'..'z')而不浪费

我寻找一种算法,让我将一个输入的比特序列表示为字母('a'..'z'),这是一个最小的事情,这样比特流可以从字母中重新生成,而不需要保留整个序列在记忆中.

也就是说,给定一个外部位源(每次读取返回一个实际上随机的位),以及用户输入多个位,我想打印出可以代表这些位的最小字符数.

理想情况下应该有一个参数化 - 在需要浪费之前需要多少内存与最大比特.

效率目标 - 与位的基数26表示相同的字符数.

非解决方案:

如果存在足够的存储空间,则存储整个序列并使用大整数MOD 26操作.

将每9位转换为2个字符 - 这似乎不是最理想的,浪费了字母输出信息容量的25%.

Commodore Ja.. 8

如果为每个字母分配不同的位数,则应该能够准确地编码允许的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

erickson.. 6

将每个47位的块转换为基数为26的10位数.这为您提供超过99.99%的效率.

这种方法以及像Huffman这样的其他方法需要填充机制来支持可变长度输入.这引入了一些低效率,这对于较长的输入而言不太重要.

在比特流的末尾,添加一个额外的1位.这必须在所有情况下完成,即使比特流的长度是47的倍数.在编码输出的最后一个块中可以跳过任何"零"值的高位字母.

当解码字母时,可以用"零"字母填写截断的最终块并将其转换为47位基2表示.最后1一位不是数据,而是标记位流的结束.

如果为每个字母分配不同的位数,则应该能够准确地编码允许的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位的块转换为基数为26的10位数.这为您提供超过99.99%的效率.

这种方法以及像Huffman这样的其他方法需要填充机制来支持可变长度输入.这引入了一些低效率,这对于较长的输入而言不太重要.

在比特流的末尾,添加一个额外的1位.这必须在所有情况下完成,即使比特流的长度是47的倍数.在编码输出的最后一个块中可以跳过任何"零"值的高位字母.

当解码字母时,可以用"零"字母填写截断的最终块并将其转换为47位基2表示.最后1一位不是数据,而是标记位流的结束.