Отпечатки пальцев для динамических наборов

Существует ли структура данных w-bit word-RAM с временем O (1) на операцию для следующей задачи ?: Поддерживать набор w-битовых неотрицательных целых чисел, который поддерживает операции

добавить (х): добавить х к набору
удалить (х): удалить х из набора
fingerprint (): вернуть отпечаток набора. Этот w-битный отпечаток обладает тем свойством, что два идентичных набора имеют одинаковый отпечаток, в то время как два разных набора, вероятно, имеют разные отпечатки

Все операции должны выполняться в постоянное время.

Схема дактилоскопии Рабина-Карпа, где где p - случайное w-битное простое число, почти работает. Проблема со временем обновления, так как вычисление занимает больше, чем постоянное время. Используя повторное возведение в квадрат, это можно сделать за O (log w). Самый быстрый модульный алгоритм возведения в степень, который я смог найти, выполняет что-то вроде (log w) / (loglog w) арифметических операций.

f (S) = (\sum_{x \in S} 2^{x}) mod p

$f(S) = \left(\sum_{x\in S} 2^x\right) \bmod p$

2^{x} mod p

$2^x \bmod p$

ds.data-structures Пэт Морин
источник

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

Пэт Морин

Ответы:

Этот ответ немного волнующий.

Выберите функцию равномерно случайным образом из набора всех функций от w-битных слов до w-битных слов. Для каждого набора сохраняйте w-битный отпечаток следующим образом: $h$

Пустой набор имеет отпечаток 0.
добавить (x) и удалить (x) обновить отпечаток пальца до , где - xor. $f$ $f \oplus h(x)$ $\oplus$

Пусть - два набора w-битных целых чисел. Если их отпечатки совпадают, то отпечаток , симметричной разности и , равен 0, что происходит с вероятностью . $S \neq T$ $S \triangle T$ $S$ $T$ $2^{-w}$

jbapple
источник

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

h

$h$