maxwilms/bloom-filter

Bloom filter - a space-efficient probabilistic data structure for PHP 5.4+

v0.9.5 2019-11-19 10:12 UTC

This package is not auto-updated.

Last update: 2024-03-26 00:07:59 UTC


README

Build Status Quality Score

A Bloom filter is a probabilistic data structure, that tests whether an element is member of a set. It will always confirm if the element is member of the set. But false-positives are possible.

When to use Bloom filters

Use this data structure when you quickly need to confirm that a certain value does not exists in a large data set. For example a certain row is not present on your database (e.g., IP address, username, email).

Installation

First install composer.

Require the bloom filter via composer:

composer require maxwilms/bloom-filter

Now you are ready to use it!

Usage

<?php

require_once('vendor/autoload.php');

use maxwilms\BloomFilter\BloomFilterGenerator;

// generate a bloom filter for 1000 elements with a probability of 1% for false positives
$bloomFilter = BloomFilterGenerator::generate(1000, 0.01); 

$bloomFilter->add('foo');
$bloomFilter->add('bar');
// ... add more

$bloomFilter->contains('foo'); // true - possibly in set
$bloomFilter->contains('baz'); // false - definitely not in set

TODO

more examples :)