Changeset 35025 in project
 Timestamp:
 01/15/18 18:11:45 (12 months ago)
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

wiki/eggref/4/bloomfilter
r34735 r35025 16 16 === makebloomfilter 17 17 18 <procedure>(makebloomfilter M MESSAGEDIGESTPRIMITIVES [K]) => bloomfilter</procedure> 19 20 Returns a bloomfilter object with {{M}} bits of discrimination and a set of hash 21 functions built from the supplied {{MESSAGEDIGESTPRIMITIVES}}, a list 22 of {{messagedigestprimitive}} objects. 23 24 The number of hashes, {{K}}, is not necessarily the same as the number 25 of messagedigests. A hash (here) is defined as an unsigned 32 bit 26 integer. Most messagedigests return more 32 bits of hash. The actual 27 length of the hash is divided into 32 bit blocks to get the individual 28 hashes. 29 30 The argument {{K}} will restrict the actual number of hashes to the 31 "first" ''K'', no matter how many more the supplied messagedigests 32 create. First in the order of {{MESSAGEDIGESTPRIMITIVES}}. 33 34 <procedure>(makebloomfilter P N MESSAGEDIGESTPRIMITIVES) => bloomfilter</procedure> 18 <procedure>(makebloomfilter M MDPS [K]) > bloomfilter</procedure> 19 20 Returns a bloomfilter object with {{M}} bits of discrimination and a set of 21 hash functions built from the supplied {{MDPS}}, a {{(listof 22 messagedigestprimitive)}} objects. 23 24 The number of hashes, {{K}}, is not necessarily the same as the number of 25 messagedigests. A hash (here) is defined as an unsigned 32 bit integer. Most 26 messagedigests return more 32 bits of hash. The actual length of the hash is 27 divided into 32 bit blocks to get the individual hashes. 28 29 The argument {{K}} will restrict the actual number of hashes to the "first" 30 ''K'', no matter how many more the supplied messagedigests create. First in 31 the order of {{MDPS}}. 32 33 <procedure>(makebloomfilter P N MDPS) > bloomfilter</procedure> 35 34 36 35 Returns a bloomfilter object with {{M}} and {{K}} values chosen for the … … 40 39 makebloomfilter. 41 40 41 === bloomfilterset! 42 43 <procedure>(bloomfilterset! BLOOMFILTER OBJECT)</procedure> 44 45 Add the specified {{OBJECT}} to the indicated {{BLOOMFILTER}}. 46 47 === bloomfilterexists? 48 49 <procedure>(bloomfilterexists? BLOOMFILTER OBJECT) > boolean</procedure> 50 51 Is the specified {{OBJECT}} in the indicated {{BLOOMFILTER}}. 52 53 === bloomfilter? 54 === checkbloomfilter 55 === errorbloomfilter 56 57 <procedure>(bloomfilter? OBJ) > boolean</procedure> 58 <procedure>(checkbloomfilter LOC OBJ [NAM]) > bloomfilter</procedure> 59 <procedure>(errorbloomfilter LOC OBJ [NAM])</procedure> 60 61 === bloomfilteralgorithms 62 63 <procedure>(bloomfilteralgorithms BLOOMFILTER) > (listof messagedigestprimitive)</procedure> 64 65 The mdps used for the filter. 66 42 67 === bloomfiltern 43 68 44 <procedure>(bloomfiltern BLOOMFILTER) => fixnum</procedure>69 <procedure>(bloomfiltern BLOOMFILTER) > fixnum</procedure> 45 70 46 71 The current population  the number of objects added to the filter. … … 50 75 === bloomfilterm 51 76 52 <procedure>(bloomfilterm BLOOMFILTER) => fixnum</procedure>77 <procedure>(bloomfilterm BLOOMFILTER) > fixnum</procedure> 53 78 54 79 The number of bits of discrimination. … … 56 81 === bloomfilterk 57 82 58 <procedure>(bloomfilterk BLOOMFILTER) => fixnum</procedure>83 <procedure>(bloomfilterk BLOOMFILTER) > fixnum</procedure> 59 84 60 85 The number of hashes. (See above.) … … 62 87 === bloomfilterpfalsepositive 63 88 64 <procedure>(bloomfilterpfalsepositive BLOOMFILTER [N]) => number</procedure>89 <procedure>(bloomfilterpfalsepositive BLOOMFILTER [N]) > number</procedure> 65 90 66 91 The probability of a falsepositive for the population capacity {{N}}, 67 92 default is the current population, {{bloomfiltern}}. 68 93 69 === bloomfilterset!70 71 <procedure>(bloomfilterset! BLOOMFILTER OBJECT)</procedure>72 73 Add the specified {{OBJECT}} to the indicated {{BLOOMFILTER}}.74 75 === bloomfilterexists?76 77 <procedure>(bloomfilterexists? BLOOMFILTER OBJECT) => boolean</procedure>78 79 Is the specified {{OBJECT}} in the indicated {{BLOOMFILTER}}.80 81 94 === actualk 82 95 83 <procedure>(actualk MESSAGEDIGESTPRIMITIVES) => fixnum</procedure> 84 85 Calculates the actual number of hashes for the 86 {{MESSAGEDIGESTPRIMITIVES}}. 96 <procedure>(actualk MDPS) > fixnum</procedure> 97 98 Calculates the actual number of hashes for the {{MDPS}}. 87 99 88 100 === optimumsize 89 101 90 <procedure>(optimumsize P N) => (fixnum fixnum)</procedure>102 <procedure>(optimumsize P N) > fixnum fixnum</procedure> 91 103 92 104 Returns 2 values, an optimal {{M}}, bits of discrimination, and {{K}}, … … 96 108 === desiredm 97 109 98 <procedure>(desiredm P N [K]) => (fixnum fixnum number)</procedure>110 <procedure>(desiredm P N [K]) > fixnum fixnum number</procedure> 99 111 100 112 Calculates a nearoptimal number of bits of discrimination to meet the … … 109 121 === optimumk 110 122 111 <procedure>(optimumk N M) => fixnum</procedure>123 <procedure>(optimumk N M) > fixnum</procedure> 112 124 113 125 Optimal count of hashes for the given population size {{N}} and {{M}} … … 116 128 === optimumm 117 129 118 <procedure>(optimumm K N) => fixnum</procedure>130 <procedure>(optimumm K N) > fixnum</procedure> 119 131 120 132 Optimal count of bits of discrimination for the given population size … … 123 135 === pfalsepositive 124 136 125 <procedure>(pfalsepositive K N M) => number</procedure>137 <procedure>(pfalsepositive K N M) > number</procedure> 126 138 127 139 What is the probability of false positives for the population size {{N}} … … 130 142 === prandomonebit 131 143 132 <procedure>(prandomonebit K N M) => number</procedure>144 <procedure>(prandomonebit K N M) > number</procedure> 133 145 134 146 Calculates the probablility of a random set bit for the given number of … … 166 178 == Version history 167 179 180 ; 1.2.0 : Add missing API. 168 181 ; 1.1.8 : Pick up the scraps. 169 182 ; 1.1.7 : Reflow. … … 180 193 == License 181 194 182 Copyright (C) 2010201 7Kon Lovett. All rights reserved.195 Copyright (C) 20102018 Kon Lovett. All rights reserved. 183 196 184 197 Permission is hereby granted, free of charge, to any person obtaining a
Note: See TracChangeset
for help on using the changeset viewer.