A funcionalidade de pesquisa está em construção.
A funcionalidade de pesquisa está em construção.

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 Paralelização em um algoritmo de pesquisa de substring mínima para expressões regulares

Yosuke OBE, Hiroaki YAMAMOTO, Hiroshi FUJIWARA

  • Exibições de texto completo

    4

  • Cite isto

Resumo:

Vamos considerar uma expressão regular r de comprimento m e uma string de texto T de comprimento n sobre um alfabeto Σ. Então o Problema de pesquisa mínima de substring RE é encontrar todas as substrings mínimas de T correspondente r. Yamamoto propôs O(mn) tempo e O(m) algoritmo espacial usando um autômato Thompson. Neste artigo, melhoramos o algoritmo de Yamamoto introduzindo paralelismo. O algoritmo proposto é executado em O(mn) tempo no pior caso e em O(mn/p) tempo na melhor das hipóteses, onde p denota o número de processadores. Além disso, mostramos um parâmetro relacionado ao tempo paralelo do algoritmo proposto. Avaliamos o algoritmo experimentalmente.

Publicação
IEICE TRANSACTIONS on Information Vol.E106-D No.5 pp.952-958
Data de publicação
2023/05/01
Publicitada
2023/02/08
ISSN online
1745-1361
DOI
10.1587/transinf.2022EDP7105
Tipo de Manuscrito
PAPER
Categoria
Fundamentos de Sistemas de Informação

autores

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

Palavra-chave