Created
September 5, 2017 19:27
-
-
Save kendru/c98b0fb0addcc0faffe7694f16d8a34f to your computer and use it in GitHub Desktop.
Javascript Trie for efficient prefix search
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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