インフレートアルゴリズム標準的なハフマン表現、著者の書き込みからルックアップテーブルを構築するためのコードです<a href="http://www.synthesis.ch/indefero/index.php/p/libsynthesis/source/tree/master/src/zlib/inftrees.c" rel="nofollow">inftrees.c</a>、で

Question

のzlibの実装：

/* 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 

私は私であるが、ドロップの意味だかを把握できコメントを何度も読んでください。別の質問は、著者がハフマンコードを作成するためにどのような方法を使用するかです。 とは何ですか？増分ですか？

ありがとうございます。ありがとうございます。

Answer 1

"後方増分huff"は、revがビット0, ..., len - 1を逆にする、huff = rev(rev(huff) + 1)を意味します。

len == 7とhuffが2進数で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