Hatena::ブログ(Diary)

Mi manca qualche giovedi`? このページをアンテナに追加 RSSフィード Twitter

2011-10-20 iPython 便利やねえ。

メールアドレスの正規表現がめちゃめちゃ遅くなることがある件について

Solr 3.5 から新たに加わる言語判定機能に、拙作の言語判定ライブラリ langdetect が正式に採用されたようで。

言語判別機能の追加 (Solr 3.5)
http://lucene.jugem.jp/?eid=455
LanguageDetection - Solr Wiki
http://wiki.apache.org/solr/LanguageDetection

もともと Apache Nutch などの言語判定に不満で作り始めたこと、そして実際に社内(サイボウズ)で langdetect を Solr に組み込んで利用していることを考えれば、本懐と言ってもいいくらい。

ありがたや。


でも、今日の話はそっちではなくて。

その langdetect の Issue Board にて教えていただいた「メールアドレスの正規表現がめちゃめちゃ遅くなることがある」件について。


論より証拠、次の Java コードを見てみよう。


import java.util.regex.Pattern;

public class RegexTest {
    private static final int RUNS = 20;
    private static final Pattern MAIL_REGEX = Pattern.compile("[-_.0-9A-Za-z]+@[-_0-9A-Za-z]+[-_.0-9A-Za-z]+");

    public static String repeat(String st, int c) {
        StringBuffer buf = new StringBuffer();
        for (int i=0;i<c;++i) buf.append(st);
        return buf.toString();
    }

    private static void regex_test(Pattern mail_regex, String text, int runs) {
        long t0 = System.currentTimeMillis();
        for (int i = 0; i < runs; i++) {
            text = mail_regex.matcher(text).replaceAll(" ");
        }
        System.out.println(String.format("%d : %s ms", text.length(), System.currentTimeMillis() - t0));
    }

    public static void main(String[] args) throws Exception {
        regex_test(MAIL_REGEX, repeat("abcdefgh", 10), RUNS);
        regex_test(MAIL_REGEX, repeat("abcdefgh", 50), RUNS);
        regex_test(MAIL_REGEX, repeat("abcdefgh", 100), RUNS);
        regex_test(MAIL_REGEX, repeat("abcdefgh", 500), RUNS);
        regex_test(MAIL_REGEX, repeat("abcdefgh", 1000), RUNS);
    }
}

MAIL_REGEX は、ありがちな「メールアドレスクラスにマッチする正規表現」。今回の主役。


repeat() は文字列を指定した回数繰り返して長い文字列を作る機能。Java は標準でそういうメソッド無いのね。*1


つまり、このコードは「空白の入っていない長い文字列」を作って、それにメールアドレスの正規表現をマッチさせてみるというものである。

このコードを実行すると、文字列の長さと、match 20 回にかかったミリ秒を出力する。


80 : 38 ms
400 : 59 ms
800 : 264 ms
4000 : 6650 ms
8000 : 26331 ms

おわかりのとおり、文字列長の二乗オーダーになっている。

特に最後の 8KB のテキストでは、1回のマッチにつき1秒以上の時間がかかっている

とんでもなく遅い。


次に、MAIL_REGEX を次のように書き換えてもう一度実行してみる。


    private static final Pattern MAIL_REGEX = Pattern.compile("[-_.0-9A-Za-z]{1,64}@[-_0-9A-Za-z]+[-_.0-9A-Za-z]+");

変更点は @ の前の '+' を '{1,64}' にしただけだが、処理速度は劇的に改善される。


80 : 27 ms
400 : 20 ms
800 : 75 ms
4000 : 240 ms
8000 : 469 ms

オーバーヘッドなどで正確に測定できてないくさいが、まあきっと線形オーダーだろう。

ちなみにメールアドレスのローカル部( @ より前)は最大 64 文字と規定されているので、規約上は後者の方がより正しい。


どうしてこんなことになるのか?

サイボウズ・ラボユースで来てくれている、正規表現オタク(褒めてますw)の新屋さんによると、これは正規表現のエンジンが「NFAベースのバックトラック実装」を採用している場合に起こりうる問題で、件の正規表現の先頭部分 /[-_.0-9A-Za-z]+/ が文字列の任意の部分にマッチする可能性を保留したまま判定を進めることにより、N^2 のオーダーになるのだろうということ。

ということなら、{1,64} と上限を付けると線形オーダーに落ちるのも納得。


まとめると(正規表現エンジンの実装にもよるが)、/[文字クラス]+/ で始まる正規表現のマッチには、「その文字クラスが連続する長さ」の2乗のオーダーがかかる、ということ。

それを抑えたいなら、/[文字クラス]{1,(最大長)}/ のように長さに制限をかけるのが一番確実な解決法。


ちなみに、Python だとこうなる。文字列長に対して線形オーダーであることがわかる。

【追記】と書いたがこれはウソ。内外から「Python の re.match は文字列の先頭にしかマッチしないよ」とご指摘を受ける。いや申し訳ない&お恥ずかしい……。

Island Life - O(n^2)正規表現
http://blog.practical-scheme.net/shiro/20111020-regexp-n-square

というわけで元記事の間違ってたコード部分は削除して、新しい評価コードを貼り付ける。


In [1]: import re

In [2]: r1 = re.compile(r'[-_.0-9A-Za-z]+@[-_0-9A-Za-z]+[-_.0-9A-Za-z]+')

In [3]: a = "abcdefgh" * 100

In [4]: b = "abcdefgh" * 1000

In [5]: r1.search(a)

In [6]: %timeit r1.search(a)
100 loops, best of 3: 4.24 ms per loop

In [7]: %timeit r1.search(b)
1 loops, best of 3: 422 ms per loop

In [8]: r2 = re.compile(r'[-_.0-9A-Za-z]{1,64}@[-_0-9A-Za-z]+[-_.0-9A-Za-z]+')

In [9]: %timeit r2.search(a)
1000 loops, best of 3: 689 us per loop

In [10]: %timeit r2.search(b)
100 loops, best of 3: 7.11 ms per loop

Python でも確かに /[文字クラス]+/ で始まると二乗オーダーに、/[文字クラス]{1,64}/ にすると線形オーダーに落ちていることがわかる。

【/追記】


というわけで、/[文字クラス]+/ で始まる正規表現はめちゃめちゃ遅くなることがあるので気をつけよう。


ちなみに、これのために初めて iPython を入れた。

いや前から存在は知ってたんだけど、Tokyo.SciPy で教えてもらった %timeit の便利さに負けた。


【追記 10/24】

コメント欄にて cocoa_ruto さんに「Ruby 1.9 だと線形だよ」と教えていただいた。感謝。

さっそくこのスクリプトを上と同じ環境の Ruby 1.9.2 にて実行してみた。


            user     system      total        real
80      0.000000   0.000000   0.000000 (  0.000000)
400     0.015000   0.000000   0.015000 (  0.015625)
800     0.000000   0.000000   0.000000 (  0.000000)
4000    0.016000   0.000000   0.016000 (  0.015625)
8000    0.047000   0.000000   0.047000 (  0.046875)
40000   0.172000   0.000000   0.172000 (  0.171875)
80000   0.344000   0.000000   0.344000 (  0.343750)
400000  1.734000   0.000000   1.734000 (  1.734375)
800000  3.484000   0.016000   3.500000 (  3.531250)

確かに線形。ちなみに + を {1,64} に変えても実行時間は変わらなかった。

鬼車の方式で自然とこうなるのか、このパターンの正規表現を特別扱いしているのかはわからないが、Ruby の場合は + と書いておいても全く問題ないようだ。


しっかし benchmark モジュールって便利なんだなあw <感心するのそこ?

【/追記】

*1:Issue Board に貼ってもらったサンプルでは Apache Commons Lang StringUtils が使われていたんだけど、そういうの入れるノめんどくさい人でも簡単に確認できるように自作しといた

makomlmakoml 2011/10/21 15:44 こんにちは。

Commons Validatorにもメールアドレスを検査するためのEmailValidatorがあり、スナップショット(version 1.4)では、このEmailValidatorがリファクタリングされて、ドメイン検証部がDomainValidatorという別のクラスに分割される予定です。

しかし、DomainValidatorには、長いTLDを与えると、正規表現の問題の評価が2乗のオーダで遅くなる問題がありました。Webサイトでの入力値の検証にValidatorが使用されることを、DoS攻撃につながる恐れがあると思い、改善するためのパッチを出しました。2007年の話です。

https://issues.apache.org/jira/browse/VALIDATOR-252

タイトルでピンときたのでコメントしてみました。

cocoa_rutococoa_ruto 2011/10/22 12:43 はじめまして
Ruby 1.9だと線形な上にJavaの{1,64}と比べてもずっと速いようです。
https://gist.github.com/1305571
速すぎるのでRUNSを2000にしています。

n_shuyon_shuyo 2011/10/24 18:14 > makoml さん

ありがとうございます。やはり問題自体は以前から知られていたわけですね。
その割りには意外と周知されていないような……。まわりでも知ってたよという人がいなかったですし。

> cocoa_ruto さん

Ruby (というか鬼車)優秀ですねえ。ありがとうございます。
記事に Ruby の結果も追加しておきます。

スパム対策のためのダミーです。もし見えても何も入力しないでください
ゲスト


画像認証