in reply to Searching for regular expression overlaps

Update: forget the post below, I was probably not awake when I wrote it.

How can you be sure that your current 200 regexes don't overlap? With 200 regexes, checking each regex against each other basically means visiting 2 ** 199 combinations, i.e. 8e60 possibilities (more precisely: 803469022129495137770981046170581301261101496891396417650688 possibilities).

And with just 275 regexes, the number of combinations is larger than the estimated number of atoms in the universe.

Update (@ 09.26 UTC): Oops, wrong calculation. The number of combinations is actually fact 200 / fact 2, i.e. a number much larger than what I wrote above (a number with more than 370 digits). Actually, with just 60 regexes, the number of combinations exceeds the estimated number of atoms in the universe.

Replies are listed 'Best First'.
Re^2: Searching for regular expression overlaps
by LanX (Saint) on Aug 13, 2016 at 10:34 UTC
    I understood only pairwise comparisons are necessary

    So it's only quadratic: n(n-1)/2 = 19900

    Cheers Rolf
    (addicted to the Perl Programming Language and ☆☆☆☆ :)
    Je suis Charlie!

[reply]
      Yes, Rolf, it seems that you're right.

      But 19900 is still far too many combinations for a manual check.

[reply]
        > But that's still far too many for a manual check.

        Manually ? Probably...

        Worst case meant checking 200+ regexes each time a new one is added.

        But it depends on the structure, when de-parsing Perl's internal representation ( use re "debug" ) you'll see that leading and trailing substrings get special treatment.

        Anyway... Don't let us waste energy on a XY question. :)

        Cheers Rolf
        (addicted to the Perl Programming Language and ☆☆☆☆ :)
        Je suis Charlie!

[reply]

In Section Seekers of Perl Wisdom