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 件に制限しています。