8
\$\begingroup\$

I'm looking for a program such that, given a finite list of strings, can find short regexes to match exactly all of them and nothing else.

Since there are multiple languages that express regexes differently, there can correspondingly be multiple regex generators. Each answer must discuss regex generation in one langauge only (or a family of languages for which there is a direct correspondence between regexes in each of them).

\$\endgroup\$
23
  • 1
    \$\begingroup\$ @Arnauld Yeah, I thought the "exactly" made it clear enough. Edited. \$\endgroup\$ Commented May 19, 2020 at 11:55
  • 3
    \$\begingroup\$ Another useful feature of such a tool would be to generate a regex that matches all strings in a list A but not any of the strings in a list B, with undefined behavior for any other input. (This is what I would have needed to optimize this handcrafted answer.) \$\endgroup\$
    – Arnauld
    Commented May 19, 2020 at 20:48
  • 1
    \$\begingroup\$ @ghosts_in_the_code to write code implementing it without reducing it(code). \$\endgroup\$ Commented Jul 21, 2020 at 10:27
  • 1
    \$\begingroup\$ @VictorVosMottorthanksMonica oh yeah the regex generator doesn't have to be golfed \$\endgroup\$ Commented Jul 21, 2020 at 10:33
  • 1
    \$\begingroup\$ Seems NP-hard. \$\endgroup\$
    – Adám
    Commented Jul 27, 2020 at 10:33

2 Answers 2

6
\$\begingroup\$

The Machine Learning Lab at the University of Trieste, Italy, wrote a web app to solve this exact problem, available at: Automatic Generation of Regular Expressions from Examples based on "genetic programming" and published a paper about it. Based on the fact that it had to come from the Machine Learning Lab of a university in Italy, and was worth publishing a paper about, it is probably a pretty hard problem to solve. Doesn't sound like the type of question for Code Golf SE, but I'm new here, so I wouldn't be the expert on that.

\$\endgroup\$
4
  • \$\begingroup\$ Welcome to the site. That's a cool approach to regex generation. Note, though, that the app isn't guaranteed to find the shortest possible regex. From the FAQ: '3. The generated regexes look unoptimized. Why? There are some optimization which could make a given regex appear better, e.g., [\d\d\.\d][\d\.]. Currently, our prototype does not apply any of these optimizations.' Nor will the generated regex match only the given strings and nothing else. You are right - this is a hard problem. \$\endgroup\$
    – Dingus
    Commented Aug 19, 2020 at 2:58
  • \$\begingroup\$ I didn't look into it, but the description of the website I linked does include "old version", so maybe there is a newer version which does apply the optimizations? I seem to remember the website looking different the first time I saw it than this time around, so maybe I really did link an old one... \$\endgroup\$
    – Sam
    Commented Aug 19, 2020 at 3:03
  • \$\begingroup\$ I believe I linked to the "Regex Generator" page, here is the "Regex Generator++" page: regex.inginf.units.it . I updated the post. I wonder if the ++ version does perform the optimizations... \$\endgroup\$
    – Sam
    Commented Aug 19, 2020 at 15:58
  • \$\begingroup\$ I believe that the ++ version does perform the optimizations. At least, in the regex golf section - which looks more similair in its UI to the ++ version - it has a stage when it is figuring out the Regex where it says "Optimizing..." \$\endgroup\$
    – Sam
    Commented Aug 19, 2020 at 19:43
0
\$\begingroup\$

I would approach this problem by searching for common subsequences in each pair of strings in the list, and then building regular expressions that include those subsequences. This would be somewhat like the Re-Pair algorithm, but it would build a grammar from a set of strings instead of one string.

For instance, these strings:

["red wolf", "red fox", "gray wolf", "gray fox"]

could be combined into two regular expressions:

"red (wolf|fox)", "gray (wolf|fox)"

which can be combined into one regular expression:

"(red|gray) (wolf|fox)"

But this problem is probably NP-complete, since it is similar to the smallest grammar problem.

\$\endgroup\$
3
  • \$\begingroup\$ Welcome to Code Golf! This site is for competitive challenges, not for asking and answering actual questions. \$\endgroup\$ Commented Oct 17, 2022 at 19:15
  • \$\begingroup\$ @RadvylfPrograms Yes, I think this question should have been posted on Computer Science Stack Exchange instead of Code Golf. \$\endgroup\$ Commented Oct 17, 2022 at 19:16
  • \$\begingroup\$ Ohhhh hang on yeah you're right. Didn't notice this is tagged with tips, this would definitely be better somewhere else. \$\endgroup\$ Commented Oct 17, 2022 at 21:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.