Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Regexes: The Bad, the Better, and the Best

loggly.com

Post reply on HN
Print view View original

21–30 of 37 posts

Re: Regexes: The Bad, the Better, and the Best

#21

Post by dpkendal »

SerpentJoe wrote: post #15
edwintorok wrote: post #13

"Awk and grep use the Thompson NFA algorithm which is in fact significantly faster in almost every way but supports a more limited set of features." AFAIK the only feature of regexes that require backtracking are back-references, as long as your regex doesn't use it why doesn't PCRE switch to the more efficient algorithm, and use the backtracking algorithm only if you actually need the feature that requires backtrack…

Backtracking is required in a lot of cases. Consider matching the pattern /^(AA|AB)*$/ against the string "AAAAAAAAB". Before it can come up with the answer (it doesn't match) the engine has to backtrack all the way from right to left.

Not true. Finite automata (NFAs, DFAs) can match that pattern (and any pattern that doesn't involve backreferences or lookaround) in O(n) time where n is the size of the input string. DFA implementations are worst-case O(n ^ 2) in the number of states of the regular expression, but this is far better in most cases than the exponential worst-case time in terms of the input string offered by backtracking implementations.

See https://swtch.com/~rsc/regexp/ for information on finite-state-machine implementations of regexp matching.

Re: Regexes: The Bad, the Better, and the Best

#22

Post by thaumasiotes »

edwintorok wrote: post #18
SerpentJoe wrote: post #15

Earlier quoted context omitted.

Backtracking is required in a lot of cases. Consider matching the pattern /^(AA|AB)*$/ against the string "AAAAAAAAB". Before it can come up with the answer (it doesn't match) the engine has to backtrack all the way from right to left.

that can be compiled to a state machine where a decision to switch states is taken based on current character only, and when all input is consumed you are either in an accepting or rejecting state. In your case I think it only needs 2 states: state 0 moves to state 1 when it sees an A, and state 1 moves to state 0 when it sees either A or B. For your string it'll be in state 0 when it sees a B and thus rejects it.

                   ┌┐
                   ↓│
               ┌────┴┐
            ┌─→│     │←──┐
            │  └─────┘   │
       ╔════╧═╗       ┌──┴──┐
    ├─→║      ╟───A──→│     │
       ╚══════╝       └─┬───┘
           ↑            │
           └─────A,B────┘
Three states if you want to process the whole input. If your model is "reject when you fail to find an appropriate transition" rather than "reject if, after processing the string, you're in a reject state", then you don't need the failure trap and you can do it in two states.

Backtracking is definitely not required, nor helpful.

Re: Regexes: The Bad, the Better, and the Best

#23

Post by thaumasiotes »

dpkendal wrote: post #21
SerpentJoe wrote: post #15

Earlier quoted context omitted.

Backtracking is required in a lot of cases. Consider matching the pattern /^(AA|AB)*$/ against the string "AAAAAAAAB". Before it can come up with the answer (it doesn't match) the engine has to backtrack all the way from right to left.

Not true. Finite automata (NFAs, DFAs) can match that pattern (and any pattern that doesn't involve backreferences or lookaround) in O(n) time where n is the size of the input string. DFA implementations are worst-case O(n ^ 2) in the number of states of the regular expression, but this is far better in most cases than the exponential worst-case time in terms of the input string offered by backtracking implementation…

> DFA implementations are worst-case O(n ^ 2) in the number of states of the regular expression

What? Why is that? If the NFA has n states, then the DFA in principle might need one state for every possible set of states the NFA might be in, of which there are 2^n. Where does n^2 come from?

Re: Regexes: The Bad, the Better, and the Best

#24

Post by bane »

taco_emoji wrote: post #12

> In General, the Longer Regex Is the Better Regex I'd rather word this as "more specific is better". Like say for a U.S. phone number (minus area code for simplicity), \d{3}-?\d{4} is better than .*-?.* because it's more specific. "Longer is better" is only useful for helping identify which regex is better, not for helping write better regexes.

This is just another statement of precision vs. recall.

https://en.wikipedia.org/wiki/Precision_and_recall

Re: Regexes: The Bad, the Better, and the Best

#25

Post by thaumasiotes »

tptacek wrote: post #10
Mithaldu wrote: post #9

Earlier quoted context omitted.

That is actually a damn good question. I didn't decide on the word by way or a rational chain of logic, but merely by having hindbrain pattern matching trigger on your behavior, based on what i've seen called that on other forums, and what i've seen you doing on here from time to time. If i had to put it in words, it would probably be something like "tell other people how to use HN without contributing significantly…

I'm doing a lot of things at once. I'm fixing a buggy register allocator, and I'm not that smart, so I can do real work for about 15 minutes before my brain overheats. I bounce to the HN front page: there's a story about regexes, and a recent trend of stories about how there are alternatives to standard regex libraries. I think, maybe this will be one of those stories. Click. Nope, it isn't. I wonder, did anyone writ…

> Downvote. The comment isn't grey! Someone voted this creepy thing up!

I have a comment at -1 points right now that shows up (to me) as black. It used to be grey. I don't know if authors now see all of their own comments in full black or if comments revert to black after a certain period of time or what, but I'm not prepared to guarantee that a comment in full black has more than 0 points.

Re: Regexes: The Bad, the Better, and the Best

#27

Post by tptacek »

thaumasiotes wrote: post #25
tptacek wrote: post #10

Earlier quoted context omitted.

I'm doing a lot of things at once. I'm fixing a buggy register allocator, and I'm not that smart, so I can do real work for about 15 minutes before my brain overheats. I bounce to the HN front page: there's a story about regexes, and a recent trend of stories about how there are alternatives to standard regex libraries. I think, maybe this will be one of those stories. Click. Nope, it isn't. I wonder, did anyone writ…

> Downvote. The comment isn't grey! Someone voted this creepy thing up! I have a comment at -1 points right now that shows up (to me) as black. It used to be grey. I don't know if authors now see all of their own comments in full black or if comments revert to black after a certain period of time or what, but I'm not prepared to guarantee that a comment in full black has more than 0 points.

HN doesn't grey comments out for their authors anymore; it rubs salt on the downvote wounds, and, more often than not, a comment you notice as grey right now will be black again in just a few minutes, so why beg people to write about it?

But HN definitely does still show negative comments from other people as grey.

Re: Regexes: The Bad, the Better, and the Best

#28

Post by vacri »

Surely the simplest optimisation to add would be anchors? Instead of starting the 'good' line "[12]", start it "^[12]".

As it stands, the 'good' regex will look through the whole line for any occurrence of 1 or 2 in the line, then start applying the rest of the regex from there. Putting an anchor in means it only looks at the first character for that 1 or 2.

Re: Regexes: The Bad, the Better, and the Best

#29

Post by thisrod »

carapace wrote: post #20

Okay but think: If you are searching a very large file for a very few occurrences of the expected match then this optimization is not so bad. If you are running line-by-line through a very large log file to extract just those two pieces of information per line, then throw away the first N characters in each line (where N is the hopefully-constant length of your timestamps plus that space char) and start the regex eng…

There's a higher order solution. Read the AWK book, do the exercises, then ignore blog posts about regexps. Make an exception when it's Russ Cox demonstrating how often this wheel has been reinvented in square form.

Re: Regexes: The Bad, the Better, and the Best

#30

Post by [deleted] »

tptacek wrote: post #10
Mithaldu wrote: post #9

Earlier quoted context omitted.

That is actually a damn good question. I didn't decide on the word by way or a rational chain of logic, but merely by having hindbrain pattern matching trigger on your behavior, based on what i've seen called that on other forums, and what i've seen you doing on here from time to time. If i had to put it in words, it would probably be something like "tell other people how to use HN without contributing significantly…

I'm doing a lot of things at once. I'm fixing a buggy register allocator, and I'm not that smart, so I can do real work for about 15 minutes before my brain overheats. I bounce to the HN front page: there's a story about regexes, and a recent trend of stories about how there are alternatives to standard regex libraries. I think, maybe this will be one of those stories. Click. Nope, it isn't. I wonder, did anyone writ…

[deleted]
Post reply on HN