19
$\begingroup$

I am concerned with the question of the asymptotic running time of the Ukkonen's algorithm, perhaps the most popular algorithm for constructing suffix trees in linear (?) time.

Here is a citation from the book "Algorithms on strings, trees and sequences" by Dan Gusfield (section 6.5.1):

"... the Aho-Corasick, Weiner, Ukkonen and McCreight algorithms all either require $\Theta(m|\Sigma|)$ space, or the $O(m)$ time bound should be replaced with the minimum of $O(m \log m)$ and $O(m \log|\Sigma|)$".

[$m$ is the string length and $\Sigma$ is the size of the alphabet]

I don't understand why that is true.

  • Space: well, in case we represent branches out of the nodes using arrays of size $\Theta(|\Sigma|)$, then, indeed, we end up with $\Theta(m|\Sigma|)$ space usage. However, as far as I can see, it is also possible to store the branches using hash tables (say, dictionaries in Python). We would then have only $\Theta(m)$ pointers stored in all hash tables altogether (since there are $\Theta(m)$ edges in the tree), while still being able to access the children nodes in $O(1)$ time, as fast as when using arrays.
  • Time: as mentioned above, using hash tables allows us to access the outgoing branches of any node in $O(1)$ time. Since the Ukkonen's algorithm requires $O(m)$ operations (including accessing children nodes), the overall running time then would be also $O(m)$.

I would be very grateful to you for any hints on why I am wrong in my conclusions and why Gusfield is right about the dependence of the Ukkonen's algorithm on the alphabet.

Improve this question
$\endgroup$
3
  • 3
    $\begingroup$ I don't think there is any proof to the effect that an alphabet-size independent time/space bound is impossible. I believe Gusfield made the statement because there is no known method to get rid of the time bound completely. In order to establish one, you'd have to elaborate on your hash functions in more detail. A true worst-case O(1) time bound for hash lookup requires a perfect hash. It's not clear to me how to do this during the algorithm (because the hash entries aren't static at that point). $\endgroup$
    – jogojapan
    Commented Mar 7, 2013 at 5:06
  • $\begingroup$ (cont'd) You could do it once the tree is complete, but then the time bound for the algorithm itself would still be unchanged. (+1 for the question though.) $\endgroup$
    – jogojapan
    Commented Mar 7, 2013 at 5:06
  • 1
    $\begingroup$ Useful context: Ukkonen's algorithm explained $\endgroup$
    – FrankW
    Commented May 7, 2014 at 14:22

1 Answer 1

Reset to default
2
$\begingroup$

As @jogojapan mentions in the comments, hasing generally is only amortized $O(1)$, so you would only get amortized bounds for the algorithm. However, I think you do not even get these: In order to get amortized $O(1)$ hashing, the hash tables have to be of size $\Omega(\Sigma)$, so you still have $\Theta(m\Sigma)$ space (and the same time requirement for initialization).

What's more, in practice the time for setting up all these hash tables will be much higher than the time to set up arrays.

You might fare better with using a global hash table that is indexed with (node, character)-pairs, but at least the "only amortized" argument will remain.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.