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
APOSTOLICO, A
SZPANKOWSKI, W
[J]. JOURNAL OF ALGORITHMS, 1992, 13 (03) : 446 - 467
[3] FRINGE ANALYSIS REVISITED
BAEZAYATES, R
[J]. 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
DEVROYE, L
[J]. COMPUTING, 1982, 28 (04) : 367 - 371
[10] PARTIAL MATCH RETRIEVAL OF MULTIDIMENSIONAL DATA
FLAJOLET, P
PUECH, C
[J]. JOURNAL OF THE ACM, 1986, 33 (02) : 371 - 407

← 1 2 3 →