算术编码器符号查找

Question

我有基于 Drdobbs ARcoder 的工作简单算术编码器。 de/encoding 算法归结为维护数组中的符号概率并更新它们。问题是我想扩展它以支持越来越多的符号，而不是固定的 +256 左右的符号。目前的实施如果符号数量增加太多，update_model() 和 getsym() 的速度太慢。

我可以将 cumulative_freq 数组转换为树状数据结构以便更快地查找和更新吗？我不介意该算法是否最终会消耗更多内存，只要它可以更好地扩展即可。

const u32 MAX_INPUT_VAL = 255;
const u32 CODE_RESCALE = MAX_INPUT_VAL+1;
const u32 CODE_EOF = MAX_INPUT_VAL+2;
const u32 CUMULATIVE_TOTAL = MAX_INPUT_VAL+3;  // total sum of all frequencies before.
const u32 CODES_END = MAX_INPUT_VAL+4;

u32 cumulative_freq[CODES_END];

// (Init symbol freqs)
for(u32 i = 0; i < CODES_END; ++i) {
    cumulative_freq[i] = i;
}

// update value propability
void update_model(u32 v) {
    // how can I make this scale better for more symbols?
    for(code_t i = v + 1; i < CODES_END; ++i) {
        cumulative_freq[i]++;
    }
}

struct sym {
    u32 low;
    u32 high;
    u32 count;
};

// encode symbol: get symbol propability
sym propability(u32 v) {
    sym p{cumulative_freq[v], cumulative_freq[v+1], cumulative_freq[CUMULATIVE_TOTAL]};
    update_model(v);
    return p;
}

// decode symbol:
std::pair<sym, u32> getsym(u64 prop) {
    // how can I make this scale better for more symbols?
    for(u32 i = 0; i < CUMULATIVE_TOTAL; ++i) {
        if(prop < cumulative_freq[i+1]) {
            sym p{cumulative_freq[i],cumulative_freq[i+1],cumulative_freq[CUMULATIVE_TOTAL]};
            update_model(i);
            return {p,i};
        }
    }
    // error: decode failed.
}

Answer 1

是的，您可以将计数排列成一棵树。每个符号都有一个包含其概率（非累积）的叶子，然后每个内部节点包含其下方节点的概率总和。

要更新模型，您需要将符号的叶及其每个祖先加 1。要进行搜索，您可以在下降到树中时动态计算符号的累积概率——每次向右移动时，您都会从左侧添加计数 child 您没有输入。

这是一个顺序统计树，但使用累积概率而不是排名：https://en.wikipedia.org/wiki/Order_statistic_tree

然而，这棵树的结构永远不会改变。没有插入或删除。因此，您不需要使用带有指针等的实际节点 objects。您可以只使用一个计数数组，像二进制堆数组一样排列：https://www.geeksforgeeks.org/array-representation-of-binary-heap/

如果你有 N 个符号，那么内部节点将有 N-1 个计数，然后是叶符号的 N 个计数，除根之外的每个节点在 floor( index-1)/2.

这个结构还是比较节省内存的，所有的操作都需要O(log N)的时间，而且代码量很小。

更新看起来像这样：

unsigned i = symbol + num_symbols-1;
for (;;) {
    ++counts[i];
    if (!i)
        break;
    i = (i-1)/2;
}

获取交易品种的累计 P:

unsigned P=0;
for (unsigned i=symbol+num_symbols-1; i>0; i=(i-1)/2) {
    if (!(i&1)) {
        //this is a right child, add counts from the left
        P+=counts[i-1];
    }
}

通过累积概率获取符号：

unsigned P=0;
unsigned i=0;
while (i<(num_symbols-1)) {
    i=i*2+1; //left child
    if (targetP >= P+counts[i]) {
        //use right child instead
        P+=counts[i];
        ++i;
    }
}
unsigned symbol = i-(num_symbols-1);

请注意 smallest-indexed 符号 (num_symbols-1) 不是树中的 left-most 除非 num_symbols 是 2 的幂，但那应该没问题。只要编码器和解码器一致，符号的顺序与您的应用程序无关。

算术编码器符号查找

arithmetic encoder symbol lookup

c++

compression

lossless-compression

data-structures