I imagine that one should be able to profile the actual data from the actual web pages and then compile an optimal (or at least a near-optimal) decision tree, i

I imagine that one should be able to profile the actual data from the actual web pages and then compile an optimal (or at least a near-optimal) decision tree, i.e., a decision tree with a minimum expected value of testing any of the inputs seen so far. Worst case is that this comes out as equivalent to the naive loop (the naive loop is essentially a degenerate decision tree), but average case should be much better. Furthermore the decision tree needn't be binary. If you group regexes by common substrings and then even group substrings for, say, a Commentz-Walter matcher, you are able to distinguish N+1 cases for N patterns, with significantly lesser costs than N times the cost of matching for one substring alone.