Order-Maintenance Problem

記念すべき最初の記事です。

最近忘却がひどいので、学んだことをちゃんとここに残していけたらなと思います。

内容

本記事では以下の論文

  • Bender M.A., Cole R., Demaine E.D., Farach-Colton M., Zito J. Two Simplified Algorithms for Maintaining Order in a List. ESA 2002.

の内容(の一部)を紹介します。

問題設定

系列 (x_1, x_2, ..., x_n) に対し、以下の操作を提供するデータ構造を考えます。

  • insert(x, x_i): 新しい要素 x を x_i の直後に挿入
  • delete(x_i): 要素 x_i を削除
  • order(x_i, x_j): i < j なら True、それ以外は False を返す

これに関係する問題の一つとして、連結リストでの実現を考える (Online) List-Labeling Problem があります。本記事では List-Labeling Problem を扱います。

この問題では、n 個のアイテムから成る連結リストの各アイテムに、アイテムの順序と大小関係が一致するような 1 から u までの整数値のタグを、どう効率的に割り当てられるかを考えます。このようなタグを割り当てることで、order クエリは単純なタグの比較で実現することができます。

例として下図のような n=4, u=8 のリストを考えます。(矢印が片方向だけですけど双方向リストです。。。)

アイテムの順序を保持したタグが割り当てられているため、order(x_1, x_3) はタグの比較 3 < 5 により True ということが即座にわかります。delete もアイテムを消すだけなので簡単です。

ただし insert は少し複雑です。例えば、insert(x, x_3) は x_3 の直後に挿入される x にタグ 6 を割り当てることで順序は保持されます。一方、insert(x, x_2) では x_1 と x_3 のタグが隣り合っているので x に割り当てられるタグが存在せず、x_2 の周囲のアイテムのタグを割り当て直す必要があります。

この問題について、1987年にDietzとSleator1 が insert を O(log n) ならし時間、order と delete を O(1) 時間で実行できる解法を与えました。この計算量は List-Labeling Problem において最適2ですが、ポテンシャル法を用いた解析が複雑でした。

そこで、Benderらは2002年に同じ計算量のシンプルな解法を与えました。以下ではその解法を紹介します。

Benderらの解法 (ESA 2002)

以降では、語長  w = \Theta(\log n) の Word RAM モデル3を仮定し、 \lg = \log_2 とします。便宜上 u は2の累乗とします。

この解法では、タグの取り得る値が葉に対応する完全二分木を考えます。例えば、上のリストの例では下図のような完全二分木になります。

すなわち u 個の葉を持ち、n 個の葉がリストのアイテム(つまり使用中のタグ)に対応します。ただし、この木構造を陽に持つわけではなく、完全二分木なので木上の操作は計算でシミュレートできます。

各ノードについて、その部分木が囲い込むタグの区間境界タグ区間と定義します。例えば上の図では、色の付いた内部ノードの境界タグ区間は根から順に [1,8], [1,4], [3,4] です。

各ノード、もといその境界タグ区間には密度が定義されます。 これはその境界タグ区間で使用されているタグの割合です。 例えば、境界タグ区間 [1,8] で4つのタグが使用されているので、根の密度は 4/8 = 0.5 です。

再割当アルゴリズム

insert(x, x_i) に対し、x に新しいタグが割り当てられない場合、 Benderらのアルゴリズムでは以下の手順で該当する区間のダグを割り当て直します。

  • Step 1: x_i の葉の先祖を辿り、疎な境界タグ区間(後で説明)を見つかるまで探索する
  • Step 2: その区間のタグを等間隔に割り当て直す

例えば、上図で insert(x, x_2) を考えます。x_2 のタグに対応する葉 4 から先祖を辿って、境界タグ区間 [1,4] が疎だとすると、アイテム x_1 のタグを 1、アイテム x_2 のタグを 3 というように、この区間内のアイテムのタグを等間隔に割り当て直します。これによって、x_2 の直後に新しくアイテムが追加できるようになります。

疎な境界タグ区間

Benderらのアルゴリズムでは、以下に定義する閾値  \tau_k より密度が小さい境界タグ区間と言います。ここで、T は 1 より大きく 2 以下の実数値の定数です。

  • サイズ  2^0 = 1区間(つまり各葉)について、 \tau_0 = 1
  • サイズ  2^k 区間(つまり高さ k の内部ノード)について、 \tau_k = T^{-k}

例えば T = 1.4 だとすると  \tau_2 = 0.51 となり、境界タグ区間 [1,4] の密度は 0.5 なので疎となります。

定理: order を O(1) 時間で実行できる

order クエリはタグのシンプルな比較で実現できますが、定数時間で実行するためには割り当てられるタグが O(w) = O(lg n) ビットで表現できることを示す必要があります。そのために以下の補題を示します。

補題:lg u = O(lg n)

リストの更新に伴いアイテム数 n は変動し、n/2 または 2n に到達したときにデータ構造は再構築されるものとします。これは配列の拡張などで良く使われるテクニック4で、再構築は定数ならし時間で実行できます。故にアイテム数が n/2 から 2n の範囲でアルゴリズムが動作するように u の値を設定します。

アルゴリズムが動作するためには、Step 1で必ず疎な境界タグ区間を見つけられる必要があります。これは少なくとも根の境界タグ区間がいつも疎であり、その密度が  \tau_{ \lg u} より小さいときに満たされます。根の密度は 2n/u を超えることはないので、 \tau_{\lg u} = 2n/u を設定すればアルゴリズムは動作します。

定義より  \tau_{ \lg u } = T^{ - \lg u } = u^{ - \lg T } なので、

 \displaystyle u^{ - \lg T } = \frac{2n}{u} \Longleftrightarrow u = (2n)^{\frac{1}{1- \lg T}}

となり、

 \displaystyle \lg u = \lg (2n)^{\frac{1}{1- \lg T}} = O(\lg n)

補題が証明されました。

定理: insert を O(log n) ならし時間で実行できる

サイズ  2^k の境界タグ区間で再割当するときのコストを考え、出納法により計算量を解析します。

その区間に対応するノードを v とします。その密度は必ず  \tau_k 以下なので、その区間のアイテム数は  2^k \tau_k 個です。つまり再割当は  O(2^k \tau_k ) = O({2^k}/{T^k}) 時間で実行できます。また再割当の結果、v の子 v' の密度は  \tau_k = 1/T^k になります。

この再割当の後、リストが更新され v' に対し次に再割当が必要となるのは密度が  \tau_{k-1} = 1/T^{k-1} を超えたときであり、それまでに少なくとも  \left( {1}/{T^{k-1}} -  {1}/{T^{k}} \right) \cdot 2^{k-1} 回の insert が実行されます。これらの insert に v の再割当にかかるコストを預金すると、insert のならしコストは

 \displaystyle \frac{ {2^k}/{T^k} }{ \left( {1}/{T^{k-1}} -  {1}/{T^{k}} \right) \cdot 2^{k-1} } = \frac{2}{T-1}  = O(1)

になります。

とある insert には lg u 個の境界タグ区間が対応し、前の補題より O(lg u) = O(lg n) なので、insert のならしコストの合計は O(lg n) です。

まとめ

BenderらによるList-Labeling Problemのシンプルな解法を紹介しました。insert の計算量は O(log n) ならし時間ですが、これは indirection という間引きテクニック5を使うことで Order-Maintenance Problem における insert は O(1) ならし時間で実行できるそうです。

シンプルなデータ構造はわたしでも理解できるのでありがたいです。応用先はいろいろあって便利そうなので、自分も隙あらば使っていきたい所存。