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 theforward
parameter to choose between forward or backward mode - The
add(str)
function will add a substringstr
toTrie
- The
match(str, index)
function will match the substringstr
at positionindex
and 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. 😊
Top comments (0)