Permalink
Switch branches/tags
Nothing to show
Find file Copy path
Fetching contributors…
Cannot retrieve contributors at this time
327 lines (274 sloc) 14.9 KB

Tutorial on named capture regular expressions in R and Python

In this 60 minute tutorial I will explain how to use named capture regular expressions to extract data from several different kinds structured text data.

Motivation for using named capture regular expressions, 5 minutes

Why would you want to use named capture regular expressions? They are useful when you want to extract groups of substrings from text data which has some structure, but no consistent delimiter such as tabs or commas between groups. They make it easy to convert such loosely structured text data into regular CSV/TSV data.

  • The regular expression 5 foo bar matches any string that contains 5 foo bar as a substring.
  • The regular expression foo|bar matches any string that contains foo or bar. The vertical bar indicates alternation – if any one of the options is present, then there is a match.
  • Square brackets are used to indicate a character class. The regular expression [0-9] foo bar means match any digit, followed by a space, followed by foo bar.
  • A capturing regular expression includes parentheses for extracting data when there is a match. For example if we apply the regular expression ([0-9]) (foo|bar) to the string prefix 8 foo suffix, we put 8 in the first capture group and foo in the second.
  • A named capture regular expression includes group names. For example if we apply the regular expression (?<number>[0-9]) (?<string>foo|bar) to the string prefix 8 foo suffix, we put 8 in the capture group named number, and foo in the capture group named string.

Named capture regular expressions are better than simple capturing regular expressions, since you can refer to the extracted data by name rather than by an arbitrary index. That results in code that is a bit more verbose, but much easier to understand. For example in Python,

import re
subject = 'chr10:213,054,000-213,055,000'
# Without named capture:
group_tuple = re.search("(chr.*?):(.*?)-([0-9,]*)", subject).groups()
print group_tuple[1]
# With named capture:
group_dict = re.search(r"""
(?P<chrom>chr.*?)
:
(?P<chromStart>.*?)
-
(?P<chromEnd>[0-9,]*)
""", subject, re.VERBOSE).groupdict()
print group_dict["chromStart"]

Both print statements show the same thing, but the intent of the second is clearer for two reasons:

  • The group names in the regular expression serve to document their purpose. Regular expressions have a bad reputation as a write-only language but named capture can be used to make them more readable: “Hmmm… what was the second group .*? supposed to match? Oh yeah, the chromStart!”
  • We can extract the data by group name (chromStart) rather than an arbitrary index (1), clarifying the intent of the Python code.

History, 5 minutes

WhoWhenFirst
Kleene1956Regular expression on paper
Thompson1968Regular expression in a program
Thompson1974grep
Wall1994Perl5 (? extensions
Hazel1997PCRE
Kuchling et al1997Named capture in Python1.5
R core2002PCRE in R
Hazel2003Named capture in PCRE
Hocking2011Named capture in R
Hocking2016extractall in Python pandas

Regular sets and regular expressions were introduced on paper by Stephen Cole Kleene in 1956 (including the “Kleene star” * for zero or more). Among the first uses of a regular expression in a program was Ken Thompson (Bachelors 1965, Masters 1966, UC Berkeley) for his version of the QED (1968) and ed (1969) text editors, developed at Bell Labs for Unix. In ed, g/re/p means “Global Regular Expression Print,” which gave the name to the grep program, also written by Thompson (1974). I’m not sure about the origin of capture groups, but Friedl claimed that “The regular expressions supported by grep and other early tools were quite limited…grep’s capturing metacharacters were \(...\), with unescaped parentheses representing literal text.” Larry Wall wrote Perl version 1 in 1987 while working at Unisys Corporation, and it had capturing regular expressions. Perl version 5 in 1994 introduced many extensions using the (? notation. Sources: wikipedia:Regular_expression and “A Casual Stroll Across the Regex Landscape,” in Ch.3 of Friedl’s book Mastering Regular Expressions.

Philip Hazel started writing the Perl-Compatible Regular Expressions (PCRE) library for the exim mail program in 1997. Python used PCRE starting with version 1.5 in 1997. Source: Python-1.5/Misc/HISTORY.

From 1.5a3 to 1.5a4...
- A completely new re.py module is provided (thanks to Andrew
Kuchling, Tim Peters and Jeffrey Ollie) which uses Philip Hazel's
"pcre" re compiler and engine.

Python 1.5 introduced named capture groups and the (?P<name>subpattern) syntax. Source: Python-1.5/Doc/libre.tex.

\item[\code{(?P<\var{name}>...)}] Similar to regular parentheses, but
the text matched by the group is accessible via the symbolic group
name \var{name}.

PCRE support for named capture was introduced in 2003. Source: PCRE changelog (my copy).

Version 4.0 17-Feb-03...
36. Added support for named subpatterns. The Python syntax (?P<name>...) is
used to name a group. Names consist of alphanumerics and underscores, and must
be unique. Back references use the syntax (?P=name) and recursive calls use
(?P>name) which is a PCRE extension to the Python extension. Groups still have
numbers.

R includes PCRE starting with version 1.6.0 in 2002. Source: R-src/NEWS.1.

CHANGES IN R VERSION 1.6.0...
    o	grep(), (g)sub() and regexpr() have a new argument `perl'
	which if TRUE uses Perl-style regexps from PCRE (if installed).

I wrote the code in https://svn.r-project.org/R/trunk/src/main/grep.c which implements named capture regular expression support for R. It was merged into base R in 2011 https://bugs.r-project.org/bugzilla3/show_bug.cgi?id=14518, and has been included with every copy of R since version 2.14.

I wrote the str.extractall method in pandas, first included with release version 0.18.0 (my Pull Request was merged in Feb 2016).

Current usage in R and Python, 10 minutes

When developing complex regular expressions, it is useful to have interactive visual feedback about what parts of your subject string matches. This functionality is provided by M-x re-builder (mastering emacs) and web pages such as pythex.

For a subject s (R character vector or Python pandas Series) and a regular expression pattern p (string),

R namedCapture packagePython pandasreturns
str_match_named(s, p)s.str.extract(p)first match in each subject
str_match_all_named(s, p)s.str.extractall(p)all matches in each subject

Named capture in R

Base R supports named capture regular expressions via C code that interfaces the Perl-Compatible Regular Expressions (PCRE) library. The base functions regexpr(p, s) and gregexpr(p, s) use PCRE when given the perl=TRUE argument. The first argument p is a single regular expression pattern (character vector of length 1), and the second argument s is the character vector of subjects (strings to parse). However their output is a bunch of integers and group names, which is not very user-friendly.

Instead I recommend using the namedCapture package, which provides the str_match_named(s, p) and str_match_all_named(s, p) functions. They are a user-friendly interface to the base regexpr and gregexpr functions. They return character matrices with column names as defined in the named groups of the regular expression. To install the namedCapture package, run the following commands in R:

if(!require(devtools))install.packages("devtools")
devtools::install_github("tdhock/namedCapture")

Notes on related functions/packages:

Named capture in Python

The re module of the Python Standard Library implements named capture regular expression support via the m.groupdict() method for a match object m.

For data analysis I recommend using the pandas library, which supports named capture regular expressions via the s.str.extract(p) and s.str.extractall(p) methods for a subject Series s and a regular expression pattern p. Both methods are an interface to the re module, and return a DataFrame with one row per match and one column per capture group. To install pandas execute one of the following shell commands:

pip install pandas
easy_install pandas

Note that in Python a P is required after the initial question mark of each group: (?P<name>pattern). In contrast, in R/PCRE/namedCapture the P is allowed but not required.

Some examples, 30 minutes

codefunctions
chr.pos.Rstr_match_named, str_match_all_named, gsub
differences_from_R.pyre.search, re.compile
chr_pos.pystr.extract, str.findall, re.subn
qsub-out.Rstr_match_named
trackDb.Rstr_match_all_named
R-Forge exercisesstr_match_named, str_match_all_named

Questions from the audience, 10 minutes

How do you ever extracted data from text files? Show us how you extracted some data from a particular text file, and we will try to suggest improvements.

Polynomial time named capture

Russ Cox’s ”Regular Expression Matching Can Be Simple And Fast” explains that due to backreference support, several common regular expression engines can have an exponential runtime (including PCRE which is used by R and Python). One way to achieve a speedup is to drop backreference support and use the re2 C++ library, which supports named capture. Qin Wenfeng implemented the excellent re2r package as his Google Summer of Code 2016 project. If you need a provably fast (polynomial time) regular expression engine in R, I recommend using re2r! See speed benchmarks below and in the re2r vignette.

R functionlibrarynamed capturecomplexity
regexpr(perl=FALSE)TREnopolynomial
stringi::stri_match()ICUnoexponential
regexpr(perl=TRUE)PCREyesexponential
str_match_re2()re2yespolynomial
if(!require(re2r))devtools::install_github("qinwf/re2r", build_vignettes=FALSE, dep=FALSE)
if(!require(stringi))install.packages("stringi")

max.N <- 25
times.list <- list()
for(N in 1:max.N){
  cat(sprintf("subject/pattern size %4d / %4d\n", N, max.N))
  subject <- paste(rep("a", N), collapse="")
  pattern <- paste(rep(c("a?", "a"), each=N), collapse="")
  N.times <- microbenchmark::microbenchmark(
    ICU=stringi::stri_match(subject, regex=pattern),
    PCRE=regexpr(pattern, subject, perl=TRUE),
    TRE=regexpr(pattern, subject, perl=FALSE),
    RE2=re2r::re2_match(pattern, subject),
    times=10)
  times.list[[N]] <- data.frame(N, N.times)
}
times <- do.call(rbind, times.list)
save(times, file="times.RData")

library(ggplot2)
library(directlabels)
linear.legend <- ggplot()+
  ggtitle("Timing regular expressions in R, linear scale")+
  scale_y_continuous("seconds")+
  scale_x_continuous("subject/pattern size",
                     limits=c(1, 27),
                     breaks=c(1, 5, 10, 15, 20, 25))+
  geom_point(aes(N, time/1e9, color=expr),
             shape=1,
             data=times)
(linear.dl <- direct.label(linear.legend, "last.polygons"))
png("figure-complexity-linear.png")
print(linear.dl)
dev.off()

log.legend <- ggplot()+
  ggtitle("Timing regular expressions in R, log scale")+
  scale_y_log10("seconds")+
  scale_x_log10("subject/pattern size",
                limits=c(1, 30),
                breaks=c(1, 5, 10, 15, 20, 25))+
  geom_point(aes(N, time/1e9, color=expr),
             shape=1,
             data=times)
(log.dl <- direct.label(log.legend, "last.polygons"))
png("figure-complexity-log.png")
print(log.dl)
dev.off()

figure-complexity-linear.png

figure-complexity-log.png

References

http://www.regular-expressions.info has some basic reference on how to write regular expressions in several languages. However it discusses neither named capture in R, nor pandas in Python.

The definitive reference on current regular expression implementations is the book “Mastering Regular Expressions,” by Jeffrey E.F. Freidl. It contains a discussion of Python and named capture, but discusses neither pandas nor R.