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

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 にて教えていただいた「メールアドレスの正規表現がめちゃめちゃ遅くなることがある」件について。 論よ

[mano-junki]

regex パフォーマンス

[raimon49]

ありがちな「メールアドレスっぽいもの」を判定する正規表現パターンで学ぶオーダーの違い。正規表現エンジンに鬼車を採用するRubyではエイリアス部に文字制限を入れてもパフォーマンスが変わらない。

[rryu]

件の正規表現がマッチしないことが確定するのにO(n)、replaceAllがすべての置換対象ではない文字を確定するのにO(n)で、合わせ技でO(n^2)になる。local partを最大64文字に制限するとO(64n)になって線形になる。