News for hackers. Stuff that matters.

A comment on The mounting cost of stale ad blocking rules (2018). Parent comment

Re:The mounting cost of stale ad blocking rules (2018) by nextaccountic on Sunday June 13, 2021 @10:02PM (#27498536)
I think the fastest data structure for this is to replace the whole thing by one big finite state transducer https://blog.burntsushi.net/transducers/ - such data structure can be built from the EasyList regexes, and perform all checks in a single lookup.

The idea here would be to compile the regex of each rule to an automata (each automata matches a set of strings) and them build a fst out of them (that would map strings to matched rules)

[ Parent | on HN ]
Re:The mounting cost of stale ad blocking rules (2018) by jhgb on Wednesday June 16, 2021 @10:39AM (#27529024)
Is it really the fastest way? I imagine that without extra data it may be, but what I was proposing in a cousin comment would involve profiling and early fast rejection by means of efficient multiple string matching. The browser should be able to collect a significant amount of historical matching data to optimize these lookups.
[ Parent | on HN ]