In my previous post, I presented some regular expressions you can use to spot dates, times, prices, email addresses and web links, along with a test page to see them in practice. REs can be pretty daunting when you’re first working with them, so I wanted to recommend a few resources that have helped me in the past.

The best overall guide on the web is regular-expressions.info, and I used some of Jan’s suggestions for email address matching. He has also written a very clever regular expressions assistant that breaks down any cryptic RE into a human-readable description. I also liked this python tutorial on REs, it’s focused on a good practical example and shows how you’d build up the expression step by step.

As I mentioned yesterday, to demonstrate the power of regular expressions on a web page I had to write my own library for handling search and replace on a web page in Javascript. This is a surprisingly tricky problem to solve. First you have to actually get the text for the web-page, which involves walking the DOM, extracting all the text nodes and then concatenating them back together. That lets you search on the full text, but if you want to change anything you have to remember which parts came from which elements. Then since only part of an element’s text may match, and the matching text may spread across several DOM elements, you have to do some awkward node splitting and reparenting to get nodes that just contain the match.

I’ve included some documentation in the library as comments, but the main entry point is the searchAndProcess() function. This takes three arguments, a regular expression to search for, a callback function you supply to create a new node to be the parent of the element that contains the matching text, and a cookie value that’s passed to the callback function so you can customize its behavior easily.

The callback function itself receives three arguments, the current document so it can create a new element, the results of the RE match, and the client-supplied cookie. The RE results are the most interesting part of this, since they’re the same format that’s returned from the JS RegExp.exec() function. They’re an array where the first entry is the full text that’s matched by the expression, but then subsequent entries contain the text that was matched by each sub-set contained with parentheses. This means I can use the second, third and fourth array entries in the phone number callback to create a number that excludes any spaces or separator characters. Here’s an example of that in practice from the test page. View the entire page’s source to see more examples of how to use it. The cookie is used to pass in the protocol to use for phone number links, usually ‘callto:’.

function makePhoneElement(currentDoc, matchResults, cookie)
{
	var anchor = currentDoc.createElement("a");

	anchor.href = cookie+matchResults[1]+matchResults[2]+matchResults[3];

	return anchor;
}

I had so much fun playing with the regular expressions for this one, that I ended up building a fairly elaborate testbed and missed my usual morning-cup-of-tea posting deadline. The page demonstrates using REs to pull out phone numbers, emails, urls, dates, times and prices from unstructured text, and uses a JS library I’m making freely available to search and replace within an HTML document. There’s some sample text to show it off, and you can put it through its paces by inputting your own strings to really test it.

If you want to see the power of this approach, try grabbing some of your own emails and pasting them into the custom box (it’s all client-side so I’ll never see any of them). You’ll be surprised at how much these expressions will pick up. Imagine how much useful information you could get from a whole company’s mailstore.

Here’s the exact REs I’m using, you may need to escape the back-slashes depending on your language:

Phone numbers (10 digit US format, with any separators)
([0-9]{3})[^0-9]*([0-9]{3})[^0-9]*([0-9]{4})

Email addresses
[a-z0-9._%+-]+@[a-z0-9.-]+\.[a-z]{2,4}

URLs with protocols
https?://[a-z0-9\./%+_\-\?=&#]+

Naked URLs (this will also pick up non-URLs like document.body)
[a-z0-9\./%+_-]+\\.[a-z]{2,4}[a-z0-9\./%+_\\-\\?=&#]*

Dollar amounts
\$\s?[0-9,]+(\.[0-9]{1,2})?(\s(thousand|m[^a-z]|mm[^a-z]|million|b[^a-z]|billion))?

Numerical times
[012]?[0-9]:[0-5][0-9]((\.|:)[0-5][0-9])?(\s?(a|p)m)?

Dates
(January|Jan|February|Feb|March|Mar|April|Apr|May|June|Jun|July|Jul|August|Aug|September|Sept|October|Oct|November|Nov|December|Dec)[^0-9a-z]+([0-9]{1,2})(st|nd|rd|th)?[^0-9a-z]+((19|20)?[0-9]{2})

Numerical dates
([0-9]{1,2})[/-]([0-9]{1,2})[/-]((19|20)?[0-9]{1,2})

These handle the common cases I’m interested in at the moment. There’s no end to how elaborate you could make them to handle all the possible different formats, but these cover a lot of ground. Now I have to resist the temptation to build these into a Firefox extension. IE’s RE engine does seem to want to overmatch with the email expression, sometimes pulling in characters past the end, but that seems to be an implementation quirk since I don’t notice that in the other environments like Firefox, Safari or grep.

As I mentioned in my review of ManagedQ, you can do some really interesting things with regular expressions. Roger Matus talked about IBM’s Personal Email Search tool back in December, and the core of that appears to be using REs to recognise phone numbers, email addresses and URLs in the body of messages. Skype and other companies have been working pretty intensively on phone number recognition, taking things a bit further with knowledge about possible dialing codes to help them reformat the numbers in a standard way. I won’t be taking things that far, but in the next article I’ll be showing you the expressions you need to recognize simple dates, times, phone numbers, email addresses, prices and URLs from a text document. You’ll be able to pick out all of these examples using a few simple expressions:

805 277 3606, 8052773606, 805 277-3606
pete@petewarden.com
http://foo.com , foo.com, http://www.foo.com
$10, $10.99, $10 million
10:30
June 1st, 2008, 6/1/08, 6/1/2008

In case you missed it on ReadWriteWeb, researchers at MIT and NYU have created a fascinating visual map of nouns. They’re pulling the word relationships from WordNet, a venerable data set that maps the relationships between over 150,000 words. I’ll be studying their paper to understand exactly how they grouped the nouns, since they seem to have done a great job of clustering them in a meaningful way across a 2D surface. That could be very useful for keyword similarity measurements and email grouping.

It also reminds me of a film-strip visualization that I saw a couple of years back, but which I can’t find the reference for unfortunately. A frame was taken every 5 seconds from a movie, and shrunk to a few pixels, and then the sequence of images were arranged in a grid. You could get information about the different scenes and moods in the whole movie at once, just from the color of each section. It wasn’t much but it was enough to let your brain’s visual processing machinery comprehend the structure.

In the same way, this map is a good way of presenting the whole space of noun categories in a way that’s much easier to navigate than a hierarchical tree or table. A common trick for memorizing arbitrary data like long random numbers is to associate each part with physical locations, because we evolved to be really good at remembering exactly where all the fruit (and leopards!) were in the local jungle. It’s easy to find and return to a given noun in this setup because you’re using the same skills.

According to a new report, over half of companies that use an Exchange mail server also use Sharepoint. This backs up my personal experience. For example, Liz works for a fairly conservative large company but even they are heavy Sharepoint users.

This is a big technological change, but it tends to slip under a lot of people’s radar because it’s a  closed-source, me-too technology with a very traditional business model. It’s successful because it’s stable, uses a familiar UI, is easy to deploy, often comes for free with Office and overall works remarkably well.

Microsoft are providing a ready-made distribution channel for getting your technology in front of employees. They’re training massive numbers of people to create and consume user-generated content on the company’s intranet. The great thing is that they leave plenty of room for third-party products to take advantage of this. They have some Exchange/Sharepoint integration, and no doubt will be increasing that in the future, but there’s a fantastic opportunity to present all sorts of interesting mail-derived information in a place people are already looking. A good example of this would be automatically populating each employee’s homepage with links to her most frequent internal and external contacts, or adding email-driven keywords there to be found by a ‘FindaYoda’ style search.

I’m so convinced this is an important direction, I have my own Sharepoint site I’m using as a testbed, hosted with Front Page Web Services [Update- They’re now FPWeb.net, at http://www.fpweb.net/sharepoint-hosting/ ]. I’ll be posting more about the integration opportunities as I dig deeper, as well as using it when I need to collaborate.

[Update- Eric did a great Sharepoint post on Friday too, with some interesting points on the way collaboration with Sharepoint is heavily grass-roots driven at the moment, which will mean a strong drive for the IT department to catch up]

[Second update –

Maybe it was my weekly D&D game last night, but probability is on my mind. One thing I’ve learnt from working in games is that accuracy is overrated in AI. Most problems in that domain have no perfect solution. The trick is to find a technique that’s right often enough to be useful, and then make it part of a workflow that makes coping with the incorrect guesses painless for the user.

A lot of Amazon’s algorithms work like this. They recommend other books based on rough statistical measures which bring up mostly uninteresting items, but it’s right often enough to justify me spending a few seconds looking at what they found. The same goes for their statistically improbable phrases. They’re odd and random most of the time but usually one or two of them do give me an insight into the book’s contents.

This is interesting for email because when I’m searching through a lot of messages I need a quick way to understand something about what they contain without reading the whole text. One of the key features of Google’s search results is the summary they extract surrounding the keywords for each hit. This gives you a pretty good idea of what the page is actually discussing. In a similar way I want to present some key phrases from an email that very quickly give you a sense of what it’s about.

The main approach I’m using is vanilla SIPs, but there’s a couple of other interesting heuristics (sounds so much more technical than ‘ways of guessing’). The first is looking for capitalized phrases within sentences. These are usually proper nouns, so you’ll get a rough idea of what people or places are discussed in a document. The second is to find sentences that end with a question mark, so you can see what questions are asked in an email.

These are fun because they’re both reliant on easily-parsed quirks of the language, rather than deep semantic processing. This means they’re quick and easy to implement. It also means that they’re not very portable to other languages, German capitalizes all nouns for example, but one problem at a time!