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