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

Question

我希望有人可能知道一个脚本，该脚本可以采用任意单词列表，并生成可以与该列表完全匹配的最短正则表达式(除此之外没有其他)。

例如，假设我的 list 是

1231
1233
1234
1236
1238
1247
1256
1258
1259

然后输出应为:

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

Answer 1

您最好保存整个列表，或者如果您想花哨的话，请创建一个Trie:

1231
1234
1247

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

现在，当您使用字符串时，检查它是否到达叶节点。确实有效。
如果您有可变长度的重叠字符串(例如:123和1234)，则需要将某些节点标记为可能的终端。

如果您真的喜欢正则表达式的想法，也可以使用trie生成正则表达式:

从根到第一个分支的节点是固定的(例如:12)

分支机构创建| :(例如:12(3|4)

叶子节点生成一个跟随父节点的字符类(或单个字符):(例如12(3[14]|47))

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

如果找到它们，则“紧凑”范围(例如[12345]变为[1-4])

为重复元素添加量词(例如:[1234][1234]变为[1234]{2}

???

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