Regular Expressions for Text Extraction: Still Undefeated

Every few months someone replaces a working regular expression with a model call and reports it as modernisation. Sometimes that is right. When the thing being extracted has a written specification, it is a strict downgrade on cost, latency, determinism and correctness at once.

The class of problems regex owns

The boundary is not about difficulty, it is about the shape of the specification. If the target is defined by a grammar somebody wrote down, a regular expression is that grammar, and it matches exactly the strings the specification permits. There is no accuracy number to quote because there is no estimation happening.

• Identifiers with a defined format. UUIDs, semantic versions, ISBNs, IBANs, ISINs, VAT numbers, ticket keys, git SHAs, hex colours. Each has a published format, several have check digits you can verify after matching.
• Machine-generated text. Log lines, stack traces, CSV fragments, HTTP headers, timestamps in a known format. Something wrote them to a template; you are reading the template backwards.
• Structural pre-filters. Does this document contain anything that looks like a card number, an email address, a phone number? A cheap regex over ten million documents narrows to the thousand that need real attention. This is the highest-value use and the most underused.
• Tokenising and cleaning. Splitting on boundaries, stripping control characters, collapsing whitespace. The normalisation code in this cluster is regex all the way down.

The arithmetic, and it is not close

Assumptions, all replaceable: 10 million documents per month, 300 tokens each, roughly 1,200 characters.

A compiled regular expression scans those 1,200 characters in microseconds — the exact figure depends on the pattern, but the order of magnitude is not in doubt for a linear-time engine. Ten million documents is on the order of tens of seconds of CPU. On a box you are already paying for, the marginal cost is indistinguishable from zero, and the latency added to a request is below the noise floor of everything else in the handler.

The same 10 million documents through a hosted model is 3 billion input tokens. At an assumed $0.10 per million that is $300 a month; at an assumed $1.00 per million it is $3,000. Add a few hundred milliseconds per document, and the fact that you now need retries, rate-limit handling and a queue, none of which the regex needed. And the model can return an ISBN that is not in the document, while the regex structurally cannot.

The ratio is not the argument, though — a $300 bill is affordable. The argument is that you are paying it for a worse answer on a task where exactness was available for free.

The outage a regex caused

The honest counterweight, and it is a serious one. On 2 July 2019 Cloudflare had a global outage in which HTTP traffic across its network failed. The cause, described in detail in their own public post-mortem, was a newly deployed WAF rule containing a regular expression that exhibited catastrophic backtracking, driving CPU to saturation across the fleet.

The mechanism is worth understanding because it is not exotic. A backtracking engine — the default in Perl, Python, Java, JavaScript, .NET and PCRE — explores alternatives on failure. Nested quantifiers over overlapping character classes, the classic shape being (a+)+b or .*.*=.*, produce a number of paths that grows exponentially with input length. A pattern that is instant on a 20-character string can take longer than the age of the universe on a 40-character one. When the input is attacker-controlled this is a denial-of-service vulnerability with its own name, ReDoS.

Three defences, in order of strength. Use a linear-time engine — RE2, Go’s regexp, the Rust regex crate — which guarantees linear time by refusing to support backreferences and lookaround. Failing that, impose a timeout and an input length cap on every match against untrusted data. And always anchor patterns and avoid nested quantifiers over overlapping classes; most catastrophic patterns are also badly written ones.

Where regex is the wrong tool

Being clear about this is what makes the rest credible. Regular expressions cannot match nested structure — that is a formal result, not a limitation of effort — which is why parsing HTML, JSON or any balanced-delimiter format with them fails on the first nested case. Use a parser.

They are also the wrong tool whenever the specification is “whatever people write”. Postal addresses vary by country and by writer. Person names have no format. Dates written by humans span next Tuesday, 3/4/25 (ambiguous by continent) and the end of Q2. Phone numbers across the world are not a regular language in practice, which is why libphonenumber is a large library rather than a pattern. Product descriptions, medical notes and free-text fields are all in this category. A regex here does not fail loudly; it accumulates hundreds of special cases and becomes the file nobody will touch.

The signal to watch for is maintenance shape. A pattern that has been edited eleven times, each time to handle one more real example, has stopped being a specification and become a very bad classifier. That is the moment to replace it — with a trained classifier if the volume is high, or a model if it is not.

The hybrid that ships

The arrangement that gets the best of both is a cascade, and it applies to nearly every extraction problem:

CANDIDATE = re.compile(r"\b[A-Z]{2}\d{2}[A-Z0-9]{11,30}\b")  # IBAN shape

def extract_ibans(text):
    hits, unsure = [], []
    for m in CANDIDATE.finditer(text):
        s = m.group(0)
        if iban_checksum_ok(s):        # mod-97 check, defined in the spec
            hits.append((s, m.start(), m.end()))   # exact, free, offsets kept
        else:
            unsure.append((s, m.start(), m.end())) # OCR error? adjudicate
    return hits, unsure

The regex does candidate generation over the whole corpus at zero marginal cost and keeps character offsets. The checksum — which is part of the IBAN specification — resolves most candidates exactly. Only the residue, typically a fraction of a per cent, is worth sending to anything expensive. Applied to the arithmetic above, a 1% escalation rate turns a $300 monthly bill into $3, and the 99% that stayed local got the more accurate answer.