Compressão eficiente de árvores não identificadas

20

Considere árvores binárias enraizadas e sem rótulo. Nós podemos comprimir essas árvores: sempre que houver indicações de sub-árvores e com (interpretação a igualdade estrutural), armazenamos (WLOG) e substituir todos os ponteiros para com ponteiros para . Veja a resposta de uli para um exemplo.T T = T = T T TTTT=T=TTT

Forneça um algoritmo que use uma árvore no sentido acima como entrada e calcule o número (mínimo) de nós que permanecem após a compactação. O algoritmo deve ser executado no tempo (no modelo de custo uniforme) com o número de nós na entrada.nO(nlogn)n

Essa foi uma pergunta do exame e não consegui encontrar uma boa solução, nem a vi.

Rafael
fonte
E qual é "o custo", "o tempo", a operação elementar aqui? O número de nós visitados? O número de arestas atravessadas? E como o tamanho da entrada é especificado?
219 uli
Essa compactação em árvore é uma instância de hash consing . Não tenho certeza se isso leva a um método de contagem genérico.
Gilles 'SO- stop be evil'
Esclareci o que é . Eu acho que "tempo" é suficientemente específico, no entanto. Em configurações não concorrentes, isso equivale a contar operações, que em termos de Landau equivalem a contar a operação elementar que ocorre com mais freqüência. n
Raphael
@ Rafael É claro que posso adivinhar qual deve ser a operação elementar pretendida e provavelmente escolherá o mesmo que todos os outros. Mas, e sei que sou pedante aqui, sempre que "limites de tempo" são dados, é importante declarar o que está sendo contado. São trocas, comparações, adições, acessos à memória, nós inspecionados, bordas atravessadas, o nome dele. É como omitir a unidade de medida em física. São ou 1010kg ? E suponho que os acessos à memória sejam quase sempre a operação mais frequente. 10ms
10131 uli
@uli Esses são os tipos de detalhes que o “modelo de custo uniforme” deve transmitir. É doloroso definir com precisão quais operações são elementares, mas em 99,99% dos casos (incluindo este) não há ambiguidade. As classes de complexidade fundamentalmente não possuem unidades, elas não medem o tempo necessário para executar uma instância, mas a maneira como esse tempo varia à medida que a entrada aumenta.
Gilles 'SO- stop be evil'

Respostas:

10

Sim, você pode executar essa compactação em , mas não é fácil :) Primeiro fazemos algumas observações e depois apresentamos o algoritmo. Assumimos que a árvore inicialmente não seja compactada - isso não é realmente necessário, mas facilita a análise.O(nlogn)

Primeiramente, caracterizamos indutivamente a "igualdade estrutural". Seja e T duas (sub) árvores. Se T e T ' são ambas as árvores nulas (sem vértices), elas são estruturalmente equivalentes. Se T e T ' não são árvores nulas, elas são estruturalmente equivalentes se seus filhos esquerdos forem estruturalmente equivalentes e seus filhos direitos forem estruturalmente equivalentes. 'Equivalência estrutural' é o ponto fixo mínimo sobre essas definições.TTTTTT

Por exemplo, quaisquer dois nós de folha são estruturalmente equivalentes, pois ambos têm as árvores nulas como seus filhos, que são estruturalmente equivalentes.

Como é bastante irritante dizer 'seus filhos esquerdos são estruturalmente equivalentes e também os filhos certos', freqüentemente diremos 'seus filhos são estruturalmente equivalentes' e pretendem o mesmo. Observe também que às vezes dizemos 'este vértice' quando queremos dizer 'a subárvore enraizada nesse vértice'.

A definição acima imediatamente nos dá uma dica de como realizar a compactação: se conhecermos a equivalência estrutural de todas as subárvores com profundidade no máximo , então podemos calcular facilmente a equivalência estrutural das subárvores com profundidade d + 1 . Precisamos fazer esse cálculo de maneira inteligente para evitar um tempo de execução de O ( n 2 ) .dd+1O(n2)

O algoritmo atribuirá identificadores a todos os vértices durante sua execução. Um identificador é um número no conjunto . Os identificadores são únicos e nunca mudam: portanto, assumimos que definimos alguma variável (global) como 1 no início do algoritmo e, toda vez que atribuímos um identificador a algum vértice, atribuímos o valor atual dessa variável ao vértice e incrementamos o valor dessa variável.{1,2,3,,n}

Primeiro, transformamos a árvore de entrada em (no máximo ) listas contendo vértices de igual profundidade, juntamente com um ponteiro para o pai. Isso é feito facilmente em O ( n ) tempo.nO(n)

Primeiro compactamos todas as folhas (podemos encontrá-las na lista com vértices de profundidade 0) em um único vértice. Atribuímos a esse vértice um identificador. A compactação de dois vértices é feita redirecionando o pai de um dos vértices para apontar para o outro vértice.

Fazemos duas observações: primeiro, qualquer vértice tem filhos de profundidade estritamente menor e, segundo, se tivermos realizado compressão em todos os vértices de profundidade menores que (e os tivermos identificado), então dois vértices de profundidade d são estruturalmente equivalentes e podem ser compactados se os identificadores de seus filhos coincidirem. Essa última observação segue o seguinte argumento: dois vértices são estruturalmente equivalentes se seus filhos são estruturalmente equivalentes e, após a compressão, isso significa que seus ponteiros estão apontando para os mesmos filhos, o que, por sua vez, significa que os identificadores de seus filhos são iguais.dd

Repetimos todas as listas com nós de igual profundidade, de pequena profundidade a grande profundidade. Para cada nível, criamos uma lista de pares inteiros, onde cada par corresponde aos identificadores dos filhos de algum vértice nesse nível. Temos que dois vértices nesse nível são estruturalmente equivalentes se seus pares inteiros correspondentes forem iguais. Usando a ordenação lexicográfica, podemos classificá-los e obter os conjuntos de pares inteiros iguais. Comprimimos esses conjuntos em vértices únicos, como acima, e os identificamos.

As observações acima provam que essa abordagem funciona e resulta na árvore compactada. O tempo total de execução é mais o tempo necessário para classificar as listas que criamos. Como o número total de pares inteiros que criamos é n , isso nos dá que o tempo total de execução é O ( n log n ) , conforme necessário. Contar quantos nós ainda restam no final do procedimento é trivial (basta ver quantos identificadores entregamos).O(n)nO(nlogn)

Alex ten Brink
fonte
Não li sua resposta em detalhes, mas acho que você mais ou menos reinventou o hash, com uma maneira estranha e específica de procurar por nós.
Gilles 'SO- stop being evil'
@Alex “filhos de degreegrau estritamente menor ” provavelmente deveria ser depth? E, apesar das árvores CS crescerem para baixo, acho "altura de uma árvore" menos confusa do que "profundidade de uma árvore".
Uli
Boa resposta. Eu sinto que deveria haver uma maneira de contornar a classificação. Meu segundo comentário na resposta do @Gilles também é válido aqui.
Raphael
@uli: sim, você está certo, eu o corrigi (não sei por que confundi essas duas palavras). Altura e profundidade são dois conceitos sutilmente diferentes, e eu precisava do último :) Pensei em seguir a "profundidade" convencional em vez de confundir todos trocando-os.
Alex10 Brink
4

A compactação de uma estrutura de dados não mutável para que não duplique nenhum subtermo estruturalmente igual é conhecida como hash consing . Essa é uma técnica importante no gerenciamento de memória na programação funcional. Hash consing é uma espécie de memorização sistemática para estruturas de dados.

Vamos hash-contras na árvore e contamos os nós após a hash. O hash que consiste em uma estrutura de dados do tamanho sempre pode ser feito em O ( nn operações; contar o número de nós no final é linear no número de nós.O(nlg(n))

Considerarei as árvores como tendo a seguinte estrutura (escrita aqui na sintaxe Haskell):

data Tree = Leaf
          | Node Tree Tree

Para cada construtor, precisamos manter um mapeamento de seus possíveis argumentos para o resultado da aplicação do construtor a esses argumentos. As folhas são triviais. Para os nós, que mantêm um mapa parcial finito , onde T é o conjunto de identificadores de árvores e N é o conjunto de identificadores de nós; T = N { } onde é o identificador da única folha. (Em termos concretos, um identificador é um ponteiro para um bloco de memória.)nodes:T×TNTNT=N{}

Podemos usar uma estrutura de dados em tempo logarítmico nodes, como uma árvore de pesquisa binária equilibrada. Abaixo, chamarei lookup nodesa operação que procura uma chave na nodesestrutura de dados e insert nodesa operação que adiciona um valor sob uma chave nova e retorna essa chave.

Agora, atravessamos a árvore e adicionamos os nós à medida que avançamos. Embora eu esteja escrevendo no pseudocódigo do tipo Haskell, tratarei nodescomo uma variável mutável global; apenas adicionaremos a ele, mas as inserções precisam ser encadeadas. A addfunção se repete em uma árvore, adicionando suas subárvores ao nodesmapa e retorna o identificador da raiz.

insert (p1,p2) =
add Leaf = $\ell$
add (Node t1 t2) =
    let p1 = add t1
    let p2 = add t2
    case lookup nodes (p1,p2) of
      Nothing -> insert nodes (p1,p2)
      Just p -> p

O número de insertchamadas, que também é o tamanho final da nodesestrutura de dados, é o número de nós após a compactação máxima. (Adicione um para a árvore vazia, se necessário.)

Gilles 'SO- parar de ser mau'
fonte
nO(nlg(n))nodes
Eu estava considerando apenas hash de subestruturas para números de maneira estruturada, de modo que o cálculo independente do hash para a mesma árvore sempre produzisse o mesmo resultado. Sua solução também é boa, desde que tenhamos estruturas de dados mutáveis ​​em nossas mãos. Eu acho que pode ser um pouco limpo, no entanto; a intercalação inserte adddeve ser explicitada e deve ser dada uma função que realmente resolva o problema.
Raphael
1
O consentimento do @Raphael Hash depende de uma estrutura finita de mapa sobre as tuplas de ponteiros / identificadores, você pode implementá-lo com tempo logarítmico para pesquisa e adição (por exemplo, com uma árvore de pesquisa binária equilibrada). Minha solução não requer mutabilidade; Eu faço nodesuma variável mutável por conveniência, mas você pode encadear isso por toda parte. Eu não vou dar o código completo, isso não é SO.
Gilles 'SO- stop being evil'
1
As estruturas de @Raphael Hashing , ao contrário de atribuir números arbitrários, é um pouco desonesto. No modelo de custo uniforme, você pode codificar qualquer coisa em um número inteiro grande e executar operações em tempo constante, o que não é realista. No mundo real, você pode usar hashes criptográficos para ter um mapeamento de fato de um para um, de conjuntos infinitos para um intervalo finito de números inteiros, mas eles são lentos. Se você usar uma soma de verificação sem criptografia como o hash, precisará pensar em colisões.
Gilles 'SO- stop being evil'
3

Aqui está outra idéia que visa (injetivamente) codificar a estrutura das árvores em números, em vez de apenas rotulá-las arbitrariamente. Para isso, usamos que a fatoração principal de qualquer número é única.

EN(l,r)lrN(E,E)

f(E)=0f(N(l,r))=2f(l)3f(r)

f

Essa última suposição é um exagero em máquinas reais; neste caso, alguém prefere usar algo semelhante à função de emparelhamento do Cantor em vez da exponenciação.

O(nlogn)O(nlogn)

Rafael
fonte
1

Como as imagens não são permitidas nos comentários:

insira a descrição da imagem aqui

canto superior esquerdo: uma árvore de entrada

canto superior direito: as subárvores enraizadas nos nós 5 e 7 também são isomórficas.

inferior esquerdo e direito: as árvores compactadas não são definidas exclusivamente.

7+5|T|6+|T|

uli
fonte
Este é realmente um exemplo da operação desejada, obrigado. Observe que seus exemplos finais são idênticos se você não distinguir entre referências originais e adicionadas.
Raphael
-1

Edit: Eu li a pergunta como T e T 'eram filhos do mesmo pai. Considerei a definição de compactação também recursiva, o que significa que você pode compactar duas subárvores compactadas anteriormente. Se essa não é a pergunta real, minha resposta pode não funcionar.

O(nlogn)T(n)=2T(n/2)+cn

def Comp(T):
   if T == null:
     return 0
   leftCount = Comp(T.left)
   rightCount = Comp(T.right)
   if leftCount == rightCount:
     if hasSameStructure(T.left, T.right):
       T.right = T.left
       return leftCount + 1
     else
       return leftCount + rightCount + 1    

Onde hasSameStructure()é uma função que compara duas subárvores já compactadas em tempo linear para ver se elas têm exatamente a mesma estrutura. Escrever uma função recursiva de tempo linear que atravessa cada uma e verifica se uma subárvore tem um filho esquerdo toda vez que a outra faz etc. não deve ser difícil.

nnr

T(n)=T(n1)+T(n2)+O(1) if nnr
2T(n/2)+O(n) otherwise
Joe
fonte
E se as subárvores não forem irmãos? Cuidar de ((T1, T1), (T2, T1)) T1 pode ser salvo duas vezes usando um ponteiro na terceira ocorrência.
219 uli
TT
As perguntas meramente afirmam que duas subtresses são identificadas como isomórficas. Nada é dito sobre eles terem o mesmo pai. Se uma subárvore T1 aparecer três vezes em uma árvore, como no meu exemplo anterior ((T1, T1), (T1, T2)), duas ocorrências poderão ser compactadas apontando para a terceira ou precisão.
213 uli