Fingerabdruck für dynamische Sets

Gibt es eine W-Bit-Wort-RAM-Datenstruktur mit O (1) Zeit pro Operation für das folgende Problem?: Behalten Sie einen Satz nicht negativer W-Bit-Ganzzahlen bei, die die Operationen unterstützen

add (x): füge x zur Menge hinzu
remove (x): entferne x aus dem Set
fingerprint (): Gibt einen Fingerabdruck des Sets zurück. Dieser W-Bit-Fingerabdruck hat die Eigenschaft, dass zwei identische Sätze denselben Fingerabdruck haben, während zwei unterschiedliche Sätze wahrscheinlich unterschiedliche Fingerabdrücke haben

Alle Operationen sollten in konstanter Zeit ausgeführt werden.

Das Rabin-Karp-Fingerabdruckschema, bei dem wobei p eine zufällige w-Bit-Primzahl ist, funktioniert fast. Das Problem liegt in der Aktualisierungszeit, da die Berechnung von mehr als konstante Zeit in nimmt. Durch wiederholtes Quadrieren kann dies in O (log w) -Zeit erfolgen. Der schnellste modulare Exponentiationsalgorithmus, den ich finden konnte, führt so etwas wie (log w) / (loglog w) arithmetische Operationen aus.

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
quelle

Ich sehe, dass hier bereits eine ähnliche Frage gestellt wurde , aber keine zeitkonstante Lösung angegeben wurde.

Pat Morin

Antworten:

Diese Antwort ist ein bisschen handgewellt.

Wählen Sie eine Funktion gleichmäßig zufällig aus der Menge aller Funktionen von W-Bit-Wörtern bis W-Bit-Wörtern. Pflegen Sie für jeden Satz einen W-Bit-Fingerabdruck wie folgt: $h$

Der leere Satz hat den Fingerabdruck 0.
addiere (x) und entferne (x) aktualisiere einen Fingerabdruck zu , wobei xor ist. $f$ $f \oplus h(x)$ $\oplus$

Sei zwei Sätze von w-Bit-Ganzzahlen. Wenn ihre Fingerabdrücke gleich sind, ist der Fingerabdruck von , die symmetrische Differenz von und , 0, was mit einer Wahrscheinlichkeit von geschieht . $S \neq T$ $S \triangle T$ $S$ $T$ $2^{-w}$

jbapple
quelle

Und in der Praxis könnten Sie mit einer Pseudozufallsfunktion (PRF) aus der Kryptographie instanziieren - z. B. etwas, das auf AES basiert. Sollte sehr effizient sein und Sie erhalten starke Versprechungen, dass es funktionieren wird (es sei denn, die Krypto ist kaputt).

h

$h$