木の収縮

コンピュータサイエンスにおいて、並列ツリー収縮は、多数のツリー問題を並列に解決するための広く適用可能な手法であり、多数の並列グラフアルゴリズムの設計のためのアルゴリズム設計手法として使用されています。並列ツリー収縮は、Gary L. MillerとJohn H. Reifによって導入され、^{[1] 、その後、X. HeとY. Yesha、 [2]、} Hillel Gazit、Gary L. Miller、Shang-Hua Teng ^[3]など多くの研究者 によって効率性を向上させるために改良されてきました。^[4]

ツリー収縮は、式の評価、最小共通祖先の発見、ツリー同型性、グラフ同型性、最大部分ツリー同型性、共通部分式の除去、グラフの3連結成分の計算、平面グラフの明示的な平面埋め込みの発見など、多くの効率的な並列アルゴリズムの設計に使用されてきた^[5]。

並列ツリー収縮に関する研究と作業に基づいて、このトピックの効率性や単純さを改善することを目的としたさまざまなアルゴリズムが提案されています。この記事では、Miller と Reif によるアルゴリズムのバリエーションである特定のソリューションとそのアプリケーションに焦点を当てます。

過去数十年にわたり、さまざまな問題に対する新しい並列アルゴリズムを導出する重要な研究が行われてきました。その目的は、高度に並列化された（多重対数深度）、作業効率の高い（逐次実行時間が線形）アルゴリズムを設計することです。^[1]いくつかの問題では、ツリーが適切な解決策であることが判明しています。これらの問題に対処するには、問題をツリーとして表現するだけで、より多くの並列性を実現できる場合があります。

木の一般的な定義を考えると、ルート頂点と、ルートに付随する複数の子頂点があります。^[6]そして、子頂点自体が子を持つ場合があり、以下同様に続きます。最終的に、パスは木の末端として定義される葉に至ります。次に、この一般的な木に基づいて、さらにいくつかの特殊なケースを考え出すことができます。(1) バランスのとれた二分木、(2)連結リスト。^[7]バランスのとれた二分木は、葉を除いて各頂点に対してちょうど 2 つの枝を持ちます。これにより、木の深さに O(log n) の境界が与えられます。^{[8]連結リストも、すべての頂点が 1 つの子しか持たない木です。}対称性の破れを使用して O(log n) の深さを実現することもできます。^[9]

一般的なツリーの場合、不均衡であるかリスト状であるか、あるいはその両方の混合であるかに関係なく、境界を O(log n) に維持したいと考えています。この問題に対処するために、オイラー ツアー手法^[10]を使用してプレフィックス合計と呼ばれるアルゴリズムを使用します。オイラー ツアー手法を使用すると、ツリーをフラット スタイルで表現できるため、プレフィックス合計をこの形式の任意のツリーに適用できます。実際、プレフィックス合計は、グループを形成する任意の値のセットとバイナリ演算で使用できます。バイナリ演算は結合的である必要があり、すべての値には逆があり、単位値が存在します。

少し考えれば、プレフィックス合計が不可能または非効率的になる例外的なケースがいくつか見つかります。値のセットに 0 が含まれる場合の乗算の例を考えてみましょう。または、逆関数を持たない max() と min() などのよく使用される演算があります。目標は、予想される O(n) の作業と O(log n) の深さで、すべてのツリーで機能するアルゴリズムを探すことです。次のセクションでは、この目標を達成するための Rake/Compress アルゴリズムを提案します。^[11]

アルゴリズム自体に入る前に、まず後で使用するいくつかの用語を見てみましょう。

• レーキ^[12] – レーキステップは、バイナリノードのすべての左葉を親に結合します。結合とは、実行したい操作を実現する機能プロセスを経ることを意味します。レーキの例を図1に示します。
• 圧縮^[12] – 圧縮ステップは、実際にはいくつかのイベントのシーケンスです。(1) 単項ノードの独立したセットを検索します。(ここでの独立性は、2つが隣接していないこと、つまり親と子の関係がないことを意味します) (2) 独立セット内の各ノードをその子と結合します(独立セットは一意ではないことに注意してください)。圧縮の例を図2に示します。

そして、ツリー収縮を使用して実際の問題を解決するために、アルゴリズムは次の構造を持ちます。

ツリーが単項ノードになるまで繰り返します
{
    レーキ;
    圧縮する;
}

とりあえず、すべてのノードが3つ以下の子を持つ、つまりバイナリであると仮定しよう。一般的に言えば、次数が制限されている限り、制限は維持される。^[13]しかし、ここでは簡単のためにバイナリの場合を分析する。上記の2つの「退化した」ケースでは、rakeはバランスのとれたバイナリツリーを扱うのに最適なツールであり、compressはリンクリストに最適です。しかし、任意のツリーではこれらの操作の組み合わせが必要になります。この組み合わせにより、次の定理を主張します。

• 定理: O(log n) 回の期待されるレーキおよび圧縮ステップの後、ツリーは単一のノードに縮小されます。

ここで、ツリー収縮アルゴリズムを次のように言い換えます。

• 入力: rを根とする二分木
• 出力: 単一ノード
• 操作: 一連の縮小ステップ。各ステップは、レーキ操作と圧縮操作 (順序は任意) で構成されます。レーキ操作は、すべてのリーフ ノードを並列に削除します。圧縮操作は、独立した単項ノードのセットを検索し、選択したノードをスプライスします。

定理に近づくために、まず二分木の特性を見てみましょう。二分木 T が与えられた場合、T のノードを 3 つのグループに分割できます。⁠ ⁠${\displaystyle T_{0}}$にはすべてのリーフ ノードが含まれ、⁠ ⁠${\displaystyle T_{1}}$には 1 つの子を持つすべてのノードが含まれ、⁠ ⁠${\displaystyle T_{2}}$には 2 つの子を持つすべてのノードが含まれます。次のことが簡単にわかります。ここで、次のことを提案します。 ${\displaystyle V(T)=T_{0}\cup T_{1}\cup T_{2}}$

• 請求：${\displaystyle |T_{0}|=|T_{2}|+1}$

この主張は、ノードの数に関する強い帰納法によって証明できます。n=1 の基本ケースが自明に成り立つことは容易にわかります。さらに、この主張は最大で n ノードを持つ任意のツリーにも成り立つと仮定します。すると、r をルートとする n+1 ノードを持つツリーが与えられた場合、次の 2 つのケースが考えられます。

1. r にサブツリーが 1 つしかない場合は、r のサブツリーについて考えます。サブツリーには、ツリー全体と同じ数のバイナリ ノードとリーフ ノードがあることがわかっています。ルートが単項ノードであるため、これは当てはまります。また、前の仮定に基づくと、単項ノードは⁠ ⁠${\displaystyle T_{0}}$または⁠ ⁠${\displaystyle T_{2}}$のどちらも変更しません。
2. r に 2 つのサブツリーがある場合、それぞれ左のサブツリーのリーフ ノードとバイナリ ノードを⁠ ⁠ と定義します。同様に、右のサブツリーについても同じ${\displaystyle T_{0}^{L},T_{2}^{L}}$⁠ ⁠ ⁠ を${\displaystyle T_{0}^{R},T_{2}^{R}}$定義します。前述のことから、およびが存在します。また、T にはリーフ ノードとバイナリ ノードがあることもわかっています。したがって、次の式を導出できます。${\displaystyle |T_{0}^{L}|=|T_{2}^{L}|+1}$${\displaystyle |T_{0}^{R}|=|T_{2}^{R}|+1}$${\displaystyle |T_{0}^{L}|+|T_{0}^{R}|}$${\displaystyle |T_{2}^{L}|+|T_{2}^{R}|+1}$

${\displaystyle |T_{0}^{L}|+|T_{0}^{R}|=|T_{2}^{L}|+1+|T_{2}^{R}|+1=(|T_{2}^{L}|+|T_{2}^{R}|+1)+1}$

それは主張を証明するものです。

主張に続いて、補題を証明し、定理を導きます。

• 補題: 縮小ステップ後のノードの数は、期待値の定数倍減少します。

縮小前のノード数を m、縮小後のノード数を m' と仮定します。定義により、rake 操作ではすべての⁠ ⁠ が${\displaystyle T_{0}}$削除され、compress 操作では少なくとも⁠ ⁠${\displaystyle T_{1}}$の 1/4 が削除されます。すべての⁠ ⁠ が${\displaystyle T_{2}}$残ります。したがって、次のことがわかります。

${\displaystyle E[m']\leq |T_{2}|+{\tfrac {3}{4}}*|T_{1}|\leq {\tfrac {3}{4}}+{\tfrac {3}{4}}*|T_{1}|+{\tfrac {3}{2}}*|T_{2}|={\tfrac {3}{4}}(1+|T_{1}|+2*|T_{2}|)={\tfrac {3}{4}}(|T_{0}|+|T_{1}|+|T_{2}|)={\tfrac {3}{4}}m}$

最後に、この補題に基づいて、各反復でノードが定数倍削減されると、⁠ ⁠${\displaystyle O(\log n)}$後には1つのノードだけが残ると結論付けることができます。^[14]

バイナリツリー（この問題はバイナリ式ツリーとも呼ばれる）として与えられた式を評価するには、 ^[15]次のことを考慮します。算術式は、葉が何らかのドメインからの値を持ち、各内部頂点が2つの子と{+、x、%}からのラベルを持つツリーです。さらに、これらのバイナリ演算は定数時間で実行できると仮定します。

ここでは、並列木収縮によって評価が行えることを示した。^[16]

• ステップ 1. すべてのノードに式を割り当てます。リーフの式は、単にリーフに含まれる値です。演算子には L + R、L − R、または L × R と記述します。ここで、L と R はそれぞれ左と右のサブツリーの式の値です。
• ステップ 2. 子が 0 個ある左 (右) の子が演算子にマージされる場合、L (R) を子の値に置き換えます。
• ステップ 3. ノードに 1 つの子がある場合、そのノードには 1 つの変数の関数である式があります。1 つの子を持つ左 (右) の子が演算子にマージされる場合、L (R) を式に置き換え、適切な場合は式内の変数を L (R) に変更します。

2 つの子を持つノードでは、式のオペランドは f(L) と g(R) です。ここで、f と g は線形関数です。1 つの子を持つノードでは、式は h(x) です。ここで、h は線形関数で、x は L または R のいずれかです。この不変条件は帰納法によって証明します。最初は、不変条件は明らかに満たされています。完全に評価されない式になるマージには 3 つの種類があります。(1) 1 子ノードが 2 子ノードにマージされます。(2) リーフが 2 子ノードにマージされます。(3) 1 子ノードが 1 子ノードにマージされます。3 種類のマージはすべて不変条件を変更しません。したがって、すべてのマージは線形関数を評価または合成するだけで、一定の時間がかかります^[17]

• 6.851: 高度なデータ構造 (Erik Demaine 教授)