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.
| Original language | English |
|---|---|
| Title of host publication | Experimental Algorithms : 13th International Symposium, SEA 2014 |
| Editors | Joachim Gudmundsson, Jyrki Katajainen |
| Number of pages | 12 |
| Publisher | Springer |
| Publication date | 2014 |
| Pages | 400-411 |
| ISBN (Print) | 978-3-319-07958-5 |
| ISBN (Electronic) | 978-3-319-07959-2 |
| DOIs | |
| Publication status | Published - 2014 |
| Event | Symposium on Experimental Algorithms 2014 - Copenhagen, Denmark Duration: 29 Jun 2014 → 1 Jul 2014 http://www.diku.dk/sea2014/ |
Conference
| Conference | Symposium on Experimental Algorithms 2014 |
|---|---|
| Country/Territory | Denmark |
| City | Copenhagen |
| Period | 29/06/2014 → 01/07/2014 |
| Internet address |
| Series | Lecture Notes in Computer Science |
|---|---|
| Volume | 8504 |
| ISSN | 0302-9743 |
Keywords
- Suffix tree
- Suffix links
- Pattern matching
- Branch lookup optimization
- Construction time reduction