bloom

package module
v0.0.0-...-75df5ec Latest Latest
Warning

This package is not in the latest version of its module.

Go to latest
Published: Sep 10, 2016 License: MIT Imports: 11 Imported by: 0

README

bloom

Standard, Scalable & partitionned bloom filter implementations. Maths for this project were coded using this implementation.


Usage

Standard
Basic usage
// 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
Merge filters
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/Import filter
// 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")
Filter fill ratio
// 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

Constants

This section is empty.

Variables

This section is empty.

Functions

This section is empty.

Types

type EncodedFilter

type EncodedFilter struct {
	Arr      []byte
	Size     uint64
	K        uint64
	Inserted uint64
}

EncodedFilter is the JSON filter structure

type Filter

type Filter struct {
	Size uint64
	// contains filtered or unexported fields
}

Filter : Implement a simple Filter

func FromFile

func FromFile(path string) (*Filter, error)

FromFile : Import filter from a file

func FromJSON

func FromJSON(raw []byte) (*Filter, error)

FromJSON : Import a JSON serialized bloom filter

func New

func New(size uint64, k uint64) *Filter

New : constructor

func (*Filter) EstimateFillRatio

func (bf *Filter) EstimateFillRatio() float64

EstimateFillRatio : Optimization of the fillRatio function, estimate instead of counting bits

func (*Filter) Feed

func (bf *Filter) Feed(s string) *Filter

Feed : Add an entry in the bloom filter

func (*Filter) FillRatio

func (bf *Filter) FillRatio() float64

FillRatio : Count each set bit into the Filter to compute the fillRatio

func (*Filter) Match

func (bf *Filter) Match(s string) bool

Match : Check if s have an entry in the filter May return false positive

func (*Filter) Merge

func (bf *Filter) Merge(oth *Filter) error

Merge two Filters, filters must have the same size Take care of fillratio when merging filters : false positive rate will increase

func (*Filter) Reset

func (bf *Filter) Reset() *Filter

Reset : zeroes the bytearray, flushing the filter

func (*Filter) ToFile

func (bf *Filter) ToFile(path string) error

ToFile : Export filter to a file

func (*Filter) ToJSON

func (bf *Filter) ToJSON() ([]byte, error)

ToJSON : Export a byte array that can be later used with bf.FromJSON

type Hasher

type Hasher func(string) uint64

Hasher : Pluggable hasher type

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

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL