JS Simple Trie Implementation
Nam PhαΊ‘m
Posted on December 25, 2021
Introduction
As you know, Trie performs quite well on string operations such as searching and extracting a substring, especially when you have many substrings to search and simply performing normal search operations will It takes a lot of time and so in this article, I will show you a simple implementation of Trie data structure in JS language. π You can use this implementation to understand how Trie works and use some of the available functions I provide. π Note that this version is still quite simple and therefore may in some cases not be good for performance. π
Implementation
The first thing you need is function(s) that lists the characters from a given string. I named these functions forwardChars and backwardChars respectively (they are generators). The Trie structure that I implement can allow you to search for a substring ending in a certain position, and that will be more convenient for you when performing tasks that involve replacing strings in textarea elements of html. And the code should be straight forward as following:
function* forwardChars(str, index) {
index |= 0;
if (index < 0)
index = 0;
for (let i = index; i < str.length; i++)
yield str.charCodeAt(i);
}
function* backwardChars(str, index) {
if (index >= str.length || !Number.isSafeInteger(index)) {
index = str.length;
index--;
}
for (let i = index; i >= 0; i--)
yield str.charCodeAt(i);
}
In this version, I will use character codes instead of plain characters.
Next, I implemented the TrieNode structure in Trie. The structure is pretty simple, it's an object that holds a codes mapping that maps from the next character code to the next TrieNode. In TrieNode, I provide only one method which is next to get the next node based on the given character code. ensure parameter to ensure a new node will be created instead of null being returned. And so, our source code will be
class TrieNode {
constructor() {
this.codes = new Map();
}
next(code, ensure) {
if (!this.codes.has(code)) {
let next = null;
if (ensure) {
next = new TrieNode();
this.codes.set(code, next);
}
return next;
}
return this.codes.get(code);
}
}
Next, we will have the Trie class, which is the main class in the entire source code. In Trie we will have
- The constructor which is used to create a root node which is a
TrieNode. Here, we will have theforwardparameter to choose between forward or backward mode - The
add(str)function will add a substringstrtoTrie - The
match(str, index)function will match the substringstrat positionindexand return the matched substring presented inTrie
And so our source code will be
class Trie {
constructor(forward = true) {
this.root = new TrieNode();
this.listChars = forward ? forwardChars : backwardChars;
}
add(str) {
let current = this.root;
for (let code of this.listChars(str))
current = current.next(code, true);
current.terminated = true;
}
match(str, index) {
let forward = this.listChars == forwardChars;
let current = this.root;
let count = 0;
let length = 0;
index |= 0;
for (let code of this.listChars(str, index)) {
count++;
current = current.next(code, false);
if (!current)
break;
if (current.terminated)
length = count;
}
return str.substr(forward ? index : ++index - length, length);
}
}
Combine them all and the full source code is
function* forwardChars(str, index) {
index |= 0;
if (index < 0)
index = 0;
for (let i = index; i < str.length; i++)
yield str.charCodeAt(i);
}
function* backwardChars(str, index) {
if (index >= str.length || !Number.isSafeInteger(index)) {
index = str.length;
index--;
}
for (let i = index; i >= 0; i--)
yield str.charCodeAt(i);
}
class TrieNode {
constructor() {
this.codes = new Map();
}
next(code, ensure) {
if (!this.codes.has(code)) {
let next = null;
if (ensure) {
next = new TrieNode();
this.codes.set(code, next);
}
return next;
}
return this.codes.get(code);
}
}
class Trie {
constructor(forward = true) {
this.root = new TrieNode();
this.listChars = forward ? forwardChars : backwardChars;
}
add(str) {
let current = this.root;
for (let code of this.listChars(str))
current = current.next(code, true);
current.terminated = true;
}
match(str, index) {
let forward = this.listChars == forwardChars;
let current = this.root;
let count = 0;
let length = 0;
index |= 0;
for (let code of this.listChars(str, index)) {
count++;
current = current.next(code, false);
if (!current)
break;
if (current.terminated)
length = count;
}
return str.substr(forward ? index : ++index - length, length);
}
}
Using the class
The thing you should focus here is the Trie class. Using the class is simple: initialize one, add substrings to it using add method and the call match on the string you want to extract at index position. So the code
let ft = new Trie(); // this is forward trie
ft.add('abc');
ft.add('abcdef');
ft.add('xyz');
ft.match('abc', 0); // return 'abc'
ft.match('abc', 1); // return ''
ft.match('ab', 0); // return ''
ft.match('abcdef', 0); // return 'abcdef'
ft.match('abcdef', 1); // return ''
ft.match('xabcdef', 0); // return ''
ft.match('xabcdef', 1); // return 'abcdef'
ft.match('xyz', 0); // return 'xyz'
ft.match('xyz', 1); // return ''
ft.match('qxyz', 0); // return ''
let bt = new Trie(false); // this is backward trie
bt.add('abc');
bt.add('abcdef');
bt.add('xyz');
bt.match('abc', 2); // return 'abc'
bt.match('abc', 1); // return ''
bt.match('xabc', 3); // return 'abc'
bt.match('xyz', 2); // return 'xyz'
I hoped the implementation helped you see how to implement such a simple Trie in JS and hoped it can help you with search operations on strings. π Have a nice day then. π
Posted on December 25, 2021
Join Our Newsletter. No Spam, Only the good stuff.
Sign up to receive the latest update from our blog.