Compression efficace des arbres non étiquetés

20

Considérez les arbres binaires sans étiquette et enracinés. Nous pouvons compressons ces arbres: chaque fois qu'il ya des pointeurs vers des sous - arbres et avec (interprétation l'égalité structurelle), nous enregistrons (wlog) et remplaçons tous les pointeurs vers avec des pointeurs vers . Voir la réponse d' uli pour un exemple.T T = T = T T TTT=T=TTT

Donnez un algorithme qui prend un arbre dans le sens ci-dessus en entrée et calcule le nombre (minimal) de nœuds qui restent après la compression. L'algorithme doit s'exécuter dans le temps (dans le modèle de coût uniforme) avec le nombre de nœuds en entrée.nO(nlogn)n

Cela a été une question d'examen et je n'ai pas été en mesure de trouver une bonne solution, ni n'en ai vu une.

Raphael
la source
Et quel est «le coût», «le temps», l'opération élémentaire ici? Le nombre de nœuds visités? Le nombre d'arêtes traversées? Et comment la taille de l'entrée est-elle spécifiée?
uli
Cette compression d'arbre est une instance de contre- hachage . Je ne sais pas si cela conduit à une méthode de comptage générique.
Gilles 'SO- arrête d'être méchant'
@uli J'ai clarifié ce que est. Je pense cependant que le «temps» est suffisamment précis. Dans les paramètres non simultanés, cela équivaut à compter les opérations, ce qui, en termes de Landau, équivaut à compter l'opération élémentaire qui se produit le plus souvent. n
Raphael
@Raphael Bien sûr, je peux deviner quelle devrait être l'opération élémentaire prévue et je choisirai probablement la même chose que tout le monde. Mais, et je sais que je suis pédant ici, chaque fois que des «limites de temps» sont données, il est important d'indiquer ce qui est compté. Est-ce des échanges, des comparaisons, des ajouts, des accès à la mémoire, des nœuds inspectés, des bords traversés, vous l'appelez. C'est comme omettre l'unité de mesure en physique. Est-ce ou ? Et je suppose que les accès à la mémoire sont presque toujours l'opération la plus fréquente. 1010kg10ms
uli
@uli C'est le genre de détails que le «modèle de coût uniforme» est censé transmettre. Il est difficile de définir précisément quelles opérations sont élémentaires, mais dans 99,99% des cas (y compris celui-ci) il n'y a pas d'ambiguïté. Les classes de complexité n'ont fondamentalement pas d'unités, elles ne mesurent pas le temps nécessaire pour effectuer une instance, mais la façon dont ce temps varie à mesure que l'entrée augmente.
Gilles 'SO- arrête d'être méchant'

Réponses:

10

Oui, vous pouvez effectuer cette compression en temps , mais ce n'est pas facile :) Nous faisons d'abord quelques observations puis présentons l'algorithme. Nous supposons que l'arbre n'est pas compressé au départ - ce n'est pas vraiment nécessaire mais facilite l'analyse.O(nlogn)

Premièrement, nous caractérisons «l'égalité structurelle» de manière inductive. Soit et deux (sous) arbres. Si et sont tous les deux des arbres nuls (n'ayant aucun sommet), ils sont structurellement équivalents. Si et sont pas tous deux des arbres nuls, alors ils sont structurellement équivalents si leurs enfants gauches sont structurellement équivalents et leurs enfants droits sont structurellement équivalents. L '«équivalence structurelle» est le point fixe minimal sur ces définitions.T T T T T TTTTTT

Par exemple, deux nœuds foliaires sont structurellement équivalents, car ils ont tous deux les arbres nuls comme leurs enfants, qui sont structurellement équivalents.

Comme il est assez ennuyeux de dire «leurs enfants de gauche sont structurellement équivalents et leurs enfants de droite aussi», nous dirons souvent «leurs enfants sont structurellement équivalents» et entendons la même chose. Notez également que nous disons parfois «ce sommet» lorsque nous voulons dire «le sous-arbre enraciné sur ce sommet».

La définition ci-dessus nous donne immédiatement un indice sur la façon d'effectuer la compression: si nous connaissons l'équivalence structurelle de tous les sous-arbres de profondeur au plus , alors nous pouvons facilement calculer l'équivalence structurelle des sous-arbres de profondeur . Nous devons faire ce calcul de manière intelligente pour éviter un temps d'exécution .d + 1 O ( n 2 )dd+1O(n2)

L'algorithme attribuera des identifiants à chaque sommet lors de son exécution. Un identifiant est un nombre dans l'ensemble . Les identifiants sont uniques et ne changent jamais: nous supposons donc que nous définissons une variable (globale) à 1 au début de l'algorithme, et chaque fois que nous attribuons un identifiant à un sommet, nous attribuons la valeur actuelle de cette variable au sommet et l'incrémentons la valeur de cette variable.{1,2,3,,n}

Nous transformons d'abord l'arbre d'entrée en (au plus ) listes contenant des sommets d'égale profondeur, ainsi qu'un pointeur vers leur parent. Cela se fait facilement en temps .O ( n )nO(n)

Nous compressons d'abord toutes les feuilles (nous pouvons trouver ces feuilles dans la liste avec des sommets de profondeur 0) en un seul sommet. Nous attribuons à ce sommet un identifiant. La compression de deux sommets se fait en redirigeant le parent de l'un des sommets pour pointer vers l'autre sommet à la place.

Nous faisons deux observations: premièrement, tout sommet a des enfants de profondeur strictement plus petite, et deuxièmement, si nous avons effectué une compression sur tous les sommets de profondeur inférieure à (et leur avons donné des identificateurs), alors deux sommets de profondeur sont structurellement équivalents et peut être compressé si les identifiants de leurs enfants coïncident. Cette dernière observation découle de l'argument suivant: deux sommets sont structurellement équivalents si leurs enfants sont structurellement équivalents, et après compression, cela signifie que leurs pointeurs pointent vers les mêmes enfants, ce qui signifie que les identifiants de leurs enfants sont égaux.ddd

Nous parcourons toutes les listes avec des nœuds de profondeur égale de petite profondeur à grande profondeur. Pour chaque niveau, nous créons une liste de paires entières, où chaque paire correspond aux identifiants des enfants de certains sommets de ce niveau. Nous avons que deux sommets de ce niveau sont structurellement équivalents si leurs paires entières correspondantes sont égales. En utilisant l'ordre lexicographique, nous pouvons les trier et obtenir les ensembles de paires entières qui sont égales. Nous compressons ces ensembles en sommets uniques comme ci-dessus et leur donnons des identificateurs.

Les observations ci-dessus prouvent que cette approche fonctionne et aboutit à l'arbre compressé. La durée totale d'exécution est plus le temps nécessaire pour trier les listes que nous créons. Comme le nombre total de paires entières que nous créons est , cela nous donne que le temps d'exécution total est , comme requis. Compter le nombre de nœuds qu'il nous reste à la fin de la procédure est trivial (il suffit de regarder le nombre d'identifiants que nous avons distribués).n O ( n log n )O(n)nO(nlogn)

Alex ten Brink
la source
Je n'ai pas lu votre réponse en détail, mais je pense que vous avez plus ou moins réinventé le hachage, avec une étrange façon de rechercher des nœuds spécifiques à un problème.
Gilles 'SO- arrête d'être méchant'
@Alex «enfants de degreedegré strictement inférieur » devrait probablement l'être depth? Et malgré les arbres CS qui poussent vers le bas, je trouve la «hauteur d'un arbre» ​​moins déroutante que la «profondeur d'un arbre».
uli
Bonne réponse. Je pense qu'il devrait y avoir un moyen de contourner le tri. Mon deuxième commentaire sur la réponse @Gilles est également valable ici.
Raphael
@uli: yup, vous avez raison, je l'ai corrigé (je ne sais pas pourquoi j'ai confondu ces deux mots). La hauteur et la profondeur sont deux concepts subtilement différents, et j'avais besoin de ce dernier :) Je pensais que je m'en tiendrais à la «profondeur» conventionnelle plutôt que de confondre tout le monde en les échangeant.
Alex ten Brink
4

La compression d'une structure de données non mutable afin qu'elle ne reproduise aucun sous-terme structurellement égal est connue sous le nom de contre- hachage . Il s'agit d'une technique importante dans la gestion de la mémoire dans la programmation fonctionnelle. Le hachage est une sorte de mémorisation systématique des structures de données.

Nous allons contre-hacher l'arbre et compter les nœuds après avoir haché. Le hachage contenant une structure de données de taille peut toujours être fait dans O ( nn opérations; compter le nombre de nœuds à la fin est linéaire dans le nombre de nœuds.O(nlg(n))

Je considérerai les arbres comme ayant la structure suivante (écrite ici dans la syntaxe Haskell):

data Tree = Leaf
          | Node Tree Tree

Pour chaque constructeur, nous devons maintenir un mappage de ses arguments possibles au résultat de l'application du constructeur à ces arguments. Les feuilles sont triviales. Pour les nœuds, nous maintenons une carte partielle finie T est l'ensemble des identificateurs d'arbre et N est l'ensemble des identificateurs de nœud; T = N { } est le seul identifiant de feuille. (Concrètement, un identifiant est un pointeur vers un bloc de mémoire.)nodes:T×TNTNT=N{}

Nous pouvons utiliser une structure de données à temps logarithmique pour nodes, comme un arbre de recherche binaire équilibré. Ci-dessous, j'appellerai lookup nodesl'opération qui recherche une clé dans la nodesstructure de données et insert nodesl'opération qui ajoute une valeur sous une nouvelle clé et renvoie cette clé.

Maintenant, nous traversons l'arbre et ajoutons les nœuds au fur et à mesure. Bien que j'écrive en pseudocode de type Haskell, je traiterai nodescomme une variable globale mutable; nous n'y ajouterons jamais, mais les insertions doivent être enfilées partout. La addfonction revient sur un arbre, en ajoutant ses sous-arbres à la nodescarte et renvoie l'identifiant de la racine.

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

Le nombre d' insertappels, qui est également la taille finale de la nodesstructure de données, est le nombre de nœuds après compression maximale. (Ajoutez-en un pour l'arbre vide si nécessaire.)

Gilles 'SO- arrête d'être méchant'
la source
nO(nlg(n))nodes
Je ne considérais que le hachage des sous-structures en nombres de manière structurée afin que le calcul indépendant du hachage pour le même arbre produise toujours le même résultat. Votre solution est très bien aussi, à condition que nous ayons des infrastructures de données mutables entre nos mains. Je pense que cela peut être nettoyé un peu, cependant; l'entrelacement de insertet adddevrait être rendu explicite et une fonction qui résout réellement le problème devrait être donnée, à mon humble avis.
Raphael
1
@Raphael Hash étant basé sur une structure de carte finie sur des tuples de pointeurs / identificateurs, vous pouvez l'implémenter avec du temps logarithmique pour la recherche et l'ajout (par exemple avec un arbre de recherche binaire équilibré). Ma solution ne nécessite pas de mutabilité; Je fais nodesune variable mutable pour plus de commodité, mais vous pouvez l'enfiler tout au long. Je ne vais pas donner le code complet, ce n'est pas SO.
Gilles 'SO- arrête d'être méchant'
1
@Raphael Hashing structures, au lieu de leur attribuer des nombres arbitraires, est un peu douteux. Dans le modèle de coût uniforme, vous pouvez encoder n'importe quoi en un grand entier et y effectuer des opérations à temps constant, ce qui n'est pas réaliste. Dans le monde réel, vous pouvez utiliser des hachages cryptographiques pour avoir un mappage un à un de facto d'ensembles infinis à une plage finie d'entiers, mais ils sont lents. Si vous utilisez une somme de contrôle non cryptographique comme hachage, vous devez penser aux collisions.
Gilles 'SO- arrête d'être méchant'
3

Voici une autre idée qui vise à coder (de manière injective) la structure des arbres en nombres, plutôt que de simplement les étiqueter arbitrairement. Pour cela, nous utilisons que la factorisation première de tout nombre est unique.

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

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

f

Cette dernière hypothèse est un étirement sur des machines réelles; dans ce cas, on préférerait utiliser quelque chose de similaire à la fonction d'appariement de Cantor au lieu de l'exponentiation.

O(nlogn)O(nlogn)

Raphael
la source
1

Comme les photos ne sont pas autorisées dans les commentaires:

entrez la description de l'image ici

en haut à gauche: une arborescence d'entrée

en haut à droite: les sous-arbres enracinés dans les nœuds 5 et 7 sont également isomorphes.

en bas à gauche et à droite: les arbres compressés ne sont pas définis de manière unique.

7+5|T|6+|T|

uli
la source
Ceci est en effet un exemple de l'opération souhaitée, merci. Notez que vos exemples finaux sont identiques si vous ne faites pas de distinction entre les références originales et ajoutées.
Raphael
-1

Edit: J'ai lu la question car T et T ′ étaient des enfants du même parent. J'ai pris la définition de la compression pour être récursive également, ce qui signifie que vous pouvez compresser deux sous-arbres précédemment compressés. Si ce n'est pas la vraie question, ma réponse pourrait ne pas fonctionner.

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    

hasSameStructure()est une fonction qui compare deux sous-arbres déjà compressés en temps linéaire pour voir s'ils ont exactement la même structure. L'écriture d'une fonction récursive temporelle linéaire qui traverse chacune et vérifie si l'un sous-arbre a un enfant gauche à chaque fois que l'autre le fait, etc. ne devrait pas être difficile.

nnr

T(n)=T(n1)+T(n2)+O(1) if nnr
2T(n/2)+O(n) otherwise
Joe
la source
Et si les sous-arbres ne sont pas des frères et sœurs? Prendre soin de ((T1, T1), (T2, T1)) T1 peut être enregistré deux fois en utilisant un pointeur deux la troisième occurrence.
uli
TT
Les questions indiquent simplement que deux sous-classes sont identifiées comme isomorphes. Rien n'est dit sur le fait qu'ils ont le même parent. Si un sous-arbre T1 apparaît trois fois dans un arbre, comme dans mon exemple précédent ((T1, T1), (T1, T2)), deux occurrences peuvent être compressées en pointant vers la troisième orccurence.
uli