Suffix tree and Tries. What is the difference?

Question

I am reading about Tries commonly known as Prefix trees and Suffix Trees.
Although I have found code for a Trie I can not find an example for a Suffix Tree. Also I get the feeling that the code that builds a Trie is the same as the one for a Suffix Tree with the only difference that in the former case we store prefixes but in the latter suffixes.
Is this true? Can anyone help me clear this out in my head? An example code would be great help!

Kebab

TL;DR The suffix tree of a string is a patricia trie of all its suffixes. The only special thing about it is that the edge labels are substrings of the original string, so they can be represented as a pair of indices and take only constant space. This is also why it can be built in linear time. – Prosthodontist

Answer 1

A suffix tree can be viewed as a data structure built on top of a trie where, instead of just adding the string itself into the trie, you would also add every possible suffix of that string. As an example, if you wanted to index the string banana in a suffix tree, you would build a trie with the following strings:

banana
anana
nana
ana
na
a

Once that's done you can search for any n-gram and see if it is present in your indexed string. In other words, the n-gram search is a prefix search of all possible suffixes of your string.

This is the simplest and slowest way to build a suffix tree. It turns out that there are many fancier variants on this data structure that improve on either or both space and build time. I'm not well versed enough in this domain to give an overview but you can start by looking into suffix arrays or this class advanced data structures (lecture 16 and 18).

This answer also does a wonderfull job explaining a variant of this data-structure.

Rewrite

This is what I suspected.The trie is used to build the suffix tree and that is why most textbooks only provide code for tries.But this is the worst-case implementation eh? – Kebab

@Kebab Suffix trees are most useful on very large strings (eg. indexing all the works of Shakespeare) where O(n^2) space and build time is simply not going to cut it. Fortunately, those bounds can be lowered quite a bit. – Rewrite

Answer 2

If you imagine a Trie in which you put some word's suffixes, you would be able to query it for the string's substrings very easily. This is the main idea behind suffix tree, it's basically a "suffix trie".

But using this naive approach, constructing this tree for a string of size n would be O(n^2) and take a lot of memory.

Since all the entries of this tree are suffixes of the same string, they share a lot of information, so there are optimized algorithms that allows you to create them more efficiently. Ukkonen's algorithm, for example, allows you to create a suffix tree online in O(n) time complexity.

Posada

So you're saying suffix trees and suffix tries are the same? – Corvese

Answer 3

The difference is very simple. A suffix tree has less "dummy" nodes than the suffix trie. These dummy nodes are single characters that increase the lookup operation at the tree

Ruebenrueda

Answer 4

Trie's nodes have links to shorter context, 'Tree' does not have it. If Tree's nodes get link to shorter context then it turns to Trie ;o)

Sky

Answer 5

A Suffix Tree for a given text is a compressed trie for all suffixes of the given text.

Ref: https://www.geeksforgeeks.org/pattern-searching-using-suffix-tree/

Coates

Answer 6

I'll give you snippets to make your understanding clearer. Disclaimer: I'm not an expert and know these DS from coding interview preparations.

At first, as was said above: suffix trie is a structure made up of hash tables (simplest variant) where we store all possible variants. So, we can search substrings if needed. Ex: 'abc'.

{'a': True, 
  'a': {'b': True},
  'a': {'b': {'c': True}}, 
  'b': True,
  'b': {'c': True},
  'c': True}

And Trie is when we store full strings to check if they're present. Ex: {'t': {'h': {'i': {'s': {'*': 'this'}}}}, 'y': {'o': {'*': 'yo'}}

You can check for further explanation question on Leetcode: Implement Trie (Prefix Tree). Link: https://leetcode.com/problems/implement-trie-prefix-tree/

Sidonie

Answer 7

I hope this example of suffix trees using js can help

class SuffixTrie {
  constructor(string) {
    this.root = {};
    this.endSymbol = '*';
    this.populateSuffixTrieFrom(string);
  }

  // O(n^2) time | O(n^2) space
  populateSuffixTrieFrom(string) {
    for (let i = 0; i < string.length; i++)
      this.insertSubStringStartingAt(i, string);
  }

  insertSubStringStartingAt(i, string) {
      let node = this.root;
      for (let j = i; j < string.length; j++) {
        const letter = string[j];
        if (!node.hasOwnProperty(letter)) node[letter] = {};
        node = node[letter];
      }

      node[this.endSymbol] = true;
  }

  // O(m) time | O(1) space
  contains(string) {
    let node = this.root;
    for (let letter of string) {
      if (!node.hasOwnProperty(letter)) return false;
      node = node[letter];
    }
    return node.hasOwnProperty(this.endSymbol);
  }
}

Panda