An incomplex algorithm for fast suffix array construction
Software Practice and ExperiencePublished 26 September 2006
Klaus‐Bernd Schürmann, Jens Stoye
Citations48
SJR quartileQ2
SJR score0.68
SNIP1.26
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
This work presents a practical algorithm for suffix array construction that consists of two easy‐to‐implement components that achieves a very fast construction for common strings as well as for worst case strings by enhancing the algorithm with further techniques.
Abstract
Abstract The suffix array of a string is a permutation of all starting positions of the string's suffixes that are lexicographically sorted. We present a practical algorithm for suffix array construction that consists of two easy‐to‐implement components. First it sorts the suffixes with respect to a fixed length prefix; then it refines each bucket of suffixes sharing the same prefix using the order of already sorted suffixes. Other suffix array construction algorithms follow more complex strategies. Moreover, we achieve a very fast construction for common strings as well as for worst case strings by enhancing our algorithm with further techniques. Copyright © 2006 John Wiley & Sons, Ltd.
Keywords
Computer ScienceBiochemistry, Genetics and Molecular Biology
Journal of the Operational Research SocietyIntroduction to Algorithms
16,942 Citations1991V. J. Rayward‐Smith, Thomas H. Cormen +2 more
A Block-sorting Lossless Data Compression Algorithm
2,362 Citations1994Michael T. Burrows, D. J. Wheeler
A block-sorting, lossless data compression algorithm, and the implementation of that algorithm, that achieves speed comparable to algorithms based on the techniques of Lempel and Ziv, but obtains compression close to the best statistical modelling techniques.
SIAM Journal on ComputingSuffix Arrays: A New Method for On-Line String Searches
1,962 Citations1993Udi Manber, Gene Myers
A new and conceptually simple data structure, called a suffixarray, for on-line string searches is introduced in this paper, and it is believed that suffixarrays will prove to be better in practice than suffixtrees for many applications.
Optimal suffix tree construction with large alphabets
441 Citations2002Martı́n Farach-Colton
This work builds suffix trees in linear time for integer alphabet using Weiner's algorithm, which matches a trivial /spl Omega/(n log n)-time lower bound based on sorting.
Lecture notes in computer scienceSimple Linear Work Suffix Array Construction
405 Citations2003Juha Kärkkäinen, Peter Sanders
The skew algorithm for suffix array construction over integer alphabets that can be implemented to run in linear time using integer sorting as its only nontrivial subroutine is introduced.
Symposium on Discrete AlgorithmsFast algorithms for sorting and searching strings
398 Citations1997Jon Bentley, Robert Sedgewick
This work presents theoretical algorithms for sorting and searching multikey data, and derive from them practical C implementations for applications in which keys are character strings, and presents extensions to more complex string problems, such as partial-match searching.
Software Practice and ExperienceReducing the space requirement of suffix trees
333 Citations1999Stefan Kurtz
This work shows that suffix trees store various kinds of redundant information, and exploits these redundancies to obtain more space efficient representations, which can be constructed without extra space, and as fast as previous representations.
Rapid identification of repeated patterns in strings, trees and arrays
276 Citations1972Richard M. Karp, Raymond E. Miller +1 more
This paper describes a strategy for constructing efficient algorithms for solving two types of matching problems and develops explicit algorithms for these two problems applied to strings and arrays.
Journal of the ACMOn the sorting-complexity of suffix tree construction
211 Citations2000Martı́n Farach-Colton, Paolo Ferragina +1 more
A recursive technique for building suffix trees that yields optimal algorithms in different computational models that match the sorting lower bound and for an alphabet consisting of integers in a polynomial range the authors get the first known linear-time algorithm.
Software Practice and ExperienceEngineering a sort function
189 Citations1993Jon Bentley, M. D. McIlroy
A new qsortfunction for a C library that chooses partitioning elements by a new sampling scheme; it partitions by a novel solution to Dijkstra's Dutch National Flag problem; and it swaps efficiently.
Journal of Discrete AlgorithmsSpace efficient linear time construction of suffix arrays
185 Citations2004Pang Ko, Srinivas Aluru
This work presents a linear time algorithm to sort all the suffixes of a string over a large alphabet of integers, which improves upon the best known direct algorithm for suffix sorting, which takes O(n log n) time.
AlgorithmicaEngineering a Lightweight Suffix Array Construction Algorithm
164 Citations2004Giovanni Manzini, Paolo Ferragina
This algorithm is “lightweight” in the sense that it uses very small space in addition to the space required by the suffix array itself, and is fast even when the input contains many repetitions: this has been shown by extensive experiments with inputs of size up to 110 Mb.
Communications of the ACMAlgorithm 347: an efficient algorithm for sorting with minimal storage [M1]
124 Citations1969Richard C. Singleton
The real procedure gauss computes the area under the left-hand portion of the normal curve by using National Bureau of Standards formulas 26.6.4, 26.5, and 26.8 for computation of the statistic and the approximation for the approximation.
Breaking a time-and-space barrier in constructing full-text indices
95 Citations2004Wing-Kai Hon, Kunihiko Sadakane +1 more
These are the first algorithms that achieve 0(n log n) time with optimal working space, under a reasonable assumption that log |A| = o(log n) and the general case where the size of the alphabet A is not constant.
On the performance of BWT sorting algorithms
93 Citations2002John P. Seward
This paper presents the base algorithm using a more formal framework, describes two important optimisations not present in the original paper, and measures performance of the variants on a set of 14 files to give a clearer picture of which variants perform well, and why.
Journal of Discrete AlgorithmsConstructing suffix arrays in linear time
92 Citations2004Dong Kyue Kim, Jeong Seop Sim +2 more
A linear-time algorithm to construct suffix arrays for integer alphabets, which do not use suffix trees as intermediate data structures during its construction, which implies that the time complexity of directly constructing suffix arrays matches that of constructing suffix trees.
Engineering radix sort
88 Citations1993Peter M. McIlroy, Keith Bostic +1 more
Three ways to sort strings by bytes left to right-a stable list sort, a stable two-array sort, and an in-place "American flag" sor¿-are illustrated with practical C programs, and all three perform comparably, usually running at least twice as fast as a good quicksort.
Faster Suffix Sorting
81 Citations1999Niklas Larsson
An efficient method for in memory construction of suffix arrays
70 Citations2003Hidenori Itoh, Hiromi Tanaka
The suffix array is a string-indexing structure and a memory efficient alternative to the suffix tree that has many advantages for text processing and an efficient algorithm for sorting suffixes is proposed, called the two-stage suffix sort.
Lecture notes in computer scienceA Fast Algorithm for Constructing Suffix Arrays for Fixed-Size Alphabets
17 Citations2004Dong Ki Kim, Jun-Ha Jo +1 more
This paper presents a fast algorithm for constructing suffix arrays for the fixed-size alphabet that constructs suffix arrays faster than any other algorithms developed for integer or general alphabets when the size of the alphabet is fixed.