Uma estrutura de dados para conjuntos de árvores.

10

As tentativas permitem o armazenamento eficiente de listas de elementos. Os prefixos são compartilhados e, portanto, economizam espaço.

Estou procurando uma maneira semelhante de armazenar árvores com eficiência. Eu gostaria de poder verificar a associação e adicionar elementos, sabendo se uma determinada árvore é uma subárvore de algumas árvores armazenadas ou se existe uma árvore armazenada sendo uma subárvore da árvore especificada também é desejável.

Normalmente, eu armazenava cerca de 500 árvores binárias desequilibradas de altura menor que 50.

EDITAR

Meu aplicativo é algum tipo de verificador de modelo usando algum tipo de memorização. Imagine que eu tenha um estado e as seguintes fórmulas: e com ser uma subfórmula complexo, e imaginar Primeiro eu quero saber se tem em . Verifico se mantém e, após um longo processo, obtenho que é esse o caso. Agora, quero saber se contém . Gostaria de lembrar o fato de que detém e de notar que para que eu possa derivar in quase instantaneamente.f = φ g = ( φ ip ) φ f s φ g s f g f g ssf=ϕg=(ϕψ)ϕfsϕgsfgfgs
Por outro lado, se eu provei que não se sustenta , então quero dizer que não se sustenta quase que instantaneamente.t f tgtft

Podemos construir uma ordem parcial em fórmulas e ter iff . Para cada estado , armazenamos dois conjuntos de fórmulas; armazena as fórmulas máximas que retêm e armazena as fórmulas mínimas que não retêm. Agora, dado um estado e uma fórmula , posso ver se , ou se , caso em que estou feito e sei diretamente se contém .g f s L ( s ) l ( s ) s g f L ( s ) , f g f l ( s ) , g f g sgfgfsL(s)l(s)sgfL(s),fgfl(s),gfgs

Atualmente, e são implementados como listas e isso claramente não é o ideal, pois preciso percorrer todas as fórmulas armazenadas individualmente. Se minhas fórmulas fossem sequências e se a ordem parcial fosse "é um prefixo de", um teste poderia ser muito mais rápido. Infelizmente, minhas fórmulas têm uma estrutura de árvore com base em , um operador modal e proposições atômicas.l ¬ , Ll¬,

Como @Raphael e @Jack apontam, eu poderia sequenciar as árvores, mas temo que isso não resolva o problema porque a ordem parcial em que estou interessado não corresponderia a "é um prefixo de".

Abdallah
fonte
Apenas uma idéia rápida: você tentou sequenciar as árvores (faça uma travessia em ordem, liste os nós visitados de acordo e adicione elementos especiais para os movimentos para cima e para baixo) e armazene-os em um trie? Obviamente, isso "apenas" permitiria verificações para as subárvores esquerdas, em certo sentido.
24511 Raphael
2
E se você simplesmente usasse uma serialização de árvores com a seguinte propriedade: é uma subárvore de se e somente se for uma subcadeia de ? Construir um é simples [se você encontrar pela primeira vez uma forma canônica de suas árvores]. Depois disso, sua pergunta é equivalente à correspondência de substring, que é um problema amplamente estudado em stringology. T T S ( T ) S ( T ) SSTTS(T)S(T)S
Jukka Suomela
11
Dê uma olhada na indexação de termos .
starblue
11
Outra idéia rápida seria armazenar todas as árvores t1, t2, .. em uma grande árvore T, lembrando para cada aresta o conjunto de árvores de que faz parte. Em seguida, para determinar se f é uma subárvore de uma das árvores armazenadas, você primeiro determina se f é uma subárvore em T e, se sim, intercepta todos os conjuntos de rótulos de borda dessa subárvore. A resposta é sim se o cruzamento não estiver vazio. (Você também pode combinar as duas etapas).
Martin B.

Respostas:

5

Você pode querer conferir g-try . Essa é essencialmente a estrutura de dados que você está procurando, mas projetada para uso com gráficos gerais em vez de apenas árvores. Como tal, não tenho certeza de que as tentativas g tenham boas garantias teóricas - acho que elas usam um algoritmo de canonização de grafos como uma sub-rotina - mas na prática elas parecem funcionar bem.

(Não tenha medo de que o artigo vinculado seja sobre "motivos de rede em redes biológicas": o g-trie é uma estrutura de dados abstrata perfeitamente boa para gráficos.)

Joshua Grochow
fonte
4

Uma forma especial disso é a persistência : consulte os documentos Tornando as estruturas de dados persistentes por Driscoll, Sarnak, Sleator e Tarjan e Localização de ponto planar usando árvores de pesquisa persistente por Sarnak & Tarjan, que armazenam famílias de árvores relacionadas.

Jack
fonte
11
Obrigado pelas referências. Não consigo acessar o Tornar estruturas de dados persistentes no momento, mas estou um pouco familiarizado com o conceito de persistência. No entanto, não vejo como posso usar a persistência para resolver meu problema. Na verdade, eu quero usar dicionários dicionários que mapeiam árvores como booleanas e a mesma árvore pode ser a chave para valores diferentes em dicionários diferentes.
Abdallah
11
Como não tinha certeza de qual era seu aplicativo, iniciei sua analogia com as tentativas, que armazenam seqüências compartilhando prefixos. Seu comentário de que "a mesma árvore pode ser a chave para valores diferentes em dicionários diferentes" também não parece se encaixar nas tentativas. Talvez você queira apenas uma coleção de assinaturas para uma árvore (e todas as suas subárvores) que possa procurar? (por exemplo, usando números de catalã para árvores binárias ou códigos Prufer para árvores marcadas.)
Jack
1

Isso soa um pouco como uma floresta (florestas desarticuladas ) ...

Ele amortiza o custo de inserção por meio de uma técnica chamada união por classificação e a operação de pesquisa usando a compactação de caminho . Sei que há também uma versão persistente dessa estrutura desenvolvida por Sylvain Conchon e Jean-Christophe Filliâtre, mas não tenho idéia se é a mesma que Jack menciona ...

Rehno Lindeque
fonte
0

Em "Estruturas de dados puramente funcionais" (1998), Chris Okasaki propõe tentativas de árvores binárias usando agregação de tipos (10.3.2).

Não sei se isso ajuda imediatamente; a solução fornecida pode não ser implementável diretamente.

Rafael
fonte
0

No jargão do programador: Se você criar as árvores a partir de subexpressões / árvores / DAGs comuns, você teria um bom modelo compacto. Gráficos acíclicos direcionados. Então um conjunto de árvores seria suficiente.

classe pública Tree {String operation; Árvore [] subárvores;

public int compareTo(Tree rhs) {
    if (rhs == null) return false;
    int cmp = operation.compareTo(rhs.operation);
    if (cmp == 0) {
        cmp = Arrays.compareTo(subtrees, rhs.subtrees);
    }
    return cmp;
}

...}

Mapa commonSubExpressions = new HashMap ();

Tree get (String expressionSyntax) {Árvore t = nova Árvore (); t.operação = ...; t.subtrees = ... chamada recursiva para obter subexpressões; Árvore t2 = commonSubExpressions.get (t); if (t2 == nulo) {t2 = t; commonSubExpressions.put (t2, t2); } retornar t2; }}

Joop Eggen
fonte