0

I have been studying about trie, suffix array and suffix tree.I know these data structures can be used to fast lookup and for many more applications. Now my question is, If suffix array is space efficient and easy to implement than what are the scenarios where suffix tree should be preferred over suffix array

Can you please list down the individual's advantages over one another.. Thanks in advance.

pushpendra singh
  • 43
  • 3
  • Possible duplicate of [Trie vs. suffix tree vs. suffix array](https://stackoverflow.com/questions/2487576/trie-vs-suffix-tree-vs-suffix-array) – robertklep Sep 24 '17 at 08:25

1 Answers1

1

Here is the abstract from Suffix arrays:A new method for on-line string searches written by Udi Manber and Gene Myers.

link to the article.

It provides a list of advantages of the suffix array in comparison to the suffix tree structure in general ca

A new and conceptually simple data structure, called a suffix array, for on-line string searches is introduced in this paper. Constructing and querying suffix arrays is reduced to a sort and search paradigm that employs novel algorithms. The main advantage of suffix arrays over suffix trees is that, in practice, they use three to five times less space. From a complexity standpoint, suffix arrays permit on-line string searches of the type, ‘‘Is W a substring of A?’’ to be answered in time O(P + log N), where P is the length of W and N is the length of A, which is competitive with (and in some cases slightly better than) suffix trees. The only drawback is that in those instances where the underlying alphabet is finite and small, suffix trees can be constructed in O(N) time in the worst case, versus O(N log N) time for suffix arrays. However, we give an augmented algorithm that, regardless of the alphabet size, constructs suffix arrays in O(N) expected time, albeit with lesser space efficiency. We believe that suffix arrays will prove to be better in practice than suffix trees for many applications

To make it brief, let's say that the suffix array has a significantly lower space complexity and better space locality than the suffix tree ; the trade-off being that the suffix tree runs faster in terms of time complexity (O(n) versus O(n.log(n)). Both give the suffixes of a string online(you can receive the string one char at a time, you don't need the whole string to run the algorithm).

Another advantage of the suffix array is the adaptability, for a substring search for instance ; the structure will allow for easier use of the data. It is also easier to implement as well.

m.raynal
  • 2,983
  • 2
  • 21
  • 34
  • but why can we say that the Suffix Array is lower space complexity and better space locality than the suffix tree ? is there any mathematical proof or we just base on the practical experiment ? – Tín Tr. Dec 07 '17 at 09:53
  • 1
    I'd say it is a practical expirement, since it is a metric which is very dependent on the language used, the implementation of the algorithm, and also the architecture it is run on. – m.raynal Dec 11 '17 at 12:48