Inducing enhanced suffix arrays for string collections (Q526901): Difference between revisions

The paper extends two algorithms used to construct the suffix array for a string collection and improves their practical performance. The first three chapters present an introduction to the field addressed, some basic notions and important results previously obtained. In the next chapters the algorithms SAIS and SACA-K are extended to gSAIS and gSACA-K, respectively. The idea to modify SAIS and SACA-K to compute the LCP array during the suffix array construction is used for the algorithms gSAIS and gSACA-K. For the proposed versions gSAIS+LCP and gSACA-K+LCP, gSAIS+DA and gSACA-K+DA, a complexity analysis is given. Experimental results show that the gSACA-K, gSACA-K+LCP and gSACA-K+DA algorithms are optimal for strings from constant alphabets, and they are fast with a very small memory footprint.