15.5 最適2分探索木

英語の文章をフランス語に翻訳するプログラムを設計することになったとしよう => 今ならニューラルネットだ！以上！

ある英単語が文章に現れるたびに同じ意味を持つフランス語の英語を探索する必要がある。英単語をキーとして対応するフランス語の単語を付属データとするn個のオブジェクトから構成される2分探索木を作ることでこの探索操作を実現できる。文章中に現れる英単語のそれぞれに対して木を探索するから総探索時間をできる限り少なく抑えたい。1回の英単語の出現にチアして探索時間をO(log n)で抑えることは2色木や平衡2分探索木を用いることで実現できる。しかし、単語が出現する回数は単語によって異なるので"the"のようによく出現する単語が探索木の根から遠くに配置される一方、"machicolation"のようにほとんど出現しない単語が根の近くに配置されるようなことが起きるかもしれない。あるキーを2分探索木の中から発見する際に訪れる節点数は、このキーを含む節点の深さに1を加えたものだから、このような2分探索木の構成は翻訳速度を低下させるに違いない。そこで頻繁に出現する単語ほど根の近くにはいちされるようにしたい。さらに文章の中にフランス語に翻訳できない単語が現れるかもしれず、そのような単語は2分探索木にまったく現れるない。以下では各単語が出現する頻度が与えられたとき、すべての探索で訪れる節点数の総和最小化するように2分探索木を構成する方法を考察する。

最適2分探索木として知られている木を構成することが我々の目的である。正確に述べる。
ソート済みのn個の異なるキーの列K = [k_1, k_2, ..., k_n] (k_1 < k_2 < ... < k_n) が与えられたとき、これらのキーがある2分探索木を構成する。各キー k_i に対して探索が起きる確率 p_i が分かっている。探索は K が含まない値に対して起きるかもしれないから、 K が含まない値を示すために n + 1 個の「ダミーキー」d_0, d_1, d_2, ..., d_n を用意する。具体的に言うと、 d_0 は k_1 未満のすべての値を表現し、d_n は k_n を超えるすべての値を表現する。また、各 i = 1, 2, ..., n-1 に対して、d_i は k_i と k_{i+1} の間のすべての値を表現する。各ダミーキー d_i に対して、探索が d_i で終わる確率 q_i も分かっているものとする。

i	0	1	2	3	4	5
p_i		0.15	0.1	0.05	0.1	0.2
q_i	0.05	0.1	0.05	0.05	0.05	0.1

(a)
k_2
k_1, k_4
d_0, d_1, k_3, k_5
d_2, d_3, d_4, d_5

期待値
0.15 * 2 + 0.1 * 1 + 0.05 * 3 + 0.1 * 2 + 0.2 * 3 = 1.35
0.05 * 3 + 0.1 * 3 + 0.05 * 4 + 0.05 * 4 + 0.05 * 4 + 0.1 * 4 = 1.45
1.35 + 1.45 = 2.8

(b)
k_2
k_1, k_5
d_0, d_1, k_4, d_5
k_3, d_4
d_2, d_3

期待値
0.15 * 2 + 0.1 * 1 + 0.05 * 4 + 0.1 * 3 + 0.2 * 2 = 1.30
0.05 * 3 + 0.1 * 3 + 0.05 * 5 + 0.05 * 5 + 0.05 * 4 + 0.1 * 3 = 1.45
1.30 + 1.45 = 2.75

n = 5 個のキーの集合に対する2つの2分探索木を示す。各キー k_i は内部節点、各ダミーキー d_i は葉である。任意の探索は成功するか失敗するかのどちらかなので

\sum_{i=1}^{n} p_i + \sum_{i=0}^{n} q_i = 1

が成立する。
各キーおよび各ダミーキーを探索する確率が与えられているので、与えられた2分探索木Tにおける1回の探索コストの期待値が決定できる。1回の探索にかかる実コストは訪れた節点の数、すなわち、発見された節店のTにおける深さ+1であると仮定する。このときTにおける1回の探索コストの期待値は

E[search cost in T] =\sum_{i=1}^n ({depth}_T (k_i) + 1) \cdot p_i + \sum_{i=0}^n ({depth}_T (d_i) + 1) \cdot q_i \\
= 1 + \sum_{i=1}^n {depth}_T (k_i) \cdot p_i + \sum_{i=0}^n {depth}_T (d_i) \cdot q_i

である。ただし、{depth}_T は木Tにおける節点の深さを示す。

与えられた確率の集合に対して、探索コストの期待値を最小化する2分探索木を構成したい。このような木を最適2分探索木と呼ぶ。 (b) は上述の確率の集合に対する最適2分探索木であり、探索コストの期待値は2.75である。最適2分探索木は必ずしも必ずしも高さが最小となる木ではなく、最大の確率を持つキーが必ずしも根に置かれるわけでもないことをこの例は示している。この例では k_5 の探索確率が最大であるが、最適2分探索木の根は k_2 である。

連鎖行列積の場合と同様、すべての可能性をシラミツブシに調べる方法からは効率的なアルゴリズムを生成できない。
n個の節店を持つ任意の2分木の節点をキー k_1, ..., k_n でラベル付けして2分探索木をつくり、さらにダミーキーを葉として追加する。章末問題12-4で示したようにn個の節点を持つ2分木の個数は \Omega (4^n / n^{3/2}) だから、全探索では指数的個数の2分探索木を検討する必要に迫られる。よって、動的計画法やで

第1段階: 最適2分探索木の構造

部分木の考察から始めて最適2分探索木の部分構造最適性を特徴づける。2分探索木の任意の部分木を考える。
この部分木はある 1 <= i <= j <= n に対して、連続する範囲 k_i, ..., k_j に属するキーを含む。
そして、キー k_i, ..., k_j を含む部分木はさらにダミーキー d_{i-1}, ..., d_j もまたその葉として含んでいる。

部分構造最適性を説明する。
最適2分探索木Tがキー k_i, ..., k_j を含む部分木 T' を持つとする。このとき、部分木 T' はキー k_i,..., k_j とダミーキー d_{i-1}, ..., d_j から定義される部分問題に対する最適2分探索木でなければならない。この事実は切り貼り論法を適用すれば証明できる(T'が最適2分探索木でないならば、最適なものに置き換えるとTの期待コストは更に下がる。最適に矛盾する)。

問題に対する最適解を部分問題に対する最適解から構成できることを示すために部分構造最適性を用いる。与えられたキー k_i, ..., k_j に対する最適部分木の根は、この中のあるキー k_r (i <= r <= j)である。そして、根 k_r の左部分木はキー k_i, ..., k_{r-1} (とダミーキー d_{i-1}, ..., d_{r-1}) を含み、右部分木はキー k_{r+1}, ..., k_j (とダミーキー d_r, ..., d_j) を含む。そこで、根のすべての候補 k_r (i <= r <= j) を検討し、キー k_i, ..., k_{r-1} および k_{r+1}, ..., k_j のそれぞれを含む最適2分探索木を決定することで、最適2分探索木を必ず発見できる。

"空"の部分木は注意を払う価値がある。キー k_i, ..., k_j を持つ部分木において、 k_i を根に選択したとしよう。上記の議論から、k_iの左部分木はキー k_i, ..., k_{r-1} を含む。この状況はキーを含まないと解釈するのが自然である。しかし、部分木はダミーキーも含んでいたはずだ。そこで、キー k_i, ..., k_{i-1} を含む部分木は実キーを含まず、1個のダミーキー d_{i-1} だけを含むと解釈する。対称的に k_j を根に選択した時、 k_j の右部分木はキー k_{j+1}, ..., k_j を含む。この状況の右部分木は実キーを含まず、ダミーキー d_j だけを含むと解釈する。

第2段階: 再帰的な解

最適解の値を再帰的に定義する準備が整った。 i >= 1, j <= n かつ j >= i-1 を満たす各i, jに対して、キー k_i, ..., k_j を含む最適2分探索木を発見する問題を部分問題の領域として採用する(j = i-1 ならば実キーはなく、ダミーキー d_{i-1} だけである)
。キー k_i,..., k_j を含む最適2分探索木の探索コストの期待値を e[i, j] で表す。最終目的は e[1, n] を計算することである。
j = i-1 の場合は簡単である。ダミーキー d_{i-1} があるだけだから、期待探索コストは e[i, i-1] = q_{i-1} である。
j >= i の場合には、 k_i, ..., k_j の中から根k_rを選択し、キー k_i, ..., k_{r-1} を持つ最適2分探索木を左部分木、キー k_{r+1}, ..., k_j を持つ最適2分探索木を右部分木とする2分探索木を構成しなければならない。ある部分木がある節点の部分木となったときに起きる期待探索コストの変化を検討する。部分木の各節点の深さは1ずつ増加する。したがって、等式

E[search cost in T] =\sum_{i=1}^n ({depth}_T (k_i) + 1) \cdot p_i + \sum_{i=0}^n ({depth}_T (d_i) + 1) \cdot q_i \\
= 1 + \sum_{i=1}^n {depth}_T (k_i) \cdot p_i + \sum_{i=0}^n {depth}_T (d_i) \cdot q_i

から、この部分木の期待探索コストは部分木の中の確率の和だけ増加する。キー k_i, ..., k_j を持つ部分木に対して、この確率の和を

w(i, j) = \sum_{l=i}^{j} p_l + \sum_{l=i-1}^j q_l

で表す。そこで k_r がキー k_i, ..., k_j を含む最適部分探索木の根であれば、

e[i, j] = p_r + ( e[i, r-1] + w(i, r-1)) + (e[r+1, j] + w(r+1, j))

が成立する。

w(i, j) = w(i, r-1) + p_r + w(r+1, j)

に注意すると、e[i, j]を

e[i, j] = e[i, r-1] + e[r+1, j] + w(i, j)

と書き換えることができる。

上記漸化式は根 k_r が既知であると仮定している。我々は期待探索コストを最小化する根を選択するから、最終的に再帰的な定式化

e[i, j] = \left\{
\begin{array}{ll}
q_{i-1} & (j = i - 1)\\
\min_{i \leq r \leq j} {e[i, r-1], + e[r+1, j] + w(i, j)} & (i \leq j)
\end{array}
\right.

を得る。

e[i, j]値が最適2分探索木の期待探索コストを与える。最適2分探索木の構造を管理するために、 1 <= i <= j <= n に対して、root[i, j] をキー k_i, ..., k_j を含む最適2分探索木の根 k_r の添字 r と定義する。 root[i, j] の値を計算する方法を以下で説明するが、これらの値から最適2分探索木を構成する方法は練習問題15.5-1とする。

第3段階: 最適2分探索木の期待探索コストの計算

最適2分探索木と連鎖行列積に対する特徴づけの類似性に気づかれただろうか？どちらの問題領域も各部分問題は添字のう連続区間に対応する。上述の式の直接的で再帰的な実現は非効率である。そこで、表 e[1..n+1, 0..n] に値 e[i, j] を保存する。第1引数の値は n ではなく、 n+1 まで動く必要がある。部分木がダミーキー d_n だけを含む場合のために、 e[n+1, n] を計算して保存する必要がある。部分木がダミーキー d_n だけを含む場合のために、 e[n+1, n] を計算して保存する必要があるからである。一方、第2引数の値は0から始まる必要がある。ダミーキー d_0 だけを含む部分木を考慮するために、 e[1, 0] を計算して保存する必要があるからである。我々は j >= i-1 を満たす要素 e[i, j] だけを利用する。キー k_i, ..., k_j を含む部分木の根を記憶するために表 root[i, j] も使う。この表は 1 <= i <= j <= n を満たす要素だけを利用する。
効率を改善するためにさらに別の表を利用する。 e[i, j] を計算するたびに \Theta (j-i) 回の加算を用いて w(i, j) の値を最初から計算する代わりに、これらの値を以下の要領で計算して表 w[1..n+1, 0..n] に保存しておく。基底は各1 <= i <= n+1 に対して w[i, i-1] = q_{i-1} である。 j >= i の場合は

w[i, j] = w[i, j-1] + p_j + q_j \hspace{100pt}(15.15)

によって計算する。したがって、 \Theta (n^2) 個の w[i, j] 値を1個当り \Theta (1) 時間で計算できる。
以下の疑似コードは確率 p_1, ..., p_n および q_0, ..., q_n とサイズnを入力として取り、表 e と root を出力する。

OPTIMAL-BST(p, q, n)
e[1..n+1, 0..n], w[1..n+1, 0..n], root[1..n, 1..n] を新しい表とする
for i = 1 to n + 1
  e[i, i-1] = q_{i-1}
  w[i, i-1] = q_{i-1}
for l = 1 to n
  for i = 1 to n - l + 1
    j = i + l - 1
    e[i, j] = \infty
    w[i, j] = w[i, j-1] + p_j + q_j
    for r = i to j
      t = e[i, r-1] + e[r+1, j] + w[i, j]
      if t < e[i, j]
        e[i, j] = t
        root[i, j] = r
return e and root

上の擬似コードおよび第15.2節で述べた手続き MATRIX-CHAIN-ORDER との類似性から、手続きの動作が容易に分かるであろう。第2-4行のfor文でe[i, i-1]とw[i, i-1]を初期化する。第5-14行のfor文では漸化式(15.14)と(15.15)を用いて、すべての 1 <= i <= j <= n に対して e[i, j] と w[i, j] を計算する。 l = 1, l = 2, ... と繰り返す。第10-14行の最も内側のfor文はキーk_i, ..., k_jを含む最適2分探索木の根となるキーk_rを決定するために添え字rの候補を比較検討する。このfor文はよりよい根の候補を発見するとその添字rをroot[i, j]に保存する。
図15.9に示したキー分布を入力とする手続きOPTIM_BSTが計算した表 e[i, j], w[i, j], root[i, j] を図15.10に示す。図15.5に示した連鎖行列積の例のように対角線が水平になるように表を回転してある。OPTIMAL-BSTは行を下から上に同じ行の中では左から右に向かって計算をすすめる。
MATRIX-CHAIN-ORDERと同様、手続きOPTIMAL-BSTは \Theta (n^3) 時間で走る。3重のfor文があり、各for文のループ制御変数は高々n個の値をとるので、実行時間は O(n^3) で抑えられる。OPTIMAL-BSTとMATRIX-CHAIN-ORDERに現れるループ制御変数は厳密に同じ範囲を取るわけではないが、どの方向についてもその差は高々1である。したがって、MATRIX-CHAIN-ORDERと同様手続きOPTIMAL-BSTの実行には \Omega (n^3) 時間が必要である。

i	0	1	2	3	4	5
p_i		0.15	0.1	0.05	0.1	0.2
q_i	0.05	0.1	0.05	0.05	0.05	0.1

e

i\j	0	1	2	3	4	5
1	0.05	0.45	0.90	1.25	1.75	2.75
2		0.1	0.4	0.7	1.2	2.0
3			0.05	0.25	0.6	1.3
4				0.05	0.3	0.9
5					0.05	0.5
6						0.1

w

i\j	0	1	2	3	4	5
1	0.05	0.3	0.45	0.55	0.7	1.0
2		0.1	0.25	0.35	0.5	0.8
3			0.05	0.15	0.3	0.6
4				0.05	0.2	0.5
5					0.05	0.35
6						0.1

root

i\j	1	2	3	4	5
1	1	1	2	2	2
2		2	2	2	4
3			3	4	5
4				4	5
5					5

練習問題

15.5-1

表rootが与えられとき、最適2分探索木の構造を出力する手続きCONSTRUCT-OPTIMAL-BST(root)の擬似コードを記述せよ

CONSTRUCT-OPTIMAL-BST(root, i, j, last)
if i == j
  return
if last == 0
  print root[i, j] + "is the root"
else if j < last
  print root[i, j] + "is the left child of" + last
else
  print root[i, j] + "is the right child of" + last
CONSTRUCT-OPTIMAL-BST(root, i, root[i, j] - 1, root[i, j])
CONSTRUCT-OPTIMAL-BST(root, root[i, j] + 1, j, root[i, j])

15.5-2

以下の確率を持つn=7個のキーの集合に対する最適2分探索木のコストと構造を決定せよ

i	0	1	2	3	4	5	6	7
p_i		0.04	0.06	0.08	0.02	0.1	0.12	0.14
q_i	0.06	0.06	0.06	0.06	0.05	0.05	0.05	0.05

e

i\j	0	1	2	3	4	5	6	7
1	0.06	0.28	0.62	1.02	1.34	1.83	2.44	3.12
2		0.06	0.4	0.7	1.02	1.51	2.05	2.7
3			0.06	0.32	0.57	1.04	1.68	2.13
4				0.06	0.24	0.57	1.01	1.55
5					0.05	0.3	0.72	1.2
6						0.05	0.32	0.78
7							0.05	0.34
8								0.05

w

i\j	0	1	2	3	4	5	6	7
1	0.06	0.16	0.28	0.42	0.49	0.64	0.81	1.0
2		0.06	0.18	0.32	0.39	0.54	0.71	0.9
3			0.06	0.2	0.27	0.42	0.59	0.78
4				0.06	0.13	0.28	0.45	0.64
5					0.05	0.2	0.37	0.56
6						0.05	0.22	0.41
7							0.05	0.24
8								0.05

root

i\j	1	2	3	4	5	6	7
1	1	2
2		2	2
3			3	3
4				4
5					5
6						6
7							7

15.5-3

表w[i,j]を管理する代わりにOPTIMAL-BSTの第9行で等式(15.12)を用いてw(i, j)値を直接計算し、計算した値を第11行で利用することにする。この変更がOPTIMAL-BSTの漸近的な実行時間に与える影響を述べよ

w[i, j] が \Theta (n^2) 個。 w[i, j] の計算に O(n) かかる。 \Theta(n^3) が O(n^3) ぐらいに劣化する

15.5-4

すべての 1 <= i <= j <= n に対して、 root[i, j-1] <= root[i, j] <= root[i+1, j] を満たす最適部分木の根が常に存在することを Knuth[212] は示した。この事実を用いて手続きOPTIMAL-BSTの実行時間を \Theta (n^2) に改善せよ