A comparison of imperative and purely functional suffix tree constructions

This work designs two “naive” versions of these algorithms which are not linear time, but use simpler data structures, and can be implemented in a purely functional style, and presents a new, “lazy” suffix tree construction which is even simpler.

Abstract

We explore the design space of implementing suffix tree algorithms in the functional paradigm. We review the linear time and space algorithms of McCreight and Ukkonen. Based on a new terminology of nested suffixes and nested prefixes, we give a simpler and more declarative explanation of these algorithms than was previously known. We design two "naive" versions of these algorithms which are not linear time, but use simpler data structures, and can be implemented in a purely functional style. Furthermore, we present a new, "lazy" suffix tree construction which is even simpler. We evaluate both imperative and functional implementations of these algorithms. Our results show that the naive algorithms perform very favourably, and in particular, the lazy construction compares very well to all the others.