Fast text searching for regular expressions or automaton searching on tries

被引：68

作者：

BaezaYates, RA ^{[1
]}

Gonnet, GH ^{[1
]}

机构：

[1] ETH ZURICH, CH-8093 ZURICH, SWITZERLAND

来源：

JOURNAL OF THE ACM | 1996年 / 43卷 / 06期

关键词：

digital trees; finite automata; regular expressions; text searching;

D O I：

10.1145/235809.235810

中图分类号：

TP3 [计算技术、计算机技术];

学科分类号：

0812 ;

摘要：

We present algorithms for efficient searching of regular expressions on preprocessed text, using a Patricia tree as a logical model for the index. We obtain searching algorithms that run in logarithmic expected time in the size of the text for a wide subclass of regular expressions, and in sublinear expected time for any regular expression. This is the first such algorithm to be found with this complexity.

引用

页码：915 / 936

页数：22

共 29 条

[1]

Aho A.V., 1974, The Design and Analysis of Computer Algorithms

[2] SELF-ALIGNMENTS IN WORDS AND THEIR APPLICATIONS [J].

APOSTOLICO, A ;

SZPANKOWSKI, W .

JOURNAL OF ALGORITHMS, 1992, 13 (03) :446-467

[3] FRINGE ANALYSIS REVISITED [J].

BAEZAYATES, R .

ACM COMPUTING SURVEYS, 1995, 27 (01) :109-119

[4]

BAEZAYATES RA, 1989, LECT NOTES COMPUT SC, V372, P46

[5]

BAEZAYATES RA, 1989, CS8916 U WAT DEP COM

[6]

BAEZAYATES RA, 1989, THESIS U WATERLOO WA

[7]

Batory D. S., 1979, ACM Transactions on Database Systems, V4, P531, DOI 10.1145/320107.320125

[8]

DELABRIANDAIS R, 1959, P W JOINT COMP C, P295

[9] A NOTE ON THE AVERAGE DEPTH OF TRIES [J].

DEVROYE, L .

COMPUTING, 1982, 28 (04) :367-371

[10] PARTIAL MATCH RETRIEVAL OF MULTIDIMENSIONAL DATA [J].

FLAJOLET, P ;

PUECH, C .

JOURNAL OF THE ACM, 1986, 33 (02) :371-407

← 1 2 3 →