17

I just wanna know, when a suffix tree is superior to an enhanced suffix array.

After reading Replacing suffix trees with enhanced suffix arrays i don't see a reason to use suffix trees anymore. Some methods can get complicated, but you can do everything with a suffix array, what you can do with a suffix tree and you need the same time complexity but less memory.

A survey even showed, that suffix arrays are faster, because they are cache friendlier, and don't produce as much cache misses, then suffix trees (so the cache can predict the array usage much better, then on the recursive tree structure).

So, does anyone know a reason to choose a suffix tree over a suffix array?

edit Ok, if you know more tell me, so far its:

  • Suffixarrays dont allow on-line construction
  • Some pattern matching algorithms run faster on Suffixtrees
  • (added) because of the on-line construction, you can save it on hd a and enlarge an existent suffixtree. If you use a SSD, it should be quiet fast aswell.
Nicolas
  • 950
  • 1
  • 7
  • 15
  • Just a guess but Suffix Trees could be smaller in terms of memory in actual implementation. – Justin Jun 25 '12 at 17:39
  • 1
    @Justin: No, in fact enhanced suffix arrays consume less memory, which is what the linked paper is all about – Niklas B. Jun 25 '12 at 17:41
  • Hmm, i don't know. If i compare Ukkonen's suffixtree construction to a linear time suffix array construction, it's not easier imo. And if you just look at the simplest construction, its easier to understand to sort a list of suffixes then to arrange them in a tree, or? – Nicolas Jun 25 '12 at 18:05
  • Might it be because of the complexity of the enhanced suffix array? We're all human beings and many programmers are too lazy to learn a new algorithm if it takes reading a dense 35-page document. I'm just reflecting on myself, because I just spent many hours to research suffix trees, made a mistake and implemented the wrong data structure, finally understood Ukkonen's algorithm (I hope)... And then I opened the Enhanced Suffix Array paper and realized how much more I need to learn to implement it (probably well over a day worth of reading/learning/coding - not including my prior research) – Sergiy Migdalskiy Jan 13 '18 at 04:39

2 Answers2

1

There are some interesting thoughts on the subject in SO itself. You can also find more technical material available on line. There is another paper that might help you with your issues, claiming to be another efficient way to implement these structures.

I am not an expert in the issue, but it seems to me that suffix arrays may be somewhat slower, even though they are more space efficient. Nevertheless, I lack the practical experience to be more detailed about both of them.

Community
  • 1
  • 1
rlinden
  • 2,053
  • 1
  • 12
  • 13
-3

Another example to show that a suffix tree is superior:

You can easily construct a suffix array if you have a suffix tree already.

But it's much more complicated to construct a suffix tree from a suffix array.

lavin
  • 2,276
  • 2
  • 13
  • 15