Эффективное повторное перемешивание каната

Question

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

Теперь, когда меняется один лист верёвки, какой эффективный способ снова пересчитать хеш всей верёвки? Т.е. что-то вроде O(log n) вместо O(n).

Одним из способов было бы использовать дерево Меркле. Однако это приводит к таким проблемам, как...

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

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

Answer 1

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

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

Например, пусть узлы и значения в них будут:

    left     right    string     weight
1:                     abcd         4
2:    1        4                    4
3:                     ef           2
4:    3        5                    2
5:                     ghi          3

Полиномиальный хеш с некоторыми фиксированными константами p и q:

h (s [0] s [1]... s [n-1]) = (s [0] * p ^ (n-1) + s [1] * p ^ (n-2) +... + s [n-1] * p ^0) mod q.

Итак, у нас есть следующие хэши, все по модулю q:

         hash
1:  a*p^3 + b*p^2 + c*p^1 + d*p^0
2:  a*p^3 + b*p^2 + c*p^1 + d*p^0
3:  e*p^1 + f*p^0
4:  e*p^1 + f*p^0
5:  g*p^2 + h*p^1 + i*p^0

---

Примечание о расчете по модулю q. Здесь и далее все сложения и умножения выполняются по модулю q. Другими словами, мы работаем в кольце целых чисел по модулю q. Мы используем тот факт, что

(a? b) mod q = ((a mod q)? (b mod q)) mod q

для? операция сложение, вычитание и умножение. Таким образом, каждый раз, когда мы делаем одну из этих операций, мы немедленно добавляем mod q чтобы цифры были маленькими. Например, если p и q меньше 2³⁰ = 1 073 741 824, сложение и вычитание могут быть выполнены в 32-разрядном целочисленном типе, и умножение будет хорошо с промежуточным 64-разрядным целочисленным типом. После каждого умножения мы немедленно берем результат по модулю q, снова помещая его в 32-разрядное целое число.

---

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

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

({a* р ^ 3 + b* р ^ 2 + c* р ^ 1 + d* p ^0} * p ^ 2 + {e* р ^ 1 + f* p ^0}) * p^3 + {g* р ^ 2 + h* р ^ 1 + i* Р ^0}

Значения в фигурных скобках - это значения, хранящиеся в выходных узлах. Мы возвращаемся вправо. Когда мы встаем, мы запоминаем собранный вес, умножаем левый хэш на p на степень этого веса (откуда берутся p^3 и p^(3+2=5)) и складываем накопленный правый хеш

Полученное значение равно просто хешу всей строки:

a* р ^ 8 + b* р ^ 7 + c* р ^ 6 + d* р ^ 5 + e* р ^ 4 + f* р ^ 3 + g* р ^ 2 + h* р ^ 1 + i* Р ^0

---

Несколько заметок здесь.

1. Мы должны пересчитать, может быть, лениво, способности p по модулю q, чтобы они могли быстро умножаться на них.

2. Вся конструкция может стать более понятной, если мы сохраним хеш всего поддерева, а не только левого поддерева, в узле. Тем не менее, таким образом, мы можем потерять возможность конкатенации O(1), имеющуюся в структуре веревки, сократив ее до обычного O(log n), так что мы могли бы просто использовать обычную ловушку вместо веревки. Даже если нет, кэширование значения хеша всего поддерева в узле, безусловно, возможно.

3. Если мы перевернем порядок степеней в хеш-полиноме, сделав его
   h (s[0] s[1] ... s[n-1]) = (s[0] * p^0 + s[1] * p^1 + ... + s[n-1] * p^(n-1)) mod q,
   математика похожа, но сбор хеша от всех правых потомков узла может быть выполнен итеративно, а не рекурсивно.