O(1)-time parallel string-matching algorithm with VLDCs

被引：7

作者：

Chung, KL

机构：

[1] Department of Information Management, Natl. Taiwan Institute of Technology, Taipei, 10672, Keelung Road

来源：

PATTERN RECOGNITION LETTERS | 1996年 / 17卷 / 05期

关键词：

string matching with VLDCs; parallel algorithm; pattern analysis; reconfigurable meshes;

D O I：

10.1016/0167-8655(96)00007-4

中图分类号：

TP18 [人工智能理论];

学科分类号：

081104 ; 0812 ; 0835 ; 1405 ;

摘要：

Given a text of length n and a pattern of length m over a finite alphabet Sigma, we consider the string matching (SM) problem with variable length don't cares (VLDCs), where a VLDC (not in Sigma) in the pattern can match any substring in the text. This paper presents a first time-optimal parallel SM algorithm with VLDCs. The proposed algorithm can be performed in 0(1) time on an in x n mesh-connected computer with a reconfigurable bus system using O(nm) processors. The previous fastest known parallel SM algorithm takes O(log n) time on the EREW PRAM model with O(nm/log n) processors.

引用

页码：475 / 479

页数：5

共 16 条

[1] PARALLEL STRING-MATCHING WITH VARIABLE-LENGTH DONT CARES [J].

BERTOSSI, AA ;

LOGI, F .

JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING, 1994, 22 (02) :229-234

[2] SCANS AS PRIMITIVE PARALLEL OPERATIONS [J].

BLELLOCH, GE .

IEEE TRANSACTIONS ON COMPUTERS, 1989, 38 (11) :1526-1538

[3]

CHUNG KL, 1993, IMPROVED 0 1 TIME AL

[4]

Crochemore M., 1994, TEXT ALGORITHMS

[5]

GRAY JP, 1989, 10TH P CALTECH C VLS, P279

[6]

Hwang K., 1993, Advanced Computer Architecture: Parallelism. Scalability

[7]

Mano M., 1979, DIGITAL LOGIC COMPUT

[8] CONNECTION AUTONOMY IN SIMD COMPUTERS - A VLSI IMPLEMENTATION [J].

MARESCA, M ;

LI, HW .

JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING, 1989, 7 (02) :302-320

[9]

MARESCA M, 1993, P INT C PARALLEL PRO, V1, P282

[10] PARALLEL COMPUTATIONS ON RECONFIGURABLE MESHES [J].

MILLER, R ;

PRASANNAKUMAR, VK ;

REISIS, DI ;

STOUT, QF .

IEEE TRANSACTIONS ON COMPUTERS, 1993, 42 (06) :678-692

← 1 2 →