Regular expressions are used in many information extraction systems like YAGO, DBpedia, Gate and SystemT. However, they sometimes do not match what their creator wanted to find. We investigate how missing words can be added automatically to a regular expression by creating disjunctions at the appropriate positions. Our demo visualizes the steps that our algorithm employs to repair the regular expression.
Regular expressions (regexes) are a popular tool in information extraction. While it is possible to learn regexes automatically from positive and negative examples, many projects craft their regexes manually. This applies, e.g., to Semantic Web projects such as YAGO and DBpedia, but also to systems such as Gate and SystemT. One of the reasons may be that the regexes contain human expertise that goes beyond the information contained in training data.
One of the challenges in such contexts is to adapt a regex so that it matches
a word that was previously missed. Consider, e.g., the simple regex [A-Za-z]+
\d\d, \d\d|\d\d/\d\d/\d\d\d\d. It covers dates that spell out the month, and
dates that consist of digits with a dash. However, it will not match “1/8/1935”.
One way to solve this is obviously to just add this word as a disjunction – but that
would not generalize to other, similar words. To repair the regex properly, we
would first have to identify where the word finds its largest approximate match in
the regex (on the right hand side of the disjunction). Then, we have to perform a
minimal surgical operation to make two digits optional. Finally, we could factor
out the 4 digits of the year. In this paper, we present our work on an algorithm
that does all of this automatically. In the example, we obtain ([A-Za-z]+ \d\d,
|(\d{1,2}/){2})\d{4}. Our demo allows the user to visualize these changes.
Related work. Several approaches [
Each regex r is associated to a syntax tree, whose leaf nodes are characters or character classes. We say that a leaf node is to the left of another leaf node, if the latter can be reached from the former in the Glushkov automaton of r. We write L(r) for the language of r. Given a regex r and a word w, our goal is to construct a regex r0 such that w 2 L(r0) ^ L(r) L(r0).
We first find a maximal matching of w to r, i.e., a partial function from
the positions of w to the leaf nodes of r. For this purpose, we first unfold the
syntactic sugar of the regex, so that it contains only Kleene stars, disjunctions,
and concatenations. Then, we use Meyer’s approximate matching algorithm [
Our demo allows the user to visualize the regex repairs that we propose. In the
beginning, the user can enter a regex and a missing word. For example, the user
can choose the regex \d{2}/\d{2}/\d{4}, and the missing word “1/8/1935”. The
demo then proceeds to show the user the maximal matching between the regex
and the missing word, as computed by Myers’ algorithm (Figure 1 (left)). In
the following, the user can walk step by step through the modifications that our
algorithm proposes. In the example, the algorithm will propose to make first the
first digit optional, and then the third (Figure 1 right). Finally, the algorithm
will simplify the regex to (\d?\d/){2}\d{4} (not shown in the figure).
Alternatively, the user can choose one of our pre-defined sets of words. We offer
the ReLie dataset [
Since information extraction for the Semantic Web is our intended use case, we ran our experiments on the afore-mentioned Wikipedia infobox dataset. We asked 15 colleagues to manually produce regexes. We improve these regexes with our algorithm by randomly adding 10 words that the regexes did not match. We allowed the algorithm to reject the repair (and add the word in a disjunction instead) if the precision sinks on a training dataset. Table 1 compares the F1value to the dis-baseline (which adds a word simply as a disjunction) and the star-baseline (.*). As expected, the dis-baseline raises recall only marginally. The star-baseline only covers those attributes that only consist of one match. Our approach, in contrast, can increase the recall of the regex. While these experiments cannot prove the viability of the approach under durance, they do show that automated regex repair is possible. 5
We have presented an algorithm for automatically adding missing words to regular expressions. Our demo allows users to visualize and understand the changes we propose. For future work we plan to investigate other feedback functions, prevent overgeneralizing repairings and work on minimizing the length of the repaired regex. Our demo is available at https://thomasrebele.org/projects/ regex-repair.
Acknowledgments. This research was supported by the grants ANR-11-LABEX0045-DIGICOSME and ANR-16-CE23-0007-01 (“DICOS”).