Nasty Popsicle Machine

    trie-prefix-tree
    DefinitelyTyped icon, indicating that this package has TypeScript declarations provided by the separate @types/trie-prefix-tree package

    1.5.1 • Public • Published

    Trie Prefix Tree

    Travis Build codecov coverage version downloads MIT License semantic-release

    This is a Trie implementation written in JavaScript, with insert and remove capability. It can be used to search a predefined dictionary for prefixes, check a prefix exists and retrieve a list of anagrams and sub-anagrams based on given letters.

    What is a Trie?

    A Trie (also known as a prefix-tree) is a data structure for storing strings in a tree. Each branch in the tree represents a single character which allows for fast and efficient depth-first searching. Let's say we have a dictionary with the words: CAR, CAT and CURL. We can visualise the trie like this:

    trie data structure

    Installation

    Pull down dependencies:

    npm install
    

    This project uses Jest for unit testing and ESLint for linting.

    To run combined linting & unit tests:

    npm test
    

    To run linting:

    npm run lint
    

    Run tests in watch mode:

    npm run test-watch
    

    Get code coverage report:

    npm run test-coverage
    

    How to Use

    To use the Trie, install and save it to your package dependencies:

    npm install trie-prefix-tree --save
    

    To create a new Trie:

    var trie = require('trie-prefix-tree');
     
    // using ES2015 Modules
    import trie from 'trie-prefix-tree';

    Instantiate the Trie:

    var myTrie = trie(['cat', 'cats', 'dogs', 'elephant', 'tiger']);

    Trie functionality:

    // retrieve a stringified dump of the Trie object
    myTrie.dump(); // { c: { a: { t: $: 1 }, s: 1 ... }}
     
    // optionally pass in spacer parameter to format the output string
    myTrie.dump(2); // equivalent of JSON.stringify(obj, null, 2);
    // retrieve the Trie object instance
    myTrie.tree();
    // add a new word to the Trie
    myTrie.addWord('lion');
    // remove an existing word from the Trie
    myTrie.removeWord('dogs');

    Adding and removing words can be chained:

    myTrie.addWord('hello').removeWord('hello');

    Prefix searching:

    // check if a prefix exists:
    myTrie.isPrefix('do'); // true
    myTrie.isPrefix('z'); // false
    // count prefixes
    myTrie.countPrefix('c'); // 2
    // get an array of words with the passed in prefix
    myTrie.getPrefix('c'); // ['cat', 'cats']
     
    // Pass false as the second parameter to disable 
    // output being sorted alphabetically
    // this is useful when your dictionary is already sorted
    // and will therefore save performance
    myTrie.getPrefix('c', false); // ['cat', 'cats']
    // get a random word at a prefix
    myTrie.getRandomWordWithPrefix('c'); // 'cat'
    myTrie.getRandomWordWithPrefix('c'); // 'cats'

    Other:

    // retrieve a full list of words in the Trie
    // the output array is automatically sorted
    myTrie.getWords(); // ['cat', 'cats', 'elephant', 'lion', 'tiger']
     
    // pass false to disable the output being sorted
    // this is useful when your dictionary is already sorted
    // and will therefore save performance
    myTrie.getWords(false); // ['cat', 'cats', 'elephant', 'tiger', 'lion']
    // check if a word exists in the Trie
    myTrie.hasWord('elephant'); // true
    myTrie.hasWord('zoo'); // false
    // generate a list of valid anagrams from the given letters
    myTrie.getAnagrams('act'); // ['cat'];
    // generate a list of valid sub-anagrams from the given letters
    myTrie.getSubAnagrams('ctalion'); ['cat', 'cats', 'lion'];

    Credits

    Credit goes to Kent C. Dodds for providing the awesome 'How to Create an Open Source JavaScript Library' course, available on egghead.io.

    License

    This project is referenced under the MIT license and is free to use and distribute.

    MIT @ Lyndsey Browning

    Install

    npm i trie-prefix-tree

    DownloadsWeekly Downloads

    6,468

    Version

    1.5.1

    License

    MIT

    Unpacked Size

    21.1 kB

    Total Files

    11

    Last publish

    Collaborators

    • lyndseybrowning