Comparisons of Practical Performance for Constructing Compressed Suffix Arrays
Park Chi-Seong, Min Hwan Kim, Suk‐Hwan Lee, Ki‐Ryong Kwon, Dong-Kyue Kim · Jeongbo gwahaghoe nonmunji. si'seu'tem mich i'lon · 2007
Suffix arrays, fundamental full-text index data structures, can be efficiently used where patterns are queried many times. Although many useful full-text index data structures have been proposed, their O(nlogn)-bit space consumption motivates researchers to develop more space-efficient ones. However, their space efficient versions such as the compressed suffix array and the FM-index have been developed; those can not reduce the practical working space because their constructions are based on the existing suffix array. Recently, two direct construction algorithms of compressed suffix arrays from the text without constructing the suffix array have been proposed. In this paper, we compare practical performance of these algorithms of compressed suffix arrays with that of various algorithms of suffix arrays by measuring the construction times, the peak memory usages during construction and the sizes of their final outputs.