• DESCRIPTION</PRE>

DESCRIPTION</PRE> <P>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.</P> <P> <HR> <H1><A NAME=``synopsis''>SYNOPSI/A</H1> <PRE> use Bloom::Filter</PRE> <PRE> my $bf = Bloom::Filter-&gt;new( capacity =&gt; 10, error_rate =&gt; .001 );</PRE> <PRE> $bf-&gt;add( @keys );</PRE> <PRE> while ( &lt;&gt; ) { chomp; print &quot;Found $_\n&quot; if $bf-&gt;check( $_ ); }</PRE> <P> <HR> <H1><A NAME=``constructors''>CONSTRUCTOR/A</H1> <DL> <DT><STRONG><A NAME=``item_new_%25PARAMS''>new %PARAM/A</STRONG><BR> <DD> Create a brand new instance. Allowable params are <A HREF=``#item_error_rate''><CODE>error_rate</CODE></A>, <A HREF=``#item_capacity''><CODE>capacity</CODE></A>. <P></P> <DT><STRONG><A NAME=``item_init''>init</A></STRONG><BR> <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. <P></P></DL> <P> <HR> <H1><A NAME=``accessors''>ACCESSOR/A</H1> <DL> <DT><STRONG><A NAME=``item_capacity''>capacity</A></STRONG><BR> <DD> Returns the total capacity of the Bloom filter <P></P> <DT><STRONG><A NAME=``item_error_rate''>error_rate</A></STRONG><BR> <DD> Returns the configured maximum error rate <P></P> <DT><STRONG><A NAME=``item_length''>length</A></STRONG><BR> <DD> Returns the length of the Bloom filter in bits <P></P> <DT><STRONG><A NAME=``item_key_count''>key_count</A></STRONG><BR> <DD> Returns the number of items currently stored in the filter <P></P> <DT><STRONG><A NAME=``item_on_bits''>on_bits</A></STRONG><BR> <DD> Returns the number of 'on' bits in the filter <P></P> <DT><STRONG><A NAME=``item_salts''>salts</A></STRONG><BR> <DD> Returns the list of salts used to create the hash functions <P></P></DL> <P> <HR> <H1><A NAME=``public methods''>PUBLIC METHOD/A</H1> <DL> <DT><STRONG><A NAME=``item_add_%40KEYS''>add @KEY/A</STRONG><BR> <DD> Adds the list of keys to the filter. Will fail, return <CODE>undef</CODE> and complain if the number of keys in the filter exceeds the configured capacity. <P></P> <DT><STRONG><A NAME=``item_check_%40KEYS''>check @KEY/A</STRONG><BR> <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. <P></P></DL> <P> <HR> <H1><A NAME=``internal methods''>INTERNAL METHOD/A</H1> <DL> <DT><STRONG><A NAME=``item__calculate_shortest_filter_length_CAPACITY_ERR_RAT''>_calculate_shortest_filter_length CAPACITY ERR_RAT&_calculate_shortest_filter_length CAPACITY ERR_RAT;/A></STRONG><BR> <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. <P></P> <DT><STRONG><A NAME=``item__get_cells_KEY''>_get_cells KEY</A></STRONG><BR> <DD> Given a key, hashes it using the list of salts and returns an array of cell indexes corresponding to the key. <P></P></DL> <P> <HR> <H1><A NAME=``author''>AUTHOR</A></H1> <P>Maciej Ceglowski &lt;<A HREF=``mailto:maciej@ceglowski.com''>maciej@ceglowski.com&gt;</P> <P> <HR> <H1><A NAME=``changelog''>CHANGELOG</A></H1> <P>Feb 2007 big speedup by Dmitriy Ryaboy &lt;<A HREF=``mailto:dmitriy.ryaboy@ask.com''>dmitriy.ryaboy@ask.com&gt; (thanks!)</P> <P> <HR> <H1><A NAME=``copyright and license''>COPYRIGHT AND LICENS©RIGHT AND LICENS;/A></H1> <P>(c) 2004 Maciej Ceglowski</P> <P>This is free software, distributed under version 2 of the GNU Public License (GPL).</P> <TABLE BORDER=0 CELLPADDING=0 CELLSPACING=0 WIDTH=100%> <TR><TD CLASS=block VALIGN=MIDDLE WIDTH=100% BGCOLOR=``#cccccc''> <FONT SIZE=+1><STRONG><P CLASS=block>&nbsp;Bloom::Filter - Sample Perl Bloom filter implementation</P></STRONG></FONT> </TD></TR> </TABLE>

</BODY>

</HTML>