Regular Expression Matching Can Be Simple And Fast (but is slow in Java, Perl, PHP, Python, Ruby, etc)
Sun, 2009.02.15 - 18:47 — müzso
"This is a tale of two approaches to regular expression matching. One of them is in widespread use in the standard interpreters for many languages, including Perl. The other is used only in a few places, notably most implementations of awk and grep. The two approaches have wildly different performance characteristics ..."
A very interesting article on regular expression matching algorithms.
A very interesting article on regular expression matching algorithms.
All of my own contents here (if not noted otherwise) are licensed under the
Creative Commons Attribution-NonCommercial-ShareAlike 4.0 License. My posts reflect my personal opinion and shall not be associated with any of my employers.
Creative Commons Attribution-NonCommercial-ShareAlike 4.0 License. My posts reflect my personal opinion and shall not be associated with any of my employers.
Comments
Wow, the article shows how
...in a worst possible expression for the backtracking algorithm and (I fail to ignore it) if the regular expression is longer then 75 characters. Let's write an infinite regexp!