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

Question

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

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

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

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

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

Answer 1

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

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

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

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

Полином хэш, с некоторой фиксированной константы р и д:

ч (с [0] с [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. Другими словами, мы работаем в ring of integers по модулю q. Мы используем тот факт, что

(а? Б) по модулю Q = ((мод д)? (Б мод д)) по модулю д

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

---

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

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

({a * р^3 + b * р^2 + c * р^1 + d * р^0} * р^2 + {e * р^1 + f * р = 0}) * р^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. Мы предвычислять, возможно, лениво, полномочия р по модулю д, чтобы иметь возможность умножить на них быстро.

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

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