Efficient Representation for Online Suffix Tree Construction

N. Jesper Larsson, Kasper Fuglsang, Kenneth Karlsson

Publikation: Konference artikel i Proceeding eller bog/rapport kapitelKonferencebidrag i proceedingsForskningpeer review

Abstract

Suffix tree construction algorithms based on suffix links are popular because they are simple to implement, can operate online in linear time, and because the suffix links are often convenient for pattern matching. We present an approach using edge-oriented suffix links, which reduces the number of branch lookup operations (known to be a bottleneck in construction time) with some additional techniques to reduce construction cost. We discuss various effects of our approach and compare it to previous techniques. An experimental evaluation shows that we are able to reduce construction time to around half that of the original algorithm, and about two thirds that of previously known branch-reduced construction.
OriginalsprogEngelsk
TitelExperimental Algorithms : 13th International Symposium, SEA 2014
RedaktørerJoachim Gudmundsson, Jyrki Katajainen
Antal sider12
ForlagSpringer
Publikationsdato2014
Sider400-411
ISBN (Trykt)978-3-319-07958-5
ISBN (Elektronisk)978-3-319-07959-2
DOI
StatusUdgivet - 2014
BegivenhedSymposium on Experimental Algorithms 2014 - Copenhagen, Danmark
Varighed: 29 jun. 20141 jul. 2014
http://www.diku.dk/sea2014/

Konference

KonferenceSymposium on Experimental Algorithms 2014
Land/OmrådeDanmark
ByCopenhagen
Periode29/06/201401/07/2014
Internetadresse
NavnLecture Notes in Computer Science
Vol/bind8504
ISSN0302-9743

Fingeraftryk

Dyk ned i forskningsemnerne om 'Efficient Representation for Online Suffix Tree Construction'. Sammen danner de et unikt fingeraftryk.

Citationsformater