我写了一个可以生成一系列符号的Java程序，比如"abcdbcdefbcdbcdefg"。我需要的是正则表达式优化器，它可以产生"a((bcd){2}ef){2}g".
由于输入可能包含Unicode，如"au0063u0063bbd"，我更喜欢Java版本。
我想获得"更短"表达式的原因是为了节省空间/内存。这里的符号序列可能很长。
一般来说，找到"最短"的优化正则表达式是很困难的。所以，在这里，我不需要那些保证"最短"标准的人。
我有一种令人讨厌的感觉，即创建与给定输入字符串或字符串集匹配的最短正则表达式的问题在计算上将是"困难的"。 （与计算柯尔莫果洛夫复杂性的问题有相似之处......
还值得注意的是，就匹配速度而言，abcdbcdefbcdbcdefg的最佳正则表达式可能是 abcdbcdefbcdbcdefg . 添加重复组可能会使正则表达式字符串更短，但不会使正则表达式更快。 事实上，除非正则表达式引擎展开重复组，否则它可能会更慢。
我需要这样做的原因是由于空间/内存限制。
你有明确的证据证明你需要这样做吗？
我怀疑您这样做不会节省有价值的空间......除非输入字符串真的很长。 （如果它们很长，那么使用常规文本压缩算法来压缩字符串会得到更好的结果。
正则表达式不能替代压缩
不要使用正则表达式来表示字符串常量。正则表达式旨在用于匹配许多字符串之一。那不是你正在做的。
我假设您正在尝试找到一个小正则表达式来编码一组有限的输入字符串。 如果是这样，您还没有选择最好的主题行。
我不能给你一个现有的程序，但我可以告诉你如何编写一个程序。
没有规范的最小正则表达式形式，确定真正的最小大小正则表达式很难。 当然，你的集合是有限的，所以这可能是一个更简单的问题。 我得考虑一下。
但是一个好的启发式算法是：
- 构造一个接受所有字符串的普通非确定性有限自动机 （NFA）。
- 将 NFA 转换为具有子集构造的确定性有限自动机 （DFA）。
- 使用标准算法最小化 DFA。
- 使用克莱恩定理证明中的构造来获得正则表达式。
请注意，步骤 3 确实为您提供了唯一的最小 DFA。这可能是对字符串集进行编码的最佳方式。