LibPatternedBloomFilter

Patterned Bloom Filter for WoW Lua 5.1 environment - Probabilistic set membership testing with minimal memory footprint.

Features

• Efficiently tests whether an element is a member of a set.
• Low memory usage, suitable for constrained environments.
• Simple API for adding and checking elements.
• Configurable false positive rate.
• Compatible with World of Warcraft Lua 5.1 environment.

Installation

To install LibPatternedBloomFilter, simply download the LibPatternedBloomFilter.lua file and include it in your WoW addon folder. Then, you can load it using LibStub in your addon code.

local LibPatternedBloomFilter = LibStub("LibPatternedBloomFilter")

Usage

-- Create a new Patterned Bloom Filter with expected 1000 values and 1% false positive rate
local filter = LibPatternedBloomFilter.New(1000, 0.01, 256, 4)

-- Add values to the filter
for i = 1, 1000 do
    filter:Insert("value" .. i)
end

-- Check for membership
for i = 1, 1200 do
    local value = "value" .. i
    if filter:Contains(value) then
        print(value .. " is possibly in the set.")
    else
        print(value .. " is definitely not in the set.")
    end
end

-- Export the filter state, so you can serialize it
local state = filter:Export()

-- Import the filter state into a new filter
local newFilter = LibPatternedBloomFilter.Import(state)

API

LibPatternedBloomFilter.New(capacity, seed, falsePositiveRate, numPatterns, bitsPerPattern)

Create a new Patterned Bloom Filter instance.

• capacity: Capacity of the filter (expected number of values).
• seed: Optional seed for hash function (default: 0).
• falsePositiveRate: Desired false positive rate (between 0.0 and 1.0, default: 0.01 which means 1%).
• numPatterns: Number of unique bit patterns to generate (default: 256).
• bitsPerPattern: Number of bits set per pattern (between 1 and 31, default: 4).
• Returns: The new Patterned Bloom Filter instance.

filter:Insert(value)

Insert a value into the filter.

• value: Value to insert.

filter:Contains(value)

Determine if a value is possibly in the filter.

• value: Value to check.
• Returns: True if value might be in the set, false if definitely not.

filter:Clear()

Clear all values from the filter.

filter:Export()

Export the current state of the filter.

• Returns: Compact representation of the filter.

LibPatternedBloomFilter.Import(state)

Import a new Patterned Bloom Filter from a compact representation.

• state: Compact representation of the filter.
• Returns: The imported Patterned Bloom Filter instance.

filter:EstimateFalsePositiveRate()

Estimate the current false positive rate (FPR) of the filter based on current load factor.

• Returns: Estimated false positive rate.

License

This library is released under the MIT License. See the LICENSE file for details.