0

私は例のインフレータブル実装を理解しようとしてきましたが、これは少し混乱しています:

static int decode(struct state *s, struct huffman *h)
{
    int len;            /* current number of bits in code */
    int code;           /* len bits being decoded */
    int first;          /* first code of length len */
    int count;          /* number of codes of length len */
    int index;          /* index of first code of length len in symbol table */

    code = first = index = 0;
    for (len = 1; len <= MAXBITS; len++) {
        code |= bits(s, 1);             /* get next bit */
        count = h->count[len];
        if (code - count < first)       /* if length len, return symbol */
            return h->symbol[index + (code - first)];
        index += count;                 /* else update for next length */
        first += count;
        first <<= 1;
        code <<= 1;
    }
    return -10;                         /* ran out of codes */
}

特にこの部分：

first += count;
first <<= 1;

誰かがビットシフトまたは定数による乗算が特定のコード長の実際の最初のコードをどのように生成するかを説明できますか? 基本的に、最初のコードのインデックスと実際の最初のコードの違いは「2倍」ですか?

簡単にするために、長さが 7 ビットから 8 ビットにロールオフすると考えてください。ここで、7 は最初のゼロ以外のカウントを生成し、固定バージョンでは 24 になります。間隔は [256, 280> であるためと思います。

私の仮定は、コードと次の長さの最初のものの間の大きさの桁数が保持されるということです。これは、それらの減算関係がシンボル オフセットを決定するための絶対値よりも関連性があるためです。ただし、そうであるかどうかはよくわかりません。 .

4

1 に答える 1

1

count[len]は各ビット長のコード数です。deflate フォーマットで定義された標準コードの場合、コードは単純に 0 からカウントアップします。したがって、最初の非ゼロの最初のコードcount[len]はlenゼロ ビットです。が 1 より大きい場合count[len]、次のコードはそれより 1 大きいか、len-10 ビットと 1 ビットになります。

その長さのコードを使用する場合は、最後にゼロ ビットを追加して次の長さに移動します。

したがって、 length の最初のコードから length の最初のコードまでステップを作成するにはi、i+1加算count[i]してから 1 ビット左にシフトします。

コード例:

length   code
   2     00
   2     01
   3     100
   3     101
   3     110
   4     1110
   4     1111

長さ 2 の最初のコードは 00 から始めます。長さ 2 のコードが 2 つあるので、2 を足して 1 ビット左にシフトします。つまり、2 を掛けて、長さ 3 の最初のコードを取得します。 0 + 2) * 2 = 4 = 100. 長さ 4 の最初のコードを取得するには、その (4 + 3) * 2 = 14 = 1110.

于 2013-05-31T00:05:05.117 に答える