This implementation is no longer maintained. A more recent implementation (in Rust) is available here.
This tool allows you to find efficiently all matches of a regular expression in a string, i.e., find all contiguous substrings of the string that satisfy the regular expression (including overlapping substrings).
The tool has not been thoroughly tested yet. Use at your own risk.
You need a Linux system with a recent installation of Python 3 (at least Python 3.6).
To install the software, simply clone this repository, then install the
necessary Python modules described in requirements.txt
. You can either install
them manually using pip3
, or setup a virtualenv:
python -m venv .venv
source .venv/bin/activate # run this at any time you restarted a shell
pip install -U -r requirements.txt
You can then run src/main.py
.
# Display all occurences of a pattern (regexp) in a file
src/main.py regexp [file]
cat [file] | src/main.py [pattern]
# For instance, this example will match 'aa@aa', 'aa@a', 'a@aa', 'a@a'
echo "aa@aa" | src/main.py ".+@.+"
# Run unit tests
make test
The matches displayed correspond to all distincts substrings of the text that match the given pattern. If the pattern contains named groups, the tool will output one match for each possible assignment of the groups.
You can define named groups as follow: (?P<group_a>a+)(?P<group_b>b+)
. This
example will extract any group of a's followed by a group of b's.
The group named match
has a special behaviour, it can be used to match only
the part captured by this group. For example:
(?P<match>\w+)@\w+
will enumerate the left parts of any feasible email address^.*(?P<match>\w+@\w+).*$
is equivalent to\w+@\w+
The tool supports a subset of the usual regular expression syntax, with several common operators. The supported grammar for the regular expressions is written in grammar.py.
The algorithm used by this tool is described in the research paper Constant-Delay Enumeration for Nondeterministic Document Spanners, by Amarilli, Bourhis, Mengel and Niewerth. It was presented at the ICDT'19 conference.
The tool will first compile the regular expression into a nondeterministic finite automaton, and then apply an enumeration algorithm. Specifically, it will first preprocess the string (without producing any matches), in time linear in the string and polynomial in the regular expression. After this precomputation, the algorithm produces the matches sequentially, with constant delay between each match.