dragoon's blog

String Algorithms
By dragoon, 11 years ago, In English

Three popular algorithms for string related problems are: Suffix Array, Suffix Automaton and Suffix Tree. So what are the advantages/disadvantages of each of these? Is there any types of problems which is easy to tackle by one of these 3, but not by other 2? Let's gather these types of information in this post. :)

  • Vote: I like it
  • +79
  • Vote: I do not like it

Comments Comments (9)
| Write comment?
»
11 years ago, # |
  Vote: I like it +25 Vote: I do not like it

From theoretical perspective there is a papper Abouelhoda, Kurtz, Ohlebusch: Replacing suffix trees with enhanced suffix arrays claiming that any problem solvable by suffix tree can be solved with same time complexity using [enhanced] suffix arrays:

Abstract

The suffix tree is one of the most important data structures in string processing and comparative genomics. However, the space consumption of the suffix tree is a bottleneck in large scale applications such as genome analysis. In this article, we will overcome this obstacle. We will show how every algorithm that uses a suffix tree as data structure can systematically be replaced with an algorithm that uses an enhanced suffix array and solves the same problem in the same time complexity. The generic name enhanced suffix array stands for data structures consisting of the suffix array and additional tables. Our new algorithms are not only more space efficient than previous ones, but they are also faster and easier to implement.

→ Reply
»
11 years ago, # |
  Vote: I like it +49 Vote: I do not like it

Here is my humble opinion:

  1. Suffix array. It's the simplest structure, but is built in instead of linear time. Requires linear memory. It's usually easy to reforumulate complex problem in terms of suffix array, but the solution is not always easy to implement: tons of binary searches and LCPs usage is common. It's not so hard, but can be frightening in the beginning.
  2. Suffix tree. It can be built online in linear time (in contrast with suffix array), but require up to O(nΣ) memory (Σ is a size of the alphabet). Solutions that use it are very similar to ones using suffix array. They are usually a bit simpler to implement, though.
  3. Suffix automaton. It's the most unintuitive structure for me. Time and memory consumption concide with suffix tree's. However, it is easier to implement. Set of problems solved by automaton differ from the one of tree and array a lot. Automaton uses 'right contexts' instead of prefixes and it can be quite confusing, as it is for me. So, I don't use automaton, if the problem is not about "writing an automaton".

I prefer suffix array on contests, but automaton may be preferrable in some cases. In contrast, my teammate likes automaton more than array. I don't remember a problem which can be solved with suffix tree only (except the training ones from Summer Informatics School).

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it +19 Vote: I do not like it

    The suffix array can be built in linear time too, and certainly faster than a suffix tree, using the Karkkainen algorithm (I've also seen it under the name DC3). Most implementations look daunting, but it is possible to prepare one which is both fast and short (easy/fast to write from a code-notebook). Of course, the nlogn one is way simpler.

    → Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    i prefer suffix array too~

    however, some problem with strict time limit may force me to use automaton :(

    → Reply
»
11 years ago, # |
  Vote: I like it +6 Vote: I do not like it

There is another type of suffix array called Dynamic Extended Suffix Array which is used for online suffix array problems, here is the link http://www-igm.univ-mlv.fr/~lecroq/articles/jda2009.pdf, in practice is not so easy to implement but is very useful.

→ Reply
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I'm currently learning all this string data-structures and I'm having troubles on how to implement them, do someone have a 'clear' implementation of them for a good understanding ? The ones I managed to find are all obscure and weird, making everything harder for beginners.

→ Reply
»
11 years ago, # |
  Vote: I like it +5 Vote: I do not like it

In this book, almost all the algorithms on texts are well explained, including suffix automaton.

http://www.google.com.cu/url?sa=t&rct=j&q=&esrc=s&source=web&cd=8&cad=rja&ved=0CGEQFjAH&url=http%3A%2F%2Fbooks.google.com%2Fbooks%2Fabout%2FText_Algorithms.html%3Fid%3DtSxLkRIyvoIC&ei=6d4sUsPONYfY9ATkyoCgBA&usg=AFQjCNFEkZyk_QHOcQaTzFldcBJ93rcO7g&bvm=bv.51773540,d.eWU

→ Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Many texts say that there is a relation between suffix automata of a string and suffix tree of the reverse string. I could not grab that. It would be great, if someone could explain that.

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Suffix tree of the reverse string == suffix link tree of automaton of the string

    → Reply