ハフマン符号長の効率的な求め方

モチベーション Canonical Huffman code (以下CHC) では符号長さえ分かれば後の処理は比較的単純。符号長が知りたい 通常のハフマンアルゴリズムはポインタで木を構築してから traverse して符号語と符号長を求めるが、木を必要としない CHC で長さを計算するためだけにこの類の木を使うのは冗長 符号化したいシンボルの数 n に対して 2n 程度の領域だけで符号長を求めるアルゴリズム。空間的にも、ローカリティ的にも有利

シンボルの数 n に対してサイズ 2n の配列Aを用意する。この配列で左上の表のハフマン木を表現することを考える 0. a 10 4. e 22 1. b 11 5. f 23 2. c 2 6. g 5 3. d 13 7. h 13 例: シンボル d のシンボル番号 (文字コード相当) は 3 で出現回数が 13 回 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 シンボルの数 n に対してサイズ 2n の配列Aを用意する。この配列で左上の表のハフマン木を表現することを考える

0. a 10 4. e 22 1. b 11 5. f 23 2. c 2 6. g 5 3. d 13 7. h 13 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 10 11 2 13 22 23 5 13 配列Aの右半分を出現回数で埋める。つまり、右半分の要素それぞれがハフマン木の葉に相当する。 シンボル番号を i、i の出現回数を ciとすると A[n + i] = ci 例えば、左上表からシンボル b は番号 1、c1 = 11 なので A[n + 1] = 11 (n = 8)

0. a 10 4. e 22 1. b 11 5. f 23 2. c 2 6. g 5 3. d 13 7. h 13 8 9 10 11 12 13 14 15 10 11 2 13 22 23 5 13 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 左半分を、各シンボルの葉へのポインタにする。具体的には、左側の要素の添え字がシンボル番号、値がポイントすべき右側の要素の添え字になる 例えば左上表からシンボル番号 i = 0 の 'a' を考える。A[0] は右半分の要素の中で 'a' の出現頻度に相当している要素を指す。よって A[0] = 8 になる。A[A[0]] = 10 とすれば 'a' の出現頻度 10 が得られる 一般化すると A[A[i]] = Ci になるように配列の左半分を埋めるということ

これにより A[0] がヒープの根になる。つまり、A[0] は出現頻度最小の値をポイントすることになる 0. a 10 4. e 22 1. b 11 5. f 23 2. c 2 6. g 5 3. d 13 7. h 13 10 9 14 11 12 13 8 15 10 11 2 13 22 23 5 13 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 次に出現頻度の値を比較キーにして二分木ヒープ(※)を構成する。このとき右半分の出現頻度の配列、つまり葉で直接ヒープを構成するのではなく、左半分のポインタで間接的にヒープを構成する。右半分の値 (葉) は変更せず、左半分だけが必要に応じて入れ替わる。 これにより A[0] がヒープの根になる。つまり、A[0] は出現頻度最小の値をポイントすることになる ※配列で二分木ヒープを構成する場合、親の添え字を i とすると左の子は 2i + 1, 右の子は 2i + 2。「親の指す値が常に子のそれよりも小さい」という制約を満たすのがヒープの条件

0. a 10 4. e 22 1. b 11 5. f 23 2. c 2 6. g 5 3. d 13 7. h 13 10 9 14 11 12 13 8 15 10 11 2 13 22 23 5 13 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 いよいよハフマン木の構築を始める。通常のハフマン木構築アルゴリズム同様、出現頻度が最も小さい二つの値を(greedy に)見つけたい。ひとつは、ヒープの根である A[0] がポイントする最小値である。

0. a 10 4. e 22 1. b 11 5. f 23 2. c 2 6. g 5 3. d 13 7. h 13 10 m1 10 9 14 11 12 13 8 15 10 11 2 13 22 23 5 13 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 一時変数 m1 に A[0] を取り出し、

0. a 10 4. e 22 1. b 11 5. f 23 2. c 2 6. g 5 3. d 13 7. h 13 m1 10 15 9 14 11 12 13 8 15 10 11 2 13 22 23 5 13 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 左半分の配列の末尾の値を先頭にコピー(上書き)し、

0. a 10 4. e 22 1. b 11 5. f 23 2. c 2 6. g 5 3. d 13 7. h 13 m1 10 14 9 8 11 12 13 15 15 10 11 2 13 22 23 5 13 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 [0, n -1] だった左半分の配列の範囲を一つ減らして [0, n - 2] の範囲でヒープを構成しなおす。 これで最初の最小値である 2 (を指しているポインタ) をヒープから取り出して、ヒープを再構成したことになる。

0. a 10 4. e 22 1. b 11 5. f 23 2. c 2 6. g 5 3. d 13 7. h 13 m1 10 14 9 8 11 12 13 15 15 10 11 2 13 22 23 5 13 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 次の最小値は構成しなおしたヒープの根 A[0] にある。よって次の最小値は A[A[0]] = A[14] = 5

0. a 10 4. e 22 1. b 11 5. f 23 2. c 2 6. g 5 3. d 13 7. h 13 m1 10 m2 14 14 9 8 11 12 13 15 15 10 11 2 13 22 23 5 13 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 二つ目の最小値を一次変数 m2 に取り出す。(今回はヒープの再構成はまだ走らせないことに注意)

ヒープから要素を一つ取り出して空いた領域 A[7] があるので、そこに二値の和 A[m1] + A[m2] = 7 の値を入れる 0. a 10 4. e 22 1. b 11 5. f 23 2. c 2 6. g 5 3. d 13 7. h 13 m1 10 m2 14 14 9 8 11 12 13 15 7 10 11 2 13 22 23 5 13 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 ここまでで最小の出現頻度の値二つが分かった。通常のハフマンアルゴリズムではここでこの二値の和を取ってできた節をハフマン木の新しい内部節 = 親とするわけだが、それと同等のことを行う。 ヒープから要素を一つ取り出して空いた領域 A[7] があるので、そこに二値の和 A[m1] + A[m2] = 7 の値を入れる

A[0] の値は既に m2 にコピーしてあり要らないので、そこから新しい要素をポイントする。 0. a 10 4. e 22 1. b 11 5. f 23 2. c 2 6. g 5 3. d 13 7. h 13 m1 m2 10 14 7 9 8 11 12 13 15 7 10 11 2 13 22 23 5 13 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 A[0] の値は既に m2 にコピーしてあり要らないので、そこから新しい要素をポイントする。

これで葉 (もしくは内部節)から親を参照したことになる 0. a 10 4. e 22 1. b 11 5. f 23 2. c 2 6. g 5 3. d 13 7. h 13 m1 m2 10 14 7 9 8 11 12 13 15 7 10 11 7 13 22 23 7 13 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 最小値として扱った要素 A[m1] と A[m2] も用済み。A[m1]、A[m2] からも新しい要素(つまり親) をポイントする。すなわち A[m1] = A[m2] = A[0] これで葉 (もしくは内部節)から親を参照したことになる

新しく追加した要素を加味して、左側のヒープを構成しなおす。(この場合、新しく追加した要素 A[7] = 7 は最小なのでヒープに変更はなし) 0. a 10 4. e 22 1. b 11 5. f 23 2. c 2 6. g 5 3. d 13 7. h 13 7 9 8 11 12 13 15 7 10 11 7 13 22 23 7 13 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 新しく追加した要素を加味して、左側のヒープを構成しなおす。(この場合、新しく追加した要素 A[7] = 7 は最小なのでヒープに変更はなし) ここまでで、ハフマン木構築処理のうち、最小の二つの要素を取って和を取り新しい要素にし、ヒープを次の繰り返しに備えて再構築する、という手順が一回完了した。

0. a 10 4. e 22 1. b 11 5. f 23 2. c 2 6. g 5 3. d 13 7. h 13 7 m1 7 9 8 11 12 13 15 7 10 11 7 13 22 23 7 13 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 以下、ここまでの手順を繰り返す 根で最小値を指す A[0] を取り出し、

左半分の配列の末尾の値を先頭にコピー(上書き)し、 0. a 10 4. e 22 1. b 11 5. f 23 2. c 2 6. g 5 3. d 13 7. h 13 7 m1 15 9 8 11 12 13 15 7 10 11 7 13 22 23 7 13 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 左半分の配列の末尾の値を先頭にコピー(上書き)し、

[0, n -2] だった左半分の配列の範囲を一つ減らして [0, n - 3] の範囲でヒープを構成しなおす 0. a 10 4. e 22 1. b 11 5. f 23 2. c 2 6. g 5 3. d 13 7. h 13 7 m1 8 9 15 11 12 13 15 7 10 11 7 13 22 23 7 13 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 [0, n -2] だった左半分の配列の範囲を一つ減らして [0, n - 3] の範囲でヒープを構成しなおす

二つ目の最小値を指すポインタを m2 に取り出し、 0. a 10 4. e 22 1. b 11 5. f 23 2. c 2 6. g 5 3. d 13 7. h 13 7 m1 m2 8 8 9 15 11 12 13 15 7 10 11 7 13 22 23 7 13 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 二つ目の最小値を指すポインタを m2 に取り出し、

A[m1] + A[m2] = 17 を、ヒープから要素を取り出したことで空いていた要素に入れる 0. a 10 4. e 22 1. b 11 5. f 23 2. c 2 6. g 5 3. d 13 7. h 13 7 m1 m2 8 8 9 15 11 12 13 17 7 10 11 7 13 22 23 7 13 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 A[m1] + A[m2] = 17 を、ヒープから要素を取り出したことで空いていた要素に入れる

用済みの要素である先頭、今回扱った二つの最小値要素から、今できた新しい要素をポイントする 0. a 10 4. e 22 1. b 11 5. f 23 2. c 2 6. g 5 3. d 13 7. h 13 7 m1 m2 8 6 9 15 11 12 13 17 6 6 11 7 13 22 23 7 13 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 用済みの要素である先頭、今回扱った二つの最小値要素から、今できた新しい要素をポイントする

0. a 10 4. e 22 1. b 11 5. f 23 2. c 2 6. g 5 3. d 13 7. h 13 9 11 15 6 12 13 17 6 6 11 7 13 22 23 7 13 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 ヒープを構成しなおす。 これでハフマン木構築の繰り返し2回目が完了。このまま繰り返していくと、ループのたびにヒープ(青の要素)とオリジナルの出現頻度値を保持していた要素(橙色の要素)が少なくなっていき、親をポイントしている要素(緑の要素)が増えていくことが直感的にわかる

A[1] が木の根が持つ値。すべてのシンボルの出現回数の合計になる 赤枠で囲っているのは、元々出現確率の値を持っていた要素、つまり葉 0. a 10 4. e 22 1. b 11 5. f 23 2. c 2 6. g 5 3. d 13 7. h 13 1 99 1 1 2 2 4 6 6 5 7 5 3 3 7 4 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 繰り返しの末、最終的には上図になる A[0] が木の根へのポインタ A[1] が木の根が持つ値。すべてのシンボルの出現回数の合計になる 赤枠で囲っているのは、元々出現確率の値を持っていた要素、つまり葉 これらの要素はヒープの構成時に、場所を移動してない つまり、A[n + i] は変わらずハフマン木の葉に相当している よって、葉 i から根まで上るには A[n + i] から始めてその値でポインタをたぐり寄せていけばよい

A[10] → A[7] → A[6] → A[4] → A[2] → A[1] と葉から始まり親を辿って根に到達 0. a 10 4. e 22 1. b 11 5. f 23 2. c 2 6. g 5 3. d 13 7. h 13 1 99 1 1 2 2 4 6 6 5 7 5 3 3 7 4 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 例えばシンボル c の符号長は、 c の番号は 2 なので n + i = 8 + 2 = A[10] A[10] → A[7] → A[6] → A[4] → A[2] → A[1] と葉から始まり親を辿って根に到達 5回辿ったので、符号長は 5

1 99 1 1 2 2 4 6 6 5 7 5 3 3 7 4 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 ここで 子 → 親はかならず右から左へ向かっている。ということは、逆に左から右、つまり先頭から末尾に向かうのは親から子に向かう動きになる。 この特徴を利用すると、左から順番に A[i] = A[A[i]] + 1 していくだけで、A[n + i] にシンボル i の符号長が入る。これを理解するために動きを追ってみる。 まず根は A[1] = 0 とする 1 1 1 2 2 4 6 6 5 7 5 3 3 7 4 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

1 1 1 2 2 4 6 6 5 7 5 3 3 7 4 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 次の要素 A[2] は 1 で、この 1 は根である A[1] の添え字を指さしている。 さて、添え字を 1 → 2 と移動してきたのは、左から右へ移動をしたということで、これはハフマン木の親から子を辿っていることに等しい。 ハフマン木では幹を一回辿るたびに符号長が +1 されるわけだから、(親が今辿った道までの符号長を記録していると考えると) A[2] までの符号長は親である A[1] の符号長 +1 である。 先に A[1] = 0 としたのは、根は当然まだ幹を一度も辿ってないので、そこまでの符号長が 0 ということ。よって A[2] = A[A[1]] + 1 = 0 + 1 1 1 1 2 2 4 6 6 5 7 5 3 3 7 4 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 同じように、A[3] = 1 → A[3] = A[A[1]] + 1 = 0 + 1

1 1 1 2 2 4 6 6 5 7 5 3 3 7 4 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 A[4] = 2 ということは、A[4] へは親である A[2] から辿ってくるということ。従って A[4] での符号長は A[4] = A[A[2]] + 1 このように、左から順番に A[i] = A[A[i]] + 1 するということは、親からひとつ子を辿ったら、親が持っていた符号の長さに +1 したことに等しい 2n まで処理すると最終的に以下のようになる 1 1 1 2 2 3 4 4 3 5 3 2 2 5 3 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 先にも述べたように、シンボル i の葉に相当するのは A[n + i]。赤枠で囲った右半分の配列の中身が、各シンボルの符号長である。例えば、シンボル c (番号2) の符号長は A[n + i] = A[8 + 2] = 5 おしまい

参考文献 Ian H. Witten, Alistair Moffat, Timothy C. Bell 『Managing Gigabytes: Compressing and Indexing Documents and Images』, Morgan Kaufmann Pub, 1999