README
Sofia Tree
A fast-recovery data structure to support auto-complete as you type features.
A kind of Radix Tree or Trie data structure baptized 'Sofia Tree' in honour to my beloved daughter. A multinode tree with a level for each letter with fast lookup operations. See Anottated Source
Features
- Non-recursive tree traverse implementation to keep memory usage low and speed up on lookup operations.
- Efficient in-memory data structure, no redis, no dependencies
- Optional built-in cache for even faster lookups.
- Optionally case sensitive
- Optionally limit number of results to get matches even faster
- Optionally exclude the given prefix if it's a valid word
- Batteries included example to benchmark its performance
Install
npm install sofia-tree
Quick and simple usage example
var SofiaTree=require('sofia-tree');
var dictionary=["f","foo","foobar","b","bar","barbar"];
var sofiaTree= new SofiaTree({
useCache: true,
caseSensitive: false
});
dictionary.forEach(function(word){
sofiaTree.insert(word);
},server);
//Retrieve all the completions including the prefix
console.log(sofiaTree.getCompletions("foo"));
["foo","foobar"]
//Retrieve all the completions without the prefix
console.log(sofiaTree.getCompletions("foo",true));
["foobar"]
//Limit the number of results without excluding the prefix (defaults to false)
console.log(sofiaTree.getCompletions("f",2)))
["f","foobar"]
//Prints the whole dictionary
console.log(sofiaTree.getCompletions(""));
["f","foo","foobar","b","bar","barbar"]
See tests for more complete use cases
A real world example
Clone the whole repo and run npm run example
to load a micro search engine, in another console run cd example && ./test.sh
to load a 350,000 words dictionary and launch 1,500 searchs with 100 threads in parallel. See Anottated Source and shell scripts
Known limitations
Actually when limiting the maximum number or matches to be retorned it won't necessarely return the first ones in alphabetical order. When returning all the results they won't be alphabetically sorted either. This is due the nature of javascript objects properties which are unordered by definition. Perhaps I'll switch properties for an array in the future.
To be done
Define nice jasmine tests and setup TravisComment the example API usage- Reduce prefixes stack memory comsuption
Partial cache invalidation mechanism when inserting new words (it actually resets the whole cache upon insertion of new words.)- Implement remove method
- Return results as stream
Case-sensitive lookups? Not sure if it's a valuable adition- Add weight on nodes to enable sort based on some business logic
- Any ideas? :)
Made with ❤ in Spain