Suffix Arrays vs Suffix Trees

Question

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.

Answer 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.