Petitverse

圧縮
木の持ち方について
木の形変化する(動的木)ため、木はセオリー通りに持つのがいいと思います。
実際には、子の情報は不要で、親の情報と自身が左右どちらの子かを持てばよいです。
例えば、
https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_15_D&lang=ja
のハフマン木は以下のような持ち方が考えられます。
0 1 2 3 4 5 6 7 8 9 10 11
0 11 -8 8 -9 -7 7 9 10 -10 -11 0

ハフマン木の生成手順

ハフマン木は典型的には以下の手順で作成します。

- 出現率とデータをセットで持ち、出現率をキーとしたヒープに全て追加する
- ヒープからデータを2つ取り出して(pop)新たなデータを作成し、出現率を足して再度ヒープに追加する(push)
以下ループ

ヒープの値を更新するdecrease-keyの操作がサポートされている場合、pop→pushをdecrease-keyに置き換えることでより高速にハフマン木を生成することが出来ます。(一般にpop+pushよりdecrease-keyの方が高速なため)

- 出現率とデータをセットで持ち、出現率をキーとしたヒープに全て追加する
- ヒープからデータを1つ取り出し(pop)、aとする
- ヒープの最小値にaを加算する(decrease-key)
以下ループ

先のハフマン木を例に解説すると
最初に出現率とデータをヒープに追加します。
(45:1),(13:2),(12:3),(16:4),(9:5),(5:6)
ヒープからデータを1つ取り出します。
(5:6)
ヒープの最小値に取り出した出現率を加算します。ついでに、データも別のものに置き換えます。
(45:1),(13:2),(12:3),(16:4),(14:7)
ヒープからデータを1つ取り出します。
(12:3)
ヒープの最小値に取り出した出現率を加算します。
(45:1),(25:8),(16:4),(14:7)
ヒープからデータを1つ取り出します。
(14:7)
ヒープの最小値に取り出した出現率を加算します。
(45:1),(25:8),(30:9)
ヒープからデータを1つ取り出します。
(25:8)
ヒープの最小値に取り出した出現率を加算します。
(45:1),(55:10)
ヒープからデータを1つ取り出します。
(45:1)
ヒープの最小値に取り出した出現率を加算します。
(100:11)
ヒープ内のデータが1つになったら終了です。

使用ヒープについて
使用する動作は値の削除(pop),値の追加(push),最小値の確認(top)あるいは値の更新(decrease-key)のみであり、ヒープの併合(meld)を使用しないため、高速な二分ヒープを使用することが出来ます。
また、出現頻度は自然数となり、最後に取り出したデータより小さなデータを追加することはないため、radix heapと呼ばれる極めて高速なヒープも使用できます。
radix heapについては以下の資料が参考になります。(それぞれ別の実装なようです)
https://www.slideshare.net/yosupo/ss-46612984
https://dl.acm.org/doi/pdf/10.1145/77600.77615

背丈五郎さん
コンパクト符号。シンプルで解凍が楽なのが良いですよね。

下の論文の方のレベル1 radix heapを読んでました。
パッと見の感想は、よすぽさんの方のradix heapの愚直な実装って感じですね。(再振り分けが微妙に違いますが、ほとんど同じ仕組み)