MagicDict

Smallest and Fastest Data Structure to query english words.

Note: This is implementation of Bloom Filter for Trie Data Structure. It can be used to test whether query word is valid or not. False positive matches are possible, but false negatives are not – in other words, a query returns either "possibly in set" or "definitely not in set".

Benchmarks:

Data Strcuture	Insert (370k words)	Query (100k words)	Delete (100k words)
Set	461 ms	220 ms	39 ms
Trie	530 ms	50 ms	26 ms
HashMap	180 ms	110 ms	14 ms
MagicDict	13 ms	3 ms	1 ms

Note: Current benchmarks have been calculated on 370k valid english words

Build

You can make this project using:

mkdir build
cd build
cmake ..

to generate a lib file or directly use MagicDict class in your source tree.