Bloom filter implemented in Perl 6
Switch branches/tags
Nothing to show
Clone or download
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Type Name Latest commit message Commit time
Failed to load latest commit information.
eg
lib/Algorithm
t
.gitignore
.proverc
.travis.yml
Dockerfile
LICENSE
META6.json
Makefile
README.md

README.md

Build Status

NAME

Algorithm::BloomFilter - A bloom filter implementation in Perl 6

SYNOPSIS

use Algorithm::BloomFilter;

my $filter = Algorithm::BloomFilter.new(
  capacity   => 100,
  error-rate => 0.01,
);

$filter.add("foo-bar");

$filter.check("foo-bar"); # True

$filter.check("bar-foo"); # False with possible false-positive

DESCRIPTION

Algorithm::BloomFilter is a pure Perl 6 implementation of Bloom Filter, mostly based on Bloom::Filter from Perl 5.

Digest::MurmurHash3 is used for hashing from version 0.1.0.

METHODS

new(Rat:D :$error-rate, Int:D :$capacity)

Creates a Bloom::Filter instance.

add(Cool:D $key)

Adds a given key to filter instance.

check(Cool:D $key) returns Bool

Checks if a given key is in filter instance.

INTERNAL METHODS

calculate-shortest-filter-length(Int:D :$num-keys, Rat:D $error-rate) returns Hash[Int]

Calculates and returns filter's length and a number of hash functions.

create-salts(Int:D :$count) returns Seq[Int]

Creates and returns $count unique and random uint32 salts.

get-cells(Cool:D $key, Int:D :$filter-length, Int:D :$blankvec, Int:D :@salts) returns List

Calculates and returns positions to check in a bit vector.

SEE ALSO

Bloom Filter

Bloom::Filter

AUTHOR

yowcow yowcow@cpan.org

COPYRIGHT AND LICENSE

Copyright 2016 yowcow

This library is free software; you can redistribute it and/or modify it under the Artistic License 2.0.