Are suffix trees and suffix arrays identical? What are the differences?

Question

I have read some information through internet...i found that somehow suffix tree is quite similar to suffix array but somehow they are no the same thing..

Given a string, a suffix tree construction algorithm looks something like this (I copied the algorithm from a website)

FOR i ← 1 to n-1        
FOR j ← 1 to i+1             
   find the end path for S[j…i]
   extend the path, if needed, to S[i+1] 

suffix tree able to list down all the subtring obtained from a given string

However, does the suffix array also give the same functionality to obtain the list of substrings? Or are suffix arrays just an implementation of suffix trees? Or suffix array just provide some storing function?

Answer 1

A suffix array is a space-efficient datastructure, which, if stored together with the original string, provides the same functions as a suffix tree.

So yes, you can think of a suffix array as a storage mechanism for suffix trees. Depending on the details, there may be performance costs to using arrays over full-blown trees, which typically are outweighed by the space-use benefits. I believe the arrays are constructed almost identically to the way trees are constructed, and, in practice, suffix arrays are the preferred method for storing/representing a suffix tree.

Answer 2

The word "suffix array" seems to be used ambiguously. On the one hand, it may mean precisely what the term says: an array of (sorted) suffixes. On the other hand, it may refer to this array of suffixes together with some other tables, making the data structure more useful for various purposes. For clarity, you can use the term "suffix table" for the array itself, and use the term "suffix array" as a cover term for the various multi-table data structures that employ a suffix table. So with this terminology, it seems clear that you downloaded a program for suffix table construction. In other words, you downloaded an implementation of a suffix sorting algorithm.

This distinction between suffix array and suffix table is important to make when comparing the efficiency of suffix arrays and suffix trees. The suffix table itself is obviously succint and efficient. But with each additional table, the gap is narrowed, so that in the end, it is difficult to say which is more efficient. A number of papers in the last ten years have reported an advantage for suffix arrays. But to achieve this superior performance, you need to be a very clever programmer.

If you really want to learn about suffix arrays, then in my opinion, learning about suffix sorting is not the place to start. Start instead with the "Extended Suffix Array" paper by Abouelhoda et al. This is not an easy paper. But on the other hand, it is very widely cited, and each paper that cites it also needs to summarize it to some extent. So in the end, if you put some work into it, you will definitely get through the paper. Once finished with Abouelhoda, read any papers that cite Aboueloda. Then read the earlier Computational Linguistics paper by Yamamoto and Church and of course papers citing this. My guess is that non-computational linguists will also get something out of this paper (don't be too constrained by your own narrow field of study). Pretty soon you'll become a suffix array expert without ever having learned about suffix sorting. When you get to this point, then go back and read some of the suffix sorting literature. You'll see that it's a very interesting fundamental CS problem. Finally, for other fundamental CS issues related to suffix arrays (combinatoric issues), I recommend the dissertation of Klaus Schürmann (Bielefeld University).