"{ Encoding: utf8 }"

"

 COPYRIGHT (c) 2019 by Claus Gittinger

              All Rights Reserved

 This software is furnished under a license and may be used

 only in accordance with the terms of that license and with the

 inclusion of the above copyright notice.   This software may not

 be provided or otherwise made available to, or used by, any

 other person.  No title to or ownership of the software is

 hereby transferred.

"

"{ Package: 'stx:libbasic2' }"

"{ NameSpace: Smalltalk }"

Collection subclass:#BloomFilter

	instanceVariableNames:'bits hashingBlocks tally'

	classVariableNames:''

	poolDictionaries:''

	category:'Collections-Unordered'

!

!BloomFilter class methodsFor:'documentation'!

copyright

"

 COPYRIGHT (c) 2019 by Claus Gittinger

              All Rights Reserved

 This software is furnished under a license and may be used

 only in accordance with the terms of that license and with the

 inclusion of the above copyright notice.   This software may not

 be provided or otherwise made available to, or used by, any

 other person.  No title to or ownership of the software is

 hereby transferred.

"

!

documentation

"

    a BloomFilter (see eg. https://de.wikipedia.org/wiki/Bloomfilter)

    is a Set-like data structure which can quickly answer whether

    an element is definitely NOT in the set, but might generate false positives

    (i.e. it might answer true, although the element is not actually present).

    Bloom filters are used for tuning, when accesses (eg. to the disk or database)

    are expensive, and can be avoided in many cases (in the NOT present case),

    and false positives only lead to additional useless queries.

    Bloom filters cannot remove or enumerate elements. 

    The only useful operations are adding and inclusion testing (includes).

    For example, a database query (eg. 'is something present'), 

    might make use of a bloom filter, to avoid the query in many cases.

    Bloom filters false positive rate degrades as the number of elements is added,

    thus a good choice of its initial size is mandatory.

"

!

examples

"<<END

[exBegin]

    |filter set nFalsePositive|

    filter := BloomFilter new:10000.

    set := Set new:10000.

    "/ add all words from the Collection class's source code

    Collection sourceStream 

        linesDo:[:eachLine |

            eachLine 

               splitOn:[:ch | ch isSeparator]

               do:[:word | 

                  filter add:word.

                  set add:word.

               ].

        ];

        close.

    "/ check some which are known to be present

    set do:[:w |

        self assert:(filter includes:w)

    ].    

    "/ check for false positives

    nFalsePositive :=

        (1 to:1000) count:[:n |

            |randomWord isFalsePositive|

            isFalsePositive := false.

            randomWord := (1 to:6) collect:[:i | ($a to: $z) atRandom] as:String.

            (set includes:randomWord) ifFalse:[

                (filter includes:randomWord) ifTrue:[

                    Transcript showCR:'false positive: ',randomWord.

                    isFalsePositive := true.

                ].    

            ].

            isFalsePositive

        ].

    Transcript show:nFalsePositive; showCR:' false positives'.

    filter inspect.

[exEnd]

END>>"

! !

!BloomFilter class methodsFor:'instance creation'!

new:initialNumberOfBits

    ^ self 

        new:initialNumberOfBits 

        hashes:{

            [:s | s hash_fnv1a] .

            [:s | s hash_sdbm] .

        }

    "Created: / 10-02-2019 / 14:14:23 / Claus Gittinger"

!

new:initialNumberOfBits hashes:hashActionBlocks

    ^ super new 

        numberOfBits:initialNumberOfBits 

        hashes:hashActionBlocks

    "Created: / 10-02-2019 / 14:13:05 / Claus Gittinger"

! !

!BloomFilter methodsFor:'adding'!

add:aString

    "add the arguemnt, aString to the set"

    |mod isNew|

    mod := bits size.

    isNew := false.

    hashingBlocks do:[:each |

        |h idx|

        h := each value:aString.

        idx := (h \\ mod)+1.

        (bits at:idx) == 0 ifTrue:[ isNew := true ].

        bits at:idx put:1.

    ].

    isNew ifTrue:[

        tally := tally + 1

    ].

    "Created: / 10-02-2019 / 14:16:29 / Claus Gittinger"

! !

!BloomFilter methodsFor:'blocked'!

do:aBlock

    self shouldNotImplement

    "Created: / 10-02-2019 / 14:40:17 / Claus Gittinger"

!

remove:aString

    "raise an error - elements cannot be removed"

    self shouldNotImplement

    "Created: / 10-02-2019 / 14:18:14 / Claus Gittinger"

! !

!BloomFilter methodsFor:'initialization'!

numberOfBits:initialNumberOfBits hashes:hashingBlocksArg

    bits := BitArray new:(initialNumberOfBits nextPrime).

    hashingBlocks := hashingBlocksArg.

    tally := 0.

    "Created: / 10-02-2019 / 14:15:10 / Claus Gittinger"

! !

!BloomFilter methodsFor:'queries'!

includes:aString

    "returns false, if the arguemnt, aString is definitly NOT in the set.

     However, it may return true as a false positive"

    |mod|

    mod := bits size.

    hashingBlocks do:[:each |

        |h|

        h := each value:aString.

        (bits at:(h \\ mod)+1) == 0 ifTrue:[^ false].

    ].

    ^ true

    "Created: / 10-02-2019 / 14:16:59 / Claus Gittinger"

! !

!BloomFilter class methodsFor:'documentation'!

version_CVS

    ^ '$Header$'

! !