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

Ben HACHIMORI; Tetsuo SHIBUYA

doi:10.1587/transfun.E92.A.1750

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

Ben HACHIMORI, Tetsuo SHIBUYA

Full Text Views

0

Cite this

Summary :

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.

Publication: IEICE TRANSACTIONS on Fundamentals Vol.E92-A No.8 pp.1750-1756

Publication Date: 2009/08/01

Publicized

Online ISSN: 1745-1337

DOI: 10.1587/transfun.E92.A.1750

Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)

Category: Theory

Cite this

Copy

Ben HACHIMORI, Tetsuo SHIBUYA, "Lazy Suffix Array: The Data Structure for Online Construction and Pattern Searching" in IEICE TRANSACTIONS on Fundamentals, vol. E92-A, no. 8, pp. 1750-1756, August 2009, doi: 10.1587/transfun.E92.A.1750.
Abstract: 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.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.E92.A.1750/_p

Copy

@ARTICLE{e92-a_8_1750,
author={Ben HACHIMORI, Tetsuo SHIBUYA, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Lazy Suffix Array: The Data Structure for Online Construction and Pattern Searching},
year={2009},
volume={E92-A},
number={8},
pages={1750-1756},
abstract={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.},
keywords={},
doi={10.1587/transfun.E92.A.1750},
ISSN={1745-1337},
month={August},}

Copy

TY - JOUR
TI - Lazy Suffix Array: The Data Structure for Online Construction and Pattern Searching
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 1750
EP - 1756
AU - Ben HACHIMORI
AU - Tetsuo SHIBUYA
PY - 2009
DO - 10.1587/transfun.E92.A.1750
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E92-A
IS - 8
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - August 2009
AB - 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.
ER -