부분적으로 정렬된 세트에 대해 최소 요소를 효율적으로 계산

Question

하위 집합 관계를 기반으로 부분 순서로 정렬하려는 집합 목록이 있습니다.

사실 완전한 순서는 필요하지 않고 최소한의 요소만 필요합니다.

제가 착각하지 않았다면, 각각의 최소 요소는 해당 그래프의 하나의 별도 구성 요소를 정의해야 하며 이 구성 요소는 준격자여야 합니다.

이 문제를 해결하는 가장 편리한 공간 및 시간 효율적인 방법은 무엇입니까?아마도 전체 그래프를 작성할 필요가 없는 방법이 있을까요?아마도 위에서 순진하게 설명한 것보다 더 나은 용어로 알려진 알고리즘이 있을까요?

위에서 요구되는 시간과 공간이 부족하다는 것을 알고 있지만 최적의 것으로 입증되었는지 여부에 관계없이 어떤 제안이라도 기꺼이 받아들일 것입니다...

배경:나는 현재 세트 사이의 모든 가장자리를 보유하고 일반화가 없는 노드를 찾는 전체 그래프 데이터베이스를 구축하고 있지만 이는 매우 복잡하고 느리며 많은 (디스크) 공간이 필요합니다.위에 언급된 목록에는 다음이 포함되어 있습니다. 대략 1억 세트.

Answer 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로 저장하는 데이터 구조로, 예를 들어 $ \ {1,3,6,7 \} $ 은 $ 1367 $ 에 해당하며 그에 따라 트리에 저장됩니다. 처음에는 $ m $ 이 비어 있습니다. 다음을 반복하십시오 : 다음 세트 $ s $ 목록에서 가져옵니다. $ M $ 에 설정되어 있는지 확인 $ S $ 의 하위 집합입니다. 그렇지 않은 경우 $ s $ $ m $ 에 삽입하십시오. 마지막으로 $ s $ 목록에서 삭제 (또는 목록의 다음 요소로 포인터를 진행하십시오). "Check ..."작업은 트리의 재귀 순회를 사용하여 상당히 효율적으로 수행 할 수 있습니다. 마지막으로 전체 목록을 거쳤 으면 $ 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 코드를 직접 제공할 수 있도록 해주세요. 제 생각에는 Pseudocode와 충분히 유사하며 아마도 많은 사람들에게 더 구체적일 것입니다.

다음은 논문에서 가져온 구현입니다.

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},{}.