第6章 Union-Findグラフ理論による音声定義の同値類分割¶

本章では、数千規模の音声ファイルに対する「ペアごとの重複類似判定」の結果から、システム全体で一貫した「重複グループ（連結成分）」を構築し、冗長なBMS定義を単一の代表元へと縮約するための離散数学的アプローチを解説する。素朴な集合の併合処理が引き起こす \(O(N^2)\) の計算量爆発を排除し、経路圧縮とランクによる結合を備えた Union-Find が、実質的な定数時間 \(O(\alpha(N))\) を達成する過程を数学的に証明する。

6.1 同値関係と統合の数理的定式化¶

音声ファイルの重複を排除するという目的は、数学的には「集合を同値類に分割し、各同値類から代表元を1つ選ぶ」という統合の構築問題に帰着する。

定義 6.1 (音声集合と同値関係)¶

パースされたすべての音声定義のインデックスからなる有限集合を \(V = \{0, 1, \dots, N-1\}\) とする。第1章および第2章のアルゴリズムにより、2つの音声 \(u, v \in V\) の最大相関係数 \(r_{uv}\) が許容閾値 \(1 - \epsilon\) を超え、かつ無音トリミング後の有効長が一致したとき、\(u\) と \(v\) は類似しているとし、関係を結ぶ。

理想的な状態において、この関係 \(R\) は集合 \(V\) 上の同値関係 \(\sim\) として振る舞うと仮定する。すなわち、任意の \(u, v, w \in V\) について以下の3条件を満たす。

反射律: \(u \sim u\)
対称律: \(u \sim v \implies v \sim u\)
推移律: \(u \sim v \land v \sim w \implies u \sim w\)

定義 6.2 (同値類と商集合)¶

同値関係 \(\sim\) によって、ある要素 \(u \in V\) と同値な要素の集合を同値類と呼び、\([u]\) と表記する。

\[[u] = \{ v \in V \mid u \sim v \} \quad \cdots (6.1)\]

このとき、全集合 \(V\) は互いに素な同値類の和集合に完全に分割される。この同値類の集合を商集合と呼び、\(V / \sim\) と表記する。最適化とは、各同値類 \([u]\) を単一の代表元に射影する写像を構築することに等しい。

6.2 課題：推移律の破れと素朴なリスト結合の破綻 (Why)¶

6.2.1 閾値判定による推移律の破れとグラフ的解釈¶

現実の物理信号データにおいて、相関係数による閾値判定は厳密には推移律を満たさない。\(u \sim v\) かつ \(v \sim w\) であっても、誤差が蓄積して \(r_{uw} < 1 - \epsilon\) となる場合があるからだ。この推移律の破れを吸収しつつ一貫したグループを作るため、本システムでは要素を頂点 \(V\)、類似判定を満たしたペアを無向辺 \(E\) とするグラフ \(G = (V, E)\) を構築し、その連結成分を同値類とみなす近似アプローチを採用する。辺で結ばれた経路が存在する頂点は、すべて同じ同値類に属すると定義し直すのである。

6.2.2 配列ベースの素朴な併合処理の破綻¶

グラフ \(G\) の連結成分を求めるために、素朴に「各グループをリストで管理し、辺 \((u, v)\) が見つかるたびにリストを結合する」アルゴリズムを実装したとする。長さ \(k\) のリストと長さ \(l\) のリストを結合するには、一方の全要素の所属グループIDを書き換える必要があり、\(O(\min(k, l))\) の時間計算量がかかる。辺が次々と追加され、巨大なグループ同士が何度も結合される最悪ケースにおいて、この併合処理の合計時間計算量は \(O(N^2)\) に膨れ上がる。音声定義数 \(N = 30000\) のような大規模なBMSファイルにおいて、この \(O(N^2)\) の走査は数秒のフリーズ（パフォーマンス低下）を引き起こし、最適化パイプラインの重大なボトルネックとなる。

6.3 定理の提示とアッカーマン関数の逆関数 (Proof)¶

この計算量爆発を抑え込むため、各同値類を「木構造」として表現し、ルートノードを代表元とするUnion-Findを導入する。

定義 6.3 (経路圧縮とランクによる結合)¶

ランクによる結合: 各ノードに高さのバウンドを示す変数 \(\text{rank}\) を持たせる。二つの木を結合する際、必ず \(\text{rank}\) の小さい木のルートを、大きい木のルートの子として接続する。
経路圧縮: ある頂点 \(u\) の所属グループを探索する際、探索経路上にあるすべての頂点の親ポインタを、直接ルートノードへ繋ぎ直す。

Important

定理 6.1 (素集合データ構造の計算量とランクの最大値) 頂点数 \(N\) の Union-Find において、「ランクによる結合」のみを適用した場合、任意の頂点のランク \(r\) は \(r \le \log_2 N\) を満たす。さらに「経路圧縮」を併用した場合、\(M\) 回の操作（Find および Union）の合計時間計算量は \(O(M \alpha(N))\) となる。ここで \(\alpha(N)\) はアッカーマン関数 \(A(x, x)\) の逆関数である。

Note

証明

まず、ランクによる結合における木のサイズの性質を数学的帰納法で証明する。補題：「ランク \(r\) の木は、少なくとも \(2^r\) 個の頂点を含む。」

ベースケース（初期状態の各ノード）：ランク \(0\) であり、頂点数は \(1 = 2^0\)。よって成立。
帰納段階：ランク \(r\) の木が形成されるのは、ランク \(r-1\) の木 \(T_1\) と \(T_2\) が結合される瞬間に限られる（それ以外の場合はランクは変化しない）。帰納法の仮定より、\(T_1\) と \(T_2\) はそれぞれ少なくとも \(2^{r-1}\) 個の頂点を持つ。結合後の頂点数は \(|T_1| + |T_2| \ge 2^{r-1} + 2^{r-1} = 2^r\) となる。したがって、ランク \(r\) の木は少なくとも \(2^r\) 個の頂点を持つことが示された。

全頂点数は \(N\) であるため、最大ランク \(r_{\max}\) について \(2^{r_{\max}} \le N\) が成り立ち、両辺の対数を取ると \(r_{\max} \le \log_2 N\) となる。この時点で木の高さは対数オーダーに抑えられている。

さらに経路圧縮を併用すると、Find操作のたびに探索パス上の辺がすべてルート直下へと再配線される。Tarjan (1975) の解析によれば、この平坦化によって深さが再帰的に削られる結果、操作あたりの償却計算量はアッカーマン関数の逆関数 \(\alpha(N)\) に漸近する。\(\alpha(N)\) は \(N\) が観測可能な宇宙の原子数であっても \(4\) 以下となる極めて増加の遅い関数であるため、実質的に定数時間 \(O(1)\) とみなせる。\(\blacksquare\)

6.4 計算量削減の定量的評価と疑似コード¶

計算量の劇的な削減¶

前述の通り、素朴なリスト結合では最悪 \(O(N^2)\) の時間を要していた同値類の構築処理は、定理6.1の性質により \(O(N \alpha(N)) \approx O(N)\) のほぼ線形時間へと劇的に圧縮された。空間計算量も、親へのポインタとランクを保持する2つの1次元配列のみで済むため \(O(N)\) となり、きわめてメモリ効率が良い。

実装への射影：疑似コードとフラット配列最適化¶

Core/Optimization/UnionFind.cs は、C#においてオブジェクト指向のオーバーヘッド（Nodeクラスのインスタンス化など）を完全に排除し、フラットな1次元配列で実装されている。

// 【疑似コード】フラット配列による O(N α(N)) の Union-Find 実装
public class UnionFind {
    private readonly int[] _parent; // 親ノードのインデックス
    private readonly byte[] _rank;  // 木のランク

    public UnionFind(int size) {
        _parent = new int[size];
        _rank = new byte[size];
        for (int i = 0; i < size; i++) {
            _parent[i] = i; // 初期状態は自身がルート
            _rank[i] = 0;
        }
    }

    // 経路圧縮を伴う Find 操作 (償却 O(α(N)))
    public int Find(int i) {
        if (_parent[i] == i) return i;
        // 再帰的にルートを探し、その結果を直接親として上書きする（経路圧縮）
        return _parent[i] = Find(_parent[i]);
    }

    // ランクによる Union 操作 (償却 O(α(N)))
    public void Union(int i, int j) {
        int rootI = Find(i);
        int rootJ = Find(j);

        if (rootI == rootJ) return; // 既に同じ同値類

        // ランクの小さい木を大きい木の直下へ繋ぐ
        if (_rank[rootI] < _rank[rootJ]) {
            _parent[rootI] = rootJ;
        } else if (_rank[rootI] > _rank[rootJ]) {
            _parent[rootJ] = rootI;
        } else {
            _parent[rootI] = rootJ;
            _rank[rootJ]++; // ランクが等しい場合のみ、結合後のランクが増加する
        }
    }
}

6.5 境界条件と代表元の決定的選択¶

グラフの連結成分（同値類）が構築された後、各グループから「どの音声定義を代表元とするか」を決定しなければならない。本システムでは、BMSのパース順にインデックスが付与されるという性質を利用し、「同値類の中で最小のインデックスを持つ要素」を代表元として選択する境界条件（決定論的制約）を設けている。

\[\text{Representative}([u]) = \min \{ v \in V \mid \text{Find}(v) == \text{Find}(u) \} \quad \cdots (6.2)\]

これにより、同値類の構築結果が実行ごとにブレることのない完全な一意性が数学的に保証されている。

6.6 参考文献 (References)¶

Tarjan, R. E. (1975). "Efficiency of a Good But Not Linear Set Union Algorithm". Journal of the ACM, 22(2), 215-225.