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

Question

我希望有人可能知道一个脚本，它可以接受任意单词列表并生成可以完全匹配该列表的最短正则表达式（而不是其他）。

例如，假设我的列表是

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 生成正则表达式：

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

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

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

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

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

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

3. ???

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

Answer 2

这是一篇旧文章，但为了那些像我一样通过网络搜索找到它的人的利益，有一个 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)。在上面的输出中，您还可以搜索并替换 (?: 和 (?^: 为 ( 并消除多余的括号，以获得这：

3([1238]|57)4

Answer 3

该项目从给定的单词列表生成正则表达式： https://github.com/bwagner/wordhierarchy

它几乎与上述 JavaScript 解决方案相同，但避免了某些多余的括号。
它仅使用“|”、非捕获组“(?:)”和选项“?”。

它最适合具有从左侧开始的公共子字符串的单词。可以改进以在任何地方处理子字符串。

生成的正则表达式可以轻松适应其他正则表达式方言。

示例用法：

java -jar dist/wordhierarchy.jar 1231 1233 1234 1236 1238 1247 1256 1258 1259
-> 12(?:3[36148]|47|5[698])

我应该提到我是这个项目的作者。

Answer 4

这是我想到的（JavaScript）。它将 20,000 个 6 位数字的列表转换为 60,000 个字符的正则表达式。与简单的 (word1|word2|...) 结构相比，按字符数计算，这几乎是 60% 的“压缩”。

我将这个问题悬而未决，因为仍有很大的改进空间，并且我希望可能有更好的工具。

var list = new listChar("");

function listChar(s, p) {
    this.char = s;
    this.depth = 0;
    this.parent = p;
    this.add = function(n) {
        if (!this.subList) {
            this.subList = {};
            this.increaseDepth();
        }
        if (!this.subList[n]) {
            this.subList[n] = new listChar(n, this);
        }
        return this.subList[n];
    }
    this.toString = function() {
        var ret = "";
        var subVals = [];
        if (this.depth >=1) {
            for (var i in this.subList) {
                subVals[subVals.length] = this.subList[i].toString();
            }
        }
        if (this.depth === 1 && subVals.length > 1) {
            ret = "[" + subVals.join("") + "]";
        } else if (this.depth === 1 && subVals.length === 1) {
            ret = subVals[0];
        } else if (this.depth > 1) {
            ret = "(" + subVals.join("|") + ")";
        }
        return this.char + ret;
    }
    this.increaseDepth = function() {
        this.depth++;
        if (this.parent) {
            this.parent.increaseDepth();
        }
    }
}

function wordList(input) {
    var listStep = list;
    while (input.length > 0) {
        var c = input.charAt(0);
        listStep = listStep.add(c);
        input = input.substring(1);
    }
}
words = [/* WORDS GO HERE*/];
for (var i = 0; i < words.length; i++) {
    wordList(words[i]);
}

document.write(list.toString());

使用

words = ["1231","1233","1234","1236","1238","1247","1256","1258","1259"];

这里是输出：

(1(2(3[13468]|47|5[689])))