Fast text searching for regular expressions or automaton searching on tries
- 1 November 1996
- journal article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 43 (6) , 915-936
- https://doi.org/10.1145/235809.235810
Abstract
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.Keywords
This publication has 14 references indexed in Scilit:
- Fringe analysis revisitedACM Computing Surveys, 1995
- Self-alignments in words and their applicationsJournal of Algorithms, 1992
- An algorithm for string matching with a sequence of don't caresInformation Processing Letters, 1991
- Partial match retrieval of multidimensional dataJournal of the ACM, 1986
- Paths in a random digital tree: limiting distributionsAdvances in Applied Probability, 1986
- A note on the average depth of triesComputing, 1982
- On searching transposed filesACM Transactions on Database Systems, 1979
- PATRICIA—Practical Algorithm To Retrieve Information Coded in AlphanumericJournal of the ACM, 1968
- Bounds for the maximal characteristic root of a non-negative irreducible matrixDuke Mathematical Journal, 1960
- Trie memoryCommunications of the ACM, 1960