1

正規のハフマン表現からルックアップ テーブルを構築するコードである inftrees.c で、作成者は次のように記述します。

 /* replicate for those indices with low len bits equal to huff */
    incr = 1U << (len - drop);
    fill = 1U << curr;
    min = fill;                 /* save offset to next table */
    do {
        fill -= incr;
        next[(huff >> drop) + fill] = here;
    } while (fill != 0);

    /* backwards increment the len-bit code huff */
    incr = 1U << (len - 1);
    while (huff & incr)
        incr >>= 1;
    if (incr != 0) {
        huff &= incr - 1;
        huff += incr;
    }
    else
        huff = 0

コメントを何度も読んでも、ドロップの意味がわかりました。もう 1 つの質問は、作者がハフマン コードを構築するためにどのような方法を使用しているのかということです。後方増分とは何ですか?

説明してくれませんか、ありがとう。

4

1 に答える 1

2

「後方インクリメントhuff」とはhuff = rev(rev(huff) + 1)、revビットを反転させることを意味します0, ..., len - 1。

len == 7とhuffがバイナリであると1110100します。最初のクリア ビットを探し、下位 (意味)/上位 (ビット パターン) をすべてクリアし、そのビットを設定します。

1110100
^
1000000 == incr: loop continues
 ^
0100000 == incr: loop continues
  ^
0010000 == incr: loop continues
   ^
0001000 == incr: loop breaks

1110100: huff
0000111: incr - 1
0000100: huff &= (incr - 1)
0001100: huff += incr
于 2011-12-18T17:42:59.993 に答える