Skip to content

Instantly share code, notes, and snippets.

@kendru
Created September 5, 2017 19:27
Show Gist options
  • Save kendru/c98b0fb0addcc0faffe7694f16d8a34f to your computer and use it in GitHub Desktop.
Save kendru/c98b0fb0addcc0faffe7694f16d8a34f to your computer and use it in GitHub Desktop.
Javascript Trie for efficient prefix search
class Node {
constructor(char, parent = null, weight = null) {
this.char = char;
this.parent = parent;
this.weight = weight;
this.children = {};
}
get isTerminal() {
return this.weight !== null;
}
toString() {
if (this.isTerminal) {
return `(${this.char}=${this.weight})`;
}
return `(${this.char} ${Object.values(this.children).map(child => child.toString()).join(' ')})`;
}
}
function insert(node, word, weight) {
if (!node || !word) {
return;
}
const c = word.charAt(0);
const nextWord = word.substring(1);
let child = node.children[c];
if (!child) {
child = new Node(c, node);
node.children[c] = child;
}
if (nextWord.length === 0) {
child.weight = weight;
return child;
}
return insert(child, nextWord, weight);
}
function find(node, word, prefix = '', results = []) {
if (!node) {
return results;
}
if (node.isTerminal) {
return results.concat([
{ word: prefix + node.char, weight: node.weight }
]);
}
if(!word) {
return Object.values(node.children).reduce(
(prevResults, matchingNode) => find(matchingNode, '', prefix + node.char, prevResults),
results
);
}
const c = word.charAt(0);
const nextWord = word.substring(1);
const nextNode = node.children[c];
if (!nextNode) {
return results;
}
return find(nextNode, nextWord, prefix + node.char, results);
}
class Trie {
constructor() {
this.root = new Node('');
}
insert(word, weight) {
return insert(this.root, word, weight);
}
find(word) {
return find(this.root, word);
}
toString() {
return this.root.toString();
}
}
let t = new Trie();
t.insert('test', 1);
t.insert('tea', 2);
t.insert('ted', 0.5);
t.insert('coffee', 10);
t.insert('covfeffe', 2.3);
console.log(t.find('co'));
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment