Computação eficiente de elementos mínimos em conjuntos parcialmente ordenados

Question

Tenho uma lista de conjuntos que gostaria de classificar em ordem parcial com base na relação de subconjunto.

Na verdade, não exijo a ordenação completa, apenas os elementos mínimos.

Se não me engano, cada elemento mínimo deve definir um componente separado do respectivo gráfico - e esse componente deve ser uma semi-reticulação.

Qual seria a maneira mais conveniente, eficiente em termos de espaço e tempo, para resolver esse problema?Talvez exista uma maneira que não exija a construção do gráfico inteiro?Talvez exista um algoritmo conhecido com uma terminologia melhor do que a que ingenuamente descrevi acima?

Estou ciente de que os requisitos de tempo e espaço estão subespecificados acima, mas ficaria feliz com quaisquer sugestões, sejam elas comprovadamente ideais ou não...

Fundo:Atualmente estou construindo um banco de dados gráfico inteiro que contém todas as arestas entre os conjuntos e depois procuro os nós que não possuem generalizações, mas isso é bastante complicado, lento e requer muito espaço (em disco).A lista mencionada acima contém cerca de 100 milhões de aparelhos.

Answer 1

Uma abordagem é classificar os conjuntos aumentando o tamanho e execute repetidamente o seguinte: Faça o primeiro conjunto na lista, envie-o e remova da lista todos os supersets. Isso irá produzir todos os conjuntos mínimos. O tempo de execução é $ O (NK) $ Definir comparações mais $ O (n \ log n) $ etapas para classificação, onde $ n $ é o número de conjuntos que você tem e $ k $ é o número de elementos mínimos. Ou, para colocá-lo de outra maneira, se cada conjunto contiver $ M $ elementos, o tempo de execução será aproximadamente $ O ( n (k + \ log n) m) $ etapas básicas.

Por que classificar por tamanho? Esta é uma otimização. O menor conjunto é garantido para ser mínimo (não há nenhuma cardinalidade menor na lista, então nenhum de seus subconjuntos pode ser na lista), então o tamanho é um truque útil para identificar um conjunto que deve certamente ser mínimo.

Sem classificação por tamanho, o tempo de execução do pior caso é provável que acabe como $ O (n ^ 2) $ Definir comparações (ou $ o (n ^ 2 m) $ etapas básicas), que é pior quando $ k \ ll n $ . .

---

Aqui está uma versão otimizada desse algoritmo. Deixe $ m $ ser uma estrutura de dados que armazena um conjunto de conjuntos, como um trie: por exemplo, o conjunto $ \ {1,3,6,7 \} $ corresponde à palavra $ 1367 $ e é armazenado no trie de acordo. Inicialmente, $ m $ está vazio. Repita o seguinte: Pegue o próximo conjunto $ S $ da lista; Verifique se qualquer conjunto na $ m $ é um subconjunto de $ S $ ; Se não, insira $ s $ em $ m $ ; Finalmente, exclua $ s $ na lista (ou avance seu ponteiro para o próximo elemento na lista). A operação "Check ..." pode ser realizada de forma justa eficiente usando uma travessia recursiva do TRIE. No final, uma vez que você passou por toda a lista, saia $ m $ .

O tempo de execução do pior caso do algoritmo otimizado permanece o mesmo. Na prática, o tempo de execução pode ser melhorado significativamente, talvez tão rápido quanto $ o (nm) $ passos básicos em alguns casos, se você tiver sorte (mas não contar nele). Você pode tentar ambos e ver que funciona melhor na prática sobre o tipo de carga de trabalho que você está lidando.

Answer 2

Eu encontrei uma solução em este artigo, p.12.

O algoritmo mencionado lá como prova deve ser traduzido para o seguinte código 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);

Eu espero que break ser crucial para o tempo de execução real, então pode ser uma boa ideia classificar X com antecedência para obter folgas antecipadas - mas não tenho certeza sobre isso.

Outro ponto que vejo aqui é que > é suposto ser irreflexivo, então x>x não segura.Mas para este código seria melhor se assim fosse.Se a==x, ele quebra em vez de procurar mais desnecessariamente.

ATUALIZAR: Agora consegui testar diferentes implementações em Python.Por favor, permita-me fornecer diretamente o código python, acho que é suficientemente semelhante ao pseudocódigo - e talvez mais concreto para muitas pessoas.

Aqui está a implementação retirada do artigo:

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;

Agora isso acabou sendo muito lento e já podemos dizer pela complexidade que é muito ruim se a largura da ordem parcial, esse é o número m de elementos mínimos deverá ser grande.

O truque é tornar esse algoritmo independente de m evitando passar por todos os elementos mínimos atuais.Em vez disso, podemos aproveitar o fato de que a pesquisa no conjunto de resultados é rápida (acho que é aí que a tentativa entra em ação).

Para cada x, geramos todas as generalizações.Agora a complexidade depende do número de x e do seu tamanho, mas não tanto do número de elementos mínimos (apenas O (n log n)?).Melhor ainda, como agora temos que remover elementos não mínimos da lista inicial de elementos em vez de adicioná-los, o tempo usado para cada x está diminuindo em vez de aumentar ao longo do tempo de execução.

Aqui está o respectivo código:

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;

Isso usa uma função geradora generalizations() para evitar computar mais generalizações de x uma vez que um já tenha sido encontrado nos elementos mínimos atuais.Isso já é bastante rápido com meus dados, mas talvez pudesse ser melhorado gerando primeiro generalizações que sejam mais gerais (precisa ser testado se isso o torna mais rápido) e, em particular, gerando apenas generalizações que consistem em elementos que já foram observados nos elementos mínimos atuais.Por exemplo se o nosso x é {a,b,c}, mas nenhum elemento mínimo atual possui c nele, não precisamos gerar nenhum subconjunto de x Isso contém c, ou sejaapenas {a,b},{a},{b},{}.