Engineering a Lightweight Suffix Array Construction Algorithm

摘要: In this paper we describe a new algorithm for building the suffix array of string. This task is equivalent to problem lexicographically sorting all suffixes input Our based on approach called deep–shallow sorting: use “shallow” sorter with short common prefix, and “deep” long prefix. All known algorithms either require large amount space or are inefficient when string contains many repeated substrings. has been designed overcome dichotomy. “lightweight” in sense that it uses very small addition required by itself. At same time our fast even repetitions: shown extensive experiments inputs size up 110 Mb. The source code algorithm, as well C library providing simple API, available under GNU GPL.