Fungsi carian sedang dalam pembinaan.
Fungsi carian sedang dalam pembinaan.

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 Keselarian pada Algoritma Carian Subrentetan Minimum untuk Ungkapan Biasa

Yosuke OBE, Hiroaki YAMAMOTO, Hiroshi FUJIWARA

  • pandangan teks lengkap

    4

  • Petikan Ini

Ringkasan:

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.

Jawatankuasa
IEICE TRANSACTIONS on Information Vol.E106-D No.5 pp.952-958
Tarikh penerbitan
2023/05/01
Diumumkan
2023/02/08
ISSN dalam talian
1745-1361
DOI
10.1587/transinf.2022EDP7105
Jenis Manuskrip
PAPER
kategori
Asas Sistem Maklumat

Pengarang

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

Kata kunci

Contents [show]