Le hachage d'un Arbre de Structure

Question

Je viens de tomber sur un scénario dans mon projet où j'ai besoin de comparer les différents objets de l'arborescence de l'égalité avec déjà connu des cas, et ont considéré qu'une sorte d'algorithme de hachage qui fonctionne sur l'arbitraire d'un arbre serait très utile.

Prenez l'exemple de l'arbre suivant:

O
 / \
 / \
 O O
 /|\ |
 / | \ |
 O O O O
 / \
 / \
 O O

Où chaque O représente un nœud de l'arbre, est un objet arbitraire, a est associé à une fonction de hachage. Donc, le problème se réduit à: vu le code de hachage de l'nœuds de la structure de l'arbre, et une structure connue, ce qui est un bon algorithme pour le calcul de a (relativement) sans collision code de hachage pour l'ensemble de l'arbre?

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

• La fonction de hachage doit dépendre sur le code de hachage de chaque nœud dans l'arbre ainsi que sa position.
• Réordonner les enfants d'un nœud devrait nettement changer la résultante de code de hachage.
• Reflétant toute la partie de l'arbre devrait nettement changer la résultante de code de hachage

Si cela peut aider, je suis à l'aide de C# 4.0, ici, dans mon projet, mais je suis principalement à la recherche d'une solution théorique, sorte de pseudo-code, une description, ou d'un code dans un autre langage impératif serait bien.

---

Mise à JOUR

Eh bien, voici ma propre solution proposée. Il a été beaucoup aidés par plusieurs des réponses ici.

Chaque nœud du sous-arbre/nœud feuille) a pour fonction de hachage:

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, comme je le vois, c'est que des codes de hachage peut être mis en cache et recalculées uniquement lorsque le nœud ou l'un de ses descendants changements. (Merci à vatine et Jason Orendorff pour le signaler).

De toute façon, je vous serais reconnaissant si des gens peuvent commenter ma solution proposée ici - si elle ne le travail est bien fait, très bien, sinon d'éventuelles améliorations seraient les bienvenues.

Answer 1

Si je devais le faire, je le ferais probablement quelque chose comme ce qui suit:

Pour chaque nœud feuille, calculer la concaténation de 0 et la valeur de hachage du nœud de données.

Pour chaque noeud interne, calcul de la concaténation de 1 et la valeur de hachage de données locales (NB: ne peut pas être le cas) et le hachage des enfants de gauche à droite.

Cela conduira à une cascade en haut de l'arborescence à chaque fois que vous changer quoi que ce soit, mais qui PEUT être de faible assez d'une surcharge de la peine. Si des changements sont relativement rares par rapport à la quantité de modifications, il peut même faire sens pour aller faire un hachage cryptographique sécurisé.

Edit1: Il y a aussi la possibilité d'ajouter un "hachage valide" drapeau de chaque nœud et simplement propager un "faux" en haut de l'arborescence (ou "hash non valide" et de propager les "vrais") en haut de l'arborescence sur un nœud de changement. De cette façon, il peut être possible d'éviter un recalcul complet lors de l'arbre de hachage est nécessaire et peut-être éviter de multiples calculs de hachage qui ne sont pas utilisés, au risque d'un peu moins prévisible de temps pour obtenir un hash en cas de besoin.

Edit3: Le code de hachage suggéré par le Noldorin dans la question ressemble comme il aurait une chance de collisions, si le résultat de GetHashCode peut jamais être égal à 0. Essentiellement, il n'y a aucun moyen de distinguer un arbre composé d'un seul nœud, avec "symbole de hachage" 30 "et" valeur de hachage de" 25, et une à deux nœuds de l'arbre, la racine a un "symbole de hachage" de 0 et une valeur de hachage" de 30 et le nœud enfant a un gâchis total de 25. Les exemples sont entièrement inventés, je ne sais pas ce qu'attend de hachage plages sont tellement, je ne peux que commenter ce que je vois dans le code.

À l'aide de 31 comme la constante multiplicative est bon, qu'il sera la cause de tout débordement pour arriver sur un non-bit de la frontière, bien que je pense que, avec suffisamment d'enfants et éventuellement contradictoire contenu dans l'arbre, la valeur de hachage de la contribution à partir d'éléments hachés début PEUT être dominé par plus tard haché éléments.

Toutefois, si le hachage effectue décemment sur les données attendues, on dirait qu'il va faire le travail. C'est certainement plus rapide que d'utiliser un hachage cryptographique (comme dans l'exemple de code ci-dessous).

Edit2: Comme pour les algorithmes spécifiques et minimale de la structure de données nécessaire, quelque chose comme ce qui suit (Python, la traduction dans une autre langue doit être relativement facile).

#! /usr/bin/env python

l'importation de la Crypto.De hachage.SHA

Nœud de classe:
 def __init__ (self, parent=None, contenu="", les enfants,=[]):
 auto.valide = False
 auto.hash = False
 auto.contenu = contenu
 auto.les enfants = les enfants


 def append_child (auto, enfant):
auto.les enfants.append(enfant)

auto.invalidate()

 def invalidate (self):
 auto.valide = False
 si l'auto.parent:
auto.parent.invalidate()

 def gethash (self):
 si l'auto.valide:
 retour auto.de hachage

 autoclave = crypto.de hachage.SHA.new()

autoclave.mise à jour(auto.le contenu)

 si l'auto.enfants:
 pour l'enfant en soi.enfants:
autoclave.mise à jour(l'enfant.gethash())
 auto.hash = "1"+autoclave.hexdigest()
autre chose:
 auto.hash = "0"+autoclave.hexdigest()

 retour auto.de hachage

 def setcontents (self):
 auto.valide = False
 retour auto.contenu

Answer 2

Bon, après votre travail d'édition où vous avez introduit une exigence que le résultat de hachage doit être différente pour d'arbres différentes mises en page, vous êtes de gauche avec option pour parcourir l'ensemble de l'arbre et écrire sa structure à un seul tableau.

C'est fait comme ceci: vous traverse l'arbre et vider les opérations que vous faites. Pour un arbre d'origine qui pourrait être (pour le côté gauche de l'enfant-droit-frère de la structure):

[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 ensuite hachage de la liste (qui est, effectivement, une chaîne de caractères) de la façon dont vous le souhaitez. Comme autre option, vous pouvez même revenir à cette liste comme un résultat de la fonction de hachage, de sorte qu'il devient sans collision arbre de représentation.

Mais l'ajout de précision des informations sur l'ensemble de la structure n'est pas ce que les fonctions de hachage d'habitude. La voie proposée doit calculer la fonction de hachage de chaque nœud comme parcourir l'ensemble de l'arbre. Ainsi, vous pouvez envisager d'autres façons de hachage, décrit ci-dessous.

---

Si vous ne voulez pas à parcourir l'ensemble de l'arbre:

Un algorithme qui m'est immédiatement venue à l'esprit c'est comme ça. Choisir un grand nombre H (c'est plus que le nombre maximal d'enfants). Pour un arbre de hachage, hash sa racine, choisissez un enfant nombre H mod noù n le nombre d'enfants de la racine, et de façon récursive de hachage de la sous-arborescence de cet enfant.

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

Si vous souhaitez de hachage moins d'éléments, mais aller à travers l'ensemble de l'arbre:

Au lieu de hachage de la sous-arborescence, vous pouvez hachage couche-sage. I. e. hachage de la racine première, que le hachage de l'un des nœuds qui sont ses enfants, puis l'un des enfants des enfants etc. Si vous couvrez l'ensemble de l'arbre à la place de l'un des chemins spécifiques. Cela rend le hachage procédure 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 nœud à partir d'une couche est repris avec de l' H mod n règle.

La différence entre cette version et la version précédente est que l'arbre doit subir un assez illogique de transformation de conserver la fonction de hachage.

Answer 3

La technique habituelle de hachage toute la séquence est la combinaison des valeurs (ou des hachages de celui-ci) de ses éléments d'une certaine manière mathématique. Je ne pense pas que l'arbre serait différent à cet égard.

Par exemple, ici, c'est la fonction de hachage pour les tuples en Python (prises à partir d'Objets/tupleobject.c dans le source de la version 2.6 de Python):

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 relativement complexe combinaison avec des constantes expérimentalement choisi pour de meilleurs résultats pour les n-uplets de typique longueurs. Ce que j'essaie de montrer avec cet extrait de code, c'est que le problème est très complexe et très heuristique, et la qualité des résultats probablement dépendre sur les aspects plus spécifiques de vos données, c'est à dire la connaissance du domaine peut vous aider à atteindre de meilleurs résultats. Cependant, pour de bon-assez de résultats, vous ne devriez pas regarder trop loin. Je suppose que la prise de cet algorithme et le regroupement de tous les nœuds de l'arbre au lieu de tous les n-uplet d'éléments, plus l'ajout de leur position dans le jeu vous donnera un très bon algorithme.

Une option de prise de position en compte est le nœud dans une afinde à pied de l'arbre.

Answer 4

Toutes les fois que l'on travaille avec des arbres de récursivité qui 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 sur le code de hachage de chaque nœud dans l'arbre ainsi que sa position.

De vérifier. Nous sommes explicitement à l'aide de node.GetHashCode() dans le calcul de l'arbre de code de hachage. En outre, en raison de la nature de l'algorithme, d'un nœud en position joue un rôle dans l'arbre final de code de hachage.

Réordonner les enfants d'un nœud devrait nettement changer la résultante de code de hachage.

De vérifier. Ils seront visitées dans un ordre différent de l'ordre de la traversée menant à un autre code de hachage. (Notez que si il y a deux enfants avec le même code de hachage vous allez vous retrouver avec le même code de hachage lors de la permutation de l'ordre de ces enfants.)

Reflétant toute la partie de l'arbre devrait nettement changer la résultante de code de hachage

De vérifier. De nouveau les noeuds être visité dans un ordre différent menant à un autre code de hachage. (Notez qu'il existe des circonstances où la réflexion pourrait conduire à le même code de hachage si chaque nœud est reflété dans un nœud avec le même code de hachage.)

Answer 5

La collision de la propriété de cette dépendra de la collision de la fonction de hachage utilisée pour le nœud de données.

Il semble que vous voulez un système où la valeur de hachage d'un nœud particulier est une combinaison de l'enfant du nœud de hachages, où l'ordre des questions.

Si vous avez l'intention sur la manipulation de cet arbre un lot, vous pouvez payer le prix dans l'espace de stockage du hashcode à chaque nœud, pour éviter la peine de calcul lorsque vous effectuez des opérations sur l'arbre.

Puisque l'ordre des nœuds enfants questions, une méthode qui pourrait fonctionner ici serait de combiner les nœuds de données et les enfants en utilisant le premier numéro de multiples et l'addition modulo certaines grand nombre.

Aller pour quelque chose de similaire à Java de la Chaîne hashcode:

Disons que vous disposez de 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 mécanisme utilisé ci-dessus peuvent être trouvés ici: http://computinglife.wordpress.com/2008/11/20/why-do-hash-functions-use-prime-numbers/