Search using spectral bloom filters in static sites
Sthir can create memory efficient search feature for your static website. Sthir is equipped with an user friendly command-line interface. In two steps you can build a working search page for your website!
Sthir is a library to create search functionality for your static websites. It scans your html pages for words and indexes these words in an efficient data structure called Spectral Bloom Filters. Spectral Bloom Filteres differs from regular ones as they can store counts for each hash (it can estimate, at minimum, how many times a hash was indexed). We are using an efficient base 15 decoding to compress and transfer the bloom filters at client side. Our goal can be described with a simple equation:
Less Memory Footprint + Term Frequency Knowledge = Perfect Search Functionality for Static Sites!
A deployed example of our library can be found on this blog.
sthir runs on Python 3.5 or above.
Installation with pip via PyPI for Linux, OS X and Windows:
pip install sthirTo check installation run the following command:
sthir -hIf you see the help messages without any error then the installation was successful.
usage: sthir [-h] [-e ErrorRate] [-s Counter_size] [-l] [-ds] path
Creates a Spectral Bloom filter(SBF) for .html files in the specified
directory.
positional arguments:
path Path to source directory for creating the filter
optional arguments:
-h, --help show this help message and exit
-e ErrorRate Error_rate for the filter Range:[0.0,1.0] Default:0.01
-s Counter_size Size in bits of each counter in filter Range:[1,10]
Default:4(recommended)
-l, --lemmetize Enable Lemmetization
-ds Disable stopword removal from files (not recommended)
To scan your HTML files and generate a static search webpage, use the command:
sthir <your-path-name>
By default, a search.html file, containing the static search functionality will be generated.
You can change the error rate of the generated Spectral Bloom Filter using:
sthir <your-path-name> -e <error-rate>
We recommend an error rate of 0.01. Having a high error rate is likely to produce more false positive results (i.e. it will recommend URLs which do not contain the search word(s)).
By default, our counters can have a maximum count of 16 (counter_size=4). Counters are used by Spectral Bloom Filters to keep track of the number of times a particular hash has been indexed in the bloom filter. So by default, we keep a count till 16. However, you can chnage the counter size using: sthir <your-path-name> -s <counter-size>.
Note:
counter_sizeofxcan store upto a maximum count2^x. For example:counter_sizeof 3, has a maximum count of2^3or8.- As Spectral Bloom Filters are a probabilistic data structure, they cannot be used to accurately determine the upper bound of each word's hashes. They keep a track of the lower bound of a word's hashes (primarily using Minimum Increment method).
Our entire documentation is available in:
Here is a working demo -
The library is licensed under MIT License. This project is developed by Parth Parikh, Mrunank Mistry, and Dhruvam Kothari.
- Spectral bloom filters by Saar Cohen and Yossi Matias. DOI: https://doi.org/10.1145/872757.872787
- Writing a full-text search engine using Bloom filters by Stavros Korokithakis was a major inspiration for this project.
- Karan Lyons and Sascha Droste for MurmurHash3js.
- Zhuhongk and Nikolas for their code on Is there a pure python implementation of MurmurHash?.
- Data files are derived from the Google Web Trillion Word Corpus, as described by Thorsten Brants and Alex Franz, and distributed by the Linguistic Data Consortium. Subsets of this corpus distributed by Peter Novig. Corpus editing and cleanup by Josh Kaufman.
- Fork it (https://github.com/pncnmnp/Spectral-Bloom-Search/fork)
- Create your feature branch (
git checkout -b feature/fooBar) - Commit your changes (
git commit -am 'Add some fooBar') - Push to the branch (
git push origin feature/fooBar) - Create a new Pull Request
https://drive.google.com/uc?id=1UpL5IPdzdPSEmv1U-ethebU_-ODKUxN0&export=download