7
$\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?

Improve this question
$\endgroup$
4
  • 1
    $\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, 2017 at 23:44
  • $\begingroup$ Your special case is also likely to be hard. $\endgroup$
    – Yuval Filmus
    Apr 2, 2017 at 6:54
  • $\begingroup$ @Chao Xu: please consider converting your comment into an answer. As you stated, it is an unresolved research problem in theoretical computer science. $\endgroup$
    – Hermann Gruber
    Nov 24, 2019 at 21:34
  • 1
    $\begingroup$ The second example of simplification the OP found is referred to as "analogue to Horner's rule" in: Keith Ellul, Bryan Krawetz, Jeffrey Shallit, Ming-wei Wang: Regular Expressions: New Results and Open Problems. Journal of Automata, Languages and Combinatorics 10(4): 407-437 (2005) $\endgroup$
    – Hermann Gruber
    Nov 24, 2019 at 21:42

0

Reset to default

Your Answer

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