| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 10331852 | Information Processing Letters | 2014 | 5 Pages |
Abstract
Suffix array (SA) construction is a time-and-memory bottleneck in many string processing applications. In this paper we improve the runtime of a small-space - semi-external - SA construction algorithm by Kärkkäinen (TCS, 2007) [5]. We achieve a speedup in practice of 2-4 times, without increasing memory usage. Our main contribution is a way to implement the “pointer copying” heuristic, used in less space-efficient SA construction algorithms, in a memory-efficient way.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Jasbir Dhaliwal,