Hachage d'ensembles d'entiers pour les tests d'inclusion

Je recherche une fonction de hachage sur les ensembles H (.) Et une relation R (.,.) Telle que si A est inclus dans B alors R (H (A), H (B)). Bien sûr, R (.,.) Doit être facile à vérifier (temps constant), et H (A) doit être calculé en temps linéaire.

Un exemple de H et R est:

$H(A) = \bigvee_{x\in A} 1 << (h(x) \mod k)$ , où k est un entier fixe et h (x) une fonction de hachage sur des entiers.
R (H (A), H (B)) = ((H (A) & H (B)) == H (A))

Y a-t-il d'autres bons exemples? (bien est difficile à définir mais intuitivement si R (H (A), H (B)) alors whp A est inclus dans B).

Modification ultérieure :

Je recherche une famille de fonctions de hachage. J'ai beaucoup d'ensembles; 3 à 8 éléments dans chaque ensemble; 90% d'entre eux ont 3 ou 4 éléments. L'exemple de fonction de hachage que j'ai donné n'est pas très bien distribué dans ce cas.
Le nombre de bits de H (.) (Dans mon exemple, k) qui devrait être petit (c'est-à-dire H (.) Doit tenir dans un entier ou long).
Une belle propriété de R est que si H (.) A k bits, alors R (.,.) Est vrai pour les paires (3 ^ k - 2 ^ k) / 4 ^ k, c'est-à-dire. pour très peu de paires.
Les filtres Bloom sont particulièrement bons pour les grands ensembles. J'ai essayé d'utiliser BF pour ce problème, mais les résultats optimaux étaient avec une seule fonction.

(crosspost de stackoverflow , je n'ai pas reçu une réponse assez bonne)

ds.algorithms hash-function Alexandru
la source

"whp" sur quoi? Supposez-vous que vos contributions proviennent d'une certaine distribution?

Jukka Suomela

Et cherchez-vous vraiment une seule fonction de hachage fixe et non une famille de fonctions de hachage?

Jukka Suomela

@Jukka: Je pense qu'il veut dire que si R (H (A), H (B)), alors avec une forte probabilité, nous concluons que A est un sous-ensemble de B. La probabilité est prise sur des choix aléatoires de A et B, ainsi que lancer de pièces internes de H et R (le cas échéant).

MS Dousti

Je recherche une famille de fonctions de hachage. Mes ensembles ont tendance à être petits (3 à 8 éléments chacun; 90% d'entre eux ont 3 ou 4 éléments), donc l'exemple de fonction de hachage que j'ai donné n'est pas très bien distribué.

Alexandru

Une belle propriété de R est que si H (.) A n bits, alors R (.,.) Est vrai pour (3 ^ n - 2 ^ n) / 4 ^ n paires, c'est-à-dire. pour très peu de paires.

Alexandru

Réponses:

(Cette réponse était à l'origine dans les commentaires, mais je la déplace vers une réponse distincte à la suggestion de Suresh.)

Pour votre application avec de très petits ensembles, vous souhaiterez probablement que le nombre de fonctions de hachage Bloom soit assez grand pour minimiser le nombre de faux positifs. Pour gagner du temps de calcul, je suggère la variation suivante d'un filtre Bloom. Supposons que vous ayez trois fonctions de hachage traditionnelles , , pour les éléments qui produisent chacun des chaînes de bits. Hachez chaque élément au niveau du bit et de ces trois fonctions de hachage. Les hachages d'élément résultants seront d'environ $k$ $h_1$ $h_2$ $h_3$ $m$ $2^{-3}=1/8^{th}$ ceux. Hachez chaque jeu au niveau du bit ou des hachages de ses éléments constitutifs. Parce que vos ensembles ont 3 à 8 éléments, les hachages résultants seront au voisinage de la moitié de ceux, ce qui est probablement ce que vous voulez le mieux pour réduire le taux de faux positifs.

La différence entre le schéma ci-dessus est que le filtre de Bloom traditionnel est analogue à la différence entre le modèle de graphique aléatoire Erdos classique et les graphiques aléatoires réguliers. Le schéma ci - dessus a le nombre effectif de hash Bloom varie un peu autour de sa moyenne de mais est assez grand pour cette différence ne devrait pas importer. $G_{n,p}$ $d$ $k$ $m/8$ $m/8$

Warren Schudy
la source

C'est particulièrement bon pour les grands m (32 ou 64) comme vous l'avez suggéré.

Alexandru

J'essaierais d'utiliser un filtre Bloom comme hachage avec la même relation que votre proposition. Le calcul de la meilleure taille de filtre et du nombre de fonctions de hachage pour votre application ne devrait pas être trop difficile; voir l' article Bloom Filter de Wikipedia pour l'inspiration. Selon la façon dont vous voulez éviter les faux positifs, quelque chose comme et pourrait suffire. $m$ $k$ $m=64$ $k=4$

Warren Schudy
la source

Pour votre application avec de très petits ensembles, vous voudrez probablement assez grand. Cela peut être assez lent avec l'approche traditionnelle. Je suggère plutôt ce qui suit.

k

$k$

Warren Schudy

(Suite du commentaire précédent) Il s'agit essentiellement d'une variante des filtres Bloom. Supposons que vous ayez trois fonctions de hachage , , pour les éléments qui produisent des chaînes de bits. Hachez un élément au niveau du bit et de ces trois. Les hachages résultants auront environ 1 / 8ème 1s. Hachage d'un ensemble au niveau du bit ou des hachages de ses éléments constitutifs. Parce que vos ensembles ont 3 à 8 éléments, les hachages résultants auront la moitié de ceux, ce qui contribuera probablement à réduire le taux de faux positifs.

h_{1}

$h_1$

h_{2}

$h_2$

h_{3}

$h_3$

m

$m$

Warren Schudy

L'avantage de cette variation est seulement qu'elle fait un meilleur usage du parallélisme inhérent aux opérations de mots que la plupart des ordinateurs ont.

Warren Schudy

Warren, vous devriez poster ceci comme réponse. Il mérite quelques votes

Suresh Venkat

@Warren, @Suresh: Je pense qu'il serait plus logique de combiner ces deux réponses étroitement liées, puis de supprimer les commentaires. Il serait plus facile à suivre, d'autant plus que l'une des réponses fait référence à des paramètres définis dans l'autre.

Jukka Suomela