Trie implementation based on a minimal automaton.

Trie implementation based on a minimal automaton for Node.js

Implementation based on "Incremental Construction of Minimal Acyclic Finite-State Automata" by Jan Daciuk, Stoyan Mihov, Bruce W. Watson and Richard E. Watson.

npm install dtrie

To run the unit tests:

npm test

To run the performance/stress tests:

npm run-script stress

Basic dictionary usage:

var dtrie = require('dtrie');
var trie = dtrie.createFromWords(['ai', 'aient', 'aime', 'aimer']);
  • filepath: path to dictionary (one word per line, unix eol)

Construct a dictionary from a file.

  • words: a list of lowercase words

Construct a dictionary from a list of words.

  • id: overwrite the generated id

Construct a new node.

Node's id, unique to each node.

Node's transitions.

  • letter: transition label

Return true if this node has a child for the given transition.

  • letter: transition label

Return the node child.

  • suffix: a suffix to check

Check if this node recognize the given suffix.

Return true if the current node is a terminal node.

This class is a subclass of Node and represent an automaton.

Construct a new automaton.

  • words: an alphabetically sorted list of lowercase words

Populate the automaton from an alphabetically sorted list of lowercase words. This method should only be called once per automaton. Words must contain letters within range [a-z].

  • word: the word to lookup

Return true if the automaton recognize the given word.

Return the number of nodes in the automaton.

This code is free to use under the terms of the MIT license.