First of all I think you actually want the distance from the regex to a fixed string, not between two regex. This is possibly a (slightly) easier problem.

Secondly I suspect that the problem (at least for regex but maybe not for glob) is undecidable. Consider the matchs:


    /(ab|ac|ce).{3}(ge|ef|gh)/

    aceabdef
    ageabdxf

[download]

Clearly the regex matches the first string (i.e a distance of 0), but for the second you could validly be asking "How many modifications to the regex are required to create a match" or "How many inserts/deletes are needed on the string for the regex to match". These are of course different questions.

If you think of the pattern space of all possible strings then each string is a single location while a regex is an area. It is quite legitimate to ask for the distance between two points, and that is easy to calculate. It is also possible to ask if a region encloses a point, that is does a string match a regex. The question you are asking is what is the distance from the nearest point in an area. Simple changes in the regex can have large effects on the area covered. The power of regex makes your question hard.

In reply to Re: Edit distance between regular expressions by hawtin
in thread Edit distance between regular expression by future.open

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post, it's "PerlMonks-approved HTML":


  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, details, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, summary, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.