Another fun idea is the opposite of the regex: the regex constructs a state machine of the needle and is then quickly able to run many haystacks through it. Sometimes you need the other optimisation: compile the entire haystack down to a state machine, and you can run many needles through it! It becomes a very primitive search index.
The haystack idea reminds me of this wonderful post from the creator of both the Rust regex crate and the ripgrep command line utility (among other awesome things).
I’m having a hard time understanding how your “haystack compilation” would work. I get the desire to be able to efficiently run many regexes on the same large file, but how could you optimize the file for arbitrary regex matching?
How is the age relevant here? The article doesn't deal with current events or the newest hottest framework. It explains algorithms and abstract ideas which haven't changed in the last 15 years.
Comments
Always a worthy, related mention: https://swtch.com/~rsc/regexp/regexp1.html
Another fun idea is the opposite of the regex: the regex constructs a state machine of the needle and is then quickly able to run many haystacks through it. Sometimes you need the other optimisation: compile the entire haystack down to a state machine, and you can run many needles through it! It becomes a very primitive search index.
The haystack idea reminds me of this wonderful post from the creator of both the Rust regex crate and the ripgrep command line utility (among other awesome things).
https://blog.burntsushi.net/transducers/
Interesting read.
Also discussed only 1 year ago:
https://news.ycombinator.com/item?id=28243636 (174 points, 10 comments)
That link is a very high quality write up.
I’m having a hard time understanding how your “haystack compilation” would work. I get the desire to be able to efficiently run many regexes on the same large file, but how could you optimize the file for arbitrary regex matching?
January 2007
No thanks
How is the age relevant here? The article doesn't deal with current events or the newest hottest framework. It explains algorithms and abstract ideas which haven't changed in the last 15 years.