\seekquarry\yioop\libraryBloomFilterFile

Code used to manage a bloom filter in-memory and in file.

A Bloom filter is used to store a set of objects. It can support inserts into the set and it can also be used to check membership in the set.

Summary

Methods
Properties
Constants
__construct()
load()
save()
checkSave()
add()
contains()
getHashBitPositionArray()
setBit()
getBit()
$filename
$unsaved_operations
$save_frequency
$num_keys
$count
$filter_size
$filter
DEFAULT_SAVE_FREQUENCY
No protected methods found
No protected properties found
N/A
No private methods found
No private properties found
N/A

Constants

DEFAULT_SAVE_FREQUENCY

DEFAULT_SAVE_FREQUENCY

If not specified in the constructor, this will be the number of operations between saves

Properties

$filename

$filename : string

Name of the file in which to store the PersistentStructure

Type

string

$unsaved_operations

$unsaved_operations : integer

Number of operations since the last save

Type

integer

$save_frequency

$save_frequency : integer

Number of operation between saves. If == -1 never save using checkSave

Type

integer

$num_keys

$num_keys : integer

Number of bit positions in the Bloom filter used to say an item is in the filter

Type

integer

$count

$count : integer

Number of items currently stored in this filter

Type

integer

$filter_size

$filter_size : integer

Size in bits of the packed string array used to store the filter's contents

Type

integer

$filter

$filter : string

Packed string used to store the Bloom filters

Type

string

Methods

__construct()

__construct(string  $fname, integer  $num_values, integer  $save_frequency = self::DEFAULT_SAVE_FREQUENCY) 

Initializes the fields of the BloomFilter and its base PersistentStructure.

Parameters

string $fname

name of the file to store the BloomFilter data in

integer $num_values

the maximum number of values that will be stored in the BloomFilter. Filter will be sized so the odds of a false positive are roughly one over this value

integer $save_frequency

how often to store the BloomFilter to disk

load()

load(string  $fname) : object

Load a PersistentStructure from a file

Parameters

string $fname

the name of the file to load the PersistentStructure from

Returns

object —

the PersistentStructure loaded

save()

save() 

Save the PersistentStructure to its filename This method is generic but super memory inefficient, so reimplement for subclasses is needed

checkSave()

checkSave() 

Add one to the unsaved_operations count. If this goes above the save_frquency then save the PersistentStructure to secondary storage

add()

add(string  $value) 

Inserts the provided item into the Bloomfilter

Parameters

string $value

item to add to filter

contains()

contains(string  $value) : boolean

Checks if the BloomFilter contains the provided $value

Parameters

string $value

item to check if is in the BloomFilter

Returns

boolean —

whether $value was in the filter or not

getHashBitPositionArray()

getHashBitPositionArray(string  $value, integer  $num_keys) : integer

Hashes $value to a bit position in the BloomFilter

Parameters

string $value

value to map to a bit position in the filter

integer $num_keys

number of bit positions in the Bloom filter used to say an item isin the filter

Returns

integer —

the bit position mapped to

setBit()

setBit(integer  $i) 

Sets to true the ith bit position in the filter.

Parameters

integer $i

the position to set to true

getBit()

getBit(integer  $i) : boolean

Looks up the value of the ith bit position in the filter

Parameters

integer $i

the position to look up

Returns

boolean —

the value of the looked up position