La fonctionnalité de recherche est en construction.
La fonctionnalité de recherche est en construction.

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

Lazy Suffix Array: The Data Structure for Online Construction and Pattern Searching Tableau de suffixes paresseux : la structure de données pour la construction en ligne et la recherche de modèles

Ben HACHIMORI, Tetsuo SHIBUYA

  • Vues en texte intégral

    0

  • Citer

Résumé:

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.

Publication
IEICE TRANSACTIONS on Fundamentals Vol.E92-A No.8 pp.1750-1756
Date de publication
2009/08/01
Publicisé
ISSN en ligne
1745-1337
DOI
10.1587/transfun.E92.A.1750
Type de manuscrit
Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
Catégories
Théorie

Auteurs

Mots-clés

Table des matières