The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice
The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice
Dans cet article, une idée d'amélioration de la construction de tableaux de suffixes à l'aide d'une évaluation paresseuse est présentée. L'évaluation du tableau de suffixes est basée sur les requêtes de recherche ; seule la partie nécessaire du tableau de suffixes est construite lorsqu'une partie non évaluée du tableau de suffixes est référencée pendant le processus de recherche. Cela prend moins de temps que de construire un tableau de suffixes complet. Nous proposons une évaluation paresseuse de l'algorithme de Schürmann-Stoye. Les résultats expérimentaux montrent que l'algorithme paresseux de Schürmann-Stoye s'exécute plus rapidement que Maniscalco, qui est reconnu comme l'algorithme de tri de suffixes le plus rapide, sous la contrainte d'un petit LCP (préfixe commun le plus long) et d'un nombre limité de requêtes de recherche.
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Copier
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
Copier
@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},}
Copier
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 -