For a problem at work, I needed to create a RegexSet of over 10 MM really long regexes. No engine out of the box could handle it. Even Rust’s RegexSet wasn’t good enough by default.
However, trying to use and read through regex-automata and regex-syntax (even in 2018) was such a very valuable and helpful learning resource. I ended up modeling the project at work off Lucene APIs, but it was all only after learning the basics from the regex crates.
Yeah 10 million regexes is huuuuge. Aho-Corasick can barely handle 10 million literals.
Future work is definitely trying to make the regex engine scale better with more patterns. Currently, it will crap out well before 10 million regexes, and I'm not sure that goal is actually attainable. But it can certainly be better than what it is today.
And of course, Hyperscan is really the gold standard here as far as multi-pattern searching goes. I'm not sure how well it will handle 10 million patterns though.
Yeah basically built a competitor to Hyperscan without the proprietary Intel bits.
Quick notes: to scale past X regexes in the set.
1. Don’t make a single RegexSet. Create multiple internally.
2. Ideally colocate similar partners together.
3. Use the immutability of a RegexSet to your advantage by generating an inverse index of “must match” portions of each regex.
4. When you get an input to match, first check the inverse index for a “may match set”, then only execute the internal automata that may possibly match on the input.
The inverse index can be as complicated (FSTs, or all of Lucene) or simple (hash map ) as you’d like it to be. The better it can filter the regexes in the set the more performance and scale you end up with. And tune the sizes of the internal automata for your usecase for some Goldilocks size for extra perf.
Right. I'll also note that this strategy probably assumes something about the search task itself, and may not work for all possible search operations. Think about what happens when your haystack is GBs big for example.
I'm guessing the answer's 'no' because you didn't elaborate to begin with, but on the off-chance - can you share any more about what the problem/project was?
Sure, it has been a while. I worked at Amazon in Brand Protection, specifically on Trademark and Logo infringement.
There were many different strategies at play (eg neural nets) but the false positives can be very expensive. But the one I described above is an expert system of manual overrides that made the final decisions.
Amazon don’t have much structured content, eg “title”, “description” and bad actors are constantly trying to obfuscate using language based grammar tricks or N1ke type attacks.
Also just the law is very nuanced. You can say “a case compatible with iPhone, that is ..” but it is infringement to say “iPhone case that is ..”
Also there are many nuances around licensing. For example, “BurntSushi T-shirts” as a company cannot have the Disney logo on it, however, a “Lego tshirt” might have the Disney logo legally on it. So a lot of overrides.
Even if you compress all the nuances into a single regex, which you can’t: there are 10 MM estimated brands worldwide (Amazon at the time hosted 1 MM) with on average 10 trademarks each that is 10 MM regexes.
Then you also need to multiple the 25 countries Amazon operates in for legal nuances, and multiple languages (eg even in the US Amazon store someone might use Spanish or Italian to sell their fake product). Additionally there is more fanout for reasons I’ve long forgotten.
Point of story 10 MM was a conservative upper bound on the RegexSet and it had to be fast and cheap. I built it on top of Lucene with some hacks here and there but it did (does) the job - fast and cheap :)
I hope now generative AI can help them more, but I’m not holding my breath.
> Even if you compress all the nuances into a single regex, which you can’t
You cant, standalone hw isnt that capable, distributed computing/cluster computing is.
> I hope now generative AI can help them more, but I’m not holding my breath.
I'm not from what I have seen.
>Also just the law is very nuanced. You can say “a case compatible with iPhone, that is ..” but it is infringement to say “iPhone case that is ..”
And Amazon would be up against users of Lexis Nexis who have a head start in all of this RegEx malarkey, by virtue of what they sell, without giving too much away about their code inner workings.
However, trying to use and read through regex-automata and regex-syntax (even in 2018) was such a very valuable and helpful learning resource. I ended up modeling the project at work off Lucene APIs, but it was all only after learning the basics from the regex crates.
Best set of libs! Thanks sushi!