/Users/cpanrun/depot/main/contrib-patched/perl/CPAN/src/Bloom-Filter/blib/html/site/lib/Bloom/Filter.html

DESCRIPTION</pre>

DESCRIPTION</pre> A Bloom filter is a probabilistic algorithm for doing existence tests in less memory than a full list of keys would require. The tradeoff to using Bloom filters is a certain configurable risk of false positives. This module implements a simple Bloom filter with configurable capacity and false positive rate. Bloom filters were first described in a 1970 paper by Burton Bloom, see <a href=``http://portal.acm.org/citation.cfm?id=362692&dl=ACM&coll=portal''>http://portal.acm.org/citation.cfm. <hr /> <h1><a name=``synopsis''>SYNOPSI/a</h1> <pre> use Bloom::Filter</pre> <pre> my $bf = Bloom::Filter->new( capacity => 10, error_rate => .001 ); </pre> <pre> $bf->add( @keys ); </pre> <pre> while ( <> ) { chomp; print ``Found $_\n'' if $bf->check( $_ ); } </pre> <hr /> <h1><a name=``constructors''>CONSTRUCTOR/a</h1> <dl> <dt><a name=``new_params'' class=``item''>new %PARAM/a

<dd> Create a brand new instance. Allowable params are <a href=``#error_rate''><code>error_rate</code></a>, <a href=``#capacity''><code>capacity</code></a>. </dd> </li> <dt><a name=``init'' class=``item''>init</a>

<dd> Calculates the best number of hash functions and optimum filter length, creates some random salts, and generates a blank bit vector. Called automatically by constructor. </dd> </li> </dl> <hr /> <h1><a name=``accessors''>ACCESSOR/a</h1> <dl> <dt><a name=``capacity'' class=``item''>capacity</a>

<dd> Returns the total capacity of the Bloom filter </dd> </li> <dt><a name=``error_rate'' class=``item''>error_rate</a>

<dd> Returns the configured maximum error rate </dd> </li> <dt><a name=``length'' class=``item''>length</a>

<dd> Returns the length of the Bloom filter in bits </dd> </li> <dt><a name=``key_count'' class=``item''>key_count</a>

<dd> Returns the number of items currently stored in the filter </dd> </li> <dt><a name=``on_bits'' class=``item''>on_bits</a>

<dd> Returns the number of 'on' bits in the filter </dd> </li> <dt><a name=``salts'' class=``item''>salts</a>

<dd> Returns the list of salts used to create the hash functions </dd> </li> </dl> <hr /> <h1><a name=``public_methods''>PUBLIC METHOD/a</h1> <dl> <dt><a name=``add_keys'' class=``item''>add @KEY/a

<dd> Adds the list of keys to the filter. Will fail, return <a href=``../../../lib/pods/perlfunc.html#undef''><code>undef</code></a> and complain if the number of keys in the filter exceeds the configured capacity. </dd> </li> <dt><a name=``check_keys'' class=``item''>check @KEY/a

<dd> Checks the provided key list against the Bloom filter, and returns a list of equivalent length, with true or false values depending on whether there was a match. </dd> </li> </dl> <hr /> <h1><a name=``internal_methods''>INTERNAL METHOD/a</h1> <dl> <dt><a name=``calculate_shortest_filter_length_capacity_err_rate'' class=``item''>_calculate_shortest_filter_length CAPACITY ERR_RAT&_calculate_shortest_filter_length CAPACITY ERR_RAT;/a>

<dd> Given a desired error rate and maximum capacity, returns the optimum combination of vector length (in bits) and number of hash functions to use in building the filter, where "optimum" means shortest vector length. </dd> </li> <dt><a name=``_get_cells'' class=``item''>_get_cells KEY</a>

<dd> Given a key, hashes it using the list of salts and returns an array of cell indexes corresponding to the key. </dd> </li> </dl> <hr /> <h1><a name=``author''>AUTHOR</a></h1> Maciej Ceglowski <<a href=``mailto:maciej@ceglowski.com''>maciej@ceglowski.com> <hr /> <h1><a name=``changelog''>CHANGELOG</a></h1> Feb 2007 big speedup by Dmitriy Ryaboy <<a href=``mailto:dmitriy.ryaboy@ask.com''>dmitriy.ryaboy@ask.com> (thanks!) <hr /> <h1><a name=``copyright_and_license''>COPYRIGHT AND LICENS©RIGHT AND LICENS;/a></h1> (c) 2004 Maciej Ceglowski This is free software, distributed under version 2 of the GNU Public License (GPL).

</body>

</html>

/Users/cpanrun/depot/main/contrib-patched/perl/CPAN/src/Bloom-Filter/blib/html/site/lib/Bloom/Filter.html