Finding dates in string

Question

I'm looking for a fast way in C# to find all dates in a string (the string is a big text, I've to scan for about 200,000 different strings).

since there are many ways to write date (for example 31/12/2012 or Dec 31, 2012 and much more), I'm using this Regex (that should cover almost all frequent ways to write dates):

string findDates = "(?:(\d{1,4})- /.- /.)|(?:(\s\d{1,2})\s+(jan(?:uary){0,1}\.{0,1}|feb(?:ruary){0,1}\.{0,1}|mar(?:ch){0,1}\.{0,1}|apr(?:il){0,1}\.{0,1}|may\.{0,1}|jun(?:e){0,1}\.{0,1}|jul(?:y){0,1}\.{0,1}|aug(?:ust){0,1}\.{0,1}|sep(?:tember){0,1}\.{0,1}|oct(?:ober){0,1}\.{0,1}|nov(?:ember){0,1}\.{0,1}|dec(?:ember){0,1}\.{0,1})\s+(\d{2,4}))|(?:(jan(?:uary){0,1}\.{0,1}|feb(?:ruary){0,1}\.{0,1}|mar(?:ch){0,1}\.{0,1}|apr(?:il){0,1}\.{0,1}|may\.{0,1}|jun(?:e){0,1}\.{0,1}|jul(?:y){0,1}\.{0,1}|aug(?:ust){0,1}\.{0,1}|sep(?:tember){0,1}\.{0,1}|oct(?:ober){0,1}\.{0,1}|nov(?:ember){0,1}\.{0,1}|dec(?:ember){0,1}\.{0,1})\s+([0-9]{1,2})[\s,]+(\d{2,4}))";

with "RegexOptions.Compiled | RegexOptions.IgnoreCase | RegexOptions.IgnorePatternWhitespace" tags. also, i tried to pre-compile the regex to make it even more fast.

The problem is that it's very slow (on some text fies more than 2 seconds) Is there any better and efficient way to do this?

Thanks

Answer 1

The expression looks good overall, as others have mentioned, it might be a bit verbose with all the {0,1} instead of ? and the (?: instead of applying RegexOptions.ExplicitCapture. But these shouldn't make the expression slow. They only result in better readability.

What might be causing slowness is the fact that there's a lot of backtracking options in the expression by making both the expanded month and the . optional. I wonder what would happen if you changed the expression to only apply the optional . once, after the month name, and what would happen if you made the month name a greedy group ((?>pattern) Nonbacktracking (or "greedy") subexpression.)

So that:

 (jan(?:uary){0,1}\.{0,1}|feb(?:ruary){0,1}\.{0,1}|mar(?:ch){0,1}\.{0,1}|apr(?:il){0,1}\.{0,1}|may\.{0,1}|jun(?:e){0,1}\.{0,1}|jul(?:y){0,1}\.{0,1}|aug(?:ust){0,1}\.{0,1}|sep(?:tember){0,1}\.{0,1}|oct(?:ober){0,1}\.{0,1}|nov(?:ember){0,1}\.{0,1}|dec(?:ember){0,1}\.{0,1})\s+(\d{2,4}))

Would become:

 (?>jan(uary)?|feb(ruary)?|mar(ch)?|apr(il)?|may|june?|july?|aug(ust)?|sep(tember)?|oct(ober)?|nov(ember)?|dec(ember)?)\.?\s+(\d{2,4}))

Not only is it much shorter, I'd expect it to be faster.

And then there's the part of the expression at the start, which doesn't really make sense to me (?:(\d{1,4})- /.- /.) Either something got lost in the formatting, or this isn't helping one bit.

\d{1,4} would make sense for a year or any other date part, but the - /.- /. after it doesn't make sense at all. I think you meant something like:

 \d{1,4}[- /.]\d{1,2}[- /.]\d{1,2}

Or something in that area. As it stands it captures garbage, probably not speeding up the matching process.

In the end I agree with Aliostad, that you're probably better off trying to find a less precise pattern to find initial candidates, then narrow the results using either DateTime.TryParseExact or with an additional set of expressions.

Instead of creating a 'global' expression to find candidates, you could use a lot of exact expressions. You'll see that with Regex it's often cheaper to run a number of exact expressions over a large input, than running one expression with a lot of |'s and ?'s in there.

So breaking down your search into multiple very exact expressions might result in a lot higher performance, these could be a start:

 \b\d{1,2}[- .\\/]\d{1,2}[- .\\/](\d{2}|\d{4})\b
 \b((jan|feb|mar|apr|jun|jul|aug|sep|oct|nov|dec)(.|[a-z]{0,10})|\d{1,2})[- .\\/,]\d{1,2}[- .\\/,](\d{2}|\d{4})\b

As you can see all optional groups have been removed from these expressions, making them a lot faster to run. I've also removed the exact spelling from the month names, as you probably want to accept 'sept' as well as 'sep' as well as 'september'

Breaking up the pattern also improves readability :).

One last tip: limit the amount of possible characters you need to backtrack, by putting a limit on things like \s+, you rarely want 20,000 spaces to match, but if they're in your source document, it will try to match them. \s{1,20} is usually enough and limits the engines ability to try to get a match where there really isn't one.

Answer 2

It is difficult to come up with an algorithm without testing it. We could recommend something which turns out slower. So really it is trying different options.

Your expression looks a bit verbose but I cannot say it is the cause of the issue. 2 seconds for a big file is OK but not for a smaller file so it is all relative to the size of the work it is doing

---

One approach I can recommend is having a two stage process.

First one is the screening to fish for the ones most likely matching and the other is to further examine only that section of the file which the match is located. For example, '\d{1,2}\s*,\s*\d{4}' is likely to be part of a date but looking for it is better than looking for all conditions concerning Jan(uary)/Feb(ruary)/Mar(ch)/....

---

And a small piece of advice: first get the metrics right, do the homework of establishing your base metrics before starting any change.

If you want to improve performance you have to have some hard and fast metrics before even attempting to improve.