Lazy Suffix Array : The Data Structure for Online Construction and Pattern Searching

スポンサーリンク

概要

• 論文の詳細を見る

• 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.

• 2009-08-01

著者

• Shibuya Tetsuo

  Human Genome Center, Institute of Medical Science, The University of Tokyo

• Shibuya Tetsuo

  Human Genome Center Institute Of Medical Science The University Of Tokyo

• Hachimori Ben

  Human Genome Center Institute Of Medical Science The University Of Tokyo

関連論文

• Message from the Editor-in-Chief
• Lazy Suffix Array : The Data Structure for Online Construction and Pattern Searching
• Max-Shift BM and Max-Shift Horspool: Practical Fast Exact String Matching Algorithms
• Max-Shift BM and Max-Shift Horspool: Practical Fast Exact String Matching Algorithms

スポンサーリンク