2
$\begingroup$

I have a dictionary-like regular expression, an "or chain" of words,

word1|word2|word3|...

Unfortunately, the chain is too large. I'd like to find the minimal regular expression that is equivalent. How can do I do that?

You should think of this as a regex like /^(word1|word2|word3)$/. I have a dictionary of words, and I want a minimal regex that will match if and only if the input string is a word in that dictionary. By minimal, I want the shortest regex that matches all words in the dictionary (and nothing else). I need a regex, not some other representation.

The words come from SQL SELECT DISTINCT word FROM t ORDER BY length DESC, word so I'm hoping for a solution that is optimized to practical use.

I was able to identify some heuristics that work for some special cases, but not a general algorithm:

  • It's easy to deal with accented variations: mãe|mae becomes ma[ãe]e). This works fine.

  • Also, ABCCC|ABCC|ABC|DF can be automatically reduced to (output) ABC{1,3}|DF or AB(?:C|CC|CCC)|DF

As @Raphael noted, "minimizing regular expressions is hard", so it is important the focus on non-generic solutions.

I found a web page that describes how to convert a regex to NFA or DFA, but that doesn't help me get back a minimal regular expression. I'm willing to use an existing library, such as this PHP one, but how do I use the library for this purpose?

$\endgroup$
  • $\begingroup$ For your particular case(finite number of strings), it's not known if the min regular expression is NP-hard. cstheory.stackexchange.com/questions/16860/… $\endgroup$ – Chao Xu Apr 1 '17 at 23:44
  • $\begingroup$ Your special case is also likely to be hard. $\endgroup$ – Yuval Filmus Apr 2 '17 at 6:54
  • 1
    $\begingroup$ Don't use "EDIT:". We have revision history, so there's no need to mark your changes. Instead, make the question read well for someone who encounters it for the first time. See cs.meta.stackexchange.com/q/657/755. I've edited your question for you. Please double-check that the result matches your intent. $\endgroup$ – D.W. Jun 2 '17 at 21:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.