Fast and compact regular expression matching

DOI10.1016/j.tcs.2008.08.042zbMath1155.68022OpenAlexW2137939491MaRDI QIDQ2378530

Philip Bille, Martín Farach-Colton

Publication date: 8 January 2009

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2008.08.042

zbMATH Keywords

regular expression matchingapproximate regular expression matching: string edit distancefour Russian techniquesubsequence indexing

Mathematics Subject Classification ID

Searching and sorting (68P10) Pattern recognition, speech recognition (68T10)

Related Items (18)

Subsequence automata with default transitions ⋮ New tabulation and sparse dynamic programming based techniques for sequence similarity problems ⋮ Approximating Longest Common Subsequence in Linear Time: Beating the $\sqrt{{n}}$ Barrier ⋮ Unnamed Item ⋮ Space-efficient STR-IC-LCS computation ⋮ An efficient algorithm for LCS problem between two arbitrary sequences ⋮ Space-Efficient Representations for Glushkov Automata ⋮ Towards Approximate Matching in Compressed Strings: Local Subsequence Recognition ⋮ A Faster Subquadratic Algorithm for the Longest Common Increasing Subsequence Problem ⋮ Faster approximate string matching for short patterns ⋮ Polylogarithmic Approximation for Edit Distance and the Asymmetric Query Complexity ⋮ Unnamed Item ⋮ Compact representations of automata for regular expression matching ⋮ From Regular Expression Matching to Parsing ⋮ Unnamed Item ⋮ From regular expression matching to parsing ⋮ Fast distance multiplication of unit-Monge matrices ⋮ A comparative study of dictionary matching with gaps: limitations, techniques and challenges

Uses Software

• Agrep

Cites Work

• Unnamed Item
• Unnamed Item
• Bounded ordered dictionaries in O(log log N) time and O(n) space
• Approximate matching of regular expressions
• A faster algorithm computing string edit distances
• Preserving order in a forest in less than logarithmic time and linear space
• Faster approximate string matching
• New techniques for regular expression searching
• Directed acyclic subsequence graph -- overview
• Searching subsequences
• Deterministic Dictionaries
• NR‐grep: a fast and flexible pattern‐matching tool
• A fast bit-vector algorithm for approximate string matching based on dynamic programming
• Space efficient dynamic stabbing with fast queries
• Rank/select operations on large alphabets
• New Algorithms for Regular Expression Matching
• Design and implementation of an efficient priority queue
• Algorithms on Strings, Trees and Sequences
• A Four Russians algorithm for regular expression pattern matching
• Fast text searching for regular expressions or automaton searching on tries
• The String-to-String Correction Problem
• A Subquadratic Algorithm for Approximate Regular Expression Matching
• Regular expression pattern matching for XML
• Programming Techniques: Regular expression search algorithm

This page was built for publication: Fast and compact regular expression matching