A trie is a tree-like data structure in which every node stores a character. A trie can store one or multiple words. If a trie stores all suffixes of a word, it is called a suffix trie. After you build a suffix trie, all substrings of a word can be retrieved easily. This post is about using suffix trie to store and retrieve all substrings (including all suffixes) in a word.
All substrings in a word are contiguous sequences of characters within a string with all possible lengths. For example, a word “ana”, its substrings include “a”, “an”, “ana”, “n”, “na”, total 5 of them. Note, that all substrings are different from all suffixes of a word. In the example of “ana”, its suffixes are “ana”, “na”, “a”, total of 3 of them. A suffix trie holds all substrings, including suffixes, of a word.
The implementation in this post uses an array data structure to store children, which is used to find the next character in the branch. The alternative solution uses a hashmap to store children. The implementation using an array is more intuitive. But each node allocates a size of 26 for the array. Most spaces are empty, which is not efficient.
Table of Content
- Map of suffix trie implementations
- Define a SuffixTrieNode classe
- Build a suffix trie
- Search a substring
- Print all nodes in trie
- Free download
Map of suffix trie implementations
Part 1 – Suffix trie implementation using array.
Part 2 – Suffix trie implementation using hash map
Define a SuffixTrieNode class
A SuffixTrieNode is a class to create nodes in a suffix trie. It has 2 variables. children is a data structure that points to the node that stores the next character in one suffix (branch). The data structure is an array. Since we use only the alphabet a-z, the length of the array is 26. indices is a list data structure that stores the start position of a substring in a word.
Java
|
1 2 3 4 5 6 |
class SuffixTrieNode { static final int NUM_OF_CHARS = 26; //limit to letter a-z SuffixTrieNode[] children = new SuffixTrieNode[NUM_OF_CHARS]; ArrayList<Integer> indices = new ArrayList<>(); //record position of suffix } |
Javascript
|
1 2 3 4 5 6 |
class SuffixTrieNode { constructor() { this.children =[]; this.indices = []; //record position of suffix } } |
Python
|
1 2 3 4 |
class SuffixTrieNode: def __init__(self): self.children =[None]*26 self.indices = []; #record position of suffix |
Build a suffix trie
A SuffixTrie class has one variable root. All operations, such as insertion, search, or traversal, start from the root. In a suffix trie, only the root has multiple children. Other nodes except leaves have one child, which is the node of the next character in the suffix. You can initialize the root in the constructor.
To build a suffix trie from a word, you use the word as the input of the constructor. You subtract suffixes from the word and call the insertSuffix method with the root, a suffix, and the index of the starting position of the suffix in the word as input.
insertSuffix method is a recursive function. The first thing is to save the index in the input node’s indices. It records the position of the substring inside the input node. It will be used in search. If the input string is null or its length is 0, it is a terminal condition. All recursive calls return to calling functions.
Otherwise, you retrieve the first character of the input string. Use the character as the index to check the input node’s children. If there is no value in that cell, create a suffixTrieNode as a child node and save it in that cell. Then the method calls itself with the new node, the substring after the first character, and the index.
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
public class SuffixTrieArray { private SuffixTrieNode root = new SuffixTrieNode(); //Constructor, Call insertSuffix, Time O(s^2), Space O(s), s is string length public SuffixTrieArray(String str) { for (int i = 0; i < str.length(); i++) insertSuffix(root, str.substring(i), i); } //Insert a suffix node, Recursion, Time O(s), Space O(s) private void insertSuffix(SuffixTrieNode node, String str, int index) { node.indices.add(index); if (str.length() > 0) { char c = (char) (str.charAt(0)-'a'); if (node.children[c] == null) node.children[c] = new SuffixTrieNode(); insertSuffix(node.children[c], str.substring(1), index); } } |
Javascript
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
class SuffixTrieArray { //Constructor, Call insertSuffix, Time O(s^2), Space O(s), s is string length constructor(str) { this.root = new SuffixTrieNode(); for (let i = 0; i < str.length; i++) this.insertSuffix(this.root, str.substring(i), i); } //Insert a suffix node, Recursion, Time O(s), Space O(s) insertSuffix(node, str, index) { node.indices.push(index); if (str.length > 0) { let c = str.charAt(0); if (node.children[c] == null) node.children[c] = new SuffixTrieNode(); this.insertSuffix(node.children[c], str.substring(1), index); } } |
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
class SuffixTrieArray : #Constructor, Call insertSuffix, Time O(s^2), Space O(s), s is string length def __init__(self, str): self.root = SuffixTrieNode() for i in range(0, len(str)): self.insertSuffix(self.root, str[i:], i) #Insert a suffix node, Recursion, Time O(s), Space O(s) def insertSuffix(self, node, str, index) : node.indices.append(index) if len(str) > 0 : k = ord(str[0]) -97 if node.children[k] is None: node.children[k] = SuffixTrieNode() self.insertSuffix(node.children[k], str[1:], index) |
Search a substring
Search is to find a substring in the word. The search method is a wrapper method of searchHelper. The start node is the root. searchHelper is a recursive method. When the input string is null or the length is 0, it is a terminal condition, you return from the recursive calls. Otherwise, you take the first character of the input string. Use the character as the index to check whether there is a value in the cell of the input node’s children. If there is a value in that cell, the value is the node with the next character. You get the node from the cell so that you can keep searching for the following characters. The recursive method calls itself with the node and the substring after the first character. If the cell doesn’t have a value, return null.
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
//Search string, Recursion, Time O(s), Space O(s) public List<Integer> search(String str) { return searchHelper(root, str); } //recursion, Time O(s), Space O(s) private List<Integer> searchHelper(SuffixTrieNode node, String str) { if (str == null || str.length() == 0) return node.indices; //return the position of suffix else { char c = (char) (str.charAt(0)-'a'); if (node.children[c] != null) { String suffix = str.substring(1); return searchHelper(node.children[c], suffix); } } return null; } |
Javascript
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
//Search string, Recursion, Time O(s), Space O(s) search(str) { return this.searchHelper(this.root, str); } //recursion, Time O(s), Space O(s) searchHelper(node, str) { if (str == null || str.length == 0) return node.indices; //return the position of suffix else { let c = str.charAt(0); if (node.children[c] != null) { let suffix = str.substring(1); return this.searchHelper(node.children[c], suffix); } } return null; } |
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
#Search string, Recursion, Time O(s), Space O(s) def search(self, str) : return self.searchHelper(self.root, str) #recursion, Time O(s), Space O(s) def searchHelper(self, node, str) : if str is None or len(str) == 0: return node.indices; #return the position of suffix else : k = ord(str[0]) - 97 if node.children[k] : suffix = str[1:] return self.searchHelper(node.children[k], suffix) return None |
Print all nodes in trie
To print all nodes in a trie, you use recursion again. When the input node is null, it is a terminal condition, you can return. Otherwise, you print the input string, which is the substring from the root to the current node. Then you check all cells in the node’s children with the indices letter a-z. If there is a value at one cell, the value is the next node in this branch. The method calls itself using this node and the input string appended with the letter.
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
//Print all suffixes, Time O(s^2), Space O(s) public void print() { printHelper(root, ""); } //Print helper, Recursion, Time O(s^2), Space O(s) private void printHelper(SuffixTrieNode node, String str) { if (node == null) return; System.out.println(str); for (int k = 0; k < SuffixTrieNode.NUM_OF_CHARS; k++) { if (node.children[k] != null) printHelper(node.children[k], str + (char)(k +'a')); } } |
Javascript
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
//Print all suffixes, Time O(s^2), Space O(s) print() { this.printHelper(this.root, ""); } //Print helper, Recursion, Time O(s^2), Space O(s) printHelper(node, str) { if (node == null) return; console.log(str); for (let k = 97; k < 122; k++) { var letter = String.fromCharCode(k); if (node.children[letter] != null) { this.printHelper(node.children[letter], str+ letter); } } } |
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
#Print all suffixes, Time O(s^2), Space O(s) def printTrie(self) : self.printHelper(self.root, "") #Print helper, Recursion, Time O(s^2), Space O(s) def printHelper(self, node, str) : if node is None: return print(str) for c in ascii_lowercase: k = ord(c) - 97 if node.children[k] : self.printHelper(node.children[k], str+ c) |
Free download
Download suffix trie implementation using Array in Java, JavaScript and Python
Trie implmentation using array
Data structures introduction PDF