Skip to content

Main content

Bloom Filter Calculator Source Code

Browse the implementation files for Bloom Filter Calculator.
tool.ts typescript
import { parseInteger } from '../../parse/integer/tool';

const hash = (value: string, seed: number): number => {
	let state = (2166136261 ^ seed) >>> 0;
	for (let index = 0; index < value.length; index += 1) {
		state ^= value.charCodeAt(index);
		state = Math.imul(state, 16777619);
	}
	return state >>> 0;
};

export const calculateBloomFilter = (
	itemsInput: unknown,
	queryInput: unknown,
	bitCountInput: unknown,
	hashCountInput: unknown
): string => {
	if (
		typeof itemsInput !== 'string' ||
		typeof queryInput !== 'string' ||
		!queryInput.trim()
	)
		return '';
	const items = [
		...new Set(
			itemsInput
				.split(/[,;\n]+/)
				.map((item) => item.trim())
				.filter(Boolean)
		)
	];
	const query = queryInput.trim();
	const bitCount = parseInteger(bitCountInput);
	const hashCount = parseInteger(hashCountInput);
	if (
		!items.length ||
		bitCount === null ||
		bitCount < 8 ||
		bitCount > 1_000_000 ||
		hashCount === null ||
		hashCount < 1 ||
		hashCount > 32
	)
		return '';
	const bits = new Uint8Array(bitCount);
	const indexes = (value: string): number[] =>
		Array.from(
			{ length: hashCount },
			(_, index) => hash(value, index + 1) % bitCount
		);
	for (const item of items)
		for (const index of indexes(item)) bits[index] = 1;
	const possiblyPresent = indexes(query).every(
		(index) => bits[index] === 1
	);
	const setBits = bits.reduce((sum, bit) => sum + bit, 0);
	const falsePositiveProbability =
		(1 - Math.exp((-hashCount * items.length) / bitCount)) **
		hashCount;
	return JSON.stringify(
		{
			bitCount,
			falsePositiveProbability: Number(
				falsePositiveProbability.toPrecision(8)
			),
			hashCount,
			itemCount: items.length,
			possiblyPresent,
			query,
			setBits
		},
		null,
		2
	);
};

export const Tool: TypeTool = {
	name: 'Bloom Filter Calculator',
	slug: 'data-structure/bloom-filter',
	intro:
		'Build a deterministic Bloom filter, test an item, and estimate its false-positive probability.',
	tool: calculateBloomFilter,
	i: [
		{
			example: 'apple, banana, pear',
			label: 'Items',
			placeholder: 'Comma- or line-separated items',
			render: 'textarea',
			type: 'text'
		},
		{
			example: 'banana',
			label: 'Query',
			placeholder: 'Item to test',
			type: 'text'
		},
		{
			example: '128',
			label: 'Bits',
			placeholder: 'Filter size in bits',
			type: 'number'
		},
		{
			example: '3',
			label: 'Hash Functions',
			placeholder: 'Number of hashes',
			type: 'number'
		}
	],
	o: [
		{
			example: '{ "possiblyPresent": true }',
			label: 'Bloom Filter Result',
			placeholder: 'Result will appear here...',
			render: 'textarea',
			type: 'text'
		}
	],
	cite: [
		{
			title: 'Bloom filter - Wikipedia',
			url: 'https://en.wikipedia.org/wiki/Bloom_filter'
		}
	]
};
export default Tool;

Description

Browse the implementation files for Bloom Filter Calculator.

References

  1. Tool.io on GitHub
  2. Tool.io TypeScript tools library

Similar or alternative tools