Хеширование корневых деревьев

Задача

Хотим научиться сравнивать корневые деревья на изоморфизм (равенство с точностью до перенумерования вершин + корень одного дерева обязательно переходит в корень другого дерева).

Хеш вершины

Заметим, что поскольку мы не можем аппелировать к номерам вершин, единственная информация, которую мы можем оперировать $~-$ это структура нашего дерева.

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

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

Полиномиальный хеш не подходит

Рассмотрим 2 дерева: $T_1 = \{ (1 2), (1 3), (1 4) \}$ и $T_2 = \{ (1 2), (1 3), (3 4), (3 5) \}$. Если мы посчитаем для них в качестве функции от детей взять полиномиальный хеш, то получим:

$$ h(T_1) = 179 + 179p + 179p^2 = 179 + p(179 + 179p) = h(T_2) $$

Какую же хеш-функцию взять?

В качестве хорошей хеш-функции подойдёт, например

$$ h(v) = 42 + \sum_{u \in sorted\_by\_hash(child(v))} log(h(u)) $$

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

Пример более complicated хеш-функции: $$ h(v) = \big[\sum_{u \in sorted\_by\_hash(child(v))} h(u)^2 + h(u) p^i + 42 \big] \mod 2^{64} $$

Асимптотика

Всё что нам нужно делать на каждом уровне $~-$ это сортировка вершин по размеру хеша и суммирование, так что итоговая сложность: $O(|V| log(|V|))$

---

Автор конспекта: Александр Гришутин

По всем вопросам пишите в telegram @rationalex