Succinct suffix sorting in external memory
作者：
Highlights：
• This research puts forward a novel algorithm called nSAIS for inducing suffix array using external memory.
• The time, space and IO complexities of nSAIS are linearly proportional to the input size.
• The constant factor for the space complexity of nSAIS is not more than 6.82.
• A program of the algorithm nSAIS is engineered for performance evaluation.
• nSAIS is rather general for the datasets of different sizes and characteristics.
摘要
•This research puts forward a novel algorithm called nSAIS for inducing suffix array using external memory.•The time, space and IO complexities of nSAIS are linearly proportional to the input size.•The constant factor for the space complexity of nSAIS is not more than 6.82.•A program of the algorithm nSAIS is engineered for performance evaluation.•nSAIS is rather general for the datasets of different sizes and characteristics.
论文关键词：Suffix array,sorting algorithm,external memory
论文评审过程：Received 8 April 2020, Revised 26 July 2020, Accepted 29 August 2020, Available online 9 September 2020, Version of Record 4 December 2020.
论文官网地址：https://doi.org/10.1016/j.ipm.2020.102378
