Learning: C++, Bit manipulation
Duration: 1 week
License: Open Source [Github]
Objective: Build a fast and minimal Data Structure to detect invalid dictionary words.
This module was used as a filter for querying possible word suggestion/predictions for swipe user input inside keyboard. While working on in-house Swipe algorithm it was observed that traditional Trie DS takes considerable amount of time to check false words, so need for a minimal DS was seen which is faster and lightweight in detecting absolutely wrong query words. It works as a filter for the main Trie DS. If a given word fails to pass this filter then it is not queried upon the main Trie DS hence saving a lot of look-ups.
Using some clever Bit-manipulation technique and properties of latin alphabets, we were able to fit this DS in just 4kb making the lookups 50x faster as compared to traditional Trie implementation.
The MagicDict can have applications in real-time spell-checker, working as initial defense layer, reducing the number of queires on the main DS implementation, with negligible memory overhead.