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

Question

我有一个字节数据流，也称为基数 256 符号。最好的算法是什么，最好是在运行中，将其转换为新的符号流，其中每个符号的基数都不同并且只在运行时才知道？输入字节流和目标基数列表的长度都很长但有限。所有非负整数，没有 float 。此外，不能保证目标基数是 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);
} 

处理终止条件和处理解码器(算术编码器)中的进位很复杂，因此您必须阅读文献，从我链接的内容开始。不过，我希望这能让您了解它的工作原理。

祝你好运