Minimal regular expression that matches a given set of words

Question

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?

Answer 1

Maybe this will not give the exact shortest regex, but (as you're looking for a practical solution) you can start with the Aho-Corasick Algorithm to obtain a TRIE-like DFA that can be easily written as a regular expression. It is proven that the automaton is minimal for the word set, but the regex you get should be at close to the optimal. The optimizations you mention seem to be possible if you look for consecutive final states on a single branch of the constructed DFA.