著者
Ben HACHIMORI Tetsuo SHIBUYA
出版者
The Institute of Electronics, Information and Communication Engineers
雑誌
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences (ISSN:09168508)
巻号頁・発行日
vol.E92-A, no.8, pp.1750-1756, 2009-08-01

In this paper, an idea for improvement of suffix array construction using lazy evaluation is presented. Evaluation of the suffix array is based on the searching queries; only the necessary part of the suffix array is built when unevaluated part of the suffix array is referred during the searching process. This is less time consuming than constructing complete suffix array. We propose lazy evaluation of Schürmann-Stoye algorithm. Experimental results show that lazy Schürmann-Stoye algorithm runs faster than Maniscalco, which is well-recognized as the fastest suffix sorting algorithm, under the constraint of small LCP (longest common prefix) and a limited number of searching queries.