counterbloomfilter.java

自70年代被Bloom提出以来,Bloom Filters作为一种空间高效利用的紧凑数据结构

import java.security.MessageDigest;
import java.security.NoSuchAlgorithmException;
import java.io.*;
import java.util.*;

/**
 * Created by IntelliJ IDEA.
 * User: administrator
 * Date: 2005-6-3
 * Time: 13:49:24
 * To change this template use File | Settings | File Templates.
 */
public class CounterBloomfilter {
    public  int [] _bits;
    private int [] _bitscounter;
    private int collsion=0;
    private int element=0;
    //m denote the length of bitstring
    private int m;
    //n denote the capacity of this bloom filters
    private int n;
    //k denote the number of hash function used by this bloom filters
    private int k;

    //error_rate denote the designed upper bound of fasle positive probability
    private double error_rate;

    public CounterBloomfilter(int size,int capacity,int number,double error_rate)
    {
        this.m=size;
        this.n=capacity;
        this.k=number;
        this.error_rate=error_rate;
        this._bits=new int [size];
        this.initbloomfilter();              
    }

    public CounterBloomfilter()
    {
        this(500,50,5,0.01);
    }

    public void initbloomfilter()
    {
        for(int i=0;i<_bits.length;i++)
                    _bits[i]=0;
        return;
    }

    public void clearAll()
    {
        this.initbloomfilter();
        this.element=0;
        return;
    }

    public  static int unsignedShortToInt(byte[] b)
    {
        int i = 0;
        try
        {
            i |= b[0] & 0xFF;
            i <<= 8;
            i |= b[1] & 0xFF;
            i=i%Short.MAX_VALUE;
         }catch(Exception e)
         {
             i=b[0];
             System.out.println("error here");
         }
         return i;
     }

    public int[] Getindexes(String key) throws IOException, NoSuchAlgorithmException
    {
        byte buffer[] =key.getBytes("UTF-8");
        MessageDigest algorithm = MessageDigest.getInstance ("SHA-1");
        algorithm.reset();
        algorithm.update(buffer);
        byte digest[] = algorithm.digest();
        int [] idxs=new int[k];
        byte[] tempshort=new byte[2];

        for(int j=0;j<k;j++)
        {
            tempshort[0]=digest[j];
            tempshort[1]=digest[j+1];
            idxs[j]= unsignedShortToInt(tempshort);
            idxs[j]= (idxs[j]%m);
            //System.out.println ("After process ,the "+j+"th value is "+idxs[j]);
        }
        return idxs;
    }

    public void Add(String key) throws NoSuchAlgorithmException, IOException
    {
        int[] address=Getindexes(key);
        element=element+1;
        for(int i=0;i<address.length;i++)
        {
            if(_bits[address[i]]>=1)
            {
                collsion++;
                _bits[address[i]]+=1;
            }
            else
                _bits[address[i]]=1;
        }

        for(int i=0;i<address.length;i++)
        {
            int counter=0;

            if(address[i]>m)
                continue;

            for(int j=i+1;j<address.length;j++)
            {
                if(address[i]==address[j])
                {
                    counter++;
                    address[j]=m+1;
                }
            }
            if(counter>0)
            System.out.println(counter+ "hash facuntions result the same address "+address[i]);
        }
    }

    public void delete(String key) throws NoSuchAlgorithmException, IOException
    {
        if(!this.Contains(key))
            return;

        int[] temp=Getindexes(key);
        element=element-1;

        for(int i=0;i<temp.length;i++)
        {
            if(_bits[temp[i]]>1)
            {
                collsion--;
                _bits[temp[i]]-=1;
            }
            else
                _bits[temp[i]]=0;
        }
    }

    public int getCollsion()
    {
        return collsion;
    }

    public void viewcoding()
    {
        String coding="";
        for(int i=0;i<_bits.length;i++)
            coding=coding+String.valueOf(_bits[i]);
        System.out.println("The coding is "+coding);
    }

    public  int[] getCoding()
    {
        return _bits;
    }

    public void setCoding(int [] sink)
    {
        for(int i=0;i<_bits.length;i++)
            _bits[i]=sink[i];
        return;
    }

    public boolean Contains(String key) throws NoSuchAlgorithmException, IOException
    {
        int[] temp=Getindexes(key);
        for(int i=0;i<temp.length;i++)
        {
            if(_bits[temp[i]]==0)
                return false;
        }
        return true;
    }

    //看看数组的所有成员是否被当前Bloom Filters涵盖
    public boolean Contains(int [] ikey) throws NoSuchAlgorithmException, IOException
    {
        int  correctCounter=0;
        for(int lengh=0;lengh<ikey.length;lengh++)
        {
            String key=String.valueOf(ikey[lengh]);
            int[] temp=Getindexes(key);
            for(int i=0;i<temp.length;i++)
            {
                if(_bits[temp[i]]==0)
                return false;
            }
            correctCounter++;
        }
        return correctCounter==ikey.length;
    }

    /*
    public int[] getBitsCounter()
    {
        return _bitscounter;
    }
    */

    public int getElements()
    {
        return element;
    }

    public double getAverageofZero()
    {
        double percentage=GetNumberofZero()/(double) _bits.length;
        return percentage;
    }

    public int GetNumberofZero()
    {
        int numberofZero=0;
        for(int i=0;i<_bits.length;i++)
            if(_bits[i]==0)
                numberofZero++;
        return numberofZero;
    }

    public void getFrequency()
    {
        TreeMap frequency=new TreeMap();
        Integer one=new Integer(1);
        for(int i=0;i<_bits.length;i++)
        {
            Integer times=(Integer) frequency.get(new Integer(_bits[i]));
            frequency.put(new Integer(_bits[i]),times==null? one: new Integer(times.intValue()+1));
        }

        for (Iterator i=frequency.entrySet().iterator(); i.hasNext(); )
        {
            Map.Entry e = (Map.Entry) i.next();
            System.out.println(e.getKey() + ": " + e.getValue());
        }
        return;
    }

    public void queryAfterOneFour(int [] dataSet,int sizeoftestset) throws NoSuchAlgorithmException, IOException
    {
        int falsenegative=0;
        for(int j=n;j<n+sizeoftestset;j++)
            if(Contains(String.valueOf(j)))
            {
                delete(String.valueOf(j));
                break;
            }

        for(int i=0;i<dataSet.length;i++)
            if (!Contains(String.valueOf(i)))
                falsenegative++;
        statistic();
        System.out.println("After 1 wrong deletion caused by false positive, it can result in "+falsenegative+" false negative");
        return;
    }

    public void queryAfteroneFouroneAdd(int [] dataSet,int sizeoftestset) throws NoSuchAlgorithmException, IOException
    {
        statistic();
        Random r=new Random(sizeoftestset);
        int numberofDeletion=1;
        int numberofDeletion1=numberofDeletion;
        for(int i=0;i<sizeoftestset && numberofDeletion>0;i++)
        {
            int deletion=n+r.nextInt(sizeoftestset);
            if(Contains(String.valueOf(deletion)))
            {
                delete(String.valueOf(deletion));
                int [] index=Getindexes(String.valueOf(deletion));
                System.out.println("False deletion the object "+deletion+" because of a false positive");
                System.out.println("The "+k+" hash locations are:");
                
                for(int j=0;j<index.length;j++)
                    System.out.println(index[j]);
                numberofDeletion--;

                System.out.println("After deleting the data "+deletion+" because of a false positive and deletion operation");
                this.fasleNegativeExposed(dataSet);
                this.probOfFalsePositive();
            }

        }
        statistic();

        for(int i=0;i<300;i++)
        {
            int newObject=n+sizeoftestset+r.nextInt(5000);
            Add(String.valueOf(newObject));
            int [] index=Getindexes(String.valueOf(newObject));
            System.out.println("The "+k+" hash locations of new object are :");

            for(int j=0;j<index.length;j++)
                System.out.println(index[j]);

            System.out.println("After "+numberofDeletion1+" wrong deletion and add "+i+"th object "+ newObject);
            fasleNegativeExposed(dataSet);
            this.probOfFalsePositive();
        }
        statistic();
        return;
    }

    public void falseNegativeNature(int [] dataSet) throws NoSuchAlgorithmException, IOException
    {
        int  falsenegative=0;
        int  cycle=dataSet.length;
        Random r=new Random(10000);
        for(int q=0;q<cycle;q++)
        {
            int objectDeletion=r.nextInt(dataSet.length);
            for(int i=objectDeletion;i<dataSet.length-1;i++)
                dataSet[i]=dataSet[i+1];
            dataSet.

            if (Contains(String.valueOf(objectDeletion)))
                delete(String.valueOf(objectDeletion));
            else
                falsenegative++;
        }
        System.out.println(falsenegative+" false negatives were resulted in nature.");
        return;
    }

    public void fasleNegativeExposed(int [] dataSet) throws NoSuchAlgorithmException, IOException
    {
        int  falsenegative=0;
        for(int q=0;q<dataSet.length;q++)
            if (!Contains(String.valueOf(q)))
                falsenegative++;
        System.out.println(falsenegative+" false negatives were exposed.");
    }

    public void viewParameter()
    {
        System.out.println("The parameters used by this filter: ");
        System.out.println("The size of this filter: "+m);
        System.out.println("The upper threshold of the probability of false positive: "+error_rate);
        System.out.println("The number of hash functions used by this filter: "+k);
        System.out.println("The upper threshold of the size of data set: "+n);
    }

    public void statistic()
    {
        System.out.println("The size of real data set: "+this.getElements());
        System.out.println("The ration between zero bits to all bits: "+this.getAverageofZero());
        System.out.println("The number of collision: "+getCollsion());
        this.viewcoding();

        System.out.println("The distribution:");
        this.getFrequency();
    }

   /*
    public void setBitsCounter(int[] bitscounter)
    {
        _bitscounter=bitscounter;
    }
    */

    public boolean or(CounterBloomfilter sink)
    {
        int [] bitsink=sink.getCoding();
        if(_bits.length!=bitsink.length)
            return false;
        for(int i=0;i<_bits.length;i++)
            _bits[i]=(_bits[i]+bitsink[i])>1?1:(_bits[i]+bitsink[i]);

        element+=sink.getElements ();
        return true;

        //相应bit位上的Counter也要合并
        /*
        for(int i=0;i<_bitscounter.length;i++)
        {
            _bitscounter[i]+=bitscounter[i];
        }
        */
    }

    public void probOfFalsePositive()
    {
        double probability=0;
        probability=Math.pow((1-Math.pow((1-1/(double)m),element*k)),k);
        System.out.println("The probability of false positive of a BF with "+element+" datas is "+probability);
    }



    public static void main(String[] args) throws NoSuchAlgorithmException, IOException
    {
        CounterBloomfilter bf=new CounterBloomfilter(3000,300,5,0.01);

        int falsepositive=0;
        int sizeoftestset=30000;
        int falsenegative=0;
        int threshold=300;
        int [] dataSet=new int[threshold];

        for(int i=0;i<threshold;i++)
            dataSet[i]=i;

        for(int i=0;i<threshold;i++)
            bf.Add(String.valueOf(dataSet[i]));
        bf.viewParameter();
        //bf.statistic();

        bf.queryAfterOneFour(dataSet,sizeoftestset);
        //bf.queryAfteroneFouroneAdd(threshold,sizeoftestset);
        bf.falseNegativeNature(threshold);

        /*
        for(int i=0;i<threshold;i++)
            bf.Add(String.valueOf(i));
                    */
        /*
        for(int j=bf.n;j<bf.n+sizeoftestset;j++)
            if(bf.Contains(String.valueOf(j)))
            {
                falsepositive+=1;
                bf.delete(String.valueOf(j));
            }

        System.out.println("The actual percentage between wrong check and total checek: "+(double) falsepositive/sizeoftestset );
        System.out.println("The statistical result after "+falsepositive+" wrong deletion");
        bf.statistic();

        for(int i=0;i<threshold;i++)
            if (!bf.Contains(String.valueOf(i)))
                falsenegative++;
        System.out.println("After "+falsepositive+" wrong deletion caused by false positive, it can result in "+falsenegative+" false negative");

        falsepositive=0;
        for(int j=bf.n+sizeoftestset;j<bf.n+3*sizeoftestset;j++)
            if(bf.Contains(String.valueOf(j)))
                falsepositive+=1;
        System.out.println("The actual percentage between wrong check and total checek: "+(double) falsepositive/sizeoftestset);
        */
    }
}