Хеширование структуры дерева

Ответ 1

Если бы я сделал это, я бы, вероятно, сделал бы что-то вроде следующего:

Для каждого листа node вычислите конкатенацию 0 и хэш данных node.

Для каждого внутреннего node вычислите конкатенацию 1 и хэш любых локальных данных (NB: может быть неприменим) и хеш дочерних элементов слева направо.

Это приведет к каскаду дерева при каждом изменении чего-либо, но это МОЖЕТ быть достаточно низким, чтобы накладные расходы были полезными. Если изменения относительно нечасты по сравнению с количеством изменений, может оказаться даже целесообразным использовать криптографически безопасный хеш.

Edit1: существует также возможность добавить флаг "hash valid" для каждого node и просто распространять "false" по дереву (или "hash invalid" и распространять "true" ) вверх по дереву на node изменить. Таким образом, может быть возможно избежать полного пересчета, когда требуется хэш хэша, и, возможно, избежать многочисленных вычислений хэша, которые не используются, с риском немного менее прогнозируемого времени для получения хэша, когда это необходимо.

Edit3: хеш-код, предложенный Нолдорином в вопросе, выглядит так, что у него будет вероятность столкновения, если результат GetHashCode может когда-либо равняться 0. По существу, нет возможности различать дерево, состоящее из одного node с хешем символа 30 и "значением хеш" 25 и деревом с двумя символами node, где корень имеет "символьный хеш" 0 и "хэш-значение" из 30, а дочерний элемент node имеет общий хэш 25. Примеры полностью выдуманы, я не знаю, какие ожидаемые диапазоны хеширования я могу лишь прокомментировать, что я вижу в представленном коде.

Использование 31 в качестве мультипликативной константы является хорошим, поскольку оно вызовет любое переполнение на небитовой границе, хотя я думаю, что с достаточным количеством детей и, возможно, состязательным контентом в дереве хэш-вклад от элементов хэширование рано МОЖЕТ доминировать над более поздними хеш-элементами.

Однако, если хеш работает прилично на ожидаемых данных, похоже, что он выполнит эту работу. Это, конечно, быстрее, чем использование криптографического хэша (как это сделано в приведенном ниже примере кода).

Edit2: Что касается конкретных алгоритмов и минимальной структуры данных, то что-то вроде следующего (Python, перевод на любой другой язык должен быть относительно простым).

#! /usr/bin/env  python

import Crypto.Hash.SHA

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


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

        self.invalidate()

    def invalidate (self):
        self.valid = False
        if self.parent:
            self.parent.invalidate()

    def gethash (self):
        if self.valid:
            return self.hash

        digester = crypto.hash.SHA.new()

        digester.update(self.contents)

        if self.children:
            for child in self.children:
                digester.update(child.gethash())
            self.hash = "1"+digester.hexdigest()
        else:
            self.hash = "0"+digester.hexdigest()

        return self.hash

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

Ответ 2

Хорошо, после вашего редактирования, где вы ввели требование о том, что результат хеширования должен отличаться для разных макетов дерева, вам остается оставить опцию, чтобы пересечь все дерево и записать его структуру в один массив.

Это делается следующим образом: вы пересекаете дерево и выполняете операции, которые вы выполняете. Для исходного дерева, которое могло бы быть (для структуры слева и справа):

[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]

Затем вы можете присвоить список (то есть, фактически, строку) так, как вам нравится. В качестве другого варианта вы можете даже вернуть этот список в результате хеш-функции, поэтому он становится деревом без столкновений.

Но добавление точной информации о всей структуре не означает, что обычно выполняют функции хэш-функции. Предложенный способ должен вычислять хеш-функцию каждого node, а также пересекать все дерево. Поэтому вы можете рассмотреть другие способы хэширования, описанные ниже.

Если вы не хотите перемещаться по всему дереву:

Один из алгоритмов, который сразу пришел мне в голову, подобен этому. Выберите большое простое число H (большее, чем максимальное количество детей). Чтобы хэш-дерево, хэш его корень, выберите дочерний номер H mod n, где n - количество дочерних элементов root и рекурсивно хэш-поддерево этого дочернего элемента.

Это, кажется, плохой вариант, если деревья отличаются только глубоко у листьев. Но, по крайней мере, он должен быстро бегать за не очень высокими деревьями.

Если вы хотите хэш меньше элементов, но пройти через все дерево:

Вместо хэширования поддерева, вы можете захотеть использовать хэш-слой. То есть хэш-корень, а не один из узлов, которые являются его дочерними элементами, затем один из дочерних элементов детей и т.д. Таким образом, вы покрываете все дерево вместо одного из определенных путей. Это делает процедуру хэширования более медленной, конечно.

    --- 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

A node из слоя выбрано с правилом H mod n.

Разница между этой версией и предыдущей версией заключается в том, что дерево должно пройти довольно нелогичное преобразование для сохранения хэш-функции.

Ответ 3

Обычная техника хэширования любой последовательности сочетает значения (или хэши) ее элементов каким-то математическим способом. Я не думаю, что в этом отношении дерево будет иным.

Например, вот хеш-функция для кортежей в Python (взятая из Object/tupleobject.c в источнике 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;
}

Это относительно сложная комбинация с константами, экспериментально выбранными для получения наилучших результатов для кортежей типичных длин. То, что я пытаюсь показать с помощью этого фрагмента кода, заключается в том, что проблема очень сложная и очень эвристическая, и качество результатов, вероятно, зависит от более конкретных аспектов ваших данных - то есть знания домена могут помочь вам достичь лучших результатов. Однако, для достаточно хороших результатов вы не должны выглядеть слишком далеко. Я бы предположил, что использование этого алгоритма и объединение всех узлов дерева вместо всех элементов кортежа плюс добавление их позиции в игру даст вам довольно хороший алгоритм.

Один из вариантов учета позиции - это позиция node в походном дереве по умолчанию.

Ответ 4

Каждый раз, когда вы работаете с рекурсией деревьев, приходите на ум:

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

Хэш-функция должна зависеть от хеш-кода каждого node внутри дерева, а также от его позиции.

Check. Мы явно используем node.GetHashCode() при вычислении хеш-кода дерева. Кроме того, из-за характера алгоритма позиция node играет роль в конечном хэш-коде дерева.

Переупорядочение дочерних элементов node должно отчетливо изменить полученный хэш-код.

Check. Они будут посещаться в другом порядке в обходном пути, приводящем к другому хэш-коду. (Обратите внимание: если есть два ребенка с одним и тем же хэш-кодом, вы получите тот же хэш-код при замене порядка этих детей.)

Отражение любой части дерева должно явно изменить полученный хеш-код

Check. Опять же, узлы будут посещаться в другом порядке, что приведет к другому хэш-коду. (Обратите внимание, что есть ситуации, когда отражение может привести к одному и тому же хеш-коду, если каждый node отражается в node с тем же хэш-кодом.)

Ответ 5

Свойство без конфликтов для этого будет зависеть от того, насколько беспощадна хэш-функция, используемая для данных node.

Похоже, вы хотите систему, в которой хэш конкретного node представляет собой комбинацию хэшей node для детей, где имеет значение порядок.

Если вы планируете много манипулировать этим деревом, вы можете заплатить цену в пространстве хранения хэш-кода с каждым node, чтобы избежать штрафа за пересчет при выполнении операций над деревом.

Поскольку порядок дочерних узлов имеет значение, метод, который может работать здесь, состоял бы в объединении данных и детей node с использованием кратных чисел и добавлением по модулю некоторого большого количества.

Чтобы найти что-то похожее на хэш-код Java String:

Скажем, у вас есть n дочерних узлов.

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

Более подробную информацию о приведенной выше схеме можно найти здесь: http://computinglife.wordpress.com/2008/11/20/why-do-hash-functions-use-prime-numbers/

Ответ 6

Я вижу, что если у вас есть большой набор деревьев для сравнения, вы можете использовать хеш-функцию для извлечения набора потенциальных кандидатов, а затем сделать прямое сравнение.

Подстрока, которая будет работать, просто использует синтаксис lisp для размещения скобок вокруг дерева, выпишите идентификатор каждого node в предварительном порядке. Но это вычислительно эквивалентно предварительному сопоставлению дерева, поэтому почему бы просто не сделать это?

Я дал два решения: один для сравнения двух деревьев, когда вы закончили (необходимо для разрешения конфликтов), а другой для вычисления хэш-кода.

СРАВНЕНИЕ ДЕРЕВА:

Наиболее эффективным способом сравнения будет просто рекурсивное перемещение каждого дерева в фиксированном порядке (предварительный порядок прост и не хуже других), сравнивая node на каждом шаге.

• Итак, просто создайте шаблон посетителя, который последовательно возвращает следующий node в предварительном порядке для дерева. т.е. конструктор может взять корень дерева.

• Затем просто создайте две вставки посетителя, которые действуют как генераторы для следующего node в preorder. т.е. Vistor v1 = новый посетитель (root1), посетитель v2 = новый посетитель (root2)

• Напишите функцию сравнения, которая может сравниться с другим node.

• Затем просто посещайте каждый node деревьев, сравнивая и возвращая false, если сравнение не выполняется. то есть.

Модуль

 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

Конечный модуль

ПОКОЛЕНИЕ КОДА ХАРАКТЕРИСТИК:

если вы хотите записать строковое представление дерева, вы можете использовать синтаксис lisp для дерева, а затем образец строки для генерации более короткого хэш-кода.

Модуль

 Function TreeToString(Node n1) : String
        if node == null
            return ""
        String s1 = "(" + n1.toString()
        for each child of n1
            s1 = TreeToString(child)

        return s1 + ")"
 End Function

node.toString() может возвращать уникальный код метки/хэша/что угодно для этого node. Затем вы можете просто выполнить сравнение подстроки со строками, возвращаемыми функцией TreeToString, чтобы определить, эквивалентны ли деревья. Для более короткого хэш-кода просто выберите функцию TreeToString, т.е. Возьмите каждые 5 символов.

Конечный модуль

Ответ 7

Я думаю, вы могли бы сделать это рекурсивно: предположим, что у вас есть хэш-функция h, которая хеширует строки произвольной длины (например, SHA-1). Теперь хэш дерева является хешем строки, созданной как конкатенация хэша текущего элемента (для этого у вас есть собственная функция) и хэшей всех дочерних элементов этого node (из рекурсивных вызовов функции).

Для двоичного дерева вы должны:

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

Вам может потребоваться тщательная проверка правильности учета геометрии дерева. Я думаю, что с некоторыми усилиями вы могли бы получить метод, для которого обнаружение столкновений для таких деревьев может быть столь же сложным, как обнаружение столкновений в основной хэш-функции.

Ответ 8

Простое перечисление (в любом детерминированном порядке) вместе с хеш-функцией, которая зависит от посещения посетителя node, должна работать.

int hash(Node root) {
  ArrayList<Node> worklist = new ArrayList<Node>();
  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.toString(hash) + "_" + Integer.toString(place)).hash();
}

Ответ 9

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 hashcode;

  IEnumerable<TreeNode> GetChildParticipiants()
  {
   yield return this;

   foreach(var child in Children)
   {
    yield return child;

    foreach(var grandchild in child.GetParticipiants() )
     yield return grandchild;
  }
  IEnumerable<TreeNode> 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 - это функция, которая объединяет два хэш-кода, поэтому последовательность имеет значение. Я не знаю, что это такое, но вы можете понять. Вы знаете немного смещения, округления,...

Идея состоит в том, что вам нужно проанализировать некоторую среду node, в зависимости от качества, которое вы хотите достичь.

Ответ 10

Я должен сказать, что ваши требования несколько противоречат всей концепции хэш-кодов.

Сложность вычисления хэш-функции должна быть очень ограниченной.

Эта вычислительная сложность не должна линейно зависеть от размера контейнера (дерева), иначе он полностью разрушает алгоритмы на основе хэш-кода.

Рассмотрение позиции как основного свойства хэш-функции узлов также несколько противоречит концепции дерева, но достижимо, если вы замените требование, что оно должно зависеть от позиции.

Общий принцип, который я бы предложил, заменяет требования MUST с требованиями СЛЕДУЕТ. Таким образом, вы можете найти подходящий и эффективный алгоритм.

Например, рассмотрим создание ограниченной последовательности целых токенов хэш-кодов и добавим то, что вы хотите к этой последовательности, в порядке предпочтения.

Порядок элементов в этой последовательности важен, он влияет на вычисленное значение.

например, для каждого node, который вы хотите вычислить:

• добавить хэш-код базового объекта
• добавить хэш-коды базовых объектов ближайших братьев и сестер, если они доступны. Я думаю, даже одного левого брата было бы достаточно.
• добавить хэш-код базового объекта родителя и ближайших братьев и сестер, как для самого node, так же как 2.

• повторите это с бабушкой и дедушкой на ограниченной глубине.

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

  тот факт, что вы добавляете хеш-код прямого исходного объекта, связанного с сайтом, дает свойство позиционирования хэш-функции.

  Если этого недостаточно, добавьте детей: Вы должны добавить каждого ребенка, только некоторые, чтобы дать достойный хэш-код.

• добавьте первый дочерний элемент и первый ребенок и первый ребенок.. ограничьте глубину некоторой константой и не вычисляйте ничего рекурсивно - только базовый хэш-код node.

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

Таким образом, сложность линейна по отношению к глубине базового дерева, а не к общему количеству элементов.

Теперь у вас есть последовательность, если целые числа, объединить их с известным алгоритмом, как предлагает Эли выше.

1,2,... 7

Таким образом, у вас будет легкая хеш-функция с позиционным свойством, не зависящим от общего размера дерева и даже не зависящим от глубины дерева, и не требующим пересчета хэш-функции всего дерева, когда вы меняете древовидную структуру.

Готов поспорить, что эти 7 чисел будут давать хеш-жертву рядом с совершенством.

Ответ 11

Написание собственной хэш-функции почти всегда является ошибкой, потому что вам в основном нужна степень в математике, чтобы сделать это хорошо. Hashfunctions невероятно неинтуитивны и имеют очень непредсказуемые характеристики столкновения.

Не пытайтесь напрямую комбинировать хэш-коды для дочерних узлов - это увеличит любые проблемы в основных хэш-функциях. Вместо этого объедините необработанные байты из каждого node по порядку и подайте это в виде байтового потока в проверенную и хэш-функцию. Все криптографические хэш-функции могут принимать байтовый поток. Если дерево малое, вы можете просто создать массив байтов и хешировать его за одну операцию.