Sidik jari untuk set dinamis

Apakah ada struktur data kata-RAM w-bit dengan O (1) waktu per operasi untuk masalah berikut ?: Memelihara serangkaian bilangan bulat non-negatif w-bit yang mendukung operasi

add (x): add x ke set
remove (x): hapus x dari set
sidik jari (): mengembalikan sidik jari set. Sidik jari w-bit ini memiliki properti yang dua set yang identik memiliki sidik jari yang sama, sedangkan dua set yang berbeda mungkin memiliki sidik jari yang berbeda.

Semua operasi harus berjalan dalam waktu yang konstan.

Skema sidik jari Rabin-Karp, di mana mana p adalah prime w-bit acak hampir berfungsi. Masalahnya dengan waktu pembaruan, karena komputasi membutuhkan lebih dari waktu yang konstan. Menggunakan kuadrat berulang, ini bisa dilakukan dalam waktu O (log w). Algoritma eksponensial modular tercepat yang dapat saya temukan melakukan sesuatu seperti (log w) / (loglog w) operasi aritmatika.

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 Pat Morin
sumber

Saya melihat bahwa pertanyaan serupa sudah diposting di sini , tetapi tidak ada solusi waktu konstan yang diberikan.

Pat Morin

Jawaban:

Jawaban ini agak lamban.

Pilih fungsi seragam secara acak dari himpunan semua fungsi dari kata w-bit ke kata w-bit. Untuk setiap set, pertahankan sidik jari w-bit sebagai berikut: $h$

Set kosong memiliki sidik jari 0.
tambah (x) dan hapus (x) perbarui sidik jari ke , di mana adalah xor. $f$ $f \oplus h(x)$ $\oplus$

Biarkan menjadi dua set bilangan bulat w-bit. Jika sidik jari mereka sama, maka sidik jari , perbedaan simetris dan , adalah 0, yang terjadi dengan probabilitas . $S \neq T$ $S \triangle T$ $S$ $T$ $2^{-w}$

jbapple
sumber

Dan dalam praktiknya Anda bisa instantiate dengan fungsi pseudorandom (PRF) dari kriptografi - misalnya, sesuatu yang didasarkan pada AES. Harus sangat efisien, dan Anda mendapat janji kuat bahwa itu akan berhasil (kecuali crypto rusak).

h

$h$