生成最短的正则表达式以匹配任意单词列表

Question

我希望有人可能知道一个脚本可以采用任意单词列表并生成可以完全匹配该列表的最短正则表达式(并且没有别的).

例如,假设我的列表是

1231
1233
1234
1236
1238
1247
1256
1258
1259

那么输出应该是:

12(3[13468]|47|5[589])

Answer 1

这是一篇旧文章，但为了那些像我一样通过网络搜索找到它的人的利益，有一个 Perl 模块可以执行此操作，称为Regexp::Optimizer，此处： http: //search.cpan.org/~dankogai/Regexp-Optimizer -0.23/lib/Regexp/Optimizer.pm

它采用正则表达式作为输入，该正则表达式可以仅包含以 分隔的输入字符串列表|，并输出最佳正则表达式。

例如，这个 Perl 命令行：

perl -mRegexp::Optimizer -e "print Regexp::Optimizer->new->optimize(qr/1231|1233|1234|1236|1238|1247|1256|1258|1259/)"

生成此输出：

(?^:(?^:12(?:3[13468]|5[689]|47)))

（假设你已经安装了Regex::Optimizer），这非常符合OP的期望。

这是另一个例子：

perl -mRegexp::Optimizer -e "print Regexp::Optimizer->new->optimize(qr/314|324|334|3574|384/)"

和输出：

(?^:(?^:3(?:[1238]|57)4))

为了进行比较，基于 trie 的最佳版本将输出3(14|24|34|574|84). 在上面的输出中，您还可以搜索并用 just替换(?:and并消除多余的括号，以获得：(?^:(

3([1238]|57)4

Answer 2

你最好保存整个列表，或者如果你想变得更奇特，创建一个Trie：

1231
1234
1247

    1
    |
    2 
   / \
  3   4
 / \   \
1   4   7

现在，当您获取字符串时，检查它是否到达叶节点。确实如此，这是有效的。

如果您有可变长度的重叠字符串（例如：123 和 1234），您需要将一些节点标记为可能的终端。

如果您确实喜欢正则表达式的想法，也可以使用 trie 来生成正则表达式：

1. 从根到第一个分支的节点是固定的（例如：12）

2. 分支创建|：（例如：12(3|4)

3. 叶节点生成跟随父节点的字符类（或单个字符）：（例如12(3[14]|47)）

这可能不会生成最短的正则表达式，为此您可能需要一些额外的工作：

1. 如果您找到它们，则为“紧凑”范围（例如[12345]变为[1-4]）

2. 为重复元素添加量词（例如：[1234][1234]成为[1234]{2}

3. ???

我真的不认为生成正则表达式值得。