Text Processing¶
In this lecture we will discuss a number of ways to process text data, with an emphasis on how to use regular expressions.
Regular Expressions¶
Regular expressions are a language for matching text patterns. As we'll see, it is a very expressive language, where I can specify patterns as simple as "does this string contain the word 'foo'?" to patterns to check whether a given string is an e-mail address or a URL. We typically refer to the specification of a single pattern as a regular expression (singular).
We will discuss regular expressions in the context of Python, but they appear in many other contexts.
To use regular expressions in Python, we need to import the "re" module.
import re
A simple pattern¶
Before we get into the language details of regular expressions, let's see how the re module works with a simple example that doesn't require understanding much about regular expressions. Let's say we have the following strings:
seq0 = "AAACCCTTTGGG"
seq1 = "AAGCGTTGGG"
And we want to determine whether the string GTT appears in these strings. We already know how to do this with string operations:
"GTT" in seq0
"GTT" in seq1
However, "GTT" is a valid regular expression: it simply specified the pattern GTT (i.e., literally that string of characters). So, we can instead use the re module. The findall function takes a string and a regular expression, and returns a list with every ocurrence of the pattern:
re.findall("GTT", seq0)
re.findall("GTT", seq1)
The regex language¶
Regular expressions can be used to specify patterns that are much more complex than the simple example shown above. For example suppose we are given a text where we want to extract all the valid e-mail address in the text. Let's start with this simple string:
s = "purple alice-b@google.com max @uchicago foo@bar alan@cs.uchicago.edu XYZ@a...edu ?&#@%$!"
If we didn't have regular expressions, we would probably split the string, and then try to determine whether each individual string is an e-mail or not. We could start by checking whether it includes an @ sign, but that would also include Twitter handles. We could check whether it includes an @ sign and a dot sign, but that could include invalid e-mail addresses.
Regular expressions will give us a way to specify a "valid e-mail address" pattern in a compact way (and finding those patterns in a straightforward way). As we'll see, the language will allow us to easily specify sets of characters (letters, numbers, alphanumeric, custom sets, etc.), repetition of patterns, groups of patterns, etc.
First of all, when specifying patterns in a regular expression we can use the period character to represent any character (except newlines). We can use the findall function to return all the (non-overlapping) substrings that match a pattern. For example, the pattern .@. matches any character, followed by an at-sign, followed by any character:
re.findall(r".@.", s)
Note: We use "raw" strings when specifying regular expressions (
r"..."). There is a good reason for that, but not one that is worth getting into in detail. If you'd like to learn more about why raw strings are preferable, read The Backlash Plague in Python's regular expression documentation.
This looks like it may be a good stepping stone towards an e-mail pattern, but notice how it includes portions of invalid e-mails address: ' @u is part of a Twitter handle, and o@b, 'Z@a', and '#@%' are not part of valid e-mail addresses.
Fortunately, regular expressions also define a number of other sets of characters:
\d: Matches any digit (0-9)\s: Matches any whitespace character (spaces, newlines, tabs, etc.)\w: Matches any alphanumeric character, plus the underscore (thewstands for "word")
So, let's try \w@\w
re.findall(r"\w@\w", s)
That seems to get us closer to what we want (it still includes two invalid e-mail address, o@b and Z@a, but let's worry about that later)
So far, we're only matching one character at a time, but we would like to actually match multiple characters before and after the at sign. Regular expressions allow us to add repetition qualifiers:
*: Matches 0 or more occurrences of the preceding character/pattern+: Matches 1 or more occurrences of the preceding character/pattern?: Matches 0 or 1 occurrences of the precending character/pattern{m,n}: Matchesmtonoccurrences of the precending character/pattern
re.findall(r"\w+@\w+", s)
We're getting closer, but \w does not include the hyphen or dot character. In regular expressions, we can specify custom sets of characters in square brackets. For example, [ab] is a set containing a and b and [ab]+ is "one or more occurrences of either a or b:
re.findall(r"[ab]+", "---aab--a---bbaabbaba-------b--ba")
So, we can try including hyphens and dots in our e-mail regex:
re.findall(r"[\w.-]+@[\w.-]+", s)
Note: The hyphen appears at the end because hyphens also have a special meaning when specifying sets of characters. In particular, it is used to specify ranges of characters. For example,
[a-z]is the set of characters "betweenaandz". If we want to include the literal hyphen character in a set of characters, it must appear as the last character, as done above.
Now we're getting all the valid e-mails, but some of the invalid e-mails are still slipping through! We could tweak this by saying that the domain (the part after the at sign) should include an alphanumeric string (including hyphens) followed by a dot followed by another alphanumeric string:
re.findall(r"[\w.-]+@[\w-]+\.[\w-]+", s)
But now we're not matching all of alan@cs.uchicago.edu. To do this, we need to specify the repetition of a specific pattern, not just a character or set of characters. In particular, the domain will be an alphanumeric string (including hyphens), followed by one or more occurrences of a dot followed by an alphanumeric string. "A dot followed by an alphanumeric string" is a pattern (not a set of characters), because we expect the dot to appear in a specific position, not anywhere in the string. We can apply the + qualifier to that pattern by putting the pattern between (?: and ):
(?:\.[\w-]+)+
Note that we put a backslash before the dot so that it is interpreted as "literally the dot character" (as opposed to the special meaning that the dot character has in regular expressions)
re.findall(r"[\w.-]+@[\w-]+(?:\.[\w-]+)+", s)
Parsing e-mail addresses is actually much more complicated. A regex that captures (most) e-mail addresses is the following:
email_regex = "(?:[a-z0-9!#$%&'*+/=?^_`{|}~-]+(?:\.[a-z0-9!#$%&'*+/=?^_`{|}~-]+)*|\"(?:[\x01-\x08\x0b\x0c\x0e-\x1f\x21\x23-\x5b\x5d-\x7f]|\\[\x01-\x09\x0b\x0c\x0e-\x7f])*\")@(?:(?:[a-z0-9](?:[a-z0-9-]*[a-z0-9])?\.)+[a-z0-9](?:[a-z0-9-]*[a-z0-9])?|\[(?:(?:25[0-5]|2[0-4][0-9]|[01]?[0-9][0-9]?)\.){3}(?:25[0-5]|2[0-4][0-9]|[01]?[0-9][0-9]?|[a-z0-9-]*[a-z0-9]:(?:[\x01-\x08\x0b\x0c\x0e-\x1f\x21-\x5a\x53-\x7f]|\\[\x01-\x09\x0b\x0c\x0e-\x7f])+)\])"
Source: http://emailregex.com/ (which, in turn, is based on the standard definition in RFC 5322
re.findall(email_regex, s)
Group matching¶
Sometimes, we may want to match a pattern while also taking into account where that pattern appears. For example, let's look at an e-mail message:
msg = open("sample-email.txt").read()
print(msg)
The first lines are called the headers of the e-mail. There are a lot of different headers, and we will only be concerned with the "From" and "To" headers, which specify the sender and recipient of the e-mail. Let's say we want to extract the sender of an e-mail; we could use the regular expression we specified before:
re.findall(email_regex, msg)
However, this returns two e-mails (the From and To) and something that happens to match the e-mail regex, but is not actually an e-mail (it is an identifier for the e-mail message). We could be tempted to say "the first e-mail is the sender's e-mail", but that may not always work. For example, suppose we have multiple e-mail messages in one file:
emails = open("sample-emails.txt").read()
print(emails)
re.findall(email_regex, emails)
Extracting the sender e-mails from the above can be tricky. Fortunately, we can write a regular expression that matches all the e-mail addresses that are preceded by "From: "
re.findall(r"From: " + email_regex, msg)
re.findall(r"From: " + email_regex, emails)
While we easily remove the "From: " using string processing functions, we can also use groups in regular expressions to specify the actual part of the pattern that we're interested in. A group is any pattern in parentheses:
re.findall(r"From: (" + email_regex + ")", emails)
The above regular expression only specifies one group, but we can specify multiple groups in a single regular expression. For example, let's take our original e-mail regex, and put parentheses around the part of the pattern before the @ sign and in the part after the @ sign:
re.findall(r"([\w.-]+)@([\w-]+(?:\.[\w-]+)+)", emails)
re.findall(r"From: ([\w.-]+)@([\w-]+(?:\.[\w-]+)+)", emails)
Notice how we now get a list of tuples back, with each tuple containing the values for each group within the matched pattern.
When using a regular expression where we only expect, at most, one match, we can also use the search function, which returns a Match object that provides a better interface for working with these groups:
m = re.search(r"([\w.-]+)@([\w-]+(?:\.[\w-]+)+)", "alan@cs.uchicago.edu")
m.groups()
m.group(0)
m.group(1)
m.group(2)
We can also name each group by using (?P<groupname>...) instead of just parentheses:
m = re.search(r"(?P<user>[\w.-]+)@(?P<domain>[\w-]+(?:\.[\w-]+)+)", "alan@cs.uchicago.edu")
m.group("user")
m.group("domain")
The Enron e-mail dataset¶
The Enron Corporation was an American energy, commodities, and services company that collapsed due to corporate fraud and corruption. The Federal Energy Regulatory Commission publicly posted all the information it used in its investigation, including several hundreds of thousands of e-mails.
This email dataset has been used in a number of scholarly works on text processing, network analysis, etc. We will do a very simple analysis of the dataset, which we downloaded from https://www.cs.cmu.edu/~enron/. We converted the dataset into the mbox file format because it will make it easy to process using regular expressions, while still allowing us to process the dataset one message at a time.
- Download full dataset (351 MB)
- Download 100K dataset (75 MB)
Once you have downloaded the datasets, you will need to uncompress them:
gunzip emails-100k.mbx.gz
gunzip emails-all.mbx.gzWe are going to count how many e-mails are sent from each e-mail address. We can simply use the same regular expression we used earlier to extract the e-mail address from the "From" header. However, because we are going to check a lot of data, we are going to compile the regular expression so we can reuse it efficiently:
from_regex = re.compile(r"From: (" + email_regex + ")")
The from_regex variable now contains an object with an efficient internal representation of the regular expression (produced from the string specification we passed to compile, and which we were earlier passing to findall and search)
The following code is the standard "iterate over a list of things and count them" code, but where we use a regex to extract the e-mail address in the From header. Notice how we don't read the entire file into memory (it's 1.5GB!). Instead, we read it line by line and search each line using the regex.
enron = open("emails-all.mbx")
from_counts = {}
for l in enron:
m = from_regex.search(l)
if m is not None:
email = m.group(1)
if email not in from_counts:
from_counts[email] = 0
from_counts[email] += 1
We will use the Counter object from the collections module to produce the top 10 entries in the from_counts dictionary:
import collections
c = collections.Counter(from_counts)
c.most_common(10)
Interestingly, there are not that many e-mails from Ken Lay or Jeff Skilling:
from_counts["kenneth.lay@enron.com"]
from_counts["jeff.skilling@enron.com"]
Avoid reinventing the wheel: the email module¶
Regular expressions provide a quick and convenient way to search for patterns in (potentially large) datasets.
![Wait, forgot to escape a space. Wheeeeee[taptaptap]eeeeee.](regular_expressions.png)
However, whenever you find yourself parsing data that follows a standard format (like e-mails do), you should avoid reinventing the wheel. Someone has probably already implemented code to parse data in that format, and they probably account for a lot more corner cases than you do. For example, the From and To headers in an e-mail can list senders/recipients in a variety of ways:
s = open("sample-email-multiple-recipients.txt").read()
print(s)
Our regular expression does not account for this! While we could tweak it, it turns out that Python already includes an email module to parse e-mail messages.
import email
msg = email.message_from_string(s)
We can access the headers using a dictionary-like syntax:
msg["from"]
msg["date"]
msg.items()
Note: The message is not a dictionary. It just provides dictionary-like access to the headers. Notice how the header names are case-insensitive.
Accessing the body of an e-mail is slightly more complicated because we have to account for messages with attachments, etc.
def get_email_body(msg):
if msg.is_multipart():
for part in msg.walk():
if part.get_content_type() == 'text/plain':
return part.get_payload()
else:
return msg.get_payload()
get_email_body(msg)
Parsing the addresses in the From, To, and CC headers can be easily done with email.utils.parseaddr and email.utils.getaddresses.
msg["from"]
email.utils.parseaddr(msg["from"])
msg["to"]
email.utils.getaddresses([msg["to"]])
def get_all_recipients(msg):
tos = msg.get_all('to', [])
ccs = msg.get_all('cc', [])
return [a for _, a in email.utils.getaddresses(tos + ccs)]
get_all_recipients(msg)
We can now write some code to count all the (sender, recipient) pairs in the Enron email dataset. We use the mailbox module, which allows us to easily iterate over each message in the file.
import mailbox
enron = mailbox.mbox("emails-100k.mbx")
pairs_counts = {}
for msg in enron:
_, from_addr = email.utils.parseaddr(msg["from"])
recipients = get_all_recipients(msg)
for r in recipients:
pair = (from_addr, r)
if pair not in pairs_counts:
pairs_counts[pair] = 0
pairs_counts[pair] += 1
This code takes longer to run than our previous code (even when using a smaller dataset) because, for every message, we have to parse the entire e-mail message (previously, we were only running a regular expression that targetted the From header exclusively). This is a tradeoff: we can get better performance with a regular expression, but we may be limited by how complete our regular expression is. However, regular expressions are still useful on their own in many cases.
import collections
c = collections.Counter(pairs_counts)
c.most_common(10)