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

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

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

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

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

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

Если вы не хотите обходить все дерево:

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

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

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

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

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

Узел из слоя выбирается по правилу H mod n.

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

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

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

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

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

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

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

Hash( h(nodee->data) || Hash(nodee->left) || Hash(nodee->right) ).

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

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

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

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

TREE COMPARISON:

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

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

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

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

4. Затем просто заходите в каждый узел дерева, сравнивая, и возвращаете false в случае неудачи сравнения, т.е.

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

End Module

HASH CODE GENERATION:

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

Module

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

End Module

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

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();
}

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<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 - это функция, которая объединяет два хэшкода, поэтому последовательность имеет значение. Я не знаю, что это такое, но вы можете разобраться. Некоторое смещение, округление...

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

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

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

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

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

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

Скажем, у вас 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/

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

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

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

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

Общий принцип, который я бы предложил, заключается в замене ДОЛЖНЫХ требований на ДОЛЖНЫЕ требования. Таким образом, можно придумать подходящий и эффективный алгоритм.

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

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

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

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

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

   //-------- 5------- глубина предка 2 и это левый брат и сестра;
   //-------/|------- ;
   //------ 4-3------- глубина 1 и это левый брат и сестра; 
   //-------/|------- ;
   //------ 2-1------- это;
   

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

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

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

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

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

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

1,2,.... 7

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

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

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

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

Всякий раз, когда вы работаете с рекурсивностью деревьев, следует помнить:

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

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

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

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

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

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

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