Alex Rivera | Logout

Generating the shortest regex to match an arbitrary word list

Asked 2011-09-15T14:48:21.627
12

I'm hoping someone might know of a script that can take an arbitrary word list and generated the shortest regex that could match that list exactly (and nothing else).

For example, suppose my list is

1231
1233
1234
1236
1238
1247
1256
1258
1259

Then the output should be:

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

1 Answer

2

Here's what I came up with (JavaScript). It turned a list of 20,000 6-digit numbers into a 60,000-character regular expression. Compared to a naive (word1|word2|...) construction, that's almost 60% "compression" by character count.

I'm leaving the question open, as there's still a lot of room for improvement and I'm holding out hope that there might be a better tool out there.

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());

Using

words = ["1231","1233","1234","1236","1238","1247","1256","1258","1259"];
answered 2011-09-15T16:00:50.413

Your Answer