The search functionality is under construction.
The search functionality is under construction.

Parallelization on a Minimal Substring Search Algorithm for Regular Expressions

Yosuke OBE, Hiroaki YAMAMOTO, Hiroshi FUJIWARA

  • Full Text Views

    4

  • Cite this

Summary :

Let us consider a regular expression r of length m and a text string T of length n over an alphabet Σ. Then, the RE minimal substring search problem is to find all minimal substrings of T matching r. Yamamoto proposed O(mn) time and O(m) space algorithm using a Thompson automaton. In this paper, we improve Yamamoto's algorithm by introducing parallelism. The proposed algorithm runs in O(mn) time in the worst case and in O(mn/p) time in the best case, where p denotes the number of processors. Besides, we show a parameter related to the parallel time of the proposed algorithm. We evaluate the algorithm experimentally.

Publication
IEICE TRANSACTIONS on Information Vol.E106-D No.5 pp.952-958
Publication Date
2023/05/01
Publicized
2023/02/08
Online ISSN
1745-1361
DOI
10.1587/transinf.2022EDP7105
Type of Manuscript
PAPER
Category
Fundamentals of Information Systems

Authors

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

Keyword