Compresión eficiente de árboles sin etiquetar

20

Considere árboles binarios enraizados sin etiquetar. Podemos comprimir dichos árboles: cada vez que hay punteros a subárboles y con (que interpretan como la igualdad estructural), almacenamos (sin pérdida de generalidad) y reemplazamos todos los punteros a con punteros a . Ver la respuesta de uli para un ejemplo.T T = T = T T TTTT=T=TTT

Proporcione un algoritmo que tome un árbol en el sentido anterior como entrada y calcule el número (mínimo) de nodos que quedan después de la compresión. El algoritmo debe ejecutarse en tiempo (en el modelo de costo uniforme) con el número de nodos en la entrada.O(nlogn)n

Esta ha sido una pregunta de examen y no he podido encontrar una buena solución, ni la he visto.

Rafael
fuente
¿Y cuál es "el costo", "el tiempo", la operación primaria aquí? ¿El número de nodos visitados? ¿El número de bordes atravesados? ¿Y cómo se especifica el tamaño de la entrada?
uli
Esta compresión de árbol es una instancia de hash consing . No estoy seguro si eso lleva a un método de conteo genérico.
Gilles 'SO- deja de ser malvado'
@uli aclaré qué es . Sin embargo, creo que el "tiempo" es lo suficientemente específico. En entornos no concurrentes, esto es equivalente a contar operaciones, lo cual es en términos de Landau equivalente a contar la operación primaria que ocurre con mayor frecuencia. n
Raphael
@Raphael Por supuesto, puedo adivinar cuál debería ser la operación primaria prevista y probablemente elegiré lo mismo que todos los demás. Pero, y sé que soy pedante aquí, cada vez que se dan "límites de tiempo" es importante indicar lo que se está contando. Se trata de intercambios, comparaciones, adiciones, accesos de memoria, nodos inspeccionados, bordes atravesados, lo que sea. Es como omitir la unidad de medida en física. ¿Es o ? Y supongo que los accesos a la memoria son casi siempre la operación más frecuente. 10kg10ms
uli
@uli Este es el tipo de detalles que se supone que transmite el "modelo de costo uniforme". Es doloroso definir con precisión qué operaciones son elementales, pero en el 99.99% de los casos (incluido este) no hay ambigüedad. Las clases de complejidad fundamentalmente no tienen unidades, no miden el tiempo que lleva realizar una instancia, pero la forma en que este tiempo varía a medida que aumenta la entrada.
Gilles 'SO- deja de ser malvado'

Respuestas:

10

Sí, puede realizar esta compresión en tiempo , pero no es fácil :) Primero hacemos algunas observaciones y luego presentamos el algoritmo. Asumimos que el árbol inicialmente no está comprimido; esto no es realmente necesario, pero facilita el análisis.O(nlogn)

En primer lugar, caracterizamos la "igualdad estructural" inductivamente. Deje que y sean dos (sub) árboles. Si y son ambos árboles nulos (sin vértices), son estructuralmente equivalentes. Si y son árboles nulos, entonces son estructuralmente equivalentes si sus hijos izquierdos son estructuralmente equivalentes y sus hijos derechos son estructuralmente equivalentes. La "equivalencia estructural" es el punto fijo mínimo sobre estas definiciones.TTTTTT

Por ejemplo, cualquiera de los dos nodos de hoja son estructuralmente equivalentes, ya que ambos tienen los árboles nulos como sus dos hijos, que son estructuralmente equivalentes.

Como es bastante molesto decir "sus hijos izquierdos son estructuralmente equivalentes y también lo son sus hijos correctos", a menudo diremos "sus hijos son estructuralmente equivalentes" y pretenden lo mismo. También tenga en cuenta que a veces decimos 'este vértice' cuando queremos decir 'el subárbol enraizado en este vértice'.

La definición anterior nos da una pista inmediata de cómo realizar la compresión: si conocemos la equivalencia estructural de todos los subárboles con profundidad como máximo , entonces podemos calcular fácilmente la equivalencia estructural de los subárboles con profundidad . Tenemos que hacer este cálculo de manera inteligente para evitar un tiempo de ejecución .dd+1O(n2)

El algoritmo asignará identificadores a cada vértice durante su ejecución. Un identificador es un número en el conjunto . Los identificadores son únicos y nunca cambian: por lo tanto, suponemos que establecemos alguna variable (global) en 1 al comienzo del algoritmo, y cada vez que asignamos un identificador a algún vértice, asignamos el valor actual de esa variable al vértice y al incremento El valor de esa variable.{1,2,3,,n}

Primero transformamos el árbol de entrada en (como máximo ) listas que contienen vértices de igual profundidad, junto con un puntero a su padre. Esto se hace fácilmente en tiempo.nO(n)

Primero comprimimos todas las hojas (podemos encontrar estas hojas en la lista con vértices de profundidad 0) en un solo vértice. Asignamos a este vértice un identificador. La compresión de dos vértices se realiza redirigiendo el padre de cualquier vértice para que apunte al otro vértice.

Hacemos dos observaciones: en primer lugar, cualquier vértice tiene hijos de profundidad estrictamente menor, y en segundo lugar, si hemos realizado compresión en todos los vértices de profundidad más pequeños que (y les hemos dado identificadores), entonces dos vértices de profundidad son estructuralmente equivalentes y se puede comprimir si los identificadores de sus hijos coinciden. Esta última observación se desprende del siguiente argumento: dos vértices son estructuralmente equivalentes si sus hijos son estructuralmente equivalentes, y después de la compresión, esto significa que sus punteros apuntan a los mismos hijos, lo que a su vez significa que los identificadores de sus hijos son iguales.dd

Realizamos iteraciones a través de todas las listas con nodos de igual profundidad desde profundidad pequeña hasta profundidad grande. Para cada nivel creamos una lista de pares enteros, donde cada par corresponde a los identificadores de los hijos de algún vértice en ese nivel. Tenemos que dos vértices en ese nivel son estructuralmente equivalentes si sus pares enteros correspondientes son iguales. Usando el orden lexicográfico, podemos ordenarlos y obtener los conjuntos de pares enteros que son iguales. Comprimimos estos conjuntos en vértices individuales como arriba y les damos identificadores.

Las observaciones anteriores demuestran que este enfoque funciona y da como resultado el árbol comprimido. El tiempo total de ejecución es más el tiempo necesario para ordenar las listas que creamos. Como el número total de pares enteros que creamos es , esto nos da que el tiempo total de ejecución es , según sea necesario. Contar cuántos nodos nos quedan al final del procedimiento es trivial (solo mira cuántos identificadores hemos entregado).O(n)nO(nlogn)

Alex ten Brink
fuente
No he leído su respuesta en detalle, pero creo que ha reinventado más o menos el hash consing, con una extraña forma específica de problema de buscar nodos.
Gilles 'SO- deja de ser malvado'
@Alex "niños de degreegrado estrictamente más pequeño " probablemente debería ser depth? Y a pesar de que los árboles CS crecen hacia abajo, encuentro "altura de un árbol" menos confuso que "profundidad de un árbol".
uli
Buena respuesta. Siento que debería haber una manera de sortear la clasificación. Mi segundo comentario sobre la respuesta de @Gilles también es válido aquí.
Raphael
@uli: sí, tienes razón, lo he corregido (no estoy seguro de por qué confundí esas dos palabras). Altura y profundidad son dos conceptos sutilmente diferentes, y necesitaba el último :) Pensé que me apegaría a la 'profundidad' convencional en lugar de confundir a todos intercambiándolos.
Alex ten Brink
4

La compresión de una estructura de datos no mutable para que no duplique ningún subterráneo estructuralmente igual se conoce como hash consing . Esta es una técnica importante en la gestión de la memoria en la programación funcional. Hash consing es una especie de memorización sistemática para estructuras de datos.

Vamos a hacer hash-cons del árbol y contar los nodos después de hash consing. El hash que consiste en una estructura de datos de tamaño siempre se puede hacer en operaciones ; contar el número de nodos al final es lineal en el número de nodos.nO(nlg(n))

Consideraré que los árboles tienen la siguiente estructura (escrita aquí en la sintaxis de Haskell):

data Tree = Leaf
          | Node Tree Tree

Para cada constructor, necesitamos mantener una asignación de sus posibles argumentos al resultado de aplicar el constructor a estos argumentos. Las hojas son triviales. Para los nodos, mantenemos un mapa parcial finito donde es el conjunto de identificadores de árbol y es el conjunto de identificadores de nodo; donde es el único identificador de hoja. (En términos concretos, un identificador es un puntero a un bloque de memoria).nodes:T×TNTNT=N{}

Podemos utilizar una estructura de datos de tiempo logarítmico para nodes, como un árbol de búsqueda binario equilibrado. A continuación, llamaré a lookup nodesla operación que busca una clave en la nodesestructura de datos, y insert nodesla operación que agrega un valor bajo una nueva clave y devuelve esa clave.

Ahora atravesamos el árbol y agregamos los nodos a medida que avanzamos. Aunque estoy escribiendo en pseudocódigo similar a Haskell, lo trataré nodescomo una variable mutable global; solo lo agregaremos alguna vez, pero las inserciones deben estar enhebradas por completo. La addfunción se repite en un árbol, agregando sus subárboles al nodesmapa y devuelve el identificador de la raíz.

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

El número de insertllamadas, que también es el tamaño final de la nodesestructura de datos, es el número de nodos después de la compresión máxima. (Agregue uno para el árbol vacío si es necesario).

Gilles 'SO- deja de ser malvado'
fuente
¿Puede dar una referencia para "El hash que consiste en una estructura de datos de tamaño siempre se puede hacer en "? Tenga en cuenta que necesitará árboles equilibrados para lograr el tiempo de ejecución deseado. nO(nlg(n))nodes
Raphael
Solo estaba considerando las estructuras de hash para números de una manera estructurada, de modo que calcular independientemente el hash para el mismo árbol siempre produjera el mismo resultado. Su solución también está bien, siempre que tengamos estructuras de datos mutables en nuestras manos. Sin embargo, creo que se puede limpiar un poco; el entrelazado de inserty adddebería hacerse explícito y, en mi opinión, debería asignarse una función que realmente resuelva el problema.
Raphael
1
@Raphael Hash consiste en una estructura de mapa finita sobre tuplas de punteros / identificadores, puede implementar eso con tiempo logarítmico para buscar y agregar (por ejemplo, con un árbol de búsqueda binario equilibrado). Mi solución no requiere mutabilidad; Hago nodesuna variable mutable por conveniencia, pero puedes enhebrarla por completo. No voy a dar el código completo, esto no es SO.
Gilles 'SO- deja de ser malvado'
1
@Raphael Hashing estructuras, en lugar de asignarlos a números arbitrarios, es un poco arriesgado. En el modelo de costo uniforme, puede codificar cualquier cosa en un número entero grande y realizar operaciones de tiempo constante en él, lo que no es realista. En el mundo real, puede usar hashes criptográficos para tener un mapeo uno a uno de facto de conjuntos infinitos a un rango finito de enteros, pero son lentos. Si utiliza una suma de comprobación no criptográfica como el hash, debe pensar en colisiones.
Gilles 'SO- deja de ser malvado'
3

Aquí hay otra idea que apunta a codificar (inyectivamente) la estructura de los árboles en números, en lugar de simplemente etiquetarlos arbitrariamente. Para eso, usamos que la factorización prima de cualquier número es única.

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

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

f

Esta última suposición es un tramo en máquinas reales; en este caso, uno preferiría usar algo similar a la función de emparejamiento de Cantor en lugar de exponenciación.

O(nlogn)O(nlogn)

Rafael
fuente
1

Como las imágenes no están permitidas en los comentarios:

ingrese la descripción de la imagen aquí

arriba a la izquierda: un árbol de entrada

arriba a la derecha: los subárboles enraizados en los nodos 5 y 7 también son isomórficos.

inferior izquierda y derecha: los árboles comprimidos no están definidos de forma exclusiva.

Tenga en cuenta que en este caso el tamaño del árbol ha bajado detambién.7+5|T|6+|T|

uli
fuente
Este es de hecho un ejemplo de la operación deseada, gracias. Tenga en cuenta que sus ejemplos finales son idénticos si no distingue entre referencias originales y agregadas.
Raphael
-1

Editar: leí la pregunta ya que T y T 'eran hijos del mismo padre. Tomé la definición de compresión como recursiva también, lo que significa que podría comprimir dos subárboles previamente comprimidos. Si esa no es la pregunta real, entonces mi respuesta puede no funcionar.

O(nlogn) pide una solución divide y vencerás. Comprima recursivamente los nodos y calcule el número de descendientes en cada subárbol después de la compresión. Aquí hay un pseudo código python-esque.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    

Dónde hasSameStructure()es una función que compara dos subárboles ya comprimidos en tiempo lineal para ver si tienen exactamente la misma estructura. Escribir una función recursiva de tiempo lineal que atraviese cada una y verifique si un subárbol tiene un hijo izquierdo cada vez que el otro tiene, etc.

Deje que y sean los tamaños de los subárboles izquierdo y derecho respectivamente (después de la compresión). Entonces el tiempo de ejecución es ynnr

T(n)=T(n1)+T(n2)+O(1) if nnr
2T(n/2)+O(n) otherwise
Joe
fuente
¿Qué pasa si los subárboles no son hermanos? El cuidado de ((T1, T1), (T2, T1)) T1 se puede guardar dos veces utilizando un puntero dos la tercera vez.
uli
@uli No estoy seguro de lo que estás diciendo. Leí la pregunta ya que y eran hijos del mismo padre. Si esa no es la pregunta real, entonces mi respuesta puede no funcionar. Tomé la definición de compresión como recursiva también, lo que significa que podría comprimir dos subárboles previamente comprimidos. TT
Joe
Las preguntas dicen que dos subfuerzos se identifican como isomórficos. No se dice nada sobre ellos teniendo el mismo padre. Si un subárbol T1 aparece tres veces en un árbol, como en mi ejemplo anterior ((T1, T1), (T1, T2)) se pueden comprimir dos ocurrencias apuntando a la tercera ocurrencia.
uli