Help:CirrusSearch/RegexTooComplex
 |
注意: このページを編集すると、編集内容が CC0 のもとで公開されることに同意したと見なされます。詳細はパブリック・ドメインのヘルプ ページを参照してください。 | |
insource:// 構文は、Lucene の方言で書かれた正規表現の検索を比較的効率的に実装しています。
効率の理由から、これらの正規表現がどれほど複雑かには制限があります。
どのような構文が複雑と見なされるか?
非決定性のあとに繰り返しが続くことで、最も複雑度が増加します。 以下のようなものです:
insource:/[ac]*a[ac]{50,200}/
[ac]* 部分は非決定的で、[ac]{50,200} 部分は繰り返しです。
一方、以下のようにすると改善されます:
insource:/[ac]*a[de]{50,200}/
これは、[de]{50,200} が [ac]* と重ならないためです。
それでも複雑であり完全に高速化できませんが、即座には却下されず一致を試みます。
一般的に、繰り返しで得られる価値よりも複雑さが上回ってしまいます。
単に繰り返す方がよいため、
insource:/[ac]*a.*[^"]+\"/
は以下よりもはるかに複雑ではありません:
insource:/[ac]*a.*[^"]{50,100}\"/
理由
Lucene は正規表現を決定性有限オートマトン (DFA) にコンパイルします。 この際、まず正規表現を非決定性有限オートマトン (NFA) に変換し、さらにそれを DFA に変換します。 この操作の最悪ケースの計算量は NFA の状態数に対して指数的になり、NFA の状態数は正規表現に依存します。 非決定性の後に繰り返し、そのまた繰り返しが続くと、状態数が指数的に増加します。 メモリを使い尽くさないように、状態数の上限を 20,000 に制限しています。