bloomcalc - Shorter alias for bloom-filter-calculator
This document describes version 0.007 of bloomcalc (from Perl distribution App-BloomUtils), released on 2020-05-24.
Usage:
% bloomcalc [--debug] [--false-positive-rate=s] [--format=name] [--fp-rate=s] [--json] [-k=s] [--log-level=level] [-m=s] [--(no)naked-res] [--num-bits=s] [--num-hashes-to-bits-per-item-ratio=s] [--num-hashes=s] [-p=s] [--page-result[=program]] [--quiet] [--trace] [--verbose] <num_items>
You supply lines of text from STDIN and it will output the bloom filter bits on STDOUT. You can also customize num_bits (m) and num_hashes (k), or, more easily, num_items and fp_rate. Some rules of thumb to remember:
num_bits
m
num_hashes
k
num_items
fp_rate
One byte per item in the input set gives about a 2% false positive rate. So if you expect two have 1024 elements, create a 1KB bloom filter with about 2% false positive rate. For other false positive rates:
10% - 4.8 bits per item 1% - 9.6 bits per item 0.1% - 14.4 bits per item 0.01% - 19.2 bits per item
Optimal number of hash functions is 0.7 times number of bits per item. Note that the number of hashes dominate performance. If you want higher performance, pick a smaller number of hashes. But for most cases, use the the optimal number of hash functions.
What is an acceptable false positive rate? This depends on your needs. 1% (1 in 100) or 0.1% (1 in 1,000) is a good start. If you want to make sure that user's chosen password is not in a known wordlist, a higher false positive rates will annoy your user more by rejecting her password more often, while lower false positive rates will require a higher memory usage.
Ref: https://corte.si/posts/code/bloom-filter-rules-of-thumb/index.html
FAQ
Why does two different false positive rates (e.g. 1% and 0.1%) give the same bloom filter size?
The parameter m is rounded upwards to the nearest power of 2 (e.g. 1024*8 bits becomes 1024*8 bits but 1025*8 becomes 2048*8 bits), so sometimes two false positive rates with different m get rounded to the same value of m. Use the bloom_filter_calculator routine to see the actual_m and actual_p (actual false-positive rate).
bloom_filter_calculator
actual_m
actual_p
* marks required options.
*
Default value:
0.02
Number of bits to set for the bloom filter.
0.7 (the default) is optimal.
Expected number of items to add to bloom filter.
Shortcut for --log-level=debug.
Set log level.
Shortcut for --log-level=error.
Shortcut for --log-level=trace.
Shortcut for --log-level=info.
Choose output format, e.g. json, text.
undef
Set output format to json.
When outputing as JSON, strip result envelope.
0
By default, when outputing as JSON, the full enveloped result is returned, e.g.:
[200,"OK",[1,2,3],{"func.extra"=>4}]
The reason is so you can get the status (1st element), status message (2nd element) as well as result metadata/extra result (4th element) instead of just the result (3rd element). However, sometimes you want just the result, e.g. when you want to pipe the result for more post-processing. In this case you can use `--naked-res` so you just get:
[1,2,3]
Filter output through a pager.
Display help message and exit.
Display program's version and exit.
This script has shell tab completion capability with support for several shells.
To activate bash completion for this script, put:
complete -C bloomcalc bloomcalc
in your bash startup (e.g. ~/.bashrc). Your next shell session will then recognize tab completion for the command. Or, you can also directly execute the line above in your shell to activate immediately.
It is recommended, however, that you install modules using cpanm-shcompgen which can activate shell completion for scripts immediately.
To activate tcsh completion for this script, put:
complete bloomcalc 'p/*/`bloomcalc`/'
in your tcsh startup (e.g. ~/.tcshrc). Your next shell session will then recognize tab completion for the command. Or, you can also directly execute the line above in your shell to activate immediately.
It is also recommended to install shcompgen (see above).
For fish and zsh, install shcompgen as described above.
Please visit the project's homepage at https://metacpan.org/release/App-BloomUtils.
Source repository is at https://github.com/perlancar/perl-App-BloomUtils.
Please report any bugs or feature requests on the bugtracker website https://rt.cpan.org/Public/Dist/Display.html?Name=App-BloomUtils
When submitting a bug or request, please include a test-file or a patch to an existing test-file that illustrates the bug or desired feature.
perlancar <perlancar@cpan.org>
This software is copyright (c) 2020, 2018 by perlancar@cpan.org.
This is free software; you can redistribute it and/or modify it under the same terms as the Perl 5 programming language system itself.
To install App::BloomUtils, copy and paste the appropriate command in to your terminal.
cpanm
cpanm App::BloomUtils
CPAN shell
perl -MCPAN -e shell install App::BloomUtils
For more information on module installation, please visit the detailed CPAN module installation guide.