Thanks for writing this up. I'm solving a similar problem, albeit different in a few important ways, and was planning on taking a semi-similar approach. Like yo

Thanks for writing this up. I'm solving a similar problem, albeit different in a few important ways, and was planning on taking a semi-similar approach. Like you, today I'm using a fairly naive implementation with some less-than-ideal complexity. I've never actually worked with a prefix tree before, so this was quite helpful for me. This may be of interest as well - a related paper, Pigasus, does this with specialized hardware but it's a similar problem of applying 10s of thousands of rules as quickly as possible. I found it while reading through acolyer's morning paper. https://blog.acolyer.org/2020/11/16/pigasus/ https://blog.acolyer.org/2020/11/16/pigasus/ Again, slightly different task - they wouldn't be going for the longest match exclusively, but all matches. Also, the rules they use are fundamentally regular expressions, so the filtering pass is to take advantage of the domain specific knowledge that rule-matches are very rare.