I have a dictionary-like regular expression, an "or chain" of words,
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:
ma[ãe]e). This works fine.
ABCCC|ABCC|ABC|DFcan be automatically reduced to (output)
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?