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

Question

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

例如，假设我的列表是：

1231
1233
1234
1236
1238
1247
1256
1258
1259

那么输出结果应该是：

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

- Asmor

---

你的函数的(更短)输出难道不会是 12[13-9]\{2\} 吗？ - Manny D

这将匹配不在列表中的内容，例如1211。 - Asmor

@arnaud576875，显然这通常不是最短的正则表达式。 - Ross Presser

@RossPresser 这很可能是执行最短的方式 ;) （也是内存表示中最短的方式） - Arnaud Le Blanc

我最终编写的程序输出的执行速度比朴素的a|b|c正则表达式快得多，这是几年前的事情了，所以我不再有数字，但至少快了几个数量级。当组合约10,000个数字字符串时，长度也缩短了大约60％。关于内存占用就不清楚了。 - Asmor

Answer 1

这是一篇旧文章，但为了那些像我一样通过网络搜索找到它的人的利益，有一个叫做Regexp::Optimizer的Perl模块可以做到这一点，网址在这里：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))

作为对比，一个最佳的基于字典树的版本将输出 3(14|24|34|574|84)。在上面的输出中，您还可以搜索并替换 (?: 和 (?^: 为 (，消除冗余的括号，以获得如下结果：

3([1238]|57)4

- Sei Lisa

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. ???

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

- NullUserException

---

不幸的是，正则表达式是必需的。它是特定工具的输入。我如何想出这个正则表达式并不重要。我希望有现成的脚本可以做到这样的事情。我正在自己开发一个工具，但如果能找到一个现成的解决方案就更好了。 - Asmor

Answer 3

这个项目从给定的单词列表生成正则表达式: https://github.com/bwagner/wordhierarchy 它几乎与上面的JavaScript解决方案相同，但避免了某些多余的括号。 它只使用 "|", 非捕获组 "(?:)" 和选项 "?"。 当有一排单个字符时，还有改进的空间： 例如，(?:3|8|1|6|4) 可以生成 [38164]。

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

样例用法：

java -jar dist/wordhierarchy.jar 1231 1233 1234 1236 1238 1247 1256 1258 1259
-> 12(?:5(?:6|9|8)|47|3(?:3|8|1|6|4))

- Bernhard Wagner

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])))

- Asmor

---

你可以通过消除只有一个子节点的节点来减少 () 的数量：http://jsfiddle.net/6NhcV/1/ 这样就得到了 (12(3[13468]|47|5[689]))。 - Arnaud Le Blanc

不错。在同一个列表中，它将长度从60583 -> 60252个字符减少了。我有点惊讶的是减少的幅度没有更大。 - Asmor