A comparison of imperative and purely functional suffix tree constructions

Giegerich R, Kurtz S (1995)
In: Science of Computer Programming. SCIENCE OF COMPUTER PROGRAMMING, 25(2-3). ELSEVIER SCIENCE BV: 187-218.

Konferenzbeitrag | Veröffentlicht | Englisch
 
Download
Es wurden keine Dateien hochgeladen. Nur Publikationsnachweis!
Autor*in
Giegerich, RobertUniBi; Kurtz, Stefan
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
1995
Titel des Konferenzbandes
Science of Computer Programming
forms.conference.field.series_title_volume.series_title.label
SCIENCE OF COMPUTER PROGRAMMING
Band
25
Ausgabe
2-3
Seite(n)
187-218
ISSN
0167-6423
Page URI
https://pub.uni-bielefeld.de/record/1628987

Zitieren

Giegerich R, Kurtz S. A comparison of imperative and purely functional suffix tree constructions. In: Science of Computer Programming. 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, SCIENCE OF COMPUTER PROGRAMMING, 25, 187-218. ELSEVIER SCIENCE BV. https://doi.org/10.1016/0167-6423(95)00003-8
Giegerich, R., and Kurtz, S. (1995). “A comparison of imperative and purely functional suffix tree constructions” in Science of Computer Programming 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. 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, 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. 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. SCIENCE OF COMPUTER PROGRAMMING. 187-218.

Export

Markieren/ Markierung löschen
Markierte Publikationen

Open Data PUB

Web of Science

Dieser Datensatz im Web of Science®

Suchen in

Google Scholar