Wikipédia dit:
Un filtre Bloom vide est un tableau de bits de m bits,Tous doivent être définis sur 0. Il faut également définir k fonctions de hachage différentes, chacune d'elles mappant ou hachant un élément de l'ensemble à l'une des m positions du tableau avec une distribution aléatoire uniforme.
J'ai lu l'article, mais ce que je ne comprends pas, c'est comment k est déterminé. Est-ce une fonction de la taille de la table?
En outre, dans les tables de hachage que j’ai écrites, j’ai utilisé un langage simple.algorithme efficace pour augmenter automatiquement la taille du hash. En gros, si jamais plus de 50% des seaux du tableau étaient remplis, je doublerais la taille du tableau. Je suppose que vous voudrez peut-être encore le faire avec une floraison filtre pour réduire les faux positifs.
Réponses:
39 pour la réponse № 1Donné:
n: combien d'éléments vous attendez dans votre filtre (par exemple, 216,553)p: votre taux de faux positifs acceptable {0..1} (p. ex.0.01→ 1%)
nous voulons calculer:
m: le nombre de bits nécessaires dans le filtre bloomk: le nombre de fonctions de hachage à appliquer
Les formules:
m = -n*ln(p) / (ln(2)^2) le nombre de bits
k = m/n * ln(2) le nombre de fonctions de hachage
Dans notre cas:
m=-216553*ln(0.01) / (ln(2)^2)=997263 / 0.48045=2,075,686bits (253 kB)k=m/n * ln(2)=2075686/216553 * 0.693147=6.46fonctions de hachage (7 fonctions de hachage)
Remarque: Tout code publié dans le domaine public. Aucune attribution requise.
17 pour la réponse № 2
Si vous lisez plus bas dans la Article Wikipedia sur les filtres Bloom, alors vous trouvez une section Probabilité de faux positifs. Cette section explique comment le nombre de fonctions de hachage influe sur les probabilités de faux positifs et vous donne la formule pour déterminer k à partir du prob attendu attendu. de faux positifs.
Citation de l'article Wikipedia:
De toute évidence, la probabilité de faux points positifsdiminue en m (le nombre de bits dans le tableau) augmente, et augmente comme n (le nombre d'inséré éléments) augmente. Pour un m et n, la valeur de k (le nombre de hachage fonctions) qui minimise la la probabilité est
6 pour la réponse № 3
Et de le disposer dans une jolie petite table:
http://pages.cs.wisc.edu/~cao/papers/summary-cache/node8.html
0 pour la réponse № 4
Il y a un excellent bloomfilter en ligne calculatrice.
Cette calculatrice interactive de filtres à fleurs vous permetestimer et trouver des coefficients pour vos besoins de filtre de bloom. Il vous montre également des graphiques pour voir les résultats visuellement et fournit toutes les formules Par exemple, les calculs pour 216 553 n articles avec probabilité p de 0,01:
n = ceil(m / (-k / log(1 - exp(log(p) / k))))
p = pow(1 - exp(-k / (m / n)), k)
m = ceil((n * log(p)) / log(1 / pow(2, log(2))));
k = round((m / n) * log(2));