Impressão digital para conjuntos dinâmicos

Existe uma estrutura de dados RAM de palavras de w bits com tempo O (1) por operação para o seguinte problema ?: Manter um conjunto de números inteiros não negativos de w bits que ofereça suporte às operações

add (x): adiciona x ao conjunto
remove (x): remove x do conjunto
impressão digital (): retorna uma impressão digital do conjunto. Essa impressão digital de w bits tem a propriedade de que dois conjuntos idênticos têm a mesma impressão digital, enquanto dois conjuntos diferentes provavelmente têm impressões digitais diferentes

Todas as operações devem ser executadas em tempo constante.

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
fonte

Vejo que uma pergunta semelhante já foi publicada aqui , mas nenhuma solução em tempo constante foi fornecida.

Pat Morin

Respostas:

Esta resposta é um pouco ondulatória.

Selecione uma função uniformemente aleatoriamente no conjunto de todas as funções, de palavras em w bits a palavras em w bits. Para cada conjunto, mantenha uma impressão digital de w bits da seguinte maneira: $h$

O conjunto vazio tem a impressão digital 0.
adicione (x) e remova (x) atualize uma impressão digital para , onde é xor. $f$ $f \oplus h(x)$ $\oplus$

Seja dois conjuntos de números inteiros de w bits. Se suas impressões digitais são as mesmas, então a impressão digital de , a diferença simétrica de e , é 0, o que acontece com a probabilidade . $S \neq T$ $S \triangle T$ $S$ $T$ $2^{-w}$

jbapple
fonte

E, na prática, você pode instanciar com uma função pseudo-aleatória (PRF) da criptografia - por exemplo, algo baseado no AES. Deve ser muito eficiente e você recebe fortes promessas de que funcionará (a menos que a criptografia esteja quebrada).

h

$h$