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 文字と規定されているので、規約上は後者の方がより正しい。
どうしてこんなことになるのか？
サイボウズ・ラボユースで来てくれている、正規表現オタク(褒めてますｗ)の新屋さんによると、これは正規表現のエンジンが「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 モジュールって便利なんだなあｗ ＜感心するのそこ？
【／追記】
