Categorize Everything All At Once

After a couple months of complete radio silence I'm back again! I've been taking some time to rest lately and I figured it's time to write something again.

This time I have an example of what I love about computer science, a little regex party trick. It comes with a bit of voodoo and abstract theory, but it has a good response to the most important question of any theory, "Why should I care?". So the voodoo has some purpose, and many useful applications, which is way more exciting than voodoo without it.

As the title says we will be doing some categorizing, labeling.. named entity recognition or however you wish to call it. And I'll show you how it's easy, and how to do it with less electricity, battery drain, heat, fan noise. In fact you get it essentially for free by computing something up front, after which it's no more expensive than searching for a word. And I built it into resharp as well.

We can do something that looks like the following:

Now for a little (unscientific) benchmark on named entity recognition, let's compare it to spaCy en_core_web_sm model for entity recognition.

	1 thread	8 threads
spaCy 3.8, NER component only	0.09 MB/s	0.43 MB/s
resharp `categorize_all`, 10 patterns	0.36 GB/s	1.92 GB/s (4500x faster)

This is an apples-to-oranges comparison, yes, but I don't think it diminishes our whopping 1.92 gorillion bytes a second. I'd argue that the two are comparable.

Why do I think these are comparable?

Are we 55.1% sure this is a date? Should we consult a mixture of experts on what is and isn't a date? Develop an AI accelerated workflow to roll a few dice? No.

last post I was talking about how regex is often used as an approximative "good enough" tool, and how its expressivity is not enough to parse HTML.

This time, yyyy-MM-dd is a regular language. Meaning we can reliably, deterministically, tell if something is a date or not using regex, even leap years included.

uno reverse

So we are not approximating anything, and look how much work the neural net has to do, to replicate a fraction of our awesome, deterministic, correct 100% of the time, power.

And that's what this tool is for, when you don't need or want to involve dice rolls.

The patterns

Below are the patterns used for the first example:

DATE [0-9]{4}-[0-9]{2}-[0-9]{2}
MONEY \$[0-9]+(?:\.[0-9]{2})?
PERCENT [0-9]+(?:\.[0-9]+)?%
EMAIL [a-z.]+@[a-z]+\.[a-z]+
URL https?://[^ ]+
NUM [0-9]+
NAME [A-Z][a-z]+\b&~(On|In|At|To|For|Of|The|An|And|Via|Was|Is)
VERB [a-z]+ing\b
ADJ [a-z]+(?:ful|less|ous|ive)\b
ADV [a-z]+ly\b

In the NAME pattern we use & for intersection and ~ for complement, if you're not familiar with them, read this post first, but they should be intuitive enough. Think of them as AND and NOT operators, which let us exclude "On", "In"... from being falsely detected as names. If any of these do happen to be your name, I apologize!

[A-Z][a-z]+\b&~(On|In|At|To|For|Of|The|An|And|Via|Was|Is)

Don't underestimate the expressivity of regular languages

You can do if-then-else on regex without leaving the domain of regular languages, meaning:

Is still expressible in pure regex. This works however many if-then-elses you wish to chain or nest, it is a boolean algebra.

The pattern becomes unreadable spaghetti, but for RE# it is nothing but a formula for how to construct a state machine. Using a bit of JavaScript string magic, we can build these from small composable pieces.

const ifThenElse = (cond: string, a: string, b: string) =>
  `((${cond}&${a})|(~(${cond})&${b}))`;

const yyyymmdd = "[0-9]{4}-[0-9]{2}-[0-9]{2}";
const february = "[0-9]{4}-02-_*";
const upTo29   = "_*-(0[1-9]|[12][0-9])";
const upTo31   = "_*-(0[1-9]|[12][0-9]|3[01])";

const date = `${yyyymmdd}&${ifThenElse(february, upTo29, upTo31)}`;

which expands to

[0-9]{4}-[0-9]{2}-[0-9]{2}&(([0-9]{4}-02-_*&_*-(0[1-9]|[12][0-9]))|(~([0-9]{4}-02-_*)&_*-(0[1-9]|[12][0-9]|3[01])))

and compiles into a state machine that looks like this (below) and excludes February the 30th. 26 DFA states is not bad at all. RE# supports up to 65536 states by default.

february fsm

february matches

We have some more tricks up our sleeve to make sure it works for larger patterns too! Let's do the whole calendar. Months 01 to 12, February has 28 days unless it's a leap year, four months have 30, the rest have 31.

const ifThenElse = (cond: string, a: string, b: string) =>
  `((${cond}&${a})|(~(${cond})&${b}))`;
const month = (mm: string) => `[0-9]{4}-${mm}-_*`;

const yyyymmdd   = "[0-9]{4}-(0[1-9]|1[0-2])-[0-9]{2}";
const upTo28     = "_*-(0[1-9]|1[0-9]|2[0-8])";
const upTo29     = "_*-(0[1-9]|[12][0-9])";
const upTo30     = "_*-(0[1-9]|[12][0-9]|30)";
const upTo31     = "_*-(0[1-9]|[12][0-9]|3[01])";

const february   = month("02");
const thirtyDays = month("(04|06|09|11)");
const isLeap = (y: number) => (y % 4 === 0 && y % 100 !== 0) || y % 400 === 0;
const leapYears = [...Array(10000).keys()].filter(isLeap)
  .map(y => String(y).padStart(4, "0"));
const leapYear   = `(${leapYears.join("|")})-_*`;

const date = `${yyyymmdd}&${ifThenElse(february,
  ifThenElse(leapYear, upTo29, upTo28),
  ifThenElse(thirtyDays, upTo30, upTo31))}`;

The pattern is an enormous monstrosity of leap years and if-then-elses, but just because the pattern is large, doesn't mean the state machine has to be.

Guess how many states this 24504 characters long pattern compiles into:

date-full-union

It has 32 DFA states.

the full yyyy-MM-dd automaton, 32 states

And in the event that the DFA does start to resemble the Milky Way, remember that the size of the state graph is misleading. Like a synapse in your brain, we only make use of the connections that are actually necessary for the task at hand. I don't even know what would happen if your whole brain fired at the same time, would you pass out or what? (UPDATE: it's a seizure.)

That's all to say we only compile states that we visit, often a tiny fraction of what you see here.

lazy-compilation

Which means we can get away with massive, even infinite state machines, without necessarily suffering the consequences. The state machine is just an abstraction, a caching technique.

About the categories

The way it works is quite simple from the state machine point of view, e.g. consider the union of these two patterns:

NUM [0-9]+
PERCENT [0-9]+(?:\.[0-9]+)?%

Cool how do I use it

It's in resharp behind the regex_set feature.

[dependencies]
resharp = { version = "0.7.5", features = ["regex_set"] }

Build a RegexSet from your patterns (below), the enum isn't necessary but perhaps makes it nicer to use.

use resharp::RegexSet;

#[derive(Debug, Clone, Copy)]
enum Entity { Date, Money, Num }

const LEXICON: &[(Entity, &str)] = &[
    (Entity::Date,  r"[0-9]{4}-[0-9]{2}-[0-9]{2}"),
    (Entity::Money, r"\$[0-9]+(?:\.[0-9]{2})?"),
    (Entity::Num,   r"[0-9]+"),
];

let set = RegexSet::new(LEXICON.iter().map(|(_, p)| *p))?;

let text = b"On 2024-01-15 Alice sent $12.50 for 3 things";
for m in set.categorize_all(text)? {
    let (entity, _) = LEXICON[m.tag];
    println!("{entity:?} {:?}", std::str::from_utf8(&text[m.start..m.end])?);
}

Date "2024-01-15"
Money "$12.50"
Num "3"

For the sake of simplicity, if two patterns match the exact same span, it reports only the lower index, though it is not a problem to return multiple overlapping patterns too, I'm still undecided on what else it should do.

Two smaller operations on the same set, in case you don't need the spans:

set.is_match(b"pay $5")?;  // true
set.matched(b"pay $5")?;   // [1, 2], every member that matches somewhere

All the experiments from this post are on github.

That's all for now, thanks for reading!