データ構造における最適な偏り木：不等コスト記号のプレフィックス符号問題とそのアルゴリズム

不等コスト記号に対する最適な接頭辞符号の問題

不等な文字コストを持つ場合の最適な接頭辞自由符号（プレフィックスフリーコード）を求める問題とは、コスト（長さ）がそれぞれ α と β（ただし α ≤ β）である2種類の記号からなる符号化アルファベットを用いて、総コスト最小の接頭辞自由符号を計算する問題です。ここでは、二分木の場合に限定して考察します。

この符号は、ハフマン符号化問題の解がハフマン木によって表されるのと同じように、「偏り木（lopsided tree／ロプサイドツリー）」として表現されます。しかしながら、構造上の類似性にもかかわらず、文字コストが不等なケースは古典的なハフマン問題よりはるかに困難です。この問題については豊富な研究文献が蓄積されているにもかかわらず、一般的な文字コストに対する多項式時間アルゴリズムは、いまだに知られていません。

α と β が整数定数の場合

一方で、α と β が整数定数である場合には、多項式時間で動作するアルゴリズムが存在することが知られています。

この設定における最小コスト木の計算問題を最初に研究したのは、1961年の Karp です。彼はこの問題を整数線形計画法への帰着によって解決しましたが、そのアルゴリズムは n と β の両方に対して指数的な計算時間を要するものでした。それ以降、最適木のコストの上限評価や、すべての重みが等しいという特殊ケースへの限定など、問題のさまざまな側面に関して多くの研究が行われてきました。

驚くべきことに、これほど多くの努力が払われたにもかかわらず、この基本的な問題が多項式時間で解けるのか、それともNP完全なのかは、依然として明らかになっていません。

動的計画法によるアプローチとその改良

Golin と Rote は、木をトップダウン方式で構築する O(n^β+2) 時間の動的計画法アルゴリズムを提示しました。

その後、単調行列（monotone matrix）の概念、すなわちモンジュ性（Monge property）や SMAWK アルゴリズムといった異なるアプローチを採用することで、この結果はさらなる改良を遂げています。

定理1：最速の構築アルゴリズム

定理1： 最適な偏り木は O(n^β) 時間で構築できる。

これは、β の値が小さい場合において現時点で最も効率的なアルゴリズムです。実際の応用では、文字コストは通常小さな値になります（例：モールス符号）。

近似アルゴリズムへの展開

近年では、効率的な近似アルゴリズムの枠組みも提案されています。

定理2： 最適な偏り木に対する多項式時間近似スキーム（PTAS）が存在する。