从基数256转换为多基数并返回的算法

Question

我有一个字节数据流，也称为基数256个符号。什么是最好的算法，在理想情况下将其转换为新的符号流，每个符号的基数变化并且只在运行时才知道？输入字节流和目标基数列表的长度都很长但是有限。所有非负整数，无浮点。此外，目标基数不能保证均匀分配或是256的倍数。

Answer 1

您的问题是算术编码的一个子集，它被用作许多压缩算法的最后一个阶段。这是最酷的事情在CS学习一种：

http://www.drdobbs.com/cpp/data-compression-with-arithmetic-encodin/240169251 https://en.wikipedia.org/wiki/Arithmetic_coding

如何您的问题具体涉及：

你想要的编码器是算术解码器，并为每个解码您将使用一个不同大小的字母表（基数），所有符号的概率相同。

编码器的主循环会做这样的事情：

int val=0; //information from the stream 
int range=1; //val is in [0,range) 
while(...) 
{ 
    int radix = next_radix(); 
    //ensure adequate efficiency 
    while(range < radix*256) 
    { 
     val = (val<<8)|(next_byte()&255); 
     range<<=8; 
    } 
    int output = (int)(radix*(long)val/range); 
    //find the smallest possible val that produces this output 
    int low = (int)((output*(long)range+radix-1)/radix); 
    //find the smallest possible val that produces the next output 
    int high = (int)(((output+1)*(long)range+radix-1)/radix); 
    val-=low; 
    range = high-low; 
    write(output); 
} 

没有与处理终止的条件和处理在您的解码器进行（算术编码器）的并发症，所以你必须阅读文学，从我链接的东西开始。尽管如此，我希望这能够让你了解它的工作原理。

好运