遺伝的アルゴリズムで遅い正規表現を検出する

ある正規表現に様々な文字列を食わせてマッチするかどうか判定することは大変頻出するコードです。
稀に、食わせる文字列のパターンによっては正規表現のマッチに猛烈に時間を消費する場合があります。

僕も少し前に遭遇し、下記に公開しています。

developer.cybozu.co.jp

この時は、(\\w|_){1,64}@ という正規表現があって、____________________ のようにアンダースコアを複数含む文字列のマッチに大変時間がかかるという問題でした。
この、「対象文字列によってはマッチに時間がかかることがある問題」を、遺伝的アルゴリズムを用いて解決できないかチャレンジしてみましょう。

考え方としては、

ランダムな文字列を 10000 個ほど生成し、
それぞれ正規表現にマッチするか判定させ、
時間がかかった順にソートし、
上位を交配させて世代を繰り返せば、

遅い文字列が抽出できるのではないか、ということです。

まず、いくつか必要な処理を作ります。
1) ある文字列が正規表現にマッチするのにどれだけ時間がかかるのかを調べる評価関数
2) ランダムな文字列を生成
3) 文字列同士の交配

評価関数

private ScoredGene calclateScore(String gene) {
    long start = System.nanoTime();
    pattern.matcher(gene).matches();
    long end = System.nanoTime();
    return new ScoredGene(gene, (int) (end - start));
}

ランダムな文字列を生成

private String newGene() {
    return RandomStringUtils.random(GENE_LENGTH); // apache lang3 のライブラリを使用
}

文字列同士の交配

// 一点交叉法で二つの子を生成
private Set<String> breed(String father, String mother) {
    int pivot = RandomUtils.nextInt(0, GENE_LENGTH);

    String part1 = father.substring(0, pivot);
    String part2 = mother.substring(pivot);

    Set<String> children = new HashSet<>();
    children.add(part1 + part2);
    children.add(part2 + part1);
    return children;
}

ではこれらを用いて、遺伝的アルゴリズムの実装をしてみます。

実装

まず、いくつかの定数を定義。

private static final int GENE_LENGTH = 20; // 対象文字列の長さ
private static final int ELITES_SIZE = 1000; // 現世代から次世代に残す遺伝子の数
private static final int MUTATION_SIZE = 1000; // 突然変異として現れる文字列の個数
private static final int POOL_SIZE = 10000; // 対象文字列の個数

では次に、世代を繰り返す処理。各遺伝子のスコアを計算し、ソートし、先頭を表示して、次の世代を生み出す、という処理の無限ループです。

public void search() {
    Set<String> genes = getRandomGenes(); // 初期遺伝子はランダムなものを使用する

    int count = 0;
    while (true) {
        // 文字列それぞれについて計算時間を取得
        List<ScoredGene> scores = calculateScore(genes);

        // マッチにかかった時間ごとにソート
        Collections.sort(scores, SCORE_COMPARATOR);

        // 先頭を表示
        System.out.println("generation " + count + ":\t" + scores.get(0));
        count++;

        // 次世代の文字列を生成
        genes = genereateNextGenes(scores);
    }
}

そして現世代の遺伝子群から次世代の遺伝子群を生み出す処理。

private Set<String> genereateNextGenes(List<ScoredGene> genes) {
    // 次世代を生成する文字列群
    List<String> elites = new ArrayList<>();

    // エリートたちを取得
    for (ScoredGene gene : genes.subList(0, ELITES_SIZE)) {
        elites.add(gene.getGene());
    }

    // 突然変異としてランダムな文字列も入れる
    for (int i = 0; i < MUTATION_SIZE; i++) {
        elites.add(newGene());
    }

    // 次世代の遺伝子群
    Set<String> next = new HashSet<>();
    next.addAll(elites); // エリート達はそのまま次世代に残る

    // 既定のプールサイズになるまで遺伝子を生成し続ける
    while (next.size() <= POOL_SIZE) {
        String father = elites.get(RandomUtils.nextInt(0, elites.size()));
        String mother = elites.get(RandomUtils.nextInt(0, elites.size()));

        Set<String> children = breed(father, mother);
        next.addAll(children);
    }

    return next;
}

使い方

こんな風に任意の正規表現を渡して search 。

public static void main(String[] args) throws IOException {
    Pattern patten = Pattern.compile("(\\w|\\\\@|[-\\%+_!/=.]){1,64}@");
    SlowRegexPatternSearcher searcher = new SlowRegexPatternSearcher(patten);
    searcher.search();
}

するとコンソールにはこんな感じでランダムな文字列とパターンマッチにかかった時間が表示され、

generation 436: %//vv///Mva⒆𨄀琂妍㐁巍➨渟 23ms
generation 437: v/AMv/v%/MMM%Ov/a/蓜 18ms
generation 438: v/vvA/M//vvv//vM//// 17ms
generation 439: M////vvvvv/v/A%//MAM 20ms

さらにしばらく待つとだんだんアンダースコアが遅いことがスコアとして現れます。

generation 1531: %jj%jp%j%%%jjj%Jpj傄懙 18ms
generation 1532: Uj_%%jj%jjpjjj%%j%%% 16ms
generation 1533: jjp%%jpjjjp%p%jj穳웬ቢ 19ms
generation 1534: p%jj%j_%%jj%j냍ⅶ앗暓ﵽ횐 17ms
generation 1535: %Uj_%%jj%%j%jpp%jj%j 18ms
generation 1536: %_%%jj%%%-%%_%%%j%䈋 18ms
generation 1537: %j_%%j_%%j_%%__%%p_% 24ms
generation 1538: _%_j_%%_%%jj%%j%j_%% 36ms
generation 1539: j_%%j_%%__%%p_%_%_j% 51ms
generation 1540: _j_%p__%_j_jp_%p%%_j 61ms
generation 1541: _j_jj_%____%_pJ_%jp% 155ms
generation 1542: j____%_%%_%__%%__j_% 318ms
generation 1543: _____%_%%_%__%%__j_% 806ms
generation 1544: __%____%_j__p_%__j%_ 1027ms
generation 1545: _%_________%_%____%_ 6399ms
generation 1546: _%_________%_%____%_ 6408ms
generation 1547: _______j_j_____%___% 8047ms
generation 1548: __j____________j____ 20494ms
generation 1549: ______%____________% 30772ms
generation 1550: __________________%_ 50260ms
generation 1551: ____________________ 79606ms