Estou procurando uma função hash sobre os conjuntos H (.) E uma relação R (.,.) De modo que, se A for incluído em B, então R (H (A), H (B)). Obviamente, R (.,.) Deve ser fácil de verificar (tempo constante) e H (A) deve ser calculado em tempo linear.
Um exemplo de H e R é:
- , onde k é um número inteiro fixo e h (x) uma função hash sobre números inteiros.
- R (H (A), H (B)) = ((H (A) e H (B)) == H (A))
Existem outros bons exemplos? (bom é difícil de definir, mas intuitivamente se R (H (A), H (B)), então whp está incluído em B).
Edição posterior :
- Estou procurando uma família de funções de hash. Eu tenho muitos sets; 3-8 elementos em cada conjunto; 90% deles têm 3 ou 4 elementos. A função de hash de exemplo que eu dei não está muito bem distribuída para este caso.
- O número de bits de H (.) (No meu exemplo, k) que devem ser pequenos (ou seja, H (.) Devem caber em um número inteiro ou longo).
- Uma boa propriedade de R é que, se H (.) Possui k bits, então R (.,.) É verdadeiro para (3 ^ k - 2 ^ k) / 4 ^ k pares, ou seja. por muito poucos pares.
- Os filtros Bloom são especialmente bons para conjuntos grandes. Tentei usar o BF para esse problema, mas os melhores resultados foram com apenas uma função.
(crosspost do stackoverflow , não recebi uma resposta boa o suficiente)
ds.algorithms
hash-function
Alexandru
fonte
fonte
Respostas:
(Essa resposta foi originalmente nos comentários, mas estou passando para uma resposta separada, por sugestão de Suresh.)
fonte
fonte