Premium
An incomplex algorithm for fast suffix array construction
Author(s) -
Schürmann KlausBernd,
Stoye Jens
Publication year - 2007
Publication title -
software: practice and experience
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.437
H-Index - 70
eISSN - 1097-024X
pISSN - 0038-0644
DOI - 10.1002/spe.768
Subject(s) - suffix array , suffix , lexicographical order , compressed suffix array , prefix , generalized suffix tree , string (physics) , permutation (music) , computer science , algorithm , suffix tree , trie , string searching algorithm , data structure , mathematics , combinatorics , programming language , philosophy , linguistics , physics , acoustics , mathematical physics
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.