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.
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?
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).
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.
I worked briefly with Mark-Jason Dominus in 2000. He added instrumentation to the Perl regex engine so that we could develop a regex debugger for the forthcoming Komodo editor. Each time the engine advanced to process the next step, we would get a callback that included vital information such as the location in the regex string and the target string.
Today, there are numerous excellent tools like this on the web. Back in 2000, it was dark magic and so much fun to work on.
There are websites that can step through a regex execution (e.g. Regex101), but I still don't have a regex debugger with arbitrary callbacks! When do I get one in Python?
12 comments
[ 2.3 ms ] story [ 41.2 ms ] threadAnother 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.
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?
https://blog.burntsushi.net/transducers/
Also discussed only 1 year ago:
https://news.ycombinator.com/item?id=28243636 (174 points, 10 comments)
No thanks
Today, there are numerous excellent tools like this on the web. Back in 2000, it was dark magic and so much fun to work on.
https://news.ycombinator.com/item?id=33566557