部分的に順序付けされたセットに対する最小限の要素を効率的に計算する

Question

サブセット関係に基づいて半順序に並べ替えたいセットのリストがあります。

実際、完全な順序付けは必要なく、最小限の要素のみが必要です。

私が誤解していなければ、各最小要素はそれぞれのグラフの 1 つの別個のコンポーネントを定義する必要があり、このコンポーネントはミートセミ格子である必要があります。

この問題を解決する最も便利なスペースと時間効率の良い方法は何でしょうか?おそらく、グラフ全体を構築する必要がない方法はあるでしょうか?おそらく、私が上記で素朴に説明したものよりも適切な用語に基づいた既知のアルゴリズムが存在するでしょうか?

時間とスペースの要件が上記で指定されていないことは承知していますが、最適であることが証明されているかどうかにかかわらず、ご提案をいただければ幸いです...

背景:現在、セット間のすべてのエッジを保持するグラフデータベース全体を構築し、一般化されていないノードを探していますが、これは非常に複雑で遅く、多くの（ディスク）スペースを必要とします。上記のリストには以下が含まれます 約1億セット.

Answer 1

1つのアプローチは、サイズを大きくすることでセットを並べ替えることです。次に、次のようにします。リスト内の最初のセットを取り出し、それを出力し、そのすべてのスーパーセットをリストから削除します。これにより、すべての最小セットが出力されます。実行時間は $ o（nk）$ set比較と $ O（n \ log n）$ です。ソートの手順、 $ n $ は、持つセット数と $ k $ の数です。最小限の要素の。あるいは、それを別の方法で置くために、各セットに $ m $ 要素が含まれている場合、実行時間はおよそ $ Oになります（ n（k + \ log n）m）$ 基本手順。

サイズで並べ替えるのはなぜですか？これは最適化です。最小のセットは最小限であることが保証されています（リストに小さなカーディナリティが小さいので、そのサブセットはリストにあってもいません）、サイズは確かに最小限にしなければならないセットを識別するための便利なトリックです。

サイズ別ソートせずに、最悪の走行時間は $ O（n ^ 2）$ の設定比較（または $ O（n ^ 2 m）$ 基本手順です。 $ k \ ll n $ のときに悪化します。

---

それはそのアルゴリズムの最適化されたバージョンです。 $ m $ を、一連のセットをTRIEとして格納するデータ構造になります。たとえば、set $ \ {1,3,6,7 \} $ は、 $ 1367 $ に対応し、それに応じてトライに格納されます。最初は、 $ m $ が空です。次のように繰り返します。リストから次のset $ s $ を取ります。 $ m $ のセットが $ s $ のサブセットかどうかを確認してください。そうでない場合は、 $ s $ を $ m $ に挿入します。最後に、リストから $ s $ を削除します（またはリスト内の次の要素へのポインタを進みます）。 「チェック...」操作は、トライの再帰的なトラバースを使ってかなり効率的に実行できます。最後に、リスト全体を通過したら、 $ m $ 。

最適化されたアルゴリズムの最悪の走行時間は同じままです。実際には、ラッキーな場合は、ラッキング時間が大幅に改善される可能性があります（ $ o（nm）$ 基本的な手順では、ラッキーの場合は基本的な手順があります（カウントしないその上）。あなたが扱っているワークロードの種類については、どちらも試してみることができます。

Answer 2

で解決策を見つけました 本書、p.12.

証拠としてそこで言及されているアルゴリズムは、次の Python コードに変換されるはずです。

T = set([]);
for x in X:
    rem = set([]);
    spe = False;
    for a in T:
        rel = oracle(x,a);
        if rel == "x>a":
            spe = True;
            break;
        elif rel == "x<a":
            rem.add(a);
    if not spe:
        T -= rem;
        T.add(x);

私は期待しています break 実際の実行時に非常に重要なので、並べ替えるとよいでしょう。 X 早めの休憩を取るために事前に準備してください -- しかし、それについてはわかりません。

ここで私が見たもう一つの点は、 > 無反射であるはずなので、 x>x は成立しません。しかし、このコードではそうした方が良いでしょう。もし a==x, 、不必要にさらに見る代わりに壊れます。

アップデート： Python でさまざまな実装をテストできるようになりました。Python コードを直接挙げることをお許しください。これは擬似コードに十分似ていると思います。そしておそらく多くの人にとってより具体的なコードだと思います。

論文から引用した実装は次のとおりです。

def oracle(rep1,rep2):
    if generalizes(rep2,rep1):
        return ">";
    elif generalizes(rep1,rep2):
        return "<";
    return None;

def find_min_els_(repIDs,ID2rep):
    min_els = set([]);
    for x in repIDs:
        spec_of_x = set([]);
        x_is_spec = False;
        for min_el in min_els:
            relation = oracle(ID2rep[x],ID2rep[min_el]);
            if relation == ">":
                x_is_spec = True;
                break;
            elif relation == "<":
                spec_of_x.add(min_el);
        if not x_is_spec:
            min_els -= spec_of_x;
            min_els.add(x);
    return min_els;

これは遅すぎることが判明しました。複雑さから、部分順序の幅、つまり数値が大きい場合には非常に悪いことがすでにわかります。 m 最小限の要素の数は大きくなることが予想されます。

秘訣は、このアルゴリズムを独立したものにすることです。 m 現在の最小限の要素をすべて通過することを避けることによって。代わりに、結果セットの検索が高速であるという事実を利用できます (トライが登場するのはここだと思います)。

各 x について、すべての一般化を生成します。ここで、複雑さは x の数とそのサイズに依存しますが、最小要素の数にはあまり依存しません (O(n log n)だけですか？）。さらに良いことに、要素の初期リストから最小以外の要素を追加するのではなく削除する必要があるため、各 x にかかる時間は実行時間の経過とともに増加するのではなく減少しています。

それぞれのコードは次のとおりです。

def generalizations(spe_rep,gens):
    for el in spe_rep:
        gen_rep = spe_rep - set([el]);
        gen_str = string(gen_rep);
        if not gen_str in gens:
            gens.add(gen_str);
            yield gen_str;
            for x in generalizations(gen_rep,gens):
                yield x;

def find_min_els(repIDs,ID2rep):
    min_els = set(repIDs);
    for x in repIDs:
        for genID in generalizations(ID2rep[x],set([])):
            if genID in min_els:
                min_els.remove(x);
                break;
    return min_els;

これはジェネレータ関数を使用します generalizations() より一般化した計算を避けるため x 現在の最小要素ですでに見つかっている場合。これは私のデータではすでに非常に高速ですが、より一般的な一般化を最初に生成することによって (これにより高速になるかどうかをテストする必要があります)、特にすでに観察された要素で構成される一般化のみを生成することで改善できる可能性があります。現在の最小限の要素で。たとえば、私たちの場合、 x は {a,b,c}, 、しかし現在の最小要素はありません c その中で、次のサブセットを生成する必要はありません。 x 含まれている c, 、つまりのみ {a,b},{a},{b},{}.