README
¶
bloom
Standard, Scalable & partitionned bloom filter implementations.
Maths for this project were coded using this implementation.
Usage
Standard
// Create a new Filter of 512 bytes using 5 different hash functions
bf := bloom.New(512, 5)
// Insert element in the filter
bf.Feed("An item")
// Query for an element membership
bf.Match("An item")
// true
bf.Match("Another item")
// false
bf := bloom.New(512, 5)
oth := bloom.New(512, 5)
bf.Feed("foo")
oth.Feed("bar")
bf.Merge(oth)
bf.Match("foo") && bf.Match("bar")
/// true
// Export filter as []byte for exportation
bytes, _ := bf.ToJSON()
// Export directly to filesystem (as json)
err := bf.ToFile("file.json")
Filters can then be imported with :
// Import directly from JSON bytes
bf, err := bloom.FromJSON(bytes)
// Import directly from filesystem (as json)
bf, err := bloom.FromFile("file.json")
// Average ratio of bits set to 1; count each bit of the underlying array
// Might cause slowdown if used too much
bf.FillRatio()
// Optimization of the function above, estimate instead of counting
bf.EstimateFillRatio()
Both functions return a float64 between 0 and 1.
Please keep in mind that EstimateFillRatio yield an approximate ratio, if you need precision below ~0.1, consider using directly FillRatio.
Scalable
bf := bloom.NewScalableDefault()
Documentation
¶
Overview ¶
Package bloom package implement a simple and scalable Bloom Filter algorithm
Index ¶
- type EncodedFilter
- type Filter
- func (bf *Filter) EstimateFillRatio() float64
- func (bf *Filter) Feed(s string) *Filter
- func (bf *Filter) FillRatio() float64
- func (bf *Filter) Match(s string) bool
- func (bf *Filter) Merge(oth *Filter) error
- func (bf *Filter) Reset() *Filter
- func (bf *Filter) ToFile(path string) error
- func (bf *Filter) ToJSON() ([]byte, error)
- type Hasher
- type ScalableFilter
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type EncodedFilter ¶
EncodedFilter is the JSON filter structure
type Filter ¶
type Filter struct {
Size uint64
// contains filtered or unexported fields
}
Filter : Implement a simple Filter
func (*Filter) EstimateFillRatio ¶
EstimateFillRatio : Optimization of the fillRatio function, estimate instead of counting bits
func (*Filter) Merge ¶
Merge two Filters, filters must have the same size Take care of fillratio when merging filters : false positive rate will increase
type ScalableFilter ¶
type ScalableFilter struct {
// contains filtered or unexported fields
}
ScalableFilter can handle situation where filter total number of elements is undetermined at instantiation Params: s: Growth rate, each new filter will be (size_prev_filter) * s P: false positive maximum probability m0: size of the initial filter r: tightning ratio, like 's' but for false positive precision
func NewDefaultScalable ¶
func NewDefaultScalable(p float64) *ScalableFilter
NewDefaultScalable create a new ScalableFilter with default arguments More details on arguments : http://gsd.di.uminho.pt/members/cbm/ps/dbloom.pdf
func NewScalable ¶
func NewScalable(p float64, s float64, m0 uint64, r float64) *ScalableFilter
NewScalable Create a new ScalableFilter
func (*ScalableFilter) Feed ¶
func (sbf *ScalableFilter) Feed(s string) *ScalableFilter
Feed : Add an entry in the scalable bloom filter
func (*ScalableFilter) Match ¶
func (sbf *ScalableFilter) Match(s string) bool
Match : Check if s have an entry in the filter May return false positive
Source Files