3 ms·
Well, you can see one approach in the uBlock source code. Matching against static, glob and regex patterns. And there is some grouping and filtering so, it's n
by edoceo 5y ago
Well, you can see one approach in the uBlock source code.
Matching against static, glob and regex patterns. And there is some grouping and filtering so, it's not like every URL gets all 64k patterns matched. And it's possible to pre-compile and group the Regex to get a little faster (lots of framework routers do this)
From my opinion the "web" is so contaminated it's a shorter accept-list than a constantly changing reject-list
- o8r3oFTZPE 5y agoPersonally use an "allow list" as opposed to a "block list". Not sure which is "easier" but definitely know which one is faster, more efficient and has zero misses or false positives. Arguably its more useful to know what a given website actualy requires than to know every possible advertising scheme. Allow lists teach about where to find desired content. Block lists do not teach anything useful in that regard.
- jhgb 5y agoI 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.