c++ - 算术编码器符号查找

Question

我有一个基于 Drdobbs ARcoder 的简单算术编码器。解码/编码算法归结为在数组中维护符号概率并更新它们。问题是我想扩展它以支持比固定 +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。要搜索，您可以在下降到树中时动态计算符号的累积概率 - 每次向右移动时，您都添加未输入的左子节点的计数。
这是一个订单统计树，但使用累积概率而不是排名:https://en.wikipedia.org/wiki/Order_statistic_tree
然而，这棵树的结构永远不会改变。没有插入或删除。正因为如此，你不需要使用带有指针等的实际节点对象。你可以只使用一个计数数组，像二进制堆数组一样排列: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);

请注意，最小索引符号 (num_symbols-1) 不是树中的最左侧，除非 num_symbols 是 2 的幂，但这应该没问题。只要编码器和解码器一致，符号的顺序就与您的应用程序无关。