是否有用Java编写的Regex优化器？

我写了一个Java程序，它可以生成一系列符号，比如"abcdbcdefbcdbcdefg" 。我需要的是Regex优化器，它可以产生"a((bcd){2}ef){2}g" 。

由于输入可能包含unicodes，比如"a\u0063\u0063\bbd" ，我更喜欢Java版本。

我想要获得“更短”表达的原因是为了节省空间/内存。这里的符号序列可能很长。

一般来说，找到“最短”的优化正则表达式很难。所以，在这里，我不需要保证“最短”标准的那些。

我有一种讨厌的感觉，即创建匹配给定输入字符串或字符串集的最短正则表达式的问题在计算上将是“困难的”。（与计算Kolmogorov复杂性的问题有相似之处…）

值得注意的是， abcdbcdefbcdbcdefg在匹配速度方面的最佳正则表达式可能是abcdbcdefbcdbcdefg 。添加重复组可能会使正则表达式字符串更短，但它不会使正则表达式更快。实际上，除非正则表达式引擎展开重复组，否则它可能会更慢。

我需要这个的原因是由于空间/内存限制。

你有明确的证据表明你需要这样做吗？

我怀疑你不会通过这样做来节省一定数量的空间…除非输入字符串真的很长。（如果它们很长，那么使用常规文本压缩算法压缩字符串会得到更好的结果。）

正则表达式不能代替压缩

不要使用正则表达式来表示字符串常量。正则表达式旨在用于匹配许多字符串中的一个。那不是你在做什么的。

我假设您正在尝试找到一个小的正则表达式来编码一组有限的输入字符串。如果是这样，您没有选择最佳主题。

我不能给你一个现有的程序，但我可以告诉你如何写一个。

没有规范的最小正则表达forms，并且确定真正的最小尺寸正则表达式是NP难的。当然你的集合是有限的，所以这可能是一个更简单的问题。我得考虑一下。

但是一个好的启发式算法将是：

请注意，第3步确实为您提供了唯一的最小DFA。这可能是编码字符串集的最佳方法。