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
Mari kita pertimbangkan ungkapan biasa r panjang m dan rentetan teks T panjang n atas abjad Σ. Kemudian, yang Masalah carian subrentetan minimum RE adalah untuk mencari semua subrentetan minimum T sepadan r. Yamamoto mencadangkan O(mn) masa dan O(m) algoritma ruang menggunakan automatik Thompson. Dalam kertas ini, kami menambah baik algoritma Yamamoto dengan memperkenalkan keselarian. Algoritma yang dicadangkan berjalan masuk O(mn) masa dalam kes terburuk dan dalam O(mn/p) masa dalam kes terbaik, di mana p menunjukkan bilangan pemproses. Selain itu, kami menunjukkan parameter yang berkaitan dengan masa selari algoritma yang dicadangkan. Kami menilai algoritma secara eksperimen.
Yosuke OBE
SCSK Corporation
Hiroaki YAMAMOTO
Shinshu University
Hiroshi FUJIWARA
Shinshu University
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.
Salinan
Yosuke OBE, Hiroaki YAMAMOTO, Hiroshi FUJIWARA, "Parallelization on a Minimal Substring Search Algorithm for Regular Expressions" in IEICE TRANSACTIONS on Information,
vol. E106-D, no. 5, pp. 952-958, May 2023, doi: 10.1587/transinf.2022EDP7105.
Abstract: 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.
URL: https://global.ieice.org/en_transactions/information/10.1587/transinf.2022EDP7105/_p
Salinan
@ARTICLE{e106-d_5_952,
author={Yosuke OBE, Hiroaki YAMAMOTO, Hiroshi FUJIWARA, },
journal={IEICE TRANSACTIONS on Information},
title={Parallelization on a Minimal Substring Search Algorithm for Regular Expressions},
year={2023},
volume={E106-D},
number={5},
pages={952-958},
abstract={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.},
keywords={},
doi={10.1587/transinf.2022EDP7105},
ISSN={1745-1361},
month={May},}
Salinan
TY - JOUR
TI - Parallelization on a Minimal Substring Search Algorithm for Regular Expressions
T2 - IEICE TRANSACTIONS on Information
SP - 952
EP - 958
AU - Yosuke OBE
AU - Hiroaki YAMAMOTO
AU - Hiroshi FUJIWARA
PY - 2023
DO - 10.1587/transinf.2022EDP7105
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E106-D
IS - 5
JA - IEICE TRANSACTIONS on Information
Y1 - May 2023
AB - 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.
ER -