1

我对Rice解码器（和编码器）做了一个简单的实现：

void rice_decode(int k) {
    int i = 0
    int j = 0;
    int x = 0;
    while(i < size-k) {
        int q = 0;
        while(get(i) == 0) {
            q++;
            i++;
        }
        x = q<<k;
        i++;
        for(j=0; j<k; j++) {
            x += get(i+j)<<j;
        }
        i += k;
        printf("%i\n", x);
        x = 0;
    }
}

具有size输入位集的大小、get(i)返回位集的i第 - 位的原语以及kRice 参数。由于我关心性能，我还使用预计算进行了更精细的实现，速度更快。然而，当我打开-O3标志时gcc，天真的实现实际上优于后者。

我的问题是：是否知道任何现有的 Rice 编码器/解码器（我更关心解码）的有效实现，它比这更好（我能找到的那些要么更慢，要么相当）？或者，您是否有任何聪明的想法可以使解码比预计算更快？

4

2 回答 2

0

There are some textbook bithacks applicable here.

while (get(i) == 0) { q++; i++;} finds the least significant bit set in a stream.

That can be replaced with -data & data, which returns a single bit set. That can be converted to index 'q' with some hash + LUT (e.g the one involving modulus with 37. -- or using SSE4 instructions with crc32, I'd bet one can simply do LUT[crc32(-data&data) & 63];

The next loop for(j=0; j<k; j++) x += get(i+j)<<j; OTOH should be replaced with x+= data & ((1<<k)-1); as one simply gets k bits from a stream and treats them as an unsigned integer.

Finally one shifts data>>=(q+k); and reads in enough bytes from input stream.

于 2013-04-12T14:02:43.337 回答
0

赖斯编码可以看作是变长编码的一种变体。因此，在过去，我使用基于表的技术来生成自动机/状态机，这些机器可以快速解码固定的霍夫曼代码和水稻代码。在网络上快速搜索快速可变长度代码或快速霍夫曼会产生许多适用的结果，其中一些是基于表格的。

于 2013-04-12T13:20:44.127 回答