パッケージマージアルゴリズム

パッケージマージアルゴリズムは、与えられたアルファベットのサイズnの分布に対して、長さ制限のあるハフマンコードを最適化するO (nL)時間アルゴリズムです。ここで、コードワードはLより長くなりません。これは貪欲アルゴリズムであり、ハフマンの元のアルゴリズムを一般化したものです。パッケージマージは、コード構築問題をバイナリコインコレクターの問題に縮小することで機能します。^[1]

コイン収集家の問題

あるコイン収集家が、さまざまな額面のコインを多数所有しており、それぞれのコインには額面とは無関係の貨幣価値があるとします。コイン収集家のお金が尽きたため、コインコレクションの一部を使ってコストNの何かを購入する必要があります。収集家は、コインコレクションから、貨幣価値が最小のコインのサブセットを選択し、額面の合計をNにしたいと考えています。

この問題の 2 進数バージョンでは、すべての額面金額は 2 の累乗、つまり 1 ドル、1/2 ドル、1/4 ドルなどになります。

パッケージマージアルゴリズムの説明

最も大きな額面が 1 ドルで、N が整数であると仮定します (これらの仮定が成り立たない場合でも、些細な変更を加えることでアルゴリズムは機能します)。コイン収集家はまず、コインを各額面ごとに貨幣価値順に並べたリストに分けます。次に、最小額面のコインを、貨幣価値の合計が最も小さいペアから始めて、ペアでパッケージ化します。コインが 1 枚余った場合は、その額面の貨幣価値が最も高いコインとなり、その後は除外されます。次に、これらのパッケージは、貨幣価値の順に、次に小さい額面のコインのリストに結合されます。そのリストのアイテムはペアでパッケージ化され、次に小さいリストに結合され、これを繰り返します。

最後に、アイテムのリストがあります。各アイテムは 1 ドル硬貨、または合計額面が 1 ドルになる 2 枚以上の小額硬貨で構成されたパッケージです。これらも貨幣価値の順に並べられています。次に、コイン収集家はそれらのうち最も価値の低い N 枚を選択します。

アルゴリズムの時間はコインの数に比例することに注意してください。

長さ制限付きハフマン符号化のコイン収集家の問題への還元

L をコードワードの最大長とする。p ₁ , …, p n_をエンコードするアルファベットのシンボルの出現頻度とする。まず、p _i ≤ p _i₊₁となるようにシンボルをソートする。各シンボルに対して、額面 2 ⁻¹ , …, 2 ⁻^Lで貨幣価値p _iのL 枚のコインを作成する。パッケージマージアルゴリズムを使用して、額面の合計がn − 1となる最小貨幣価値のコインセットを選択する。h _{i を}選択された貨幣価値p _iのコインの数とする。最適な長さ制限ハフマンコードは、シンボルi を長さh _iのビット文字列でエンコードする。標準的なハフマンコードは、h _{i が}既知であれば、単純なボトムアップの貪欲法で簡単に構築でき、これが高速データ圧縮の基礎となる。^[2]

パフォーマンスの改善と一般化

この縮小により、アルゴリズムはO(nL)時間およびO(nL)空間になります。ただし、元の論文「最適な長さ制限付きハフマンコードの高速アルゴリズム」では、これをO(nL)時間およびO(n)空間に改善する方法が示されています。アイデアは、アルゴリズムを最初に実行し、元の問題の半分のサイズになる 2 つの同等のサブ問題を決定できるだけのデータのみを保持するというものです。これは再帰的に行われ、結果として、約 2 倍の時間がかかりますが、線形空間のみを必要とするアルゴリズムになります。^[1]

パッケージマージアルゴリズムには、乗法定数を減らしたり、繰り返しのp _iを持つ問題などの特殊なケースで高速化したりするために、他の多くの改良が加えられています。^{[3]パッケージマージアプローチは、}アルファベットコーディングなどの関連する問題にも適応されています。^[4]

グラフ理論を伴う方法は、パッケージマージアルゴリズムよりも漸近的な空間計算量が優れていることが示されていますが、実用的な応用はあまり見られません。

参考文献

^ ab Larmore, Lawrence L. ; Hirschberg, Daniel S. (1990). 「最適な長さ制限付きハフマンコードの高速アルゴリズム」Journal of the Association for Computing Machinery . 37 (3): 464– 473. doi : 10.1145/79147.79150 . S2CID 11696729.
^ Moffat, Alistair; Turpin, Andrew (1997 年 10 月). 「最小冗長プレフィックスコードの実装について」. IEEE Transactions on Communications . 45 (10): 1200– 1207. doi :10.1109/26.634683.
^ Witten, Ian H. ; Moffat, Alistair; Bell, Timothy Clinton (1999). 『ギガバイトの管理: ドキュメントと画像の圧縮とインデックス作成(第 2 版)』Morgan Kaufmann Publishers . ISBN 978-1-55860-570-1. 1558605703.
^ Larmore, Lawrence L. ; Przytycka, Teresa M. (1994). 「高さ制限付きアルファベット二分木の最適解の高速アルゴリズム」SIAM Journal on Computing . 23 (6): 1283– 1312. doi :10.1137/s0097539792231167.

外部リンク

Baer, Michael B. (2006). 「20 (またはそれくらい) の質問: D進数長さ制限プレフィックスコーディング」. arXiv : cs.IT/0602085 .
Moffat, Alistair; Turpin, Andrew; Katajainen, Jyrki (1995 年 3 月)。「スペース効率に優れた最適プレフィックスコードの構築」IEEE データ圧縮会議。米国ユタ州スノーバード。doi : 10.1109/DCC.1995.515509。
パッケージマージアルゴリズムの実装 "[1]"
パッケージマージアルゴリズムを使用する高速エントロピーコーダ[2]

[LaHi-1] Larmore, Lawrence L. ; Hirschberg, Daniel S. (1990). 「最適な長さ制限付きハフマンコードの高速アルゴリズム」Journal of the Association for Computing Machinery . 37 (3): 464– 473. doi : 10.1145/79147.79150 . S2CID 11696729.

[MoTu-2] Moffat, Alistair; Turpin, Andrew (1997 年 10 月). 「最小冗長プレフィックスコードの実装について」. IEEE Transactions on Communications . 45 (10): 1200– 1207. doi :10.1109/26.634683.

[MG-3] Witten, Ian H. ; Moffat, Alistair; Bell, Timothy Clinton (1999). 『ギガバイトの管理: ドキュメントと画像の圧縮とインデックス作成(第 2 版)』Morgan Kaufmann Publishers . ISBN 978-1-55860-570-1. 1558605703.

[LaPr-4] Larmore, Lawrence L. ; Przytycka, Teresa M. (1994). 「高さ制限付きアルファベット二分木の最適解の高速アルゴリズム」SIAM Journal on Computing . 23 (6): 1283– 1312. doi :10.1137/s0097539792231167.