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

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 解决方案相同，但避免了某些多余的括号。 它仅使用“|”、非捕获组“

(?:)

”和选项“

?

”。 当有一排单个字符时，还有改进的空间： 而不是例如

(?: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))

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

Answer 4

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

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