[flagged]
Finding all regex matches has always been O(n²)
71–80 of 82 posts
Re: Finding all regex matches has always been O(n²)
#72I believe the technique described is similar to what I published here (this is not about all matches, but left-longest/shortest)
"Compiling regular expressions to sequential machines" (2005) ACM Symposium of Applied Computing https://dl.acm.org/doi/10.1145/1066677.1066992
(Note that there is a small mistake in the paper due to ambiguity, found by Vladimir Gapeyev. So the result does not hold in the generality stated but only for a special case when there is no ambiguity at "the end". There went my first PhD student publication...)
The two pass technique used to be implemented in the Scala compiler at the time (building DFAs upfront) , which could do regexps over lists and other sequences, but the approach would not work for top-down tree regexps so I did not pursue that and it got ripped out later.
It is good to see derivative regular expressions, Brzozowski/"position automata" used and discussed.
Re: Finding all regex matches has always been O(n²)
#73I wonder how gracefully redgrep handles this. This tool hasn't been talked about since the year of its release. If I recall correctly, it doesn't handle some obstruse regexes the way conventional tools do however. https://github.com/google/redgrep
I have not verified it but i assume matching the whole line grep-style would bypass this problem entirely
Since a regex with ^$ can not have overlapping matches it should guarantee linearity, given a linear engine. Or in the case of preprocessing lines first and then running is_match it's also linear
Re: Finding all regex matches has always been O(n²)
#74> i think i'll rest for a bit after this. i can only do 80-hour weeks for so long
Jesus Christ, 80 hours?! I really hope the author seriously takes a proper break! I mean, they seem to be riding that incredible high that comes from having a breakthrough in deeply understanding a really tough problem after thinking about it for too long, so I kind of get it, but that is also all the more reason to take good care the precious brain that now stores all that knowledge, before it burns out!
Re: Finding all regex matches has always been O(n²)
#75A couple of notes:
- The Austin Group has recently accepted lazy quantifiers for inclusion into the next release of POSIX[1]. They think they have worked out a reasonable declarative definition for what they should mean. I am less than sure of that, but either way dismissing the whole thing as irredeemably tied to backtracking seems inappropriate.
- Once again the generalization in the title is AFAIK largely correct for industrial engines, but incorrect—arguably to the point of being misleading—for academic work. Just looking into the “parsing” subfolder of my papers stash reveals a 1998 paper[2] on linear-time maximal-munch tokenization, so at the very least the problem was recognized, and IIRC there’s a bunch of related work around that paper too.
- It is true that you can’t stream the haystack in the general case, but to what precise extent you can is an interesting question with a known algorithmic answer[3].
[1] https://www.austingroupbugs.net/view.php?id=793, https://www.austingroupbugs.net/view.php?id=1329, https://www.austingroupbugs.net/view.php?id=1857, see also the mailing list.
[2] Reps (1998), ACM TOPLAS 20(2), 259–273, https://dl.acm.org/doi/10.1145/276393.276394, https://research.cs.wisc.edu/wpis/papers/toplas98b.pdf.
[3] Grathwohl, Henglein, Rasmussen (2014), ICTAC ’14, LNCS 8687, 224–240, https://link.springer.com/chapter/10.1007/978-3-319-10882-7_..., https://utr.dk/pubs/files/grathwohl2014-0-paper.pdf.
Re: Finding all regex matches has always been O(n²)
#76A couple of notes: - The Austin Group has recently accepted lazy quantifiers for inclusion into the next release of POSIX[1]. They think they have worked out a reasonable declarative definition for what they should mean. I am less than sure of that, but either way dismissing the whole thing as irredeemably tied to backtracking seems inappropriate. - Once again the generalization in the title is AFAIK largely correct…
> lazy quantifiers for inclusion into the next release of POSIX
That is surprising!
We've found that in certain simpler scenarios it's possible to use complement to express lazy quantifiers, but in the general case it appears very fragile.
a simple example: a.*?b can be rewritten to something like (a.*b&~(a.*b_+)) in RE# syntax, which effectively means "there is a match, but must not contain a shorter match"
> 1998 TOPLAS
I will read through it properly, but i can already see from page 8 that it requires a table of (DFA size x input length) which makes me very suspicious that it is more of a thought exercise than a real world solution.
> It is true that you can’t stream the haystack in the general case, but to what precise extent you can is an interesting question with a known algorithmic answer[3].
Thank you for this, this is an interesting paper
Re: Finding all regex matches has always been O(n²)
#77[flagged]
I also have the impression that the writing was at least "enhanced" with an LLM. For example, the amount of " - " dashes (over 60) is much higher than in a normal text. By the way, I consider it a pretty disgraceful defect of HN that people routinely "flag" opinions merely because they disagree. The flag is for spam, not for downvoting.
Haha. But I guess it proves my assertion that "we can still tell" was wrong. Scary to think about the future though. Soon less RLHF'd models will be available, and it won't be so easy to recognize their tells. I don't think the whole post was written by an LLM in one prompt and I'm sure it was actually a lot of work to write, but yeah, it was definitely enhanced by one.
It reminds me of how peer review is supposed to be blind, but certain authors like Simon Peyton Jones have such a distinctive voice that surely reviewers instantly know when a paper is by him. The models have been successfully made to talk in a particular way, and it's very clear once you becomes familiar with it. My guess is that most HN users are not familiar and I just sound like a crazy person to them
The author admitted it in another comment anyway https://news.ycombinator.com/item?id=47494833
Re: Finding all regex matches has always been O(n²)
#78Earlier quoted context omitted.
I'm of the opinion that their post is still human-written. They describe in their first blog post that it's human written (which could be a lie, but oh well) and their other blog posts seem to have the same informal lowercase hyphenated writing style. Sentance length varies throughout the posts. Sure, you could prompt this writing style, but I lean towards thinking that the piece is human written.
It is human written and i've thoroughly went over every paragraph but i did use some help with wording. i suppose it does show now that you mention it
It does but apparently not to the point that it bothers most people. So I guess I wouldn't worry about it. Keep up the good work on making regex faster!
Re: Finding all regex matches has always been O(n²)
#79A couple of notes: - The Austin Group has recently accepted lazy quantifiers for inclusion into the next release of POSIX[1]. They think they have worked out a reasonable declarative definition for what they should mean. I am less than sure of that, but either way dismissing the whole thing as irredeemably tied to backtracking seems inappropriate. - Once again the generalization in the title is AFAIK largely correct…
> lazy quantifiers for inclusion into the next release of POSIX That is surprising! We've found that in certain simpler scenarios it's possible to use complement to express lazy quantifiers, but in the general case it appears very fragile. a simple example: a.*?b can be rewritten to something like (a.*b&~(a.*b_+)) in RE# syntax, which effectively means "there is a match, but must not contain a shorter match" > 1998 T…
>> lazy quantifiers for inclusion into the next release of POSIX
> That is surprising!
I mean, POSIX BREs (only!) also include (single-digit) backreferences. Surprisingly, (with such a restriction) this is actually polynomial[1,2] if impractical (h/t 'burntsushi for the reference[3]). But I still wouldn’t take POSIX as the arbiter of sanity in this case. Thus far I’m not even convinced their text actually amounts to a well-defined ordering on parse trees.
I don’t know if nongreedy quantifiers are all that interesting without match groups, though, so this isn’t a particularly burning question in my view.
[1] https://branchfree.org/2019/04/04/question-is-matching-fixed...
Re: Finding all regex matches has always been O(n²)
#80Earlier quoted context omitted.
The fact that terms like Aho-Corasick, PLDI, Go, etc. are properly capitalized, including if they begin sentences, but otherwise sentences are uncapitalized, makes me think it's an explicit LLM instruction "don't capitalize the start of sentences" rather than writing style.
What's with this silly "all lower case" style lately? Jack Dorsey's layoff message last month did the same thing. Is it some kind of "Prove you're not an AI by purposely writing like an idiot" or something?
it's been common in the unix/c/lisp worlds since before you were born
when 6 bit ascii was all caps only, people got used to monocase, then 7-bit lowercase ascii blew in a fresh wind.