indiesquidge/autocomplete

low-level, primitive autocomplete using trie data structure

Autocomplete

A low-level, primitive autocomplete using trie data structure

Features

This autocomplete library has the ability to insert words manually, get word suggestions based on a query, populate the data structure with a dictionary array of words, and delete undesired words.

NOTE: The library is not populated with any words by default.

Insertion

const completion = createTrie();

completion.insert("hello");

completion.count(); // => 1

completion.insert("world");

completion.count(); // => 2

Suggestions

completion.suggest("he"); // => ['hello']

completion.insert("hellen");

completion.suggest("he"); // => ["hello", "hellen"]

completion.suggest("w"); // => ["world"]

Population

const fs = require("fs");
const text = "/usr/share/dict/words";
const dictionary = fs.readFileSync(text).toString().trim().split("\n");
const completion = createTrie();

completion.populate(dictionary);

completion.suggest("world"); // => [ 'world', 'worlded', 'worldful', …]

Deletion

completion.suggest("world"); // => ['world', 'worlded', 'worldful', …]

completion.delete("worlded");

completion.suggest("world"); // => ['world', 'worldful', …]

Future Improvements

• case-insensitive suggestions

  • it'd be nice to be able to type in "ap" and have something like "Apache" come up as a suggestion; since keys are strings in JS and strings are case-sensitive, this would require a bit of refactoring around how we discover the startNode in Trie#suggest

• substring suggestions

  • right now, words are only displayed as suggestions if the word is prefixed by the query; a better implementation would include suggestions that have the query as a substring appearing anywhere in the word, not just as a prefix; e.g., querying in "ist" would return suggestions like "istle" and "isthmus", but also "listen"

---

Inspired by the "Compelete-Me" project from the Turing School of Software & Design

autocomplete's Issues

Suggestions include query when they shouldn't

If my query includes an inserted word as a prefix, it includes my query in the list of suggestions.

If my query starts with the same letter as an inserted word, I get a strange suggestion that appears to be the merging of the query and the inserted word.

const completion = createTrie();

completion.suggest("listening"); // should be [], got []
completion.insert("list");
completion.suggest("listening"); // should still be [], got ["listening"]
completion.suggest("lost"); // should still be [], got ["lostist"] (!!!)

Requesting to delete a word throws unexpected error

Requesting to delete a word with some matching prefix to an existing word throws a useful error

const completion = createTrie()

completion.insert('list')
completion.delete('lis') // throws `Error: foo is not a word, nothing deleted`

But if I request to delete a word with no matching prefix to an existing word, the error thrown is not helpful

const completion = createTrie()

completion.delete('foo') // throws `TypeError: Cannot read property 'getIsCompleteString' of undefined`

I would expect the latter snippet to throw the same error as the former snippet.