Regular Expressions in R: A Primer

Preamble

Hi readers,
Sorry for the delay in posting, I’ve been hard at work getting my talk ready for the ESA annual meeting in Sacramento next week. I’ll definitely post a recap and link to my slides after the conference.

I’m on a workacation on Lake of Bays in Ontario (my home province) at the moment, enjoying the lake-side life on my breaks.

I’m continuing work on my Build Your Bar project, dabbling in natural language processing. I find myself using regular expressions (regex) frequently enough to think it warrants a post. The R help on Regex ?regex is long and technical and makes no attempt to convince you of it’s importance. So here is a quick primer on using regex in R, the focus will be on perl-like regular expressions.

History

Regular Expressions have been a part of computing since the early days of home computing. When the primary input-output interface to a computer was text, an efficient means of finding the exact text you were interested in was necessary. “Simple” shorthands for complicated series of characters were developed. The idea for regular expressions originated in the work of Stephen Kleene(1956) on regular sets. Just over a decade later, Ken Thompson imported the ideas into the Unix operating system via the text editing software QED. For a more detailed history of regex I suggest reading Staffan Noteberg’s brief review.

R’s Native Regex

R supports two, or imprecisely three, regex schemes. The two true regex schemes are Extended which follows the POSIX 1003.2 standard and Perl-Like my personal favourite that adapts the incredibly powerful regex syntax of the perl programming language. The last scheme is Fixed which is less of a regex style than a lack thereof, fixed mode will take characters absolutely literally, except for R’s own escape characters.

By default R uses extended regex, the unfortunate consequence is if you choose to follow my lead and use perl-style regex, you have to be a bit more verbose in your code and specify perl = TRUE each time you use a regex function¹. I however feel it’s a small price to pay for getting to use perl-like regex.

More about Perl-Like

The help file for regex offers the advice to head to pcre web page, but you will likely want to go straight to the source: http://perldoc.perl.org/perlre.html. The perl documentation page on the current state of their regex syntax is a handy reference for anyone who plans on using perl-like regex.

Unfortunately for us R users, many of perl’s really handy regex features aren’t available to us. Native perl regex allow for concurrent search and accession, meaning you can search for multiple tokens within a string and access the returned tokens without storing the matches in an intermediary object first. More simply, in perl, searching and editing a string is essentially the same action. In R, searching and accession are handled by completely seperate functions, and regular expressions aren’t tokenized to allow multiple operations on the same search criterion.

These differences are due to the fact that perl was designed for text manipulation, it is self-described as the “swiss army knife” of scripting languages allowing you to functionality from multiple languages with perl as the middle-man. The lingua franca of all programming languages is the source code, which perl can elegantly cut, trim, and glue together. R was built for statistics, and so string manipulation is more of an acquired skill. However, let it never be said you can’t do powerful string manipulation in R, it’s just not true. String manipulation in R is clunky, maybe, but powerful enough to do anything you need.

Finding That Special String

I love string manipulation because it appeals to my love of puzzle solving. Finding just the right regex to get what you’re looking for really gives me the thrill of the hunt.

• So you want to find a number in the middle of a word, but only after an m and only in the last word of string: REGEX
• So you want to trim whitespace from the end of the string but only if there are 3 or more spaces: REGEX
• Want to find brand names with between one and three capitalized words in a list of drink ingredients REGEX

Hopefully your interest is piqued and you now want to learn all about using regex like a wizard. If so, great, because I’m going to show you how! But first, a key R idiosyncracy that needs to be addressed.

R Idiosyncracy

R by default recognizes backslashes “\” as the beginning of an escape sequence, also called a metacharacter. Perl also uses a backslash to indicate a metacharacter so there is a clash. In native perl “\d” is a metacharacter meaning all digits, but when R sees “\d” it thinks you’re invoking the metacharacter in an inappropriate way. To get the behaviour you’d expect, you need to escape the behaviour of the backslash to have it pass the un-escaped regex. You do this by adding an extra backslash “\\d” behaves exactly as you’d expect “\d” to.
This situation gets particularly comical when you want to use a literal backslash in a regular expression. In native perl “\\” gets you a literal backslash, but in R you need to escape BOTH backslashes to get the desired behaviour “\\\\” gets you a literal backslash (as I am typing this in R markdown which by default follows R escaping rules, I just typed 8 backslashes to show you four, ugh).

First Steps (Wild-Cards and Quantifiers)

The first things you’re going to need to learn to become a Perl-Like regex master is to use wild-cards and quantifiers. You may have run into wild-cards in any number of different places, google used to support them for example. Wild-cards are regex speak for “just give me anything”.

Unless you’ve worked with regex before you’ve probably never worked closely with quantifiers. Quantifiers are regex speak for “give me some number of these”. If you’ve seen the wild-cards “*” and “?” from DOS, “?” is a wild-card meaning any one character, “*” is a wild-card with an indefinite quantifier meaning give me any number of any character.

Character	Meaning
.	Match any 1 character
*	Match ZERO or more of the previous character
+	Match ONE or more of the previous character
?	Match ZERO or ONE of the previous character
{N, M}	Match atleast N but fewer than M of the previous character Leaving M empty ({N,}) means N or more

With these tools at your disposal you can begin your odyssey into the world of pattern matching. Let’s see some examples

Regex	Sample Matches
"Al.*"	"Alfred", "Albert", "Alphonso", "Alex likes going to the movies"
"5? ?Apples"	"5 Apples", "5Apples", " Apples", "Apples"
"(Na )+Batman!"	"Na Na Na Na Na Na Na Na Batman!" but not "Batman!"

As you may have noticed, the special quantifiers (“*“,”+“, and”?“) are all just convenient shorthands for (”{0,}“,”{1,}“, and”{0,1}“), you’ll find you use the special quantifiers more frequently.

Brackets, Groups, and Alternation

I’ve hinted at this next group of behaviours in the previous set of examples. The “(Na )+” I used to match the batman theme song is an example of grouping. Using parantheses groups a series of characters such that they can be quantified like a single character. The above regex states that I want one or more sets of the sequence “Na”.

Suppose you weren’t satisfied that you found all the ways people transcribe the batman theme, for example you have a friend use the phoneme “Da” to represent the notes in the song. Never fear, bracketed character classes to the rescue. You can allow the regular expression to choose one of several characters. Bracketed character classes are denoted with square braces “[]”.

Lastly, maybe the vowel is all wrong too. Maybe you think people might be using phonemes like “Duh” or “Nah”. You can specify these specific combinations within a group, and let the regex match any group with an alternation. Alternations are specified with “|”.

Regex	Sample Matches
"(Na )+Batman!"	"Na Na Na Na Na Na Na Na Batman!"
"([ND]a )+Batman!"	"Na Na Na Na Na Na Na Na Batman!" and "Da Na Na Na Da Na Na Na Batman!"
"[ND]((a)|(uh)|(ah))"	"Duh", "Na", "Dah"

Now you should be able to get just about any set of characters, and in any amount as you could possibly want.

Positioning and Quantifier Modification

Another useful tool is the ability to specificy where in a string you’d like to match. Two handy positioning modifiers are allowed in a regular experession. You can specify the beginning of a string “^” and the end of a string “$”

Regex	Sample Matches
"^Hi"	"Hi there reader" but not "You there reader, Hi"
"Goodbye$"	"Dear reader, Goodbye" but not "Goodbye dear reader"

Quantifier modification is a topic I’ve touched on in a previous post where I demonstrated how to process html to extract tag values. The question mark has a double meaning depending on where it is found in a regular expression. Normally it is a treated as a quantifier meaning {0,1}, however when it appears immediately after another quantifier, it instructs that quantifier to behave non-greedily.

Greedy is a reference to a quantifier’s habit of trying to capture as many characters as possible. If given a choice between matching one or seven characters, it will choose seven. We can modify this behaviour to just take one.
Take for example the body of a very simple html document:

<body>
<p> Generic things on the <b>Internet<b> have grown <b> tiresome</b></p>
</body>

If I was curious about all the things the author thought worthy of bolding, I might first try the regex
"<b>.+</b>"

But I would get one match <b>Internet<b> have grown <b> tiresome</b>
My indefinite quantifier would match all the way to the very last </b> in the document, obviously not what I wanted. So instead I should tell the “+” quantifier to not be so greedy
"<b>.+?</b>"

Then it would correctly match "<b>Internet</b>" and "<b>Tiresome</b>".

Special Characters

The last type of metacharacter I’d like to show you are the special character classes, useful in bracketed character classes and on there own or combined with quantifiers. Some useful character class metacharacters are

Character	Meaning
\w	any word character - all numbers, letters, and underscores
\W	non-word character - anything except the above
\d	any single digit number
\s	any space character (regular space or tab)

And with that you should be able to match just about any pattern in a string that your heart desires, here are a few interesting examples.
Stringr comes pre-loaded with a method to trim whitespace from a string, with regex we can do that by saying match some number of whitespaces at the beginning or end of the string like so:

gsub(pattern = \"(^ +)|( +$)\", replacement = "", string)²

Or as I mentioned earlier, maybe you want to find brand names in a set of ingredients, the ingredient set was comma delimited, and brands of note were tagged with ® the html code for the tm symbol. Brand names also have each word capitalized and tend to be between 1-4 words and may include hyphens. To pull out each brand in the ingredient list you could do this:

matchPull(pattern = "([A-Z][\\w-']*? ){0,3}[A-Z][\\w-']+?®")³

The one thing you may not recognize is the bracketed character class "[A-Z]" which means exactly what it looks, all the capitals from A through Z.

Outro

I hope from this post you’ve learned a little bit about the application of regular expressions in R and can see some opportunities to use them in your own work. The ability to precisely and effectively specify exactly the string you’re interested makes performing any text mining tasks orders of magnitude easier. Also if you’re just interested in organizing and curating data sets for thesis work for example the ability to accurately edit information stored in strings is a massive advantage over doing manual edits in software such as excel.

As always, thanks for reading!

-Chris

---

1. I recently discovered the wonderful package stringr another of Hadley Wickham’s packages. The syntax for specifying perl-like mode with stringr functions is different, you just wrap your regex string in a call to the perl function like so: stringr_foo("string", pattern = perl("pattern")). Stringr is a dependency of several of Wickham’s other packages so you likely already have it installed.↩
2. The function gsub is R’s equivalent of find and replace all↩
3. The matchPull function is my convenience function for finding and extracting a matched text from a string. Similar in idea to str_extract from stringr, but I wrote matchPull before I knew about stringr, and I’m too lazy to learn someone else’s convenience function when I have my own. Plus as a hold over from my days coding in java I think underscores in function names are yucky. Code for matchPull is available in my post here and also comes in my friendlyShiny package.↩

Build Your Bar Project: Synthesis and Exploratory Data Analysis

Hello readers, this post will be a good one I promise. I’ve started using R Markdown which seems like it will greatly increase the speed with which I can give you analyses.

Diving Back In

We left off last time after having downloaded a ton of html files containing drink recipe data. The first thing to do is to have a look inside the html file. This step is critical for looking at how to pull out the information that we want

Exerpts

Found the drink name

<title> 73 Bus #2 recipe</title> 

Found some key words

<meta content="73 bus #2, 73, bus, #2, gin,<br/>
  triple sec, lime juice, cranberry juice, drink recipe, drink, recipe,<br/>
  alcoholic drink recipe, cocktail recipe, cocktail, mixed drink, martini"<br/> 
  name="keywords">

Found the hierarchy (drink class)

<div class="pm" style="margin-top:20px;"><a href="/cat/1/
  ">Cocktails</a>
  > <a href="/cat/14/">Short drinks</a> 
  > <a href="/cat/141/">by base-ingredient</a> 
  > <a href="/cat/40/">gin-based</a></div>

Pulling out the information

So at this point I’ve identified seven variables I’d like to track for each drink

1. Drink name
2. Drink hierarchy(class)
3. Ingredients
4. Keywords
5. Number of ratings
6. Average rating (out of 10)
7. URL

In order to get at these values I need to design a regular expression that will only capture the tag of interest. I discussed regular expressions briefly in my previous post, we will rely heavily on the non-greedy quantifier “.+?” I discussed here.

Data Extraction

In order to pull the data out I used R (surprise surprise). I wrote two small accessory functions. One to make string manipulation easier, and one to remove html tags.

#Use either regexpr(default) or grexepr to match elements of interest
#Extract and return them using regmatches
matchPull <- function(pattern, text, invert = FALSE, global = FALSE, ...){
  if(global){
    match <- gregexpr(pattern, text, ...)
  } else {
    match <- regexpr(pattern, text, ...)
  }
  
  pulled <- regmatches(text, match, invert)
  if(length(pulled) == 0) pulled <- NA
  
  pulled
}

# Remove html tags, note the use of the .*? quantifier, 
# a cousin of .+? that can match 0 characters
# Where .+? matches 1 of more.
stripTags <- function(text){
  gsub("<.*?>", "", text, perl = TRUE)
}

First step lets bring in one of the many html files we downloaded and try to extract all of the important data. We’ll use the examples noted above to practice.

fileCon <- file(siteName, blocking = FALSE)
site <- paste0(readLines(con = fileCon), collapse = "\n")
close(fileCon)

# Pull out the whole title, remove the tages
# and remove the word recipe which flanks each recipe name
name <-  matchPull("<title>.*?</title>", site,
                   ignore.case = TRUE, perl = TRUE)
name <- stripTags(name)
name <- sub(" recipe$", "", name, perl = TRUE)
  
# Pull out just the meta tag with the name keywords,
# the pull out the contents, and remove quotes
keywords <- matchPull("<meta content=.*?name=\"keywords\"", site, 
                      ignore.case = TRUE, perl = TRUE)
keywords <- matchPull("\".*?\"", keywords, perl = TRUE)
keywords <- gsub("\"", "", keywords)

# Pull out the division of class "pm" style "yadda-yadda"
# and remove all tags
hierarchy <- matchPull("<div class=\"pm\" style=\"margin-top:20px;\">.*?</div>", 
                       site, ignore.case = TRUE, perl = TRUE)
hierarchy <- stripTags(hierarchy)

Once we’ve figured out how to get all the useful data out of one file, we can encase it in a function that returns one row of data, and apply that to all the files we downloaded (after testing it on a much smaller subset). After that we’ll have a data frame containing all the juicy data, which is much easier to work with. Suppose we’ve encased our processing in {processSite <- function(siteName)} we can apply it many sites all at once by wrapping it in another function

processSites <- function(siteList){
  frameSeed <- processSite(siteList[1])
  drinkFrame <- frameSeed[rep(1, length(siteList)),]
  
  #This sapply structure is basically just a for loop
  sapply(1:length(siteList), function(i){
    drinkFrame[i,] <<- processSite(siteList[i]) 
  })
  
  drinkFrame
}

fileNames <- list.files()#Make sure you've set your working directory before this
fileNames <- fileNames[grepl("\\.html", fileNames)] #grab just .html files

#Try it out on the first 6 files
practiceNames <- head(fileNames)
practiceData <- processSites(practiceNames)

#After inspecting practice data for quality, process them all
drinkData <- processSites(fileNames)

Processing ~17000 sites took R around 6 minutes (wow) on my computer, producing a 10Mb data.frame, which I saved so that I never have to run this code again. Now that the data is in, we can begin with the fun parts. I’ll some skip the quality control steps to get right to the meaty stuff.

Exploratory Data Analysis (EDA)

The cornerstone of any data related project is poking and proding the data to figure out what’s in there. Make some histograms, correlation matrices, and any other simple data visualizations you think might be informative. This step is probably my favourite because it

1. Helps recognize general patterns
2. Identifies issues with data quality
3. It’s fun to watch your data set begin to tell its first story

I’ll present one EDA that I thought was fun. I began getting interested in what people liked to name their drinks, surely there would be some cool patterns in that. I decided I wanted to try my hand at making a word cloud with some of the most common words in drink names. To make a word cloud using R I used the wordcloud package and the tm (text mining) package.

library(wordcloud)
library(tm)

load("drinkData.rda") #Bring in our drinkData from the last step

# Filter out drinks that are neither cocktails nor shots 
# by looking in their hierarchy
drinksFrame <- drinksTable[grepl("(cocktails)|(shots)", 
                                 drinksTable$hierarchy, 
                                 ignore.case = TRUE, 
                                 perl = TRUE),]

# I had a few cases of multiple duplicates, 
# this loop keeps tacks on Alt to duplicated names
# Repeats until no duplicates are found
while(anyDuplicated(drinksFrame$name) != 0){
  dupeNamed <- duplicated(drinksFrame$name)
  drinksFrame$name[dupeNamed] <- 
    paste(drinksFrame$name[dupeNamed],"Alt",sep=" ")
}

#Clean up now empty dupeNamed vector
rm(dupeNamed)

#Convert from character vector to one long string of words
nameVector <- paste0(tolower(drinksFrame$name), collapse = " ") 

# Use tm's built in functions to remove stopwords, see below for a note,
# Also remove alt (because I put it there)
# As well as punctuation. I removed numbers because the site named 
# duplicates with sequential numbers
# And "2" was one of the most popular words 
nameVectorCleaned <- removeWords(nameVector, c(stopwords("english"), "alt"))
nameVectorCleaned <- removePunctuation(nameVectorCleaned)
nameVectorCleaned <- removeNumbers(nameVectorCleaned)

# Split the cleaned string back into a vector of words (tokens really)
# Separated by white space
nameVector <- unlist(strsplit(nameVectorCleaned, " "))

#Then use table to count instances of each word
#Remove number one which was an empty string
#(an unfortunate consequence of our splitting algorithm)
nameFreqs <- table(nameVector)[-1]
nameWords <- as.character(names(nameFreqs))
namesFreqs <- as.numeric(nameFreqs)

freqOrder <- order(nameFreqs, decreasing = TRUE) #Create an ordering vector
top100 <- head(freqOrder, 100) #Indices of the 100 most popular words

#Make a 10 inch by 10 inch pdf to hold the wordcloud  
pdf("boozeNameCloud.pdf", width = 10, height = 10)

#Plot the words, ordered and sized by frequency
wordcloud(nameWords[top100], namesFreqs[top100], 
          scale = c(12,1), random.order = FALSE)

#Close up shop and admire our work
dev.off()

I re-ran the code to make the wordcloud pdf multiple times, because there is something stochastic in the word placement. After a few tries the words aligned and suited my aesthetic tastes. And so I give you

Booze Cloud!

Click to embignify

Build Your Bar Project: Introduction and Data Acquisition

As promised today I'm going to be talking about my "big data" (although I'm beginning to find the term a bit cringe-inducing) project looking at how best to build a bar given a bottle limit or price limit.

Inspiration

I was having lunch last Friday at the bar lounge of a local restaurant, my seat was situated with a nice view of the bar in all it's glory, hundreds of bottles, with representatives of almost every kind of booze imaginable. I love cooking and to a lesser degree, mixology, but I've always wanted to have a small home bar.

My dream bar would be stocked so that visitors will almost always be able to really pick their poison. I began thinking; up on that wall was at a minimum 250 bottles, at an average price of at least $40 per bottle, I would need over $10,000 to replicate it, which is vastly out of my price range. In the spirit of making do, I began to wonder, how many bottles would I really need to provide suitable coverage of all possible drink recipes? Or, if I could only afford so many bottles, how could I maximize the number of possibilities.

The Plan

With the wheels set in motion I began wondering how best to answer these questions. I have seen drinking magazine articles offer nice heuristics on how to choose an ideal micro-bar selection, but being a datahead I decided there must be a data oriented solution.

I knew that there were numerous online recipe catalogs on the internet that I could mine data from, so when I got home, I got to googling. Within a couple of minutes I had chosen a website boasting close to 20000 recipes, and decided it would be my data deposit, keeping with the metaphor.

Data Harvesting

In order to get my hands on that pile of data I needed to make sure the websites were suitable to mine. I began with exploring the directory structure of the website by browsing. I began getting ideas of what recipes I wanted to include in the analysis, punches generally require planning so I didn't want those, and non-alcoholic beverages are a niche my bar isn't means for, so I was sure I was going to exclude those. I decided I was going to spider the website I found, and pull out the recipe page URLs with some regular expressions.

Get Those Spiders Crawling

This was one of my first real experiences attempting to download tens of thousands of websites, so if you have any suggestions for how I could have simplified this stage please leave a comment below. My tool of choice for this step was wget, an incredible free tool for download automation. I used the following code to spider the site:

$ wget -U mozilla -o logArhythm.txt --spider --force-html URL

This step could take a very long time depending on the size of the website. Mine took 4-5 hours.

Flags and Arguments

Flag	Argument(s)	Notes
-U	an identity for the spider	Server drops connections with spiders, so masquerade as a firefox user
-o	text file of choice	Where to put a log file containing output
--spider	None	Deactivates default behaviour of downloading all files, recursively follows links within the site of interest allowing the directory structure of the site to be discovered
--force-html	None	Treat all found files as html to facillitate crawling
	URL	Location of site to download

Process the log file

So now we have a completed log file containing wget's default output. The next step was to load log file into R, my favourite scripting language, and extract just URLs, ignoring all the extra output wget provides.

#Read in text from a file, split into character (strings) by whitespace
logText <- scan("logArhythm.txt", what = "character)

Scan returns a vector of strings delimited by white space.  For each page visited by my spider the log file contains several lines of output. Conveniently, the log only contains the full URL once for each visited page, this makes it easy to find the URLs with minimal redundancy. The spider can visit the same page multiple times, so duplicate URLs are removed with a call to unique.

URLs <- logText[grepl("http", logText)]
URLs <- unique(URLs)

The variable URLs now contains the location of each page on the site, I just want drink recipes. All drink recipe pages have the terminal portion of the path "/drink[code].html" with [code] being anywhere from 1 - 6 alphanumeric digits. To identify URLs that correspond to recipe pages I used a simple regular expression. See the footnotes for a description of the perl-style regular expression ".+?"¹

isDrinkURL <- grepl("drink.+?", URLs. perl = TRUE)
drinkURLs <- URLs[isDrinkURL]
write(drinkURLs, "drinkSiteList.txt)

Now we have a text file containing every website within the domain I examined that ends in "/drink[Some Code].html", this file is perfect for the next step. Wget can take an input file containing a list of websites to download. Make sure you run wget in a folder that you don't mind filling with a ton of files.

$ wget -i drinkSiteList.txt -U mozilla

I left this download running over night and woke up to the wonderful present of 60 megs of raw html data, lo and behold only the drink recipe sites had been downloaded, the steps up until this stage had been successful. Please be conscientious about executing code like this, unchecked use of wget can be very taxing on a server and on your own bandwidth. Wget comes with many safeguards including download size limits, download rate limitation, and some other tools to avoid damaging a site that you like enough to want to borrow data from.

As I am still new to blogging this post took an excruciating amount of time to compose and so I'm going to end it here. In the coming weeks I hope to master html and perhaps some productivity tools to reduce the production time of a work like this so I can provide you with lengthier analyses.

Please stay tuned for more on this project. I already have some exploratory analyses completed including a word cloud. and if I can make it happen there will be a random drink name generator to give you ideas for your next famous party cocktail.

Chris

---

1 R supports several types of regular expressions, one of the most powerful being Perl like. The regular expression ".+?" means give me any character {.} and I want at least one, but possibly more {+} and choose the fewest number of characters that match {?}. In more technical terms, plus is an indefinite quantifier meaning it can capture different numbers of characters, the default behaviour is greedy, it tries to match as many characters as possible, the question mark changes the behaviour to non-greedy. In this case it isn't necessary to specify non-greedy matching, but when matching tags later in the analysis it is integral. For example "<p>.+</p>" when searching an html document would match from the beginning of the first paragraph to the end of the last one where "<p>.+?</p>" would only match the first paragraph^↩