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

Parallelization on a Minimal Substring Search Algorithm for Regular Expressions Parallélisation sur un algorithme de recherche de sous-chaînes minimales pour les expressions régulières

Yosuke OBE, Hiroaki YAMAMOTO, Hiroshi FUJIWARA

  • Vues en texte intégral

    4

  • Citer

Résumé:

Considérons une expression régulière r de longueur m et une chaîne de texte T de longueur n sur un alphabet Σ. Puis le RE problème de recherche de sous-chaîne minimal est de trouver toutes les sous-chaînes minimales de T assorti r. Yamamoto a proposé O(mn) temps et O(m) algorithme spatial utilisant un automate de Thompson. Dans cet article, nous améliorons l'algorithme de Yamamoto en introduisant le parallélisme. L'algorithme proposé s'exécute dans O(mn) temps dans le pire des cas et dans O(mn/p) temps dans le meilleur des cas, où p désigne le nombre de processeurs. Par ailleurs, nous montrons un paramètre lié au temps parallèle de l’algorithme proposé. Nous évaluons l'algorithme expérimentalement.

Publication
IEICE TRANSACTIONS on Information Vol.E106-D No.5 pp.952-958
Date de publication
2023/05/01
Publicisé
2023/02/08
ISSN en ligne
1745-1361
DOI
10.1587/transinf.2022EDP7105
Type de manuscrit
PAPER
Catégories
Fondamentaux des Systèmes d'Information

Auteurs

Yosuke OBE
  SCSK Corporation
Hiroaki YAMAMOTO
  Shinshu University
Hiroshi FUJIWARA
  Shinshu University

Mots-clés

Table des matières