Hachage d’une structure d’arbre

Je viens de découvrir un scénario dans mon projet où il est nécessaire de comparer différents objects arborescents pour des raisons d’égalité avec des instances déjà connues, et j’ai considéré qu’un algorithme de hachage opérant sur un arbre arbitraire serait très utile.

Prenons par exemple l’arbre suivant:

         O
        / \
       / \
      OO
     / | \ |
    / |  \ |
   OOOO
           / \
          / \
         OO

Où chaque O représente un nœud de l’arbre, est un object arbitraire, a une fonction de hachage associée. Donc, le problème se réduit à: à partir du code de hachage des nœuds de la structure arborescente et d’une structure connue, qu’est-ce qu’un algorithme décent pour calculer un code de hachage (relativement) sans collision pour l’arborescence entière?

Quelques notes sur les propriétés de la fonction de hachage:

  • La fonction de hachage doit dépendre du code de hachage de chaque nœud de l’arborescence ainsi que de sa position.
  • La réorganisation des enfants d’un nœud doit modifier distinctement le code de hachage résultant.
  • La reflection de n’importe quelle partie de l’arborescence devrait modifier distinctement le code de hachage résultant

Si cela peut vous aider, j’utilise C # 4.0 dans mon projet, même si je recherche principalement une solution théorique, donc un pseudo-code, une description ou un code dans un autre langage impératif conviendrait.


METTRE À JOUR

Eh bien, voici ma propre solution proposée. Plusieurs des réponses ont beaucoup aidé.

Chaque noeud (sous-arbre / noeud feuille) a la fonction de hachage suivante:

 public override int GetHashCode() { int hashCode = unchecked((this.Symbol.GetHashCode() * 31 + this.Value.GetHashCode())); for (int i = 0; i < this.Children.Count; i++) hashCode = unchecked(hashCode * 31 + this.Children[i].GetHashCode()); return hashCode; } 

La bonne chose à propos de cette méthode, à mon avis, est que les codes de hachage peuvent être mis en cache et seulement recalculés lorsque le nœud ou l’un de ses descendants change. (Merci à vatine et Jason Orendorff de l’avoir signalé).

Quoi qu’il en soit, je vous serais reconnaissant si les gens pouvaient commenter ma solution proposée ici – si elle fait bien le travail, alors très bien, sinon toutes les améliorations possibles seraient les bienvenues.

Si je devais le faire, je ferais probablement quelque chose comme ceci:

Pour chaque nœud feuille, calculez la concaténation de 0 et le hachage des données du nœud.

Pour chaque nœud interne, calculez la concaténation de 1 et le hachage de toutes les données locales (NB: peut ne pas être applicable) et le hachage des enfants de gauche à droite.

Cela conduira à une cascade dans l’arborescence à chaque fois que vous changez quelque chose, mais cela peut être assez faible pour que cela vaille la peine. Si les changements sont relativement peu fréquents par rapport à la quantité de modifications, il peut même être judicieux d’utiliser un hachage sécurisé sur le plan cryptographique.

Edit1: Il y a aussi la possibilité d’append un drapeau “hash valid” à chaque noeud et de simplement propager un “false” dans l’arborescence (ou “hash invalide” et propager “true”) dans l’arborescence lors d’un changement de noeud. De cette façon, il est possible d’éviter un recalcul complet lorsque le hachage de l’arborescence est nécessaire et d’éviter éventuellement plusieurs calculs de hachage qui ne sont pas utilisés, au risque d’un temps légèrement moins prévisible pour obtenir un hachage en cas de besoin.

Edit3: Le code de hachage proposé par Noldorin dans la question semble avoir une chance de collision, si le résultat de GetHashCode peut être égal à 0. Essentiellement, il est impossible de distinguer une arborescence composée d’un seul nœud, avec “symbole hash “30 et” value hash “25 et un arbre à deux nœuds, où la racine a un” hash symbole “de 0 et un” value hash “de 30 et le nœud enfant a un total de hachage de 25. Les exemples sont entièrement inventé, je ne sais pas quelles sont les plages de hachage attendues, donc je ne peux que commenter ce que je vois dans le code présenté.

Utiliser 31 comme constante multiplicative est bon, dans la mesure où cela entraînera tout dépassement de capacité sur une frontière non binary, bien que je pense qu’avec suffisamment d’enfants et éventuellement du contenu contradictoire dans l’arborescence, la consortingbution de hachage des éléments hachés au début de MAI être dominé par les articles hachés plus tard.

Cependant, si le hachage fonctionne correctement avec les données attendues, il semblerait qu’il fera le travail. C’est certainement plus rapide que d’utiliser un hachage cryptographique (comme dans l’exemple de code ci-dessous).

Edit2: En ce qui concerne les algorithmes spécifiques et la structure de données minimum nécessaire, quelque chose comme le suivant (Python, la traduction vers toute autre langue devrait être relativement facile).

 #!  / usr / bin / env python

 importer Crypto.Hash.SHA

 classe Node:
     def __init__ (self, parent = None, contents = "", children = []):
         self.valid = False
         self.hash = Faux
         self.contents = contenu
         self.children = enfants


     def append_child (self, child):
         self.children.append (enfant)

         self.invalidate ()

     def invalider (auto):
         self.valid = False
         si auto.parent:
             self.parent.invalidate ()

     def gethash (self):
         si auto.valide:
             retourner self.hash

         digesteur = crypto.hash.SHA.new ()

         digester.update (self.contents)

         si self.children:
             pour les enfants en auto:
                 digester.update (child.gethash ())
             self.hash = "1" + digester.hexdigest ()
         autre:
             self.hash = "0" + digester.hexdigest ()

         retourner self.hash

     def setcontents (self):
         self.valid = False
         retourner self.contents

Bon, après votre édition où vous avez introduit une exigence selon laquelle le résultat du hachage doit être différent pour différentes mises en forme d’arborescence, vous ne pouvez que parcourir l’arborescence entière et écrire sa structure dans un seul tableau.

Cela se fait comme ceci: vous parcourez l’arborescence et vider les opérations que vous faites. Pour un arbre original qui pourrait être (pour une structure frère-enfant-droit-frère):

 [1, child, 2, child, 3, sibling, 4, sibling, 5, parent, parent, //we're at root again sibling, 6, child, 7, child, 8, sibling, 9, parent, parent] 

Vous pouvez alors hacher la liste (c’est-à-dire, effectivement, une chaîne) comme vous le souhaitez. En tant qu’autre option, vous pouvez même retourner cette liste à la suite d’une fonction de hachage, pour qu’elle devienne une représentation d’arborescence sans collision.

Mais les fonctions de hachage ne permettent généralement pas d’append des informations précises sur l’ensemble de la structure. La méthode proposée doit calculer la fonction de hachage de chaque nœud et parcourir l’arbre entier. Vous pouvez donc envisager d’autres méthodes de hachage, décrites ci-dessous.


Si vous ne voulez pas parcourir l’arbre entier:

Un algorithme qui me vint immédiatement à l’esprit est comme ceci. Choisissez un grand nombre premier H (c’est plus que le nombre maximal d’enfants). Pour hacher un arbre, hachez sa racine, choisissez un numéro enfant H mod n , où n est le nombre d’enfants de root, et rechute de manière récursive le sous-arbre de cet enfant.

Cela semble être une mauvaise option si les arbres ne diffèrent que profondément près des feuilles. Mais au moins, il devrait être rapide pour les arbres peu grands.

Si vous voulez hacher moins d’éléments mais parcourir l’arbre entier :

Au lieu de hacher le sous-arbre, vous souhaiterez peut-être hacher la couche. C’est-à-dire que la racine de hachage en premier lieu, que le hachage de l’un des nœuds qui sont ses enfants, puis un des enfants des enfants, etc. Vous couvrez donc l’arbre entier au lieu d’un chemin spécifique. Cela rend la procédure de hachage plus lente, bien sûr.

  --- O ------- layer 0, n=1 / \ / \ --- O --- O ----- layer 1, n=2 /|\ | / | \ | / | \ | O - O - O O------ layer 2, n=4 / \ / \ ------ O --- O -- layer 3, n=2 

Un noeud d’une couche est sélectionné avec la règle H mod n .

La différence entre cette version et la version précédente est qu’un arbre doit subir une transformation assez illogique pour conserver la fonction de hachage.

La technique habituelle de hachage d’une séquence consiste à combiner les valeurs (ou leurs hachages) de ses éléments de manière mathématique. Je ne pense pas qu’un arbre serait différent à cet égard.

Par exemple, voici la fonction de hachage pour les tuples dans Python (tirée de Objects / tupleobject.c dans la source de Python 2.6):

 static long tuplehash(PyTupleObject *v) { register long x, y; register Py_ssize_t len = Py_SIZE(v); register PyObject **p; long mult = 1000003L; x = 0x345678L; p = v->ob_item; while (--len >= 0) { y = PyObject_Hash(*p++); if (y == -1) return -1; x = (x ^ y) * mult; /* the cast might truncate len; that doesn't change hash stability */ mult += (long)(82520L + len + len); } x += 97531L; if (x == -1) x = -2; return x; } 

C’est une combinaison relativement complexe avec des constantes choisies expérimentalement pour obtenir les meilleurs résultats pour les tuples de longueurs typiques. Ce que j’essaie de montrer avec cet extrait de code est que le problème est très complexe et très heuristique et que la qualité des résultats dépend probablement d’aspects plus spécifiques de vos données – autrement dit, la connaissance du domaine peut vous aider à obtenir de meilleurs résultats. Cependant, pour des résultats suffisamment bons, vous ne devriez pas regarder trop loin. Je suppose que prendre cet algorithme et combiner tous les nœuds de l’arbre au lieu de tous les éléments du tuple, en plus d’append leur position dans le jeu, vous donnera un très bon algorithme.

Une option pour prendre en compte la position est la position du nœud dans une marche inordonnée de l’arbre.

Chaque fois que vous travaillez avec des arbres, la récursivité devrait vous venir à l’esprit:

 public override int GetHashCode() { int hash = 5381; foreach(var node in this.BreadthFirstTraversal()) { hash = 33 * hash + node.GetHashCode(); } } 

La fonction de hachage doit dépendre du code de hachage de chaque nœud de l’arborescence ainsi que de sa position.

Vérifier. Nous utilisons explicitement node.GetHashCode() dans le calcul du code de hachage de l’arbre. De plus, en raison de la nature de l’algorithme, la position d’un nœud joue un rôle dans le code de hachage ultime de l’arbre.

La réorganisation des enfants d’un nœud doit modifier distinctement le code de hachage résultant.

Vérifier. Ils seront visités dans un ordre différent dans la traversée en ordre menant à un code de hachage différent. (Notez que s’il y a deux enfants avec le même code de hachage, vous obtiendrez le même code de hachage lors du remplacement de l’ordre de ces enfants.)

La reflection de n’importe quelle partie de l’arborescence devrait modifier distinctement le code de hachage résultant

Vérifier. Là encore, les nœuds seraient visités dans un ordre différent, ce qui conduirait à un code de hachage différent. (Notez que dans certaines circonstances, la reflection peut mener au même code de hachage si chaque nœud est reflété dans un nœud avec le même code de hachage.)

La propriété sans collision dépendra de la manière dont la fonction de hachage utilisée pour les données de nœud est sans collision.

Il semble que vous vouliez un système où le hachage d’un nœud particulier est une combinaison des hachages de nœuds enfants, où l’ordre est important.

Si vous prévoyez de manipuler beaucoup cette arborescence, vous pouvez vouloir payer le prix dans l’espace de stockage du hashcode avec chaque nœud, afin d’éviter la pénalité de recalcul lors de l’exécution d’opérations sur l’arborescence.

Puisque l’ordre des noeuds enfants est important, une méthode qui pourrait fonctionner ici serait de combiner les données de noeuds et les enfants en utilisant des multiples de nombres premiers et des modulos d’addition.

Pour quelque chose de similaire au hashcode de Java:

Disons que vous avez n nœuds enfants.

 hash(node) = hash(nodedata) + hash(childnode[0]) * 31^(n-1) + hash(childnode[1]) * 31^(n-2) + <...> + hash(childnode[n]) 

Plus de détails sur le schéma utilisé ci-dessus peuvent être trouvés ici: http://computinglife.wordpress.com/2008/11/20/why-do-hash-functions-use-prime-numbers/

Je peux voir que si vous avez un grand ensemble d’arbres à comparer, vous pouvez utiliser une fonction de hachage pour récupérer un ensemble de candidats potentiels, puis effectuer une comparaison directe.

Une sous-chaîne qui fonctionnerait serait simplement d’utiliser la syntaxe lisp pour mettre des parenthèses autour de l’arbre, écrire les identifiants de chaque nœud en pré-commande. Mais cela équivaut à une comparaison pré-commande de l’arbre, alors pourquoi ne pas le faire?

J’ai donné 2 solutions: l’une est pour comparer les deux arbres lorsque vous avez terminé (nécessaire pour résoudre les collisions) et l’autre pour calculer le code de hachage.

COMPARAISON DES ARBRES:

Le moyen le plus efficace de comparer sera simplement de parcourir récursivement chaque arbre dans un ordre fixe (la pré-commande est simple et aussi bonne que toute autre chose), en comparant le nœud à chaque étape.

  1. Il suffit donc de créer un motif Visitor qui renvoie successivement le prochain noeud en pré-commande pour un arbre. c’est-à-dire que son constructeur peut prendre la racine de l’arbre.

  2. Ensuite, créez simplement deux insertions du visiteur, qui agissent en tant que générateurs pour le nœud suivant en pré-commande. ie Vistor = nouveau visiteur (root1), visiteur v2 = nouveau visiteur (root2)

  3. Ecrivez une fonction de comparaison qui peut se comparer à un autre nœud.

  4. Il suffit ensuite de visiter chaque nœud des arbres, en comparant et en renvoyant false si la comparaison échoue. c’est à dire

Module

  Function Compare(Node root1, Node root2) Visitor v1 = new Visitor(root1) Visitor v2 = new Visitor(root2) loop Node n1 = v1.next Node n2 = v2.next if (n1 == null) and (n2 == null) then return true if (n1 == null) or (n2 == null) then return false if n1.compare(n2) != 0 then return false end loop // unreachable End Function 

Module de fin

GÉNÉRATION DE CODE DE HASH:

Si vous souhaitez écrire une représentation sous forme de chaîne de l’arborescence, vous pouvez utiliser la syntaxe lisp pour une arborescence, puis échantillonner la chaîne pour générer un code de hachage plus court.

Module

  Function TreeToSsortingng(Node n1) : Ssortingng if node == null return "" Ssortingng s1 = "(" + n1.toSsortingng() for each child of n1 s1 = TreeToSsortingng(child) return s1 + ")" End Function 

Node.toSsortingng () peut renvoyer le libellé / code de hachage unique pour ce noeud. Vous pouvez ensuite faire une comparaison de sous-chaîne à partir des chaînes renvoyées par la fonction TreeToSsortingng pour déterminer si les arbres sont équivalents. Pour un hashcode plus court, échantillonnez simplement la fonction TreeToSsortingng, c’est-à-dire prenez tous les 5 caractères.

Module de fin

Je pense que vous pouvez le faire récursivement: Supposons que vous ayez une fonction de hachage h qui hache des chaînes de longueur arbitraire (par exemple SHA-1). Maintenant, le hachage d’une arborescence est le hachage d’une chaîne créée comme une concaténation du hachage de l’élément en cours (vous avez votre propre fonction pour cela) et des hachages de tous les enfants de ce nœud (à partir des appels récursifs du fonction).

Pour un arbre binary, vous auriez:

Hash( h(node->data) || Hash(node->left) || Hash(node->right) )

Vous devrez peut-être vérifier soigneusement si la géomésortinge de l’arbre est correctement prise en compte. Je pense qu’avec un peu d’effort, vous pourriez dériver une méthode pour laquelle trouver des collisions pour de tels arbres pourrait être aussi difficile que de trouver des collisions dans la fonction de hachage sous-jacente.

Une énumération simple (dans n’importe quel ordre déterministe) associée à une fonction de hachage qui dépend de la visite du nœud devrait fonctionner.

 int hash(Node root) { ArrayList worklist = new ArrayList(); worklist.add(root); int h = 0; int n = 0; while (!worklist.isEmpty()) { Node x = worklist.remove(worklist.size() - 1); worklist.addAll(x.children()); h ^= place_hash(x.hash(), n); n++; } return h; } int place_hash(int hash, int place) { return (Integer.toSsortingng(hash) + "_" + Integer.toSsortingng(place)).hash(); } 
 class TreeNode { public static QualityAgainstPerformance = 3; // tune this for your needs public static PositionMarkConstan = 23498735; // just anything public object TargetObject; // this is a subject of this TreeNode, which has to add it's hashcode; IEnumerable GetChildParticipiants() { yield return this; foreach(var child in Children) { yield return child; foreach(var grandchild in child.GetParticipiants() ) yield return grandchild; } IEnumerable GetParentParticipiants() { TreeNode parent = Parent; do yield return parent; while( ( parent = parent.Parent ) != null ); } public override int GetHashcode() { int computed = 0; var nodesToCombine = (Parent != null ? Parent : this).GetChildParticipiants() .Take(QualityAgainstPerformance/2) .Concat(GetParentParticipiants().Take(QualityAgainstPerformance/2)); foreach(var node in nodesToCombine) { if ( node.ReferenceEquals(this) ) computed = AddToMix(computed, PositionMarkConstant ); computed = AddToMix(computed, node.GetPositionInParent()); computed = AddToMix(computed, node.TargetObject.GetHashCode()); } return computed; } } 

AddToTheMix est une fonction qui combine les deux codes de hachage, de sorte que la séquence est importante. Je ne sais pas ce que c’est, mais vous pouvez comprendre. Un peu de décalage, d’arrondi, vous savez …

L’idée est que vous devez parsingr certains environnements du nœud, en fonction de la qualité que vous souhaitez atteindre.

Je dois dire que vos exigences sont quelque peu en contradiction avec le concept entier des codes de hachage.

La complexité de calcul de la fonction de hachage devrait être très limitée.

Sa complexité de calcul ne devrait pas dépendre linéairement de la taille du conteneur (l’arborescence), sinon elle enfreindrait totalement les algorithmes basés sur le hashcode.

Considérer la position comme une propriété majeure de la fonction de hachage des nœuds va également à l’encontre du concept de l’arborescence, mais réalisable, si vous remplacez l’exigence, qu’il DOIT dépendre de la position.

Le principe général que je suggérerais, remplace les exigences de MUST avec les exigences de SHOULD. De cette façon, vous pouvez trouver un algorithme approprié et efficace.

Par exemple, envisagez de créer une séquence limitée de jetons de hashcode de nombre entier et d’append ce que vous voulez à cette séquence, dans l’ordre de préférence.

L’ordre des éléments dans cette séquence est important, il affecte la valeur calculée.

par exemple pour chaque noeud que vous souhaitez calculer:

  1. append le code de hachage de l’object sous-jacent
  2. Ajoutez les codes de hachage des objects sous-jacents des frères et sœurs les plus proches, s’ils sont disponibles. Je pense que même le simple frère gauche serait suffisant.
  3. Ajoutez le code de hachage de l’object sous-jacent du parent et ses frères et sœurs les plus proches, comme pour le nœud lui-même, identique à 2.
  4. Répétez cette opération avec les grands-parents à une profondeur limitée.

     //--------5------- ancestor depth 2 and it's left sibling; //-------/|------- ; //------4-3------- ancestor depth 1 and it's left sibling; //-------/|------- ; //------2-1------- this; 

    Le fait que vous ajoutiez le code de hachage de l’object sous-jacent direct d’un frère donne une propriété positionnelle à la fonction de hachage.

    si cela ne suffit pas, ajoutez les enfants: vous devez append tous les enfants, certains juste pour donner un hashcode décent.

  5. Ajouter le premier enfant et son premier enfant et son premier enfant .. limiter la profondeur à une certaine constante et ne rien calculer de manière récursive – juste le hashcode de l’object du noeud sous-jacent.

     //----- this; //-----/--; //----6---; //---/--; //--7---; 

De cette façon, la complexité est linéaire à la profondeur de l’arbre sous-jacent, et non au nombre total d’éléments.

Maintenant, vous avez une séquence si les entiers, combinez-les avec un algorithme connu, comme Ely suggère ci-dessus.

1,2, … 7

De cette façon, vous aurez une fonction de hachage légère, avec une propriété positionnelle, ne dépendant pas de la taille totale de l’arbre, et même ne dépendant pas de la profondeur de l’arbre, et ne nécessitant pas de recalculer la fonction de hachage structure arborescente.

Je parie que ces 7 numéros donneraient une dissortingbution de hash proche de la perfection.

Ecrire votre propre fonction de hachage est presque toujours un bug, car vous avez essentiellement besoin d’un diplôme en mathématiques pour bien le faire. Les fonctions de hachage sont incroyablement non intuitives et présentent des caractéristiques de collision hautement imprévisibles.

N’essayez pas de combiner directement les codes de hachage pour les nœuds Child – cela agrandira tous les problèmes dans les fonctions de hachage sous-jacentes. Au lieu de cela, concaténer les octets bruts de chaque nœud dans l’ordre, et les alimenter comme un stream d’octets à une fonction de hachage éprouvée. Toutes les fonctions de hachage cryptographiques peuvent accepter un stream d’octets. Si l’arborescence est petite, vous pouvez créer un tableau d’octets et le hacher en une seule opération.