Suffix array: Difference between revisions

Revision as of 00:38, 6 February 2009

Revision as of 00:39, 6 February 2009

Line 24:

The easiest way to construct a suffix array is to use an efficient [[comparison sort]] algorithm. This requires <math>O(n \log n)</math> suffix comparisons, but a suffix comparison requires <math>O(n)</math> time, so the overall runtime of this approach is <math>O(n^2 \log n)</math>. More sophisticated algorithms improve this to <math>O(n \log n)</math> by exploiting the results of partial sorts to avoid redundant comparisons. Several <math>\Theta(n)</math> algorithms (of Pang Ko and Srinivas AluruJuha, Petuha Kärkkäinen and Peter Sanders, etc) have also been developed which provide faster construction and have space usage of <math>O(n)</math> with low constants.

A recent work by Salson ''et al'' presentproposes an algorithm for updating the suffix array of a text that has been edited. instead of rebuilding a new suffix array from scratch.Even if the theoretical worst-case time complexity is <math>O(n \log n)</math>, it appears to perform much better in practice that the quickest methods.

==Applications==