A comparison of imperative and purely functional suffix tree constructions

Giegerich R, Kurtz S (1995)
In: SCIENCE OF COMPUTER PROGRAMMING. 25. ELSEVIER SCIENCE BV: 187-218.

Conference Paper | Published | English

No fulltext has been uploaded

Author
;
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.
Publishing Year
ISSN
PUB-ID

Cite this

Giegerich R, Kurtz S. A comparison of imperative and purely functional suffix tree constructions. In: SCIENCE OF COMPUTER PROGRAMMING. Vol 25. ELSEVIER SCIENCE BV; 1995: 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.
Giegerich, R., and Kurtz, S. (1995). “A comparison of imperative and purely functional suffix tree constructions” in SCIENCE OF COMPUTER PROGRAMMING, vol. 25, (ELSEVIER SCIENCE BV), 187-218.
Giegerich, R., & Kurtz, S., 1995. A comparison of imperative and purely functional suffix tree constructions. In SCIENCE OF COMPUTER PROGRAMMING. no.25 ELSEVIER SCIENCE BV, pp. 187-218.
R. Giegerich and S. Kurtz, “A comparison of imperative and purely functional suffix tree constructions”, SCIENCE OF COMPUTER PROGRAMMING, vol. 25, ELSEVIER SCIENCE BV, 1995, pp.187-218.
Giegerich, R., Kurtz, S.: A comparison of imperative and purely functional suffix tree constructions. SCIENCE OF COMPUTER PROGRAMMING. 25, p. 187-218. ELSEVIER SCIENCE BV (1995).
Giegerich, Robert, and Kurtz, Stefan. “A comparison of imperative and purely functional suffix tree constructions”. SCIENCE OF COMPUTER PROGRAMMING. ELSEVIER SCIENCE BV, 1995.Vol. 25. 187-218.
This data publication is cited in the following publications:
This publication cites the following data publications:

Export

0 Marked Publications

Open Data PUB

Web of Science

View record in Web of Science®

Search this title in

Google Scholar