1996/11/01 by Ricardo Baeza‐Yates, Gastón H. Gonnet · 1 citation
Computer Science · Mathematics · #Algorithms and Data Compression #Natural Language Processing Techniques #semigroups and automata theory #Regular expression #Computer science #Logarithm #Automaton #Nondeterministic finite automaton #Time complexity #Sublinear function #Tree (set theory) #Theoretical computer science #Algorithm #Expression (computer science) #Discrete mathematics #Mathematics #Combinatorics #Automata theory
paper · pdf · doi:10.1145/235809.235810
openalex publication_date 1996/11/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/06/11
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.