BloomFilter32bp2


1   /* BloomFilter
2   *
3   * $Id: BloomFilter32bp2.java,v 1.2.16.1 2007/01/13 01:31:39 stack-sf Exp $
4   *
5   * Created on Jun 21, 2005
6   *
7   * Copyright (C) 2005 Internet Archive; a slight adaptation of
8   * LGPL work (C) Sebastiano Vigna
9   *
10  * This file is part of the Heritrix web crawler (crawler.archive.org).
11  *
12  * Heritrix is free software; you can redistribute it and/or modify
13  * it under the terms of the GNU Lesser Public License as published by
14  * the Free Software Foundation; either version 2.1 of the License, or
15  * any later version.
16  *
17  * Heritrix is distributed in the hope that it will be useful,
18  * but WITHOUT ANY WARRANTY; without even the implied warranty of
19  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
20  * GNU Lesser Public License for more details.
21  *
22  * You should have received a copy of the GNU Lesser Public License
23  * along with Heritrix; if not, write to the Free Software
24  * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
25  */
26  
27  package org.archive.util;
28  
29  import java.io.Serializable  ;
30  import java.security.SecureRandom  ;
31  
32  /** A Bloom filter.
33   *
34   * SLIGHTLY ADAPTED VERSION OF MG4J it.unimi.dsi.mg4j.util.BloomFilter
35   * 
36   * <p>KEY CHANGES:
37   *
38   * <ul>
39   * <li>Adapted to use 32bit ops as much as possible... may be slightly
40   * faster on 32bit hardware/OS</li>
41   * <li>Changed to use bitfield that is a power-of-two in size, allowing
42   * hash() to use bitshifting rather than modulus... may be slightly
43   * faster</li>
44   * <li>NUMBER_OF_WEIGHTS is 2083, to better avoid collisions between 
45   * similar strings</li>
46   * <li>Removed dependence on cern.colt MersenneTwister (replaced with
47   * SecureRandom) and QuickBitVector (replaced with local methods).</li>
48   * </ul>
49   * 
50   * <hr>
51   * 
52   * <P>Instances of this class represent a set of character sequences (with false positives)
53   * using a Bloom filter. Because of the way Bloom filters work,
54   * you cannot remove elements.
55   *
56   * <P>Bloom filters have an expected error rate, depending on the number
57   * of hash functions used, on the filter size and on the number of elements in the filter. This implementation
58   * uses a variable optimal number of hash functions, depending on the expected
59   * number of elements. More precisely, a Bloom
60   * filter for <var>n</var> character sequences with <var>d</var> hash functions will use
61   * ln 2 <var>d</var><var>n</var> &#8776; 1.44 <var>d</var><var>n</var> bits;
62   * false positives will happen with probability 2<sup>-<var>d</var></sup>.
63   *
64   * <P>Hash functions are generated at creation time using universal hashing. Each hash function
65   * uses {@link #NUMBER_OF_WEIGHTS} random integers, which are cyclically multiplied by
66   * the character codes in a character sequence. The resulting integers are XOR-ed together.
67   *
68   * <P>This class exports access methods that are very similar to those of {@link java.util.Set},
69   * but it does not implement that interface, as too many non-optional methods
70   * would be unimplementable (e.g., iterators).
71   *
72   * @author Sebastiano Vigna
73   */
74  public class BloomFilter32bp2 implements Serializable  , BloomFilter {
75  
76      private static final long serialVersionUID = -2292902803681146635L;
77  
78      /** The number of weights used to create hash functions. */
79      final public static int NUMBER_OF_WEIGHTS = 2083; // CHANGED FROM 16
80      /** The number of bits in this filter. */
81      final public long m; 
82      /** the power-of-two that m is */
83      final public long power; // 1<<power == m
84      /** The number of hash functions used by this filter. */
85      final public int d;
86      /** The underlying bit vectorS. */
87      final private int[] bits;
88      /** The random integers used to generate the hash functions. */
89      final private int[][] weight;
90  
91      /** The number of elements currently in the filter. It may be
92       * smaller than the actual number of additions of distinct character
93       * sequences because of false positives.
94       */
95      private int size;
96  
97      /** The natural logarithm of 2, used in the computation of the number of bits. */
98      private final static double NATURAL_LOG_OF_2 = Math.log( 2 );
99  
100     private final static boolean DEBUG = false;
101 
102     /** Creates a new Bloom filter with given number of hash functions and expected number of elements.
103      *
104      * @param n the expected number of elements.
105      * @param d the number of hash functions; if the filter add not more than <code>n</code> elements,
106      * false positives will happen with probability 2<sup>-<var>d</var></sup>.
107      */
108     public BloomFilter32bp2( final int n, final int d ) {
109         this.d = d;
110         long minBits = (long) ((long)n * (long)d / NATURAL_LOG_OF_2);
111         long pow = 0;
112         while((1L<<pow) < minBits) {
113             pow++;
114         }
115         this.power = pow;
116         this.m = 1L<<pow;
117         int len = (int) (m / 32);
118         if ( m > 1L<<32 ) {
119             throw new IllegalArgumentException  ( "This filter would require " + m + " bits" );
120         }
121         System.out.println("power "+power+" bits "+m+" len "+len);
122 
123         bits = new int[ len ];
124 
125         if ( DEBUG ) System.err.println( "Number of bits: " + m );
126 
127         // seeded for reproduceable behavior in repeated runs; BUT: 
128         // SecureRandom's default implementation (as of 1.5) 
129         // seems to mix in its own seeding.
130         final SecureRandom   random = new SecureRandom  (new byte[] {19,96});
131         weight = new int[ d ][];
132         for( int i = 0; i < d; i++ ) {
133             weight[ i ] = new int[ NUMBER_OF_WEIGHTS ];
134             for( int j = 0; j < NUMBER_OF_WEIGHTS; j++ )
135                  weight[ i ][ j ] = random.nextInt();
136         }
137     }
138 
139     /** The number of character sequences in the filter.
140      *
141      * @return the number of character sequences in the filter (but see {@link #contains(CharSequence)}).
142      */
143 
144     public int size() {
145         return size;
146     }
147 
148     /** Hashes the given sequence with the given hash function.
149      *
150      * @param s a character sequence.
151      * @param l the length of <code>s</code>.
152      * @param k a hash function index (smaller than {@link #d}).
153      * @return the position in the filter corresponding to <code>s</code> for the hash function <code>k</code>.
154      */
155     private int hash( final CharSequence   s, final int l, final int k ) {
156         final int[] w = weight[ k ];
157         int h = 0, i = l;
158         while( i-- != 0 ) h ^= s.charAt( i ) * w[ i % NUMBER_OF_WEIGHTS ];
159         return h >>> (32-power); 
160     }
161 
162     /** Checks whether the given character sequence is in this filter.
163      *
164      * <P>Note that this method may return true on a character sequence that is has
165      * not been added to the filter. This will happen with probability 2<sub>-<var>d</var></sub>,
166      * where <var>d</var> is the number of hash functions specified at creation time, if
167      * the number of the elements in the filter is less than <var>n</var>, the number
168      * of expected elements specified at creation time.
169      *
170      * @param s a character sequence.
171      * @return true if the sequence is in the filter (or if a sequence with the
172      * same hash sequence is in the filter).
173      */
174 
175     public boolean contains( final CharSequence   s ) {
176         int i = d, l = s.length();
177         while( i-- != 0 ) if ( ! getBit( hash( s, l, i ) ) ) return false;
178         return true;
179     }
180 
181     /** Adds a character sequence to the filter.
182      *
183      * @param s a character sequence.
184      * @return true if the character sequence was not in the filter (but see {@link #contains(CharSequence)}).
185      */
186 
187     public boolean add( final CharSequence   s ) {
188         boolean result = false;
189         int i = d, l = s.length();
190         int h;
191         while( i-- != 0 ) {
192             h = hash( s, l, i );
193             if ( ! getBit( h ) ) result = true;
194             setBit( h );
195         }
196         if ( result ) size++;
197         return result;
198     }
199     
200     protected final static int ADDRESS_BITS_PER_UNIT = 5; // 32=2^5
201     protected final static int BIT_INDEX_MASK = 31; // = BITS_PER_UNIT - 1;
202 
203     /**
204      * Returns from the local bitvector the value of the bit with 
205      * the specified index. The value is <tt>true</tt> if the bit 
206      * with the index <tt>bitIndex</tt> is currently set; otherwise, 
207      * returns <tt>false</tt>.
208      *
209      * (adapted from cern.colt.bitvector.QuickBitVector)
210      * 
211      * @param     bitIndex   the bit index.
212      * @return    the value of the bit with the specified index.
213      */
214     protected boolean getBit(int bitIndex) {
215         return ((bits[(int)(bitIndex >>> ADDRESS_BITS_PER_UNIT)] & (1 << (bitIndex & BIT_INDEX_MASK))) != 0);
216     }
217 
218     /**
219      * Changes the bit with index <tt>bitIndex</tt> in local bitvector.
220      *
221      * (adapted from cern.colt.bitvector.QuickBitVector)
222      * 
223      * @param     bitIndex   the index of the bit to be set.
224      */
225     protected void setBit(int bitIndex) {
226             bits[(int)(bitIndex >>> ADDRESS_BITS_PER_UNIT)] |= 1 << (bitIndex & BIT_INDEX_MASK);
227     }
228     
229     /* (non-Javadoc)
230      * @see org.archive.util.BloomFilter#getSizeBytes()
231      */
232     public long getSizeBytes() {
233         return bits.length*4;
234     }
235 }
236
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags