Databases
StackOverflow2013
Postsdbo
PORegex implementation that can handle machine-generated regex's: *non-backtracking*, O(n)?
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PORegex implementation that can handle machine-generated regex's: *non-backtracking*, O(n)?
    primarykey
    data
    text
    <p><strong><em>Edit 2:</em></strong> For a practical demonstration of why this remains important, look no further than <a href="http://stackstatus.net/post/147710624694/outage-postmortem-july-20-2016" rel="nofollow noreferrer">stackoverflow's own regex-caused outage today (2016-07-20)</a>!</p> <p><strong><em>Edit:</em></strong> This question has considerably evolved since I first asked it. See below for two fast+compatible, but not completely fully featured implementations. If you know of more or better implementations, please mention them, there still isn't an ideal implementation here yet! </p> <h1>Where can I find <em>reliably</em> fast Regex implementation?</h1> <p>Does anyone know of a normal <em>non-backtracking</em> (<code>System.Text.RegularExpressions</code> backtracks) linear time regex implementation either for .NET or native and reasonably usable from .NET? To be useful, it would need to:</p> <ul> <li>have a <strong>worst case</strong> time-complexity of regex evaluation of <strong>O(m*n)</strong> where m is the length of the regex, and n the length of the input.</li> <li>have a <strong>normal time-complexity of O(n)</strong>, since almost no regular expressions actually trigger the exponential state-space, or, if they can, only do so on a minute subset of the input.</li> <li>have a <strong>reasonable construction speed</strong> (i.e. no potentially exponential DFA's)</li> <li>be intended for use by human beings, not mathematicians - e.g. I don't want to reimplement unicode character classes: <strong>.NET or PCRE style character classes are a plus.</strong></li> </ul> <h2>Bonus Points:</h2> <ul> <li><strong>bonus points</strong> for practicality if it implements stack-based features which <strong>let it handle nesting</strong> at the expense of consuming O(n+m) memory rather than O(m) memory.</li> <li>bonus points for <strong><em>either</em></strong> capturing subexpressions <strong><em>or</em></strong> replacements (if there are an exponential number of possible subexpression matches, then enumerating <em>all</em> of them is inherently exponential - but enumerating the first few shouldn't be, and similarly for replacements). You can workaround missing either feature by using the other, so having either one is sufficient.</li> <li>lotsa bonus points for <strong>treating regexes as first class values</strong> (so you can take the union, intersection, concatenation, negation - in particular negation and intersection as those are very hard to do by string manipulation of the regex definition)</li> <li><strong>lazy matching</strong> i.e. matching on unlimited streams without putting it all in memory is a plus. If the streams don't support seeking, capturing subexpressions and/or replacements aren't (in general) possible in a single pass.</li> <li><strong>Backreferences are out</strong>, they are fundamentally unreliable; i.e. can always exhibit exponential behavior given pathological input cases.</li> </ul> <p>Such algorithms exist (This is basic automata theory...) - but are there any practically usable <em>implementations</em> accessible from .NET?</p> <h2>Background: (you can skip this)</h2> <p>I like using Regex's for quick and dirty text clean-ups, but I've repeatedly run into issues where the common backtracking NFA implemtation used by perl/java/python/.NET shows exponential behavior. These cases are unfortunately rather easy to trigger as soon as you start automatically generating your regular expressions. Even non-exponential performance can become exceedingly poor when you alternate between regexes that match the same prefix - for instance, in a really basic example, if you take a dictionary and turn it into a regular expression, expect terrible performance. </p> <p><strong>For a quick overview of why better implementations exist and have since the 60s, see <a href="http://swtch.com/~rsc/regexp/regexp1.html" rel="nofollow noreferrer">Regular Expression Matching Can Be Simple And Fast</a>.</strong></p> <h2>Not quite practical options:</h2> <ul> <li><em>Almost ideal</em>: <a href="http://www.let.rug.nl/vannoord/Fsa/" rel="nofollow noreferrer"><strong>FSA toolkit</strong></a>. Can compile regexes to fast C implementations of DFA's+NFA's, allows transducers(!) too, has first class regexes (encapsulation yay!) including syntax for intersection and parametrization. <strong><em>But it's in prolog</em></strong>... (why is something with this kind of practical features not available in a mainstream language???)</li> <li><em>Fast but impractical</em>: a full parser, such as the excellent <a href="http://www.antlr.org/" rel="nofollow noreferrer"><strong>ANTLR</strong></a> generally supports reliably fast regexes. However, antlr's syntax is far more verbose, and of course permits constructs that may not generate valid parsers, so you'd need to find some safe subset.</li> </ul> <h1>Good implementations:</h1> <ul> <li><a href="http://code.google.com/p/re2/" rel="nofollow noreferrer"><strong>RE2</strong></a> - a google open source library aiming for reasonable PCRE compatibility minus backreferences. I think this is the successor to the unix port of plan9's regex lib, given the author.</li> <li><a href="http://laurikari.net/tre/" rel="nofollow noreferrer"><strong>TRE</strong></a> - also mostly compatible with PCRE and even does backreferences, although using those you lose speed guarantees. And it has a mega-nifty approximate matching mode!</li> </ul> <p>Unfortunately both implementations are C++ and would require interop to use from .NET.</p>
    singulars
    1. PO
      singulars
      1. PTAnswer
    1. This table or related slice is empty.
    1. PTQuestion
    1. USEamon Nerbonne
    1. USEamon Nerbonne
    plurals
    1. This table or related slice is empty.
    1. PL
      singulars
      1. LTLinked
    2. PL
      singulars
      1. LTLinked
    1. This table or related slice is empty.
    1. PO
      singulars
      1. PTAnswer
    2. PO
      singulars
      1. PTAnswer
    3. PO
      singulars
      1. PTAnswer
    1. VO
      singulars
      1. PORegex implementation that can handle machine-generated regex's: *non-backtracking*, O(n)?
      1. USAhmad Mageed
      1. VTFavorite
    2. VO
      singulars
      1. PORegex implementation that can handle machine-generated regex's: *non-backtracking*, O(n)?
      1. USEamon Nerbonne
      1. VTBountyStart
    3. VO
      singulars
      1. PORegex implementation that can handle machine-generated regex's: *non-backtracking*, O(n)?
      1. This table or related slice is empty.
      1. VTUpMod
    1. COThat sounds like you may be writing your regexs in an inefficient manner.
      singulars
      1. PORegex implementation that can handle machine-generated regex's: *non-backtracking*, O(n)?
      1. USBrad Gilbert
    2. COThe whole point is that there exist implementations since the 60s (!) for which no regexes are inefficient in this sense. All regular expressions (without backreferences) *can* be evaluated in linear time - I'm looking for an implementation that dumps backreferences and gives me reliable performance instead.
      singulars
      1. PORegex implementation that can handle machine-generated regex's: *non-backtracking*, O(n)?
      1. USEamon Nerbonne
    3. COSee [http://swtch.com/~rsc/regexp/regexp1.html Regular Expression Matching Can Be Simple And Fast] for an explanation.
      singulars
      1. PORegex implementation that can handle machine-generated regex's: *non-backtracking*, O(n)?
      1. USEamon Nerbonne
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload