最下位共通祖先

グラフ理論とコンピュータサイエンスでは、ツリーまたは有向非巡回グラフ(DAG) T内の2 つのノードvとwの最小共通祖先( LCA ) (最小共通祖先とも呼ばれる) は、 vとw の両方を子孫として持つ最も低い (つまり、最も深い) ノードであり、各ノードはそれ自身の子孫であると定義されます (したがって、v がwから直接接続されている場合、wが最小共通祖先です)。

Tにおけるvとwの LCA は、ルートから最も遠い位置にあるvとwの共通祖先です。最小共通祖先の計算は、たとえば、ツリー内のノードのペア間の距離を決定する手順の一部として役立ちます。v からwまでの距離は、ルートからvまでの距離に、ルートからwまでの距離を加算し、ルートから最小共通祖先までの距離の 2 倍を減算して計算できます(Djidjev、Pantziou、Zaroliagis 1991)。

各ノードがその親を指すツリー データ構造では、 vとwからルートへのパスの最初の交差点を見つけることで、最小共通祖先を簡単に特定できます。一般に、このアルゴリズムに必要な計算時間はO(h)です。ここで、hはツリーの高さ (リーフからルートまでの最長パスの長さ) です。ただし、最小共通祖先をより迅速に見つけられるようにツリーを処理するアルゴリズムはいくつか存在します。たとえば、 Tarjan のオフライン最小共通祖先アルゴリズムは、線形時間でツリーを前処理して、定数時間の LCA クエリを提供します。一般的な DAG にも同様のアルゴリズムがありますが、超線形の複雑さを伴います。

最低共通祖先問題は、アルフレッド・エイホ、ジョン・ホップクロフト、ジェフリー・ウルマン(1973) によって定義されましたが、 最も効率的な最低共通祖先データ構造を初めて開発したのは ドヴ・ハレルとロバート・タージャン(1984) でした。彼らのアルゴリズムは、重いパス分解を使用して任意のツリーを線形時間で処理するため、後続の最低共通祖先クエリにはクエリごとに定数時間で応答できます。ただし、彼らのデータ構造は複雑で実装が困難です。タージャンは、オフライン バッチのノード ペアの最下位共通祖先を計算するための、和集合検索データ構造に基づく、より単純だが効率の悪いアルゴリズムも発見しました。

Baruch SchieberとUzi Vishkin  (1988) は、Harel と Tarjan のデータ構造を簡略化し、同じ漸近的前処理とクエリ時間境界を持つ実装可能な構造を生み出しました。彼らの簡略化は、2 種類の特別なツリーでは最小共通祖先を簡単に特定できるという原則に基づいています。ツリーがパスである場合、最小共通祖先は、クエリされた 2 つのノードのレベルの最小値から計算できます。一方、ツリーが完全なバイナリ ツリーである場合は、最小共通祖先がインデックスに対する単純なバイナリ演算に簡略化されるようにノードにインデックスを付けることができます。Schieber と Vishkin の構造は、任意のツリーをパスのコレクションに分解し、パス間の接続がバイナリ ツリーの構造を持つようにし、これら 2 つのより単純なインデックス作成手法の両方を組み合わせています。

Omer Berkman と Uzi Vishkin (1993) は、最小共通祖先クエリに回答するまったく新しい方法を発見し、これもまた一定のクエリ時間で線形の前処理時間を実現しました。彼らの方法では、入力ツリーから形成されたグラフのすべてのエッジを 2 倍にしてオイラー ツアーを形成し、このツアーを使用して、ツアーが訪れる順序でノードのレベル番号のシーケンスを書きます。次に、最小共通祖先クエリを、この番号シーケンスのサブ間隔内で発生する最小値を検索するクエリに変換できます。次に、彼らはこの範囲最小クエリ問題 (RMQ) を 2 つの手法を組み合わせて処理します。1 つは、サイズが 2 の累乗である大きな間隔に対する回答を事前計算することに基づく手法で、もう 1 つは、小さな間隔のクエリに対するテーブル検索に基づいています。この方法は、後に Michael Bender とMartin Farach-Colton  (2000) によって簡略化された形式で発表されました。以前に Gabow、Bentley、Tarjan (1984) によって観察されたように、範囲最小問題は、デカルト木の手法を使用して、最小共通祖先問題に変換することができます。

Alstrup et al. (2004) と Fischer & Heun (2006) によってさらに簡略化が行われました。

SleatorとTarjan  (1983) は、この問題の動的 LCA バリアントを提案しました。このバリアントでは、データ構造は、ツリーを変更する操作 (つまり、エッジの追加と削除によるツリーの再配置) が混在する LCA クエリを処理できるように準備する必要があります。このバリアントは、すべての変更とクエリに対して、ツリーの合計サイズで時間内に解決できます。これは、サイズによるパーティション分割を伴う動的ツリー データ構造を使用してフォレストを維持することで実現されます。これにより、各ツリーの重軽分解が維持され、ツリーのサイズの対数時間で LCA クエリを実行できます。 ${\displaystyle O(\log N)}$

前述のように、LCA は RMQ に縮小できます。結果として生じる RMQ 問題に対する効率的な解決法は、数値シーケンスをブロックに分割することから始まります。ブロック間およびブロック内のクエリには、2 つの異なる手法が使用されます。

LCA から RMQ への縮約は、ツリーをたどることから始まります。訪問した各ノードについて、ラベルと深度を順番に記録します。ノードxとy がこのシーケンスのiとj の位置にそれぞれ出現するとします。すると、 xとyの LCA はRMQ( i , j )の位置で見つかります。ここで、RMQ は深度値に対して実行されます。

一般的な RMQ には一定の時間と線形空間のソリューションが存在しますが、LCA の特性を利用した簡略化されたソリューションを適用することもできます。この簡略化されたソリューションは、LCA から簡略化された RMQ にのみ使用できます。

上記のソリューションと同様に、シーケンスを各ブロックに分割します。各ブロックのサイズは です。 ${\displaystyle B_{i}}$${\displaystyle B_{i}}$${\displaystyle b={1 \over 2}\log n}$

シーケンスをブロックに分割することで、 次の 2 つの異なるケースを解決してクエリを解決できます。 ${\displaystyle RMQ(i,j)}$

ケース 1 のクエリに回答するために、クエリ時間を短縮するために 3 つの変数グループが事前に計算されています。 ${\displaystyle RMQ(i,j)}$

まず、各ブロック内の最小のインデックスを持つ最小の要素が事前に計算され、 として表されます。 のセットはスペースを占有します。 ${\displaystyle B_{i}}$${\displaystyle y_{i}}$${\displaystyle y_{i}}$${\displaystyle O(n/b)}$

次に、 のセットが与えられた場合、このセットの RMQ クエリは、定数時間と線形空間 のソリューションを使用して事前計算されます。ブロックがあるため、そのソリューションのルックアップ テーブルはスペースを占有します。、=スペースであるためです。したがって、定数時間と線形空間のソリューションを使用してこれらのブロックに対して事前計算された RMQ クエリは、スペースのみを占有します。 ${\displaystyle y_{i}}$${\displaystyle n/b}$${\displaystyle O({n \over b}\log {n \over b})}$${\displaystyle b={1 \over 2}\log n}$${\displaystyle O({n \over b}\log {n \over b})}$${\displaystyle O(n)}$${\displaystyle O(n)}$

3 番目に、各ブロック で、となるのインデックスをとします。から までのすべてについて、ブロック は2 つの区間とに分割されます。次に、各ブロック と の区間に対する最小のインデックスを持つ最小の要素が事前に計算されます。このような最小の要素は、 の区間ではプレフィックス min と呼ばれ、 の区間ではサフィックス minと呼ばれます。の各反復では、プレフィックス min とサフィックス min のペアが計算されます。したがって、ブロック内のプレフィックス min とサフィックス min の合計数は です。ブロック があるため、プレフィックス min 配列とサフィックス min 配列はすべて、合計で個のスペースを取ります。 ${\displaystyle B_{i}}$${\displaystyle k_{i}}$${\displaystyle B_{i}}$${\displaystyle 0\leq ki<b}$${\displaystyle k_{i}}$${\displaystyle 0}$${\displaystyle b}$${\displaystyle B_{i}}$${\displaystyle [0,k_{i})}$${\displaystyle [k_{i},b)}$${\displaystyle [0,k_{i})}$${\displaystyle [k_{i},b)}$${\displaystyle B_{i}}$${\displaystyle [0,k_{i})}$${\displaystyle [k_{i},b)}$${\displaystyle k_{i}}$${\displaystyle B_{i}}$${\displaystyle 2b}$${\displaystyle n/b}$${\displaystyle O(2b\cdot {n \over b})}$${\displaystyle O(n)}$

合計すると、上記の 3 つの事前計算済み変数のグループすべてを格納するためのスペースが必要になります。 ${\displaystyle O(n)}$

したがって、ケース 1 のクエリに回答するには、次の 3 つの質問のうち最低限の質問に答えるだけです。 ${\displaystyle RMQ(i,j)}$

をインデックス の要素を含むブロックとし、インデックス については とします。 ${\displaystyle B_{i}}$${\displaystyle i}$${\displaystyle B_{j}}$${\displaystyle j}$

1. ブロック内の接尾辞min${\displaystyle [i\mod b,b)}$${\displaystyle B_{i}}$
2. 定数時間と線形空間のソリューションを使用してブロックからsのサブセットに対するRMQクエリに回答する${\displaystyle y}$${\displaystyle \{B_{i+1}...B_{j-1}\}}$
3. ブロック内の接頭辞min${\displaystyle [0,j\mod b)}$${\displaystyle B_{j}}$

3 つの質問はすべて一定時間で回答できます。したがって、ケース 1 は線形空間と一定時間で回答できます。

LCA から簡約された RMQ のシーケンスには、通常の RMQ にはない 1 つのプロパティがあります。次の要素は常に現在の要素から +1 または -1 です。例:

したがって、各ブロックは、0 が現在の深度 -1 を表し、1 が現在の深度 +1 を表すビット文字列としてエンコードできます。この変換により、ブロックはサイズ のビット文字列に変換されます。サイズ のビット文字列には、可能なビット文字列があります。 なので、 です。 ${\displaystyle B_{i}}$${\displaystyle B_{i}}$${\displaystyle b-1}$${\displaystyle b-1}$${\displaystyle 2^{b-1}}$${\displaystyle b={1 \over 2}\log n}$${\displaystyle 2^{b-1}\leq 2^{b}=2^{{1 \over 2}\log n}=n^{1 \over 2}={\sqrt {n}}}$

したがって、は常に のサイズを持つ可能なビット文字列の 1 つです。 ${\displaystyle B_{i}}$${\displaystyle {\sqrt {n}}}$${\displaystyle b-1}$

次に、各可能なビット文字列に対して、単純な二次空間定数時間ソリューションを適用します。これにより、 のスペースが占有されます。 ${\displaystyle {\sqrt {n}}\cdot b^{2}}$${\displaystyle O({\sqrt {n}}\cdot (\log n)^{2})\leq O({\sqrt {n}}\cdot {\sqrt {n}})=O(n)}$

したがって、ケース 2 のクエリに答えるには、対応するブロック (ビット文字列) を見つけて、そのビット文字列のテーブル検索を実行するだけです。したがって、ケース 2 は、線形空間を使用して一定の検索時間で解決できます。 ${\displaystyle RMQ(i,j)}$

もともとツリーのコンテキストで研究されていた最小共通祖先の概念は、2 つの定義のいずれかを使用して、有向非巡回グラフ (DAG) に対して定義できます。どちらの定義でも、DAG のエッジは親から子を指していると想定されます。

• G = ( V , E )が与えられたとき、Aït-Kaci et al. (1989) は、x ≤ yである場合に限りx がyから到達可能であるようなposet ( V , ≤)を定義します。 xとyの最低共通祖先は、共通祖先集合{ z ∈ V | x ≤ zかつy ≤ z }の ≤ の下の最小要素です。
• Benderら(2005)は、 xとyの最低共通祖先が、xとyの共通祖先の集合によって誘導されるGのサブグラフ内の出次数ゼロのノードであるという同等の定義を与えました。

ツリーでは、最下位の共通祖先は一意です。n 個のノードを持つ DAG では、各ノード ペアに最大n -2個の LCA が存在する可能性があります (Bender ら、2005 年)。一方、任意に接続された DAG では、ノード ペアの LCA の存在は保証されません。

最小共通祖先を見つけるためのブルートフォースアルゴリズムは、Aït-Kaci ら (1989) によって提供されています。xとyのすべての祖先を見つけ、2 つのセットの共通部分の最大要素を返します。ツリー上の LCA アルゴリズムに類似した、グラフを前処理して定数時間の LCA クエリを可能にする、より優れたアルゴリズムが存在します。LCA の存在の問題は、 Kowaluk と Lingas (2005) によるO(| V || E |)アルゴリズムによって、スパース DAG に対して最適に解決できます。

Dash et al. (2013) は、有向非巡回グラフの前処理を行い、ルート付き DAGの代表的な最小共通祖先を定数時間で計算するための統一フレームワークを提示しています。このフレームワークは、スパースグラフの前処理時間をほぼ線形に達成でき、一般に公開されています。^[1]

継承階層内のクラスの最下位共通祖先を計算する問題は、オブジェクト指向プログラミングシステムの実装で発生します(Aït-Kaci 他 1989)。LCA 問題は、分散コンピューティングで見られる複雑なシステムのモデルにも応用されています(Bender 他 2005)。

• レベルの祖先問題
• セミラティス

• Aho, Alfred ; Hopcroft, John ; Ullman, Jeffrey (1973)、「ツリーにおける最下位共通祖先の検出について」、Proc. 5th ACM Symp. Theory of Computing (STOC)、pp. 253–265、doi : 10.1145/800125.804056、S2CID  17705738。
• Aït-Kaci, H.; Boyer, R.; Lincoln, P.; Nasr, R. (1989)、「格子演算の効率的な実装」(PDF)、ACM Transactions on Programming Languages and Systems、11 (1): 115–146、CiteSeerX  10.1.1.106.4911、doi :10.1145/59287.59293、S2CID  2931984。
• Alstrup, Stephen; Gavoille, Cyril; Kaplan, Haim; Rauhe, Theis (2004)、「最も近い共通祖先: 分散環境の調査と新しいアルゴリズム」、Theory of Computing Systems、37 (3): 441–456、CiteSeerX  10.1.1.76.5973、doi :10.1007/s00224-004-1155-5、S2CID  944712​​7予備版は SPAA 2002 に掲載されました。
• Bender, Michael A.; Farach-Colton, Martin (2000)、「LCA 問題の再考」、第 4 回ラテンアメリカ理論情報学シンポジウム議事録、コンピュータサイエンス講義ノート、第 1776 巻、Springer-Verlag、pp. 88–94、doi :10.1007/10719839_9、ISBN 978-3-540-67306-4。
• Bender, Michael A.; Farach-Colton, Martín ; Pemmasani, Giridhar; Skiena, Steven ; Sumazin, Pavel (2005)、「ツリーと有向非巡回グラフにおける最小共通祖先」(PDF)、Journal of Algorithms、57 (2): 75–94、doi :10.1016/j.jalgor.2005.08.001。
• Berkman, Omer; Vishkin, Uzi (1993)、「再帰的スターツリー並列データ構造」、SIAM Journal on Computing、22 (2): 221–242、doi :10.1137/0222017、2017年9月23日時点のオリジナルよりアーカイブ。
• Dash, Santanu Kumar; Scholz, Sven-Bodo; Herhut, Stephan; Christianson, Bruce (2013)、「有向非巡回グラフにおける代表的な最低共通祖先を計算するためのスケーラブルなアプローチ」(PDF)、理論計算機科学、513 : 25–37、doi : 10.1016/j.tcs.2013.09.030、hdl :2299/12152
• Djidjev, Hristo N.; Pantziou, Grammati E.; Zaroliagis, Christos D. (1991)、「平面グラフにおける最短経路と距離の計算」、Automata、言語、プログラミング: 第 18 回国際コロキウム、スペイン、マドリード、1991 年 7 月 8 ～ 12 日、議事録、コンピュータ サイエンスの講義ノート、vol. 510、Springer、pp. 327 ～ 338、doi :10.1007/3-540-54233-7_145、ISBN 978-3-540-54233-9。
• フィッシャー、ヨハネス、ヒューン、フォルカー (2006)、「RMQ 問題の理論的および実践的改善と LCA および LCE への応用」、第 17 回組み合わせパターン マッチングに関する年次シンポジウムの議事録、コンピュータ サイエンスの講義ノート、第 4009 巻、Springer-Verlag、pp. 36–48、CiteSeerX  10.1.1.64.5439、doi :10.1007/11780441_5、ISBN 978-3-540-35455-0。
• Gabow, Harold N. ; Bentley, Jon Louis ; Tarjan, Robert E. (1984)、「Scaling and related Techniques for geometry issues」、STOC '84: Proc. 16th ACM Symposium on Theory of Computing、ニューヨーク、NY、USA: ACM、pp. 135–143、doi :10.1145/800057.808675、ISBN 978-0897911337、S2CID  17752833。
• Harel, Dov; Tarjan, Robert E. (1984)、「最も近い共通祖先を見つけるための高速アルゴリズム」、SIAM Journal on Computing、13 (2): 338–355、doi :10.1137/0213024。
• Kowaluk, Miroslaw; Lingas, Andrzej (2005)、「LCA クエリー in 有向非巡回グラフ」、Caires, Luís; Italiano, Giuseppe F .; Monteiro, Luís; Palamidessi, Catuscia ; Yung, Moti (編)、Automata, Languages and Programming、第 32 回国際コロキウム、ICALP 2005、ポルトガル、リスボン、2005 年 7 月 11 ～ 15 日、議事録、Lecture Notes in Computer Science、vol. 3580、Springer、pp. 241 ～ 248、CiteSeerX  10.1.1.460.6923、doi :10.1007/11523468_20、ISBN 978-3-540-27580-0
• Schieber, Baruch ; Vishkin, Uzi (1988)、「最小共通祖先の発見について: 簡略化と並列化」、SIAM Journal on Computing、17 (6): 1253–1262、doi :10.1137/0217079。
• Sleator, DD ; Tarjan, RE (1983)、「動的ツリーのデータ構造」(PDF)、第 13 回 ACM コンピューティング理論シンポジウム議事録 - STOC '81、pp. 114–122、doi :10.1145/800076.802464、S2CID  15402750

• 二分探索木の最小共通祖先、Kamal Rawat 著
• 木に対するベンダーとファラッハ・コルトンのアルゴリズムの Python 実装 ( David Eppstein著)
• 任意の有向非巡回グラフの Python 実装
• 2003 年の MIT データ構造コースの LCA に関する講義ノート。Erik Demaineによるコースで、Loizos Michael と Christos Kapoutsis がノートを執筆しました。2007 年に同じコースで提供されたノートで、Alison Cichowlas が執筆しました。
• C 言語の二分木の最小共通祖先。バランスの取れた二分木にのみ機能する Schieber-Vishkin 手法の簡略版。
• ドナルド・クヌースがシーバー・ヴィシュキン法を説明するビデオ
• Topcoder の範囲最小クエリと最小共通祖先に関する記事
• Edward Kmett による Haskell の lca パッケージのドキュメント。skew-binary ランダム アクセス リスト アルゴリズムが含まれています。同じパッケージのオンライン LCA スライドの純粋に機能的なデータ構造。