A comparison of imperative and purely functional suffix tree constructions

Giegerich R, Kurtz S (1995)
SCIENCE OF COMPUTER PROGRAMMING 25(2-3): 187-218.

Download
Es wurde kein Volltext hochgeladen. Nur Publikationsnachweis!
Konferenzbeitrag | Veröffentlicht | Englisch
Autor
;
Abstract / Bemerkung
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.
Erscheinungsjahr
Band
25
Zeitschriftennummer
2-3
Seite
187-218
ISSN
PUB-ID

Zitieren

Giegerich R, Kurtz S. A comparison of imperative and purely functional suffix tree constructions. SCIENCE OF COMPUTER PROGRAMMING. 1995;25(2-3):187-218.
Giegerich, R., & Kurtz, S. (1995). A comparison of imperative and purely functional suffix tree constructions. SCIENCE OF COMPUTER PROGRAMMING, 25(2-3), 187-218. doi:10.1016/0167-6423(95)00003-8
Giegerich, R., and Kurtz, S. (1995). A comparison of imperative and purely functional suffix tree constructions. SCIENCE OF COMPUTER PROGRAMMING 25, 187-218.
Giegerich, R., & Kurtz, S., 1995. A comparison of imperative and purely functional suffix tree constructions. SCIENCE OF COMPUTER PROGRAMMING, 25(2-3), p 187-218.
R. Giegerich and S. Kurtz, “A comparison of imperative and purely functional suffix tree constructions”, SCIENCE OF COMPUTER PROGRAMMING, vol. 25, 1995, pp. 187-218.
Giegerich, R., Kurtz, S.: A comparison of imperative and purely functional suffix tree constructions. SCIENCE OF COMPUTER PROGRAMMING. 25, 187-218 (1995).
Giegerich, Robert, and Kurtz, Stefan. “A comparison of imperative and purely functional suffix tree constructions”. SCIENCE OF COMPUTER PROGRAMMING 25.2-3 (1995): 187-218.