This is my implementation of the suffix tree using the O(n^2) naive algorithm recursively. It is also my first big project in which I've used all the knowledge I have acquired about C++ so far. I would appreciate any advice on how to improve my code and make it compatible with the modern C++ best practices.
SuffixTree.h
#ifndef SUFFIX_TREE_H
#define SUFFIX_TREE_H
#include <string>
#include <map>
#include <vector>
#include <fstream>
namespace trie
{
typedef std::size_t size_type;
template <typename T1, typename T2>
// bidirectional map to create one-to-one mapping between the alphabet of input string and it's rank in `BiMap`
class BiMap
{
public:
void insert(const T1& a, const T2& b); // insert and create a mapping between `a` and `b`
void generateKeys(const std::string& text); // find unique alphabets in `text` and call `insert` with their respective ranks
T2 retrieve(const T1& key); // return the rank when passed it's corresponding alphabet
T1 retrieve(const T2& key); // return the alphabet when passed it's corresponding rank
size_type getSize(); // return total mappings created (used to specify how many children a node must have)
void print(); // print the mappings
private:
std::map<T1, T2*> map1_; // alphabet saved as key with it's value pointing to it's corresponding rank which is key of `map2_`
std::map<T2, T1*> map2_; // rank saved as key with it's value pointing to it's corresponding alphabet which is key of `map1_`
};
// node of the suffix tree
struct Node
{
Node(size_type id, int length, int size);
size_type id_; // represents the position in text where suffix represented by this node begins
int length_; // length of the substring encapsulated by the given node (only for internal nodes). -1 means it's a leaf.
std::vector<Node*> children_; // `BiMap::getSize()` number of children for each node.
};
class SuffixTree
{
public:
SuffixTree(const std::string& text = ""); // constructor for text passed from main
SuffixTree(const std::ifstream& file); // constructor for text passed from input file
Node* insert(Node* current, size_type id, int length = 0); // recursive function to insert node with id = `id` called on root
void constructTree(); // loop over all suffixes of `text_` and call `insert` on each
void printSuffixes(); // print suffixes inorder
void printSuffixes(Node* current); // called by above function
void printInorder(); // print all nodes in suffix tree inorder
void printInorder(Node* current); // called by above function
void deleteTree(Node* current); // recursive deleter called by the destructor
~SuffixTree();
private:
std::string text_; // saves the input text
BiMap<char, size_type> map_; // maps alphabet of `text_`
Node *root_; // constructed as soon as `SuffixTree` object is created
};
}
#include "SuffixTree.inl"
#endif
SuffixTree.inl
#include "SuffixTree.h"
#include <iostream>
#include <set>
#include <sstream>
template <typename T1, typename T2>
void trie::BiMap<T1, T2>::insert(const T1& t1, const T2& t2)
{
auto itr1 = map1_.emplace(t1, nullptr).first;
auto itr2 = map2_.emplace(t2, nullptr).first;
map1_[itr1->first] = (T2*) &(itr2->first); // I know this is dangerous but once built, I only use it for reading.
map2_[itr2->first] = (T1*) &(itr1->first); // This is the simplest BiMap implementation I came up with.
}
template <typename T1, typename T2>
void trie::BiMap<T1, T2>::generateKeys(const std::string& text)
{
std::set<char> S;
for (size_type i = 0; i < text.size(); ++i)
S.insert(text[i]);
size_type rank = 0;
for (auto itr = S.cbegin(); itr != S.cend(); ++itr)
insert(*itr, rank++);
}
template <typename T1, typename T2>
T2 trie::BiMap<T1, T2>::retrieve(const T1& key)
{
if (map1_.find(key) == map1_.cend())
exit(EXIT_FAILURE);
return *map1_[key];
}
template <typename T1, typename T2>
T1 trie::BiMap<T1, T2>::retrieve(const T2& key)
{
if (map2_.find(key) == map2_.cend())
exit(EXIT_FAILURE);
return *map2_[key];
}
template <typename T1, typename T2>
trie::size_type trie::BiMap<T1, T2>::getSize()
{
return map1_.size() | map2_.size();
}
template <typename T1, typename T2>
void trie::BiMap<T1, T2>::print()
{
for (typename std::map<T1, T2*>::const_iterator itr = map1_.cbegin(), end = map1_.cend(); itr != end; ++itr)
std::cout << itr->first << " -> " << *itr->second << std::endl;
}
trie::Node::Node(size_type id, int length, int size)
: id_(id), length_(length), children_(size, nullptr)
{
}
trie::SuffixTree::SuffixTree(const std::string& text)
: text_(text)
{
map_.generateKeys(text_);
map_.print();
root_ = new Node(-1, 0, map_.getSize()); // `id` and `length` of root node don't matter as they're never accessed
}
trie::SuffixTree::SuffixTree(const std::ifstream& file)
{
std::stringstream ss;
ss << file.rdbuf(); // redirect file buffer to string stream
text_ = ss.str(); // copy the string from ss to `text_`
map_.generateKeys(text_);
map_.print();
root_ = new Node(-1, 0, map_.getSize());
}
trie::Node* trie::SuffixTree::insert(Node* current, size_type id, int length)
{
if (current == nullptr) // return the leaf to link it to it's parent
return new Node(id, -1, map_.getSize());
if (current->length_ == -1) // if `current` is a leaf
{
size_type i = id + length; // `length` is used to keep track of how many matches we have done so far in the path till here.
// Hard to explain this one. You'll have to look at the insertion of `a~`, the 2nd last suffix in `banana~`, to understand it right.
size_type j = current->id_ + length;
while (text_[i] == text_[j]) // match the substring represented by this node (using j) with the substring starting at position `id` in text
{
length += 1;
i += 1;
j += 1;
}
/*
Link of `current` with it's parent is broken and a new node is inserted in it's place whose `length` represents
the substring we have matched so far in the path from `root` till `current`.
The "broken" node, `current`, is rejoined at the correct position in the `children` of the new node.
The "correct position" is determined by the first char which the rest of the string `current` represents (where text_[i] and text_[j] are not equal).
Once that's done, continue the recursive insertion procedure from `text_[i]`.
*/
Node *temp = new Node(current->id_, length, map_.getSize());
size_type rankJ = map_.retrieve(text_[j]);
temp->children_[rankJ] = current;
size_type rankI = map_.retrieve(text_[i]);
temp->children_[rankI] = insert(temp->children_[rankI], id, length);
return temp; // `temp` has to be returned as now it is the new child of the parent instead of `current`.
}
else // if `current` is an internal node
{
size_type i = id + length;
size_type j = current->id_ + length;
size_type limit = current->length_-length;
while (limit && text_[i] == text_[j])
{
length += 1;
i += 1;
j += 1;
limit -= 1;
}
size_type rankI = map_.retrieve(text_[i]);
current->children_[rankI] = insert(current->children_[rankI], id, length); // if everything is matching so far, we continue down
return current;
}
}
void trie::SuffixTree::constructTree()
{
for (size_type i = 0; i < text_.size(); ++i)
{
size_type rank = map_.retrieve(text_[i]);
root_->children_[rank] = insert(root_->children_[rank], i);
}
}
void trie::SuffixTree::printSuffixes()
{
printSuffixes(root_);
}
void trie::SuffixTree::printSuffixes(Node* current)
{
if (current == nullptr)
return;
if (current->length_ == -1)
std::cout << text_.substr(current->id_) << std::endl;
for (size_type i = 0; i < current->children_.size(); ++i)
printSuffixes(current->children_[i]);
}
void trie::SuffixTree::printInorder()
{
printInorder(root_);
}
void trie::SuffixTree::printInorder(Node* current)
{
if (current == nullptr)
return;
for (size_type i = 0; i < current->children_.size(); ++i)
printInorder(current->children_[i]);
std::cout << current->id_ << ' ' << current->length_ << std::endl;
}
void trie::SuffixTree::deleteTree(Node* current)
{
if (current == nullptr)
return;
for (size_type i = 0; i < current->children_.size(); ++i)
deleteTree(current->children_[i]);
delete current;
}
trie::SuffixTree::~SuffixTree()
{
deleteTree(root_);
}
main.cpp
#include <iostream>
#include "SuffixTree.h"
int main()
{
trie::SuffixTree Tree("banana~");
Tree.constructTree();
Tree.printSuffixes();
}
